/ 
List-SkipList-0.10
/ List::SkipList

NAME

List::SkipList - Perl implementation of skip lists

REQUIREMENTS

Carp::Assert is used for validation and debugging. (The assertions can be commented out if the module cannot be installed.) Otherwise standard modules are used.

Installation

Installation is pretty standard:

perl Makefile.PL
make
make test
make 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 a prototype implementation of skip lists in Perl. 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 exceeds the target key, then it descends a level.

Skip lists generally perform as well as balanced trees for searching but do not have the overhead with respect to inserting new items.

For more information on skip lists, see the "SEE ALSO" section below.

Methods

A detailed description of the methods used is below.

new
$list = new SkipList( max_level => 32 );

Creates a new skip list. max_level will default to 32 if it is not specified. It is generally a good idea to leave this value alone unless you are using small lists.

The initial list (see the list method) will be a random number of levels, and will increase over time if inserted nodes have higher levels.

You can also control the probability used to determine level sizes by setting the P value:

$list = new SkipList( p => 0.5 );

The value defaults to 0.5.

For more information on what these values mean, consult the references below in the "SEE ALSO" section.

If you need to use a different node class for using customized comparison routines, you will need to specify a different class:

$list = new SkipList( node_class => 'MyNodeClass' );

See the "Customizing the Node Class" section below.

insert
$list->insert( $key, $value );

Inserts a new node into the list.

exists
if ($list->exists( $key )) { ... }

Returns true if there exists a node associated with the key, false otherwise.

find
$value = $list->find( $key );

Searches for the node associated with the key, and returns the value. If the key cannot be found, returns undef.

first_key
$key = $list->first_key;

Returns the first key in the list.

next_key
$key = $list->next_key( $last_key );

Returns the key following the previous key.

delete
$value = $list->delete( $key );

Deletes the node associated with the key, and returns the value. If the key cannot be found, returns undef.

clear
$list->clear;

Erases existing nodes and resets the list.

size
$size = $list->size;

Returns the number of nodes in the list.

Internal Methods

Internal methods are documented below. These are intended for developer use only. These may change in future versions.

_search
($node, $header_ref) = $list->_search( $key );

Searches for the node with a key. If the key is found, that node is returned along with a header. If the key is not found, the previous node from where the node would be if it existed is returned.

p
$plevel = $list->p;

Returns the P value. Intended for internal use only.

max_level
$max = $list->max_level;

Returns the maximum level that _random_level can generate.

_random_level
$level = $list->_random_level;

This is an internal function for generating a random level for new nodes.

Levels are determined by the P value. The probability that a node will have 1 level is P; the probability that a node will have 2 levels is P^2; the probability that a node will have 3 levels is P^3, et cetera.

The value will never be greater than max_level.

list
$node = $list->list;

Returns the initial node in the list, which is a List::SkipList::Node (See below.)

The key and value for this node are undefined.

_node_class
$node_class_name = $list->_node_class;

Returns the name of the node class used. By default this is the List::SkipList::Node, which is discussed below.

_set_node_class
_set_max_level
_set_p

These methods are used only during initialization of the object. Do not call these methods after the object has been created!

Node Methods

Methods for the List::SkipList::Node object are listed below. They are for internal use by the main Lists::SkipList module.

new
$node = new List::SkipList::Node( key => $key, value => $value,
                                  header => \@header );

Creates a new node for the list. The parameters are optional.

key
$key = $node->key;

Returns the node's key.

$node->key( $key );

When used with an argument, sets the node's key.

key_cmp
if ($node->key_cmp( $key ) != 0) { ... }

Compares the node key with the parameter. Equivalent to using

if (($node->key cmp $key) != 0)) { ... }

without the need to deal with the node key being undef.

By default the comparison is a string comparison. If you need a different form of comparison, use a custom node class.

value
$value = $node->value;

Returns the node's value.

$node->value( $value );

When used with an argument, sets the node's value.

@header = $node->header;

$header_ref = $node->header;

Returns the forward list (see forward) array of the node. This is an array of nodes which point to the node returned, where each index in the array refers to the level. That is,

$header[$i] == $list->forward($i)

Where $i is between 0 and level.

$node->header( @header );

$node->header( $header_ref );

When used with an argument, sets the forward list. Unlike the forward method, it does not check if list elements are of the correct type.

forward
$next = $node->forward( $level );

Returns the next node associated with the level.

$node->forward( $level, $next );

Sets the next node associated with the level.

level
$levels = $node->level;

Returns the number of levels in the node.

Customizing the Node Class

The default node may not handle specialized data types. To define your own custom class, you need to derive a child class from List::SkipList::Node.

Below is an example of a node which redefines the default type to use numeric instead of string comparisons:

package NumericNode;

use Carp::Assert; # this is required since the parent uses this

our @ISA = qw( List::SkipList::Node );

sub key_cmp {
  my $self = shift;
  assert( UNIVERSAL::isa($self, "List::SkipList::Node") ), if DEBUG;

  my $left  = $self->key;  # node key
  my $right = shift;       # value to compare the node key with

  # We should gracefully handle $left being undefined
  unless (defined $left) { return -1; }

  return ($left <=> $right);
}

To use this, we say simply

$number_list = new List::SkipList( node_class => 'NumericNode' );

The list should work normally.

TODO

The following features may be added in future versions:

Searching with "Fingers"
Merging Lists
Splitting Lists
Cloning

CAVEATS

This is a prototype module and may contain bugs.

AUTHOR

Robert Rothenberg <rrwo@cpan.org>

Acknowledgements

Carl Shapiro <cshapiro@panix.com> for introduction to skip lists.

Suggestions and Bug Reporting

Feedback is always welcome. Please use the CPAN Request Tracker at http://rt.cpan.org to submit bug reports.

LICENSE

Copyright (c) 2003 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.

This module intentionally has a superficial subset of the interface in the Tree:Base module, since skip lists can be used instead of trees.