view release on metacpan or  search on metacpan

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

  my ($self, $dup) = @_;
  $self->{DUPLICATES} = $dup || 0;
}

sub _set_node_class {
  my ($self, $node_class) = @_;
  $self->{NODECLASS} = $node_class;
}

sub _node_class {
    my ($self) = @_;
    $self->{NODECLASS};
  }

sub reset {
  my ($self) = @_;
  $self->{LASTKEY}  = undef;
}

sub clear {
  my ($self) = @_;

  $self->{SIZE}     = 0;
  $self->{SIZE_THRESHOLD} = 2;
  $self->{LAST_SIZE_TH}   = 0;
  $self->{SIZE_LEVEL}     = MIN_LEVEL;

  my $hdr = [ (undef) x $self->{SIZE_LEVEL} ];

  CORE::delete $self->{LIST};
  $self->{LIST} = new Algorithm::SkipList::Header( undef, undef, $hdr );

  $self->{LIST_END}  = undef;
  $self->{LASTINSRT} = undef;

  $self->reset;
}

sub _set_max_level {
  my ($self, $level) = @_;
  if ($level > MAX_LEVEL) {
    croak "Cannot set max_level greater than ", MAX_LEVEL;
  } elsif ($level < MIN_LEVEL) {
    croak "Cannot set max_level less than ", MIN_LEVEL;
  } elsif ((defined $self->list) && ($level < $self->list->level)) {
    croak "Current level exceeds specified level";
  }
  $self->{MAXLEVEL} = $level;
}

sub max_level {
  my ($self, $level) = @_;

  if (defined $level) {
    $self->_set_max_level($level);
  } else {
    $self->{MAXLEVEL};
  }
}

# We use the formula from Pugh's "Skip List Cookbook" paper.  We
# generate a reverse-sorted array of values based on p and k.  In
# _new_node_level() we look for the highest value in the array that is
# less than a random number n (0<n<1).

sub _build_distribution {
  no integer;

  my ($self) = @_;

  my $p = $self->p;
  my $k = $self->k;

  $self->{P_LEVELS} = [ (0) x MAX_LEVEL ]; 
  for my $i (0..MAX_LEVEL) {
    $self->{P_LEVELS}->[$i] = $p**($i+$k);
  }
}

sub _set_p {
  no integer;

  my ($self, $p) = @_;

  unless ( ($p>0) && ($p<1) ) {
    croak "Unvalid value for P (must be between 0 and 1)";
  }

  $self->{P} = $p;
  $self->_build_distribution;

}

sub p {
  no integer;

  my ($self, $p) = @_;

  if (defined $p) {
    $self->_set_p($p);
  } else {
    $self->{P};
  }
}

sub _set_k {
  my ($self, $k) = @_;

  unless ( $k>=0 ) {
    croak "Unvalid value for K (must be at least 0)";
  }

  $self->{K} = $k;
  $self->_build_distribution;
}

sub k {
  my ($self, $k) = @_;

  if (defined $k) {
    $self->_set_k($k);