Attachment "skiplist.n" to
ticket [553980ffff]
added by
ericm
2002-05-09 10:01:45.
'\"
'\" Copyright (c) 2000 by Keith Vetter
'\" This software is licensed under a BSD license as described in tcl/tk
'\" license.txt file but with the copyright held by Keith Vetter.
'\"
'\"
.so man.macros
.TH skiplist n 1.0 Struct "Tcl Data Structures"
.BS
'\" Note: do not modify the .SH NAME line immediately below!
.SH NAME
::struct::skiplist \- Create and manipulate skiplist objects
.SH SYNOPSIS
\fBpackage require struct ?1.0?\fR
.sp
\fB::struct::skiplist\fR \fIskiplistName\fR
.sp
.BE
.SH DESCRIPTION
.PP
The \fB::struct::skiplist\fR command creates a new skiplist object
with an associated global Tcl command whose name is
\fIskiplistName\fR. This command may be used to invoke various
operations on the skiplist. It has the following general form:
.PP
Skip lists are an alternative data structure to binary trees. They can
be used to maintain ordered lists over any sequence of insertions and
deletions. Skip lists use randomness to achieve probabilistic
balancing, and as a result the algorithms for insertion and deletion
in skip lists are much simpler and faster than those for binary trees.
.PP
To read more about skip lists see Pugh, William. \fISkip lists: a
probabilistic alternative to balanced trees\fR. In: Communications of the
ACM, June 1990, 33(6) 668-676.
.PP
Currently, the key can be either a number or a string, and comparisons
are performed with the built in greater than operator.
.CS
\fIskiplistName option \fR?\fIarg arg ...\fR?
.CE
\fIOption\fR and the \fIarg\fRs
determine the exact behavior of the command. The following
commands are possible for skiplist objects:
.TP
\fIskiplistName\fR \fBdelete\fR \fInode\fR ?\fInode\fR ...?
Remove the specified nodes from the skiplist.
.TP
\fIskiplistName \fBdestroy\fR
Destroy the skiplist, including its storage space and associated command.
.TP
\fIskiplistName \fBinsert\fR \fIkey\fR \fIvalue\fR
Insert a node with the given \fIkey\fR and \fIvalue\fR into the
skiplist. If a node with that key already exists, then the that node's
value is updated and its node level is returned. Otherwise a new node
is created and 0 is returned.
.TP
\fIskiplistName\fR \fBsearch\fR \fInode\fR ?\fI-key key\fR?
Search for a given key in a skiplist. If not found then 0 is returned.
If found, then a two element list of 1 followed by the node's value is retuned.
.TP
\fIskiplistName\fR \fBsize\fR
Return a count of the number of nodes in the skiplist.
.TP
\fIskiplistName\fR \fBwalk\fR \fIcmd\fR
Walk the skiplist from the first node to the last. At each node, the
command \fIcmd\fR will be evaluated with the key and value of the
current node appended.
.SH KEYWORDS
skiplist
