basis/deques/deques-docs.factor

   1 USING: help.markup help.syntax kernel math sequences
   2 quotations ;
   3 IN: deques
   4
   5 HELP: deque-empty?
   6 { $values { "deque" deque } { "?" boolean } }
   7 { $contract "Returns true if a deque is empty." }
   8 { $notes "This operation is O(1)." }
   9 { $examples
  10   { $example
  11     "USING: deques prettyprint unrolled-lists ;"
  12     "<unrolled-list> deque-empty? ."
  13     "t"
  14   }
  15 } ;
  16
  17 HELP: clear-deque
  18 { $values
  19      { "deque" deque } }
  20 { $description "Removes all elements from a deque." } ;
  21
  22 HELP: deque-member?
  23 { $values
  24      { "value" object } { "deque" deque }
  25      { "?" boolean } }
  26 { $description "Returns true if the " { $snippet "value" } " is found in the deque." } ;
  27
  28 HELP: push-front
  29 { $values { "obj" object } { "deque" deque } }
  30 { $description "Push the object onto the front of the deque." }
  31 { $notes "This operation is O(1)." } ;
  32
  33 HELP: push-front*
  34 { $values { "obj" object } { "deque" deque } { "node" "a node" } }
  35 { $contract "Push the object onto the front of the deque and return the newly created node." }
  36 { $notes "This operation is O(1)." }
  37 { $examples
  38   { $example
  39     "USING: deques dlists kernel prettyprint ;"
  40     "33 <hashed-dlist> push-front* node-value ."
  41     "33"
  42   }
  43 } ;
  44
  45 HELP: push-back
  46 { $values { "obj" object } { "deque" deque } }
  47 { $description "Push the object onto the back of the deque." }
  48 { $notes "This operation is O(1)." } ;
  49
  50 HELP: push-back*
  51 { $values { "obj" object } { "deque" deque } { "node" "a node" } }
  52 { $contract "Push the object onto the back of the deque and return the newly created node." }
  53 { $notes "This operation is O(1)." } ;
  54
  55 HELP: push-all-back
  56 { $values
  57      { "seq" sequence } { "deque" deque } }
  58 { $description "Pushes a sequence of elements onto the back of a deque." } ;
  59
  60 HELP: push-all-front
  61 { $values
  62      { "seq" sequence } { "deque" deque } }
  63 { $description "Pushes a sequence of elements onto the front of a deque." } ;
  64
  65 HELP: peek-front*
  66 { $values { "deque" deque } { "obj" object } { "?" boolean } }
  67 { $contract "Returns the object at the front of the deque, and a boolean indicating if an object was found." } ;
  68
  69 HELP: peek-front
  70 { $values { "deque" deque } { "obj" object } }
  71 { $description "Returns the object at the front of the deque." }
  72 { $errors "Throws an error if the deque is empty." } ;
  73
  74 HELP: ?peek-front
  75 { $values { "deque" deque } { "obj/f" { $maybe object } } }
  76 { $description "A forgiving version of " { $link peek-front } ". If the deque is empty, returns " { $link f } "." } ;
  77
  78 HELP: pop-front
  79 { $values { "deque" deque } { "obj" object } }
  80 { $description "Pop the object off the front of the deque and return the object." }
  81 { $notes "This operation is O(1)." } ;
  82
  83 HELP: pop-front*
  84 { $values { "deque" deque } }
  85 { $contract "Pop the object off the front of the deque." }
  86 { $notes "This operation is O(1)." } ;
  87
  88 HELP: peek-back*
  89 { $values { "deque" deque } { "obj" object } { "?" boolean } }
  90 { $contract "Returns the object at the back of the deque, and a boolean indicating if an object was found." } ;
  91
  92 HELP: peek-back
  93 { $values { "deque" deque } { "obj" object } }
  94 { $description "Returns the object at the back of the deque." }
  95 { $errors "Throws an error if the deque is empty." } ;
  96
  97 HELP: ?peek-back
  98 { $values { "deque" deque } { "obj/f" { $maybe object } } }
  99 { $description "A forgiving version of " { $link peek-back } ". If the deque is empty, returns " { $link f } "." } ;
 100
 101 HELP: pop-back
 102 { $values { "deque" deque } { "obj" object } }
 103 { $description "Pop the object off the back of the deque and return the object." }
 104 { $notes "This operation is O(1)." } ;
 105
 106 HELP: pop-back*
 107 { $values { "deque" deque } }
 108 { $contract "Pop the object off the back of the deque." }
 109 { $notes "This operation is O(1)." } ;
 110
 111 HELP: delete-node
 112 { $values
 113      { "node" object } { "deque" deque } }
 114 { $contract "Deletes the node from the deque." } ;
 115
 116 HELP: deque
 117 { $description "A data structure that has constant-time insertion and removal of elements at both ends." } ;
 118
 119 HELP: node-value
 120 { $values
 121      { "node" object }
 122      { "value" object } }
 123 { $description "Accesses the value stored at a node." } ;
 124
 125 HELP: slurp-deque
 126 { $values
 127      { "deque" deque } { "quot" { $quotation ( ... obj -- ... ) } } }
 128 { $description "Pops off the back element of the deque and calls the quotation in a loop until the deque is empty." }
 129 { $examples
 130   { $example
 131     "USING: deques dlists io kernel ;"
 132     "{ \"one\" \"two\" \"three\" } <hashed-dlist> [ push-all-front ] keep [ print ] slurp-deque"
 133     "one\ntwo\nthree"
 134   }
 135 } ;
 136
 137 ARTICLE: "deques" "Deques"
 138 "The " { $vocab-link "deques" } " vocabulary implements the deque data structure which has constant-time insertion and removal of elements at both ends."
 139 $nl
 140 "Deques must be instances of a mixin class:"
 141 { $subsections deque }
 142 "Deques must implement a protocol."
 143 $nl
 144 "Querying the deque:"
 145 { $subsections
 146     peek-front
 147     peek-back
 148     deque-empty?
 149     deque-member?
 150 }
 151 "Adding and removing elements:"
 152 { $subsections
 153     push-front*
 154     push-back*
 155     pop-front*
 156     pop-back*
 157     clear-deque
 158 }
 159 "Working with node objects output by " { $link push-front* } " and " { $link push-back* } ":"
 160 { $subsections
 161     delete-node
 162     node-value
 163 }
 164 "Utility operations built in terms of the above:"
 165 { $subsections
 166     push-front
 167     push-all-front
 168     push-back
 169     push-all-back
 170     pop-front
 171     pop-back
 172     slurp-deque
 173 }
 174 "When using a deque as a queue, the convention is to queue elements with " { $link push-front } " and deque them with " { $link pop-back } "." ;
 175
 176 ABOUT: "deques"