basis/heaps/heaps-docs.factor

   1 USING: heaps.private help.markup help.syntax kernel math assocs
   2 math.order quotations ;
   3 IN: heaps
   4
   5 ARTICLE: "heaps" "Heaps"
   6 "A heap is an implementation of a " { $emphasis "priority queue" } ", which is a structure that maintains a sorted set of elements. The key property is that insertion of an arbitrary element and removal of the first element (determined by order) is performed in O(log n) time."
   7 $nl
   8 "Heap elements are key/value pairs and are compared using the " { $link <=> } " generic word on the first element of the pair."
   9 $nl
  10 "There are two classes of heaps. Min-heaps sort their elements so that the minimum element is first:"
  11 { $subsection min-heap }
  12 { $subsection min-heap? }
  13 { $subsection <min-heap> }
  14 "Max-heaps sort their elements so that the maximum element is first:"
  15 { $subsection max-heap }
  16 { $subsection max-heap? }
  17 { $subsection <max-heap> }
  18 "Both obey a protocol."
  19 $nl
  20 "Queries:"
  21 { $subsection heap-empty? }
  22 { $subsection heap-size }
  23 { $subsection heap-peek }
  24 "Insertion:"
  25 { $subsection heap-push }
  26 { $subsection heap-push* }
  27 { $subsection heap-push-all }
  28 "Removal:"
  29 { $subsection heap-pop* }
  30 { $subsection heap-pop }
  31 { $subsection heap-delete }
  32 "Processing heaps:"
  33 { $subsection slurp-heap } ;
  34
  35 ABOUT: "heaps"
  36
  37 HELP: <min-heap>
  38 { $values { "min-heap" min-heap } }
  39 { $description "Create a new " { $link min-heap } "." } ;
  40
  41 HELP: <max-heap>
  42 { $values { "max-heap" max-heap } }
  43 { $description "Create a new " { $link max-heap } "." } ;
  44
  45 HELP: heap-push
  46 { $values { "key" "a comparable object" } { "value" object } { "heap" "a heap" } }
  47 { $description "Push a pair onto a heap. The key must be comparable with all other keys by the " { $link <=> } " generic word." }
  48 { $side-effects "heap" } ;
  49
  50 HELP: heap-push*
  51 { $values { "key" "a comparable object" } { "value" object } { "heap" "a heap" } { "entry" entry } }
  52 { $description "Push a pair onto a heap, and output an entry which may later be passed to " { $link heap-delete } "." }
  53 { $side-effects "heap" } ;
  54
  55 HELP: heap-push-all
  56 { $values { "assoc" assoc } { "heap" "a heap" } }
  57 { $description "Push every key/value pair of an assoc onto a heap." }
  58 { $side-effects "heap" } ;
  59
  60 HELP: heap-peek
  61 { $values { "heap" "a heap" } { "key" object } { "value" object } }
  62 { $description "Output the first element in the heap, leaving it in the heap." } ;
  63
  64 HELP: heap-pop*
  65 { $values { "heap" "a heap" } }
  66 { $description "Remove the first element from the heap." }
  67 { $side-effects "heap" } ;
  68
  69 HELP: heap-pop
  70 { $values { "heap" "a heap" } { "key" object } { "value" object } }
  71 { $description "Output and remove the first element in the heap." }
  72 { $side-effects "heap" } ;
  73
  74 HELP: heap-empty?
  75 { $values { "heap" "a heap" } { "?" "a boolean" } }
  76 { $description "Tests if a heap has no nodes." } ;
  77
  78 HELP: heap-size
  79 { $values { "heap" "a heap" } { "n" integer } }
  80 { $description "Returns the number of key/value pairs in the heap." } ;
  81
  82 HELP: heap-delete
  83 { $values { "entry" entry } { "heap" "a heap" } }
  84 { $description "Remove the specified entry from the heap." }
  85 { $errors "Throws an error if the entry is from another heap or if it has already been deleted." }
  86 { $side-effects "heap" } ;
  87
  88 HELP: slurp-heap
  89 { $values
  90      { "heap" "a heap" } { "quot" quotation } }
  91 { $description "Removes values from a heap and processes them with the quotation until the heap is empty." } ;