basis/persistent/heaps/heaps-docs.factor

   1 USING: help.syntax help.markup kernel arrays assocs ;
   2 IN: persistent.heaps
   3
   4 HELP: <persistent-heap>
   5 { $values { "heap" "a persistent heap" } }
   6 { $description "Creates a new persistent heap" } ;
   7
   8 HELP: <singleton-heap>
   9 { $values { "value" object } { "prio" "a priority" } { "heap" "a persistent heap" } }
  10 { $description "Creates a new persistent heap consisting of one object with the given priority." } ;
  11
  12 HELP: pheap-empty?
  13 { $values { "heap" "a persistent heap" } { "?" "a boolean" } }
  14 { $description "Returns true if this is an empty persistent heap." } ;
  15
  16 HELP: pheap-peek
  17 { $values { "heap" "a persistent heap" } { "value" "an object in the heap" } { "prio" "the minimum priority" } }
  18 { $description "Gets the object in the heap with minumum priority." } ;
  19
  20 HELP: pheap-push
  21 { $values { "heap" "a persistent heap" } { "value" object } { "prio" "a priority" } { "newheap" "a new persistent heap" } }
  22 { $description "Creates a new persistent heap also containing the given object of the given priority." } ;
  23
  24 HELP: pheap-pop*
  25 { $values { "heap" "a persistent heap" } { "newheap" "a new persistent heap" } }
  26 { $description "Creates a new persistent heap with the minimum element removed." } ;
  27
  28 HELP: pheap-pop
  29 { $values { "heap" "a persistent heap" } { "newheap" "a new persistent heap" } { "value" object } { "prio" "a priority" } }
  30 { $description "Creates a new persistent heap with the minimum element removed, returning that element and its priority." } ;
  31
  32 HELP: assoc>pheap
  33 { $values { "assoc" assoc } { "heap" "a persistent heap" } }
  34 { $description "Creates a new persistent heap from an associative mapping whose keys are the entries in the heap and whose values are the associated priorities." } ;
  35
  36 HELP: pheap>alist
  37 { $values { "heap" "a persistent heap" } { "alist" "an association list" } }
  38 { $description "Creates an association list whose keys are the entries in the heap and whose values are the associated priorities. It is in sorted order by priority. This does not modify the heap." } ;
  39
  40 HELP: pheap>values
  41 { $values { "heap" "a persistent heap" } { "seq" array } }
  42 { $description "Creates an an array of all of the values in the heap, in sorted order by priority. This does not modify the heap." } ;
  43
  44 ARTICLE: "persistent-heaps" "Persistent heaps"
  45 "This vocabulary implements persistent minheaps, aka priority queues. They are purely functional and support efficient O(log n) operations of pushing and popping, with O(1) time access to the minimum element. To create heaps, use the following words:"
  46 { $subsection <persistent-heap> }
  47 { $subsection <singleton-heap> }
  48 "To manipulate them:"
  49 { $subsection pheap-peek }
  50 { $subsection pheap-push }
  51 { $subsection pheap-pop }
  52 { $subsection pheap-pop* }
  53 { $subsection pheap-empty? }
  54 { $subsection assoc>pheap }
  55 { $subsection pheap>alist }
  56 { $subsection pheap>values } ;
  57
  58 ABOUT: "persistent-heaps"