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 } }
  53 { $contract "Returns the object at the front of the deque." } ;
  54
  55 HELP: pop-front
  56 { $values { "deque" deque } { "obj" object } }
  57 { $description "Pop the object off the front of the deque and return the object." }
  58 { $notes "This operation is O(1)." } ;
  59
  60 HELP: pop-front*
  61 { $values { "deque" deque } }
  62 { $contract "Pop the object off the front of the deque." }
  63 { $notes "This operation is O(1)." } ;
  64
  65 HELP: peek-back
  66 { $values { "deque" deque } { "obj" object } }
  67 { $contract "Returns the object at the back of the deque." } ;
  68
  69 HELP: pop-back
  70 { $values { "deque" deque } { "obj" object } }
  71 { $description "Pop the object off the back of the deque and return the object." }
  72 { $notes "This operation is O(1)." } ;
  73
  74 HELP: pop-back*
  75 { $values { "deque" deque } }
  76 { $contract "Pop the object off the back of the deque." }
  77 { $notes "This operation is O(1)." } ;
  78
  79 HELP: delete-node
  80 { $values
  81      { "node" object } { "deque" deque } }
  82 { $contract "Deletes the node from the deque." } ;
  83
  84 HELP: deque
  85 { $description "A data structure that has constant-time insertion and removal of elements at both ends." } ;
  86
  87 HELP: node-value
  88 { $values
  89      { "node" object }
  90      { "value" object } }
  91 { $description "Accesses the value stored at a node." } ;
  92
  93 HELP: slurp-deque
  94 { $values
  95      { "deque" deque } { "quot" quotation } }
  96 { $description "Pops off the back element of the deque and calls the quotation in a loop until the deque is empty." } ;
  97
  98 ARTICLE: "deques" "Deques"
  99 "The " { $vocab-link "deques" } " vocabulary implements the deque data structure which has constant-time insertion and removal of elements at both ends."
 100 $nl
 101 "Deques must be instances of a mixin class:"
 102 { $subsection deque }
 103 "Deques must implement a protocol."
 104 $nl
 105 "Querying the deque:"
 106 { $subsection peek-front }
 107 { $subsection peek-back }
 108 { $subsection deque-empty? }
 109 { $subsection deque-member? }
 110 "Adding and removing elements:"
 111 { $subsection push-front* }
 112 { $subsection push-back* }
 113 { $subsection pop-front* }
 114 { $subsection pop-back* }
 115 { $subsection clear-deque }
 116 "Working with node objects output by " { $link push-front* } " and " { $link push-back* } ":"
 117 { $subsection delete-node }
 118 { $subsection node-value }
 119 "Utility operations built in terms of the above:"
 120 { $subsection push-front }
 121 { $subsection push-all-front }
 122 { $subsection push-back }
 123 { $subsection push-all-back }
 124 { $subsection pop-front }
 125 { $subsection pop-back }
 126 { $subsection slurp-deque }
 127 "When using a deque as a queue, the convention is to queue elements with " { $link push-front } " and deque them with " { $link pop-back } "." ;
 128
 129 ABOUT: "deques"