1struct::skiplist(n) Tcl Data Structures struct::skiplist(n)
2______________________________________________________________________________
6
8 struct::skiplist - Create and manipulate skiplists
9
11 package require Tcl 8.2
12 package require struct::skiplist ?1.3?
14 skiplistName option ?arg arg ...?
16 skiplistName delete node ?node...?
18 skiplistName destroy
20 skiplistName insert key value
22 skiplistName search node ?-key key?
24 skiplistName size
26 skiplistName walk cmd
28______________________________________________________________________________
30
32 The ::struct::skiplist command creates a new skiplist object with an
33 associated global Tcl command whose name is skiplistName. This command
34 may be used to invoke various operations on the skiplist. It has the
35 following general form:
36 skiplistName option ?arg arg ...?
38 Option and the args determine the exact behavior of the command.
39 Skip lists are an alternative data structure to binary trees. They can
41 be used to maintain ordered lists over any sequence of insertions and
42 deletions. Skip lists use randomness to achieve probabilistic balanc‐
43 ing, and as a result the algorithms for insertion and deletion in skip
44 lists are much simpler and faster than those for binary trees.
45 To read more about skip lists see Pugh, William. Skip lists: a proba‐
47 bilistic alternative to balanced trees In: Communications of the ACM,
48 June 1990, 33(6) 668-676.
49 Currently, the key can be either a number or a string, and comparisons
51 are performed with the built in greater than operator. The following
52 commands are possible for skiplist objects:
53 skiplistName delete node ?node...?
55 Remove the specified nodes from the skiplist.
56 skiplistName destroy
58 Destroy the skiplist, including its storage space and associated
59 command.
60 skiplistName insert key value
62 Insert a node with the given key and value into the skiplist. If
63 a node with that key already exists, then the that node's value
64 is updated and its node level is returned. Otherwise a new node
65 is created and 0 is returned.
66 skiplistName search node ?-key key?
68 Search for a given key in a skiplist. If not found then 0 is
69 returned. If found, then a two element list of 1 followed by
70 the node's value is retuned.
71 skiplistName size
73 Return a count of the number of nodes in the skiplist.
74 skiplistName walk cmd
76 Walk the skiplist from the first node to the last. At each node,
77 the command cmd will be evaluated with the key and value of the
78 current node appended.
79
81 This document, and the package it describes, will undoubtedly contain
82 bugs and other problems. Please report such in the category struct ::
83 skiplist of the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist].
84 Please also report any ideas for enhancements you may have for either
85 package and/or documentation.
86 When proposing code changes, please provide unified diffs, i.e the out‐
88 put of diff -u.
89 Note further that attachments are strongly preferred over inlined
91 patches. Attachments can be made by going to the Edit form of the
92 ticket immediately after its creation, and then using the left-most
93 button in the secondary navigation bar.
94
96 skiplist
97
99 Data structures
100
102 Copyright (c) 2000 Keith Vetter
103tcllib 1.3 struct::skiplist(n)