text: 
  <html><head>
  <title>struct::skiplist - Tcl Data Structures</title>
  <style type="text/css"><!--
      HTML {
  	background: 	#FFFFFF;
  	color: 		black;
      }
      BODY {
  	background: 	#FFFFFF;
  	color:	 	black;
      }
      DIV.doctools {
  	margin-left:	10%;
  	margin-right:	10%;
      }
      DIV.doctools H1,DIV.doctools H2 {
  	margin-left:	-5%;
      }
      H1, H2, H3, H4 {
  	margin-top: 	1em;
  	font-family:	sans-serif;
  	font-size:	large;
  	color:		#005A9C;
  	background: 	transparent;
  	text-align:		left;
      }
      H1.doctools_title {
  	text-align: center;
      }
      UL,OL {
  	margin-right: 0em;
  	margin-top: 3pt;
  	margin-bottom: 3pt;
      }
      UL LI {
  	list-style: disc;
      }
      OL LI {
  	list-style: decimal;
      }
      DT {
  	padding-top: 	1ex;
      }
      UL.doctools_toc,UL.doctools_toc UL, UL.doctools_toc UL UL {
  	font:		normal 12pt/14pt sans-serif;
  	list-style:	none;
      }
      LI.doctools_section, LI.doctools_subsection {
  	list-style: 	none;
  	margin-left: 	0em;
  	text-indent:	0em;
  	padding: 	0em;
      }
      PRE {
  	display: 	block;
  	font-family:	monospace;
  	white-space:	pre;
  	margin:		0%;
  	padding-top:	0.5ex;
  	padding-bottom:	0.5ex;
  	padding-left:	1ex;
  	padding-right:	1ex;
  	width:		100%;
      }
      PRE.doctools_example {
  	color: 		black;
  	background: 	#f5dcb3;
  	border:		1px solid black;
      }
      UL.doctools_requirements LI, UL.doctools_syntax LI {
  	list-style: 	none;
  	margin-left: 	0em;
  	text-indent:	0em;
  	padding:	0em;
      }
      DIV.doctools_synopsis {
  	color: 		black;
  	background: 	#80ffff;
  	border:		1px solid black;
  	font-family:	serif;
  	margin-top: 	1em;
  	margin-bottom: 	1em;
      }
      UL.doctools_syntax {
  	margin-top: 	1em;
  	border-top:	1px solid black;
      }
      UL.doctools_requirements {
  	margin-bottom: 	1em;
  	border-bottom:	1px solid black;
      }
  --></style>
  </head>
  <! -- Generated from file 'skiplist.man' by tcllib/doctools with format 'html'
     -->
  <! -- Copyright &copy; 2000 Keith Vetter
     -->
  <! -- struct::skiplist.n
     -->
  <body><hr> [
     <a href="../../../../../../../../home">Tcllib Home</a>
  | <a href="../../../../toc.html">Main Table Of Contents</a>
  | <a href="../../../toc.html">Table Of Contents</a>
  | <a href="../../../../index.html">Keyword Index</a>
  | <a href="../../../../toc0.html">Categories</a>
  | <a href="../../../../toc1.html">Modules</a>
  | <a href="../../../../toc2.html">Applications</a>
   ] <hr>
  <div class="doctools">
  <h1 class="doctools_title">struct::skiplist(n) 1.3 tcllib &quot;Tcl Data Structures&quot;</h1>
  <div id="name" class="doctools_section"><h2><a name="name">Name</a></h2>
  <p>struct::skiplist - Create and manipulate skiplists</p>
  </div>
  <div id="toc" class="doctools_section"><h2><a name="toc">Table Of Contents</a></h2>
  <ul class="doctools_toc">
  <li class="doctools_section"><a href="#toc">Table Of Contents</a></li>
  <li class="doctools_section"><a href="#synopsis">Synopsis</a></li>
  <li class="doctools_section"><a href="#section1">Description</a></li>
  <li class="doctools_section"><a href="#section2">Bugs, Ideas, Feedback</a></li>
  <li class="doctools_section"><a href="#keywords">Keywords</a></li>
  <li class="doctools_section"><a href="#category">Category</a></li>
  <li class="doctools_section"><a href="#copyright">Copyright</a></li>
  </ul>
  </div>
  <div id="synopsis" class="doctools_section"><h2><a name="synopsis">Synopsis</a></h2>
  <div class="doctools_synopsis">
  <ul class="doctools_requirements">
  <li>package require <b class="pkgname">Tcl 8.2</b></li>
  <li>package require <b class="pkgname">struct::skiplist <span class="opt">?1.3?</span></b></li>
  </ul>
  <ul class="doctools_syntax">
  <li><a href="#1"><b class="cmd">skiplistName</b> <i class="arg">option</i> <span class="opt">?<i class="arg">arg arg ...</i>?</span></a></li>
  <li><a href="#2"><i class="arg">skiplistName</i> <b class="method">delete</b> <i class="arg">node</i> <span class="opt">?<i class="arg">node</i>...?</span></a></li>
  <li><a href="#3"><i class="arg">skiplistName</i> <b class="method">destroy</b></a></li>
  <li><a href="#4"><i class="arg">skiplistName</i> <b class="method">insert</b> <i class="arg">key value</i></a></li>
  <li><a href="#5"><i class="arg">skiplistName</i> <b class="method">search</b> <i class="arg">node</i> <span class="opt">?<b class="const">-key</b> <i class="arg">key</i>?</span></a></li>
  <li><a href="#6"><i class="arg">skiplistName</i> <b class="method">size</b></a></li>
  <li><a href="#7"><i class="arg">skiplistName</i> <b class="method">walk</b> <i class="arg">cmd</i></a></li>
  </ul>
  </div>
  </div>
  <div id="section1" class="doctools_section"><h2><a name="section1">Description</a></h2>
  <p>The <b class="cmd">::struct::skiplist</b> command creates a new skiplist object
  with an associated global Tcl command whose name is
  <i class="arg">skiplistName</i>. This command may be used to invoke various
  operations on the skiplist. It has the following general form:</p>
  <dl class="doctools_definitions">
  <dt><a name="1"><b class="cmd">skiplistName</b> <i class="arg">option</i> <span class="opt">?<i class="arg">arg arg ...</i>?</span></a></dt>
  <dd><p><i class="arg">Option</i> and the <i class="arg">arg</i>s determine the exact behavior of the
  command.</p></dd>
  </dl>
  <p>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.</p>
  <p>To read more about skip lists see Pugh, William.
  <em>Skip lists: a probabilistic alternative to balanced trees</em>
  In: Communications of the ACM, June 1990, 33(6) 668-676.</p>
  <p>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:</p>
  <dl class="doctools_definitions">
  <dt><a name="2"><i class="arg">skiplistName</i> <b class="method">delete</b> <i class="arg">node</i> <span class="opt">?<i class="arg">node</i>...?</span></a></dt>
  <dd><p>Remove the specified nodes from the skiplist.</p></dd>
  <dt><a name="3"><i class="arg">skiplistName</i> <b class="method">destroy</b></a></dt>
  <dd><p>Destroy the skiplist, including its storage space and associated command.</p></dd>
  <dt><a name="4"><i class="arg">skiplistName</i> <b class="method">insert</b> <i class="arg">key value</i></a></dt>
  <dd><p>Insert a node with the given <i class="arg">key</i> and <i class="arg">value</i> 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.</p></dd>
  <dt><a name="5"><i class="arg">skiplistName</i> <b class="method">search</b> <i class="arg">node</i> <span class="opt">?<b class="const">-key</b> <i class="arg">key</i>?</span></a></dt>
  <dd><p>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.</p></dd>
  <dt><a name="6"><i class="arg">skiplistName</i> <b class="method">size</b></a></dt>
  <dd><p>Return a count of the number of nodes in the skiplist.</p></dd>
  <dt><a name="7"><i class="arg">skiplistName</i> <b class="method">walk</b> <i class="arg">cmd</i></a></dt>
  <dd><p>Walk the skiplist from the first node to the last. At each node, the
  command <i class="arg">cmd</i> will be evaluated with the key and value of the
  current node appended.</p></dd>
  </dl>
  </div>
  <div id="section2" class="doctools_section"><h2><a name="section2">Bugs, Ideas, Feedback</a></h2>
  <p>This document, and the package it describes, will undoubtedly contain
  bugs and other problems.
  Please report such in the category <em>struct :: skiplist</em> of the
  <a href="http://core.tcl.tk/tcllib/reportlist">Tcllib Trackers</a>.
  Please also report any ideas for enhancements you may have for either
  package and/or documentation.</p>
  </div>
  <div id="keywords" class="doctools_section"><h2><a name="keywords">Keywords</a></h2>
  <p><a href="../../../../index.html#key306">skiplist</a></p>
  </div>
  <div id="category" class="doctools_section"><h2><a name="category">Category</a></h2>
  <p>Data structures</p>
  </div>
  <div id="copyright" class="doctools_section"><h2><a name="copyright">Copyright</a></h2>
  <p>Copyright &copy; 2000 Keith Vetter</p>
  </div>
  </div></body></html>
  