1[comment {-*- tcl -*-}]
2[manpage_begin struct::skiplist n 1.3]
3[copyright {2000 Keith Vetter}]
4[comment {
5    This software is licensed under a BSD license as described in tcl/tk
6    license.txt file but with the copyright held by Keith Vetter.
7}]
8[moddesc   {Tcl Data Structures}]
9[titledesc {Create and manipulate skiplists}]
10[category  {Data structures}]
11[require Tcl 8.2]
12[require struct::skiplist [opt 1.3]]
13[description]
14[para]
15
16The [cmd ::struct::skiplist] command creates a new skiplist object
17with an associated global Tcl command whose name is
18[arg skiplistName]. This command may be used to invoke various
19operations on the skiplist. It has the following general form:
20
21[list_begin definitions]
22[call [cmd skiplistName] [arg option] [opt [arg "arg arg ..."]]]
23
24[arg Option] and the [arg arg]s determine the exact behavior of the
25command.
26
27[list_end]
28
29[para]
30
31Skip lists are an alternative data structure to binary trees. They can
32be used to maintain ordered lists over any sequence of insertions and
33deletions. Skip lists use randomness to achieve probabilistic
34balancing, and as a result the algorithms for insertion and deletion
35in skip lists are much simpler and faster than those for binary trees.
36
37[para]
38
39To read more about skip lists see Pugh, William.
40[emph {Skip lists: a probabilistic alternative to balanced trees}]
41In: Communications of the ACM, June 1990, 33(6) 668-676.
42
43[para]
44
45Currently, the key can be either a number or a string, and comparisons
46are performed with the built in greater than operator.
47
48The following commands are possible for skiplist objects:
49
50[list_begin definitions]
51[call [arg skiplistName] [method delete] [arg node] [opt [arg node]...]]
52
53Remove the specified nodes from the skiplist.
54
55
56[call [arg skiplistName] [method destroy]]
57
58Destroy the skiplist, including its storage space and associated command.
59
60
61[call [arg skiplistName] [method insert] [arg {key value}]]
62
63Insert a node with the given [arg key] and [arg value] into the
64skiplist. If a node with that key already exists, then the that node's
65value is updated and its node level is returned. Otherwise a new node
66is created and 0 is returned.
67
68
69[call [arg skiplistName] [method search] [arg node] [opt "[const -key] [arg key]"]]
70
71Search for a given key in a skiplist. If not found then 0 is returned.
72If found, then a two element list of 1 followed by the node's value is retuned.
73
74
75[call [arg skiplistName] [method size]]
76
77Return a count of the number of nodes in the skiplist.
78
79[call [arg skiplistName] [method walk] [arg cmd]]
80
81Walk the skiplist from the first node to the last. At each node, the
82command [arg cmd] will be evaluated with the key and value of the
83current node appended.
84
85[list_end]
86
87[section {BUGS, IDEAS, FEEDBACK}]
88
89This document, and the package it describes, will undoubtedly contain
90bugs and other problems.
91
92Please report such in the category [emph {struct :: skiplist}] of the
93[uri {http://sourceforge.net/tracker/?group_id=12883} {Tcllib SF Trackers}].
94
95Please also report any ideas for enhancements you may have for either
96package and/or documentation.
97
98
99[keywords skiplist]
100[manpage_end]
101