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