1 USING: help.markup help.syntax kernel math sequences
6 { $values { "deque" deque } { "?" boolean } }
7 { $contract "Returns true if a deque is empty." }
8 { $notes "This operation is O(1)." }
11 "USING: deques prettyprint unrolled-lists ;"
12 "<unrolled-list> deque-empty? ."
20 { $description "Removes all elements from a deque." } ;
24 { "value" object } { "deque" deque }
26 { $description "Returns true if the " { $snippet "value" } " is found in the deque." } ;
29 { $values { "obj" object } { "deque" deque } }
30 { $description "Push the object onto the front of the deque." }
31 { $notes "This operation is O(1)." } ;
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)." }
39 "USING: deques dlists kernel prettyprint ;"
40 "33 <hashed-dlist> push-front* node-value ."
46 { $values { "obj" object } { "deque" deque } }
47 { $description "Push the object onto the back of the deque." }
48 { $notes "This operation is O(1)." } ;
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)." } ;
57 { "seq" sequence } { "deque" deque } }
58 { $description "Pushes a sequence of elements onto the back of a deque." } ;
62 { "seq" sequence } { "deque" deque } }
63 { $description "Pushes a sequence of elements onto the front of a deque." } ;
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." } ;
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." } ;
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 } "." } ;
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)." } ;
84 { $values { "deque" deque } }
85 { $contract "Pop the object off the front of the deque." }
86 { $notes "This operation is O(1)." } ;
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." } ;
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." } ;
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 } "." } ;
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)." } ;
107 { $values { "deque" deque } }
108 { $contract "Pop the object off the back of the deque." }
109 { $notes "This operation is O(1)." } ;
113 { "node" object } { "deque" deque } }
114 { $contract "Deletes the node from the deque." } ;
117 { $description "A data structure that has constant-time insertion and removal of elements at both ends." } ;
123 { $description "Accesses the value stored at a node." } ;
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." }
131 "USING: deques dlists io kernel ;"
132 "{ \"one\" \"two\" \"three\" } <hashed-dlist> [ push-all-front ] keep [ print ] slurp-deque"
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."
140 "Deques must be instances of a mixin class:"
141 { $subsections deque }
142 "Deques must implement a protocol."
144 "Querying the deque:"
151 "Adding and removing elements:"
159 "Working with node objects output by " { $link push-front* } " and " { $link push-back* } ":"
164 "Utility operations built in terms of the above:"
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 } "." ;