1 USING: help.markup help.syntax kernel quotations
2 deques search-deques hashtables ;
5 ARTICLE: "dlists" "Double-linked lists"
6 "A double-linked list is the canonical implementation of a " { $link deque } "."
8 "Double-linked lists form a class:"
13 "Constructing a double-linked list:"
14 { $subsections <dlist> }
15 "Double-linked lists support all the operations of the deque protocol (" { $link "deques" } ") as well as the following."
17 "Iterating over elements:"
24 "Deleting a node matching a predicate:"
29 "Search deque implementation:"
30 { $subsections <hashed-dlist> } ;
35 { $values { "list" dlist } }
36 { $description "Creates a new double-linked list." } ;
39 { $values { "search-deque" search-deque } }
40 { $description "Creates a new " { $link search-deque } " backed by a " { $link dlist } ", with a " { $link hashtable } " for fast membership tests." } ;
43 { $values { "dlist" { $link dlist } } { "quot" quotation } { "?" boolean } }
44 { $description "Just like " { $link dlist-find } " except it doesn't return the object." }
45 { $notes "This operation is O(n)." } ;
48 { $values { "dlist" { $link dlist } } { "quot" quotation } { "obj/f" { $maybe object } } { "?" boolean } }
49 { $description "Applies the quotation to each element of the " { $link dlist } " in turn, until it outputs a true value or the end of the " { $link dlist } " is reached. Outputs either the object it found or " { $link f } ", and a boolean which is true if an object is found." }
50 { $notes "Returns a boolean to allow dlists to store " { $link f } "."
52 "This operation is O(n)."
56 { $values { "dlist" dlist } { "quot" quotation } { "dlist'" dlist } }
57 { $description "Applies the quotation to each element of the " { $link dlist } " in turn, removing the corresponding nodes if the quotation returns " { $link f } "." }
58 { $side-effects { "dlist" } } ;
61 { $values { "dlist" dlist } { "n" "a non-negative number" } }
62 { $description "Calculates the length of the linked list." }
63 { $notes "This operation is O(n)." } ;
66 { $values { "dlist" { $link dlist } } { "quot" quotation } { "obj/f" { $maybe object } } { "?" boolean } }
67 { $description "Calls " { $link dlist-find } " on the " { $link dlist } " and deletes the node returned, if any. Returns the value of the deleted node and a boolean to allow the deleted value to distinguished from " { $link f } ", for nothing deleted." }
68 { $notes "This operation is O(n)." } ;
71 { $values { "dlist" { $link dlist } } { "quot" quotation } { "obj/f" { $maybe object } } }
72 { $description "Like " { $link delete-node-if* } " but cannot distinguish from deleting a node whose value is " { $link f } " or not deleting an element." }
73 { $notes "This operation is O(n)." } ;
76 { $values { "dlist" { $link dlist } } { "quot" quotation } }
77 { $description "Iterate a " { $link dlist } ", calling quot on each element." } ;