view release on metacpan or  search on metacpan

lib/Algorithm/SkipList.pm  view on Meta::CPAN

package Algorithm::SkipList;

use 5.006;
use strict;
use warnings::register __PACKAGE__;

our $VERSION = '1.02';
# $VERSION = eval $VERSION;

use AutoLoader qw( AUTOLOAD );
use Carp qw( carp croak );

require Algorithm::SkipList::Node;
require Algorithm::SkipList::Header;

# Future versions should check Config module to determine if it is
# being run on a 64-bit processor, and set MAX_LEVEL to 64.

use constant MIN_LEVEL       =>  2;
use constant MAX_LEVEL       => 32;
use constant DEF_P           => 0.25;
use constant DEF_K           => 0;

use constant BASE_NODE_CLASS => 'Algorithm::SkipList::Node';

# We use Exporter instead of something like Exporter::Lite because
# Carp uses it.

require Exporter;

our @EXPORT    = ( );
our @EXPORT_OK = ( );

sub new {
  no integer;

  my $class = shift;

  my $self = {
    NODECLASS => BASE_NODE_CLASS,       # node class used by list
    LIST      => undef,                 # pointer to the header node
    SIZE      => undef,                 # size of list
    SIZE_THRESHOLD => undef,            # size at which SIZE_LEVEL increased
    LAST_SIZE_TH   => undef,            # previous SIZE_THRESHOLD
    SIZE_LEVEL     => undef,            # maximum level random_level
    MAXLEVEL  => MAX_LEVEL,             # absolute maximum level
    P         => 0,                     # probability for each level
    K         => 0,                     # minimum power of P
    P_LEVELS  => [ ],                   # array used by random_level
    LIST_END  => undef,                 # node with greatest key
    LASTKEY   => undef,                 # last key used by next_key
    LASTINSRT => undef,                 # cached insertion fingers
    DUPLICATES => 0,                    # allow duplicates?
  };

  bless $self, $class;

  $self->_set_p( DEF_P ); # initializes P_LEVELS
  $self->_set_k( DEF_K );

  if (@_) {
    my %args = @_;
    foreach my $arg_name (CORE::keys %args) {
      my $method = "_set_" . $arg_name;
      if ($self->can($method)) {
	$self->$method( $args{ $arg_name } );
      } else {
	croak "Invalid parameter name: ``$arg_name\'\'";
      }
    }
  }

  $self->clear;

  return $self;
}