Provided by: tcllib_1.21+dfsg-1_all bug

NAME

       struct::skiplist - Create and manipulate skiplists

SYNOPSIS

       package require Tcl  8.2

       package require struct::skiplist  ?1.3?

       skiplistName option ?arg arg ...?

       skiplistName delete node ?node...?

       skiplistName destroy

       skiplistName insert key value

       skiplistName search node ?-key key?

       skiplistName size

       skiplistName walk cmd

_________________________________________________________________________________________________

DESCRIPTION

       The ::struct::skiplist command creates a new skiplist object with an associated global Tcl
       command whose name is skiplistName. This command may be used to invoke various  operations
       on the skiplist. It has the following general form:

       skiplistName option ?arg arg ...?
              Option and the args determine the exact behavior of the command.

       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.

       To read more about skip lists see Pugh, William.  Skip lists: a probabilistic  alternative
       to balanced trees In: Communications of the ACM, June 1990, 33(6) 668-676.

       Currently,  the key can be either a number or a string, and comparisons are performed with
       the built in greater than operator.  The following  commands  are  possible  for  skiplist
       objects:

       skiplistName delete node ?node...?
              Remove the specified nodes from the skiplist.

       skiplistName destroy
              Destroy the skiplist, including its storage space and associated command.

       skiplistName insert key value
              Insert  a  node with the given key and value 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.

       skiplistName search node ?-key key?
              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.

       skiplistName size
              Return a count of the number of nodes in the skiplist.

       skiplistName walk cmd
              Walk the skiplist from the first node to the last. At each node,  the  command  cmd
              will be evaluated with the key and value of the current node appended.

BUGS, IDEAS, FEEDBACK

       This  document,  and  the  package  it  describes, will undoubtedly contain bugs and other
       problems.  Please report such in the category struct :: skiplist of  the  Tcllib  Trackers
       [http://core.tcl.tk/tcllib/reportlist].  Please also report any ideas for enhancements you
       may have for either package and/or documentation.

       When proposing code changes, please provide unified diffs, i.e the output of diff -u.

       Note further that attachments are strongly preferred over inlined patches. Attachments can
       be  made  by going to the Edit form of the ticket immediately after its creation, and then
       using the left-most button in the secondary navigation bar.

KEYWORDS

       skiplist

CATEGORY

       Data structures

COPYRIGHT

       Copyright (c) 2000 Keith Vetter