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 { $subsections
  12     min-heap
  13     min-heap?
  14     <min-heap>
  15 }
  16 "Max-heaps sort their elements so that the maximum element is first:"
  17 { $subsections
  18     max-heap
  19     max-heap?
  20     <max-heap>
  21 }
  22 "Both obey a protocol."
  23 $nl
  24 "Queries:"
  25 { $subsections
  26     heap-empty?
  27     heap-size
  28     heap-peek
  29 }
  30 "Insertion:"
  31 { $subsections
  32     heap-push
  33     heap-push*
  34     heap-push-all
  35 }
  36 "Removal:"
  37 { $subsections
  38     heap-pop*
  39     heap-pop
  40     heap-delete
  41 }
  42 "Processing heaps:"
  43 { $subsections slurp-heap } ;
  44
  45 ABOUT: "heaps"
  46
  47 HELP: <min-heap>
  48 { $values { "min-heap" min-heap } }
  49 { $description "Create a new " { $link min-heap } "." } ;
  50
  51 HELP: <max-heap>
  52 { $values { "max-heap" max-heap } }
  53 { $description "Create a new " { $link max-heap } "." } ;
  54
  55 HELP: heap-push
  56 { $values { "value" object } { "key" "a comparable object" } { "heap" heap } }
  57 { $description "Push a pair onto a heap. The key must be comparable with all other keys by the " { $link <=> } " generic word." }
  58 { $side-effects "heap" } ;
  59
  60 HELP: heap-push*
  61 { $values { "value" object } { "key" "a comparable object" } { "heap" heap } { "entry" entry } }
  62 { $description "Push a pair onto a heap, and output an entry which may later be passed to " { $link heap-delete } "." }
  63 { $side-effects "heap" } ;
  64
  65 HELP: heap-push-all
  66 { $values { "assoc" assoc } { "heap" heap } }
  67 { $description "Push every key/value pair of an assoc onto a heap." }
  68 { $side-effects "heap" } ;
  69
  70 HELP: heap-peek
  71 { $values { "heap" heap } { "value" object } { "key" object } }
  72 { $description "Output the first element in the heap, leaving it in the heap." } ;
  73
  74 HELP: heap-pop*
  75 { $values { "heap" heap } }
  76 { $description "Remove the first element from the heap." }
  77 { $side-effects "heap" } ;
  78
  79 HELP: heap-pop
  80 { $values { "heap" heap } { "value" object } { "key" object } }
  81 { $description "Output and remove the first element in the heap." }
  82 { $side-effects "heap" } ;
  83
  84 HELP: heap-empty?
  85 { $values { "heap" heap } { "?" boolean } }
  86 { $description "Tests if a heap has no nodes." } ;
  87
  88 HELP: heap-size
  89 { $values { "heap" heap } { "n" integer } }
  90 { $description "Returns the number of key/value pairs in the heap." } ;
  91
  92 HELP: heap-delete
  93 { $values { "entry" entry } { "heap" heap } }
  94 { $description "Remove the specified entry from the heap." }
  95 { $errors "Throws an error if the entry is from another heap or if it has already been deleted." }
  96 { $side-effects "heap" } ;
  97
  98 HELP: slurp-heap
  99 { $values { "heap" heap } { "quot" { $quotation ( ... value key -- ... ) } } }
 100 { $description "Removes entries from a heap and processes them with the quotation until the heap is empty." } ;