NAME
    List::SkipList - Perl implementation of skip lists

REQUIREMENTS
    Perl 5.6.1 is required.

    The following non-standard modules are required:

      enum

    Carp::Assert is no longer required.  However, the assertions can
    be uncommented for debugging.

Installation
    Installation can be done using the traditional Makefile.PL or the
    newer Build.PL methods.

    Using Makefile.PL:

      perl Makefile.PL
      make
      make test
      make install

    (On Windows platforms you should use nmake instead.)

    Using Build.PL (if you have Module::Build installed):

      perl Build.PL
      perl Build
      perl Build test
      perl Build install    

SYNOPSIS
      my $list = new List::SkipList();

      $list->insert( 'key1', 'value' );
      $list->insert( 'key2', 'another value' );

      $value = $list->find('key2');

      $list->delete('key1');

DESCRIPTION
    This is an implementation of skip lists in Perl.  What are "skip
    lists"?

      Skip lists are a probabilistic data structure that seem likely
      to supplant balanced trees as the implementation method of
      choice for many applications. Skip list algorithms have the same
      asymptotic expected time bounds as balanced trees and are
      simpler, faster and use less space.(*)

    This particular implementation may not necessarily be faster or
    use less space, but in superficial testing, it does appear to be a
    reasonably faster substitute for some tree modules.  See the
    included Benchmark.txt file for comparisons with other Perl
    modules.

    Skip lists are similar to linked lists, except that they have
    random links at various levels that allow searches to skip over
    sections of the list, like so:

      4 +---------------------------> +----------------------> +
        |                             |                        |
      3 +------------> +------------> +-------> +-------> +--> +
        |              |              |         |         |    |
      2 +-------> +--> +-------> +--> +--> +--> +-------> +--> +
        |         |    |         |    |    |    |         |    |
      1 +--> +--> +--> +--> +--> +--> +--> +--> +--> +--> +--> +
             A    B    C    D    E    F    G    H    I    J   NIL

    A search would start at the top level: if the link to the right
    exceeds the target key, then it descends a level.

    More information is available in the module documentation.

    (*) Bill Pugh, inventor of skip lists.  Quoted from WikiPedia
        <http://en.wikipedia.org/wiki/Skip_list>

REVISION HISTORY
    Changes since v0.51:

    0.60  Sat Apr 24 2004
	- updates to POD
	- cleaned up comments
	- added next function
	- redid last_key, first_key and next_key functions
	- last_key accepts arguments to modify LASTKEY
	- changed calls to die to croak
	- added experimental hooks to implement prev and prev_key methods
	- added stub prev_key method
	- bug fix: reset method called during copy method
	- added more tests to heavy test script
	* renamed find to find_with_finger and added find for searches
          which do not return updated fingers
	* renamed _search to _search_with_finger and added _search for
	  searches which do not return updated fingers
	- modified next_key test to check for initial key of "0"
	- removed if (CACHE_INSERT_FINGERS) tests
	- additional optimizations and code cleanup
	- added test to search for non-existent keys in Benchmark.pl

    A detailed revision history is in the Changes file included with
    this distribution.

CAVEATS
    Skip lists are non-deterministic.  Because of this, bugs in programs
    that use this module may be subtle and difficult to reproduce without
    many repeated attempts.

AUTHOR
    Robert Rothenberg <rrwo at cpan.org>

LICENSE
    Copyright (c) 2003-2004 Robert Rothenberg. All rights reserved. This
    program is free software; you can redistribute it and/or modify it
    under the same terms as Perl itself.

SEE ALSO
    See the article "A Skip List Cookbook" (William Pugh, 1989), or
    similar ones by the author at http://www.cs.umd.edu/~pugh/ which
    discuss skip lists.