USING: heaps.private help.markup help.syntax kernel math assocs
-math.order ;
+math.order quotations ;
IN: heaps
ARTICLE: "heaps" "Heaps"
"Heap elements are key/value pairs and are compared using the " { $link <=> } " generic word on the first element of the pair."
$nl
"There are two classes of heaps. Min-heaps sort their elements so that the minimum element is first:"
-{ $subsection min-heap }
-{ $subsection min-heap? }
-{ $subsection <min-heap> }
+{ $subsections
+ min-heap
+ min-heap?
+ <min-heap>
+}
"Max-heaps sort their elements so that the maximum element is first:"
-{ $subsection max-heap }
-{ $subsection max-heap? }
-{ $subsection <max-heap> }
+{ $subsections
+ max-heap
+ max-heap?
+ <max-heap>
+}
"Both obey a protocol."
$nl
"Queries:"
-{ $subsection heap-empty? }
-{ $subsection heap-size }
-{ $subsection heap-peek }
+{ $subsections
+ heap-empty?
+ heap-size
+ heap-peek
+}
"Insertion:"
-{ $subsection heap-push }
-{ $subsection heap-push* }
-{ $subsection heap-push-all }
+{ $subsections
+ heap-push
+ heap-push*
+ heap-push-all
+}
"Removal:"
-{ $subsection heap-pop* }
-{ $subsection heap-pop }
-{ $subsection heap-delete } ;
+{ $subsections
+ heap-pop*
+ heap-pop
+ heap-delete
+}
+"Processing heaps:"
+{ $subsections slurp-heap } ;
ABOUT: "heaps"
{ $description "Create a new " { $link max-heap } "." } ;
HELP: heap-push
-{ $values { "key" "a comparable object" } { "value" object } { "heap" "a heap" } }
+{ $values { "value" object } { "key" "a comparable object" } { "heap" heap } }
{ $description "Push a pair onto a heap. The key must be comparable with all other keys by the " { $link <=> } " generic word." }
{ $side-effects "heap" } ;
HELP: heap-push*
-{ $values { "key" "a comparable object" } { "value" object } { "heap" "a heap" } { "entry" entry } }
+{ $values { "value" object } { "key" "a comparable object" } { "heap" heap } { "entry" entry } }
{ $description "Push a pair onto a heap, and output an entry which may later be passed to " { $link heap-delete } "." }
{ $side-effects "heap" } ;
HELP: heap-push-all
-{ $values { "assoc" assoc } { "heap" "a heap" } }
+{ $values { "assoc" assoc } { "heap" heap } }
{ $description "Push every key/value pair of an assoc onto a heap." }
{ $side-effects "heap" } ;
HELP: heap-peek
-{ $values { "heap" "a heap" } { "key" object } { "value" object } }
+{ $values { "heap" heap } { "value" object } { "key" object } }
{ $description "Output the first element in the heap, leaving it in the heap." } ;
HELP: heap-pop*
-{ $values { "heap" "a heap" } }
+{ $values { "heap" heap } }
{ $description "Remove the first element from the heap." }
{ $side-effects "heap" } ;
HELP: heap-pop
-{ $values { "heap" "a heap" } { "key" object } { "value" object } }
+{ $values { "heap" heap } { "value" object } { "key" object } }
{ $description "Output and remove the first element in the heap." }
{ $side-effects "heap" } ;
HELP: heap-empty?
-{ $values { "heap" "a heap" } { "?" "a boolean" } }
+{ $values { "heap" heap } { "?" boolean } }
{ $description "Tests if a heap has no nodes." } ;
HELP: heap-size
-{ $values { "heap" "a heap" } { "n" integer } }
+{ $values { "heap" heap } { "n" integer } }
{ $description "Returns the number of key/value pairs in the heap." } ;
HELP: heap-delete
-{ $values { "entry" entry } { "heap" "a heap" } }
+{ $values { "entry" entry } { "heap" heap } }
{ $description "Remove the specified entry from the heap." }
{ $errors "Throws an error if the entry is from another heap or if it has already been deleted." }
{ $side-effects "heap" } ;
+
+HELP: slurp-heap
+{ $values { "heap" heap } { "quot" { $quotation ( ... value key -- ... ) } } }
+{ $description "Removes entries from a heap and processes them with the quotation until the heap is empty." } ;