Algorithm-SkipList

 view release on metacpan or  search on metacpan

Changes  view on Meta::CPAN

	* max_level cannot be greater than 32 (cleaner code)
	- increased coverage of "heavy" test script
	- minor updates to all test scripts

0.65 Thu June  3 2004
	- updated README

0.64 Thu June  3 2004
        - updated examples in documentation of custom node
	- minor optimizations and code cleanup
	- commented-out call to prev() in _debug
	- removed use of Carp::Assert in tests
	- redesigned benchmark script and included parse-out.pl
	- updated Benchmark.txt
	- updated README

0.63  Fri May 28 2004
	- The default value of P is now 0.25, which appears to yield
	  better results in tests.
	* renamed _random_level to _new_node_level
	- SIZE_THRESHOLD/SIZE_LEVEL now decrease with deletions

Changes  view on Meta::CPAN

0.40  Wed Mar 17 2004
	- added Benchmark file to distribution
	* key_cmp now ignores when key is undefined
	- _insert returns the value of $node->key_cmp($key)
	- broke up test cases into separate files
	- added finger caching to speed up sequential inserts
	- fixed bugs with values, keys, copy, merge, first_key and next_key
          methods related to use of search fingers
	- fixed bug with append method
	- fixed bug with search fingers: they were not being used
	- _debug now prints to STDERR
	* reset method is not called when a new node is added or deleted
          (which is in accord with documentation)
	- stub for next method added
	- List::SkipList::Node ignores invalid and extra arguments
	- minor optimizations in List::SkipList and List::SkipList::Node
	- improved speed of _random_level
	- disabled assertions (for 50% speed improvement!)
	- inserted corrected comment in README about actual performance in
	  comparison to trees

Changes  view on Meta::CPAN

	- added validate_key and validate_node methods to Node

0.11  Sun Nov 16 2003
	- modified test script to better check next_key function
	- bug fix: next_key did not check that $last_key existed

0.10  Sat Nov 15 01:11:00 2003
	- updated test script appropriately
	- added first_key and next_key methods
	- added ability to customize List::SkipList::Node
	- moved debug method to after __END__ block
	- renamed random_level to _random_level
	- changed type checking to use isa() method
	- updated documentation

0.02  Fri Nov 14 01:08:00 2003
	- incorporated experimental code into module
	- began writing initial test script

0.01  Fri Nov 14 00:50:00 2003
	- original version; created by h2xs 1.21 with options

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

  if ($node->key_cmp($key) == 0) {
    $self->last_key( $node, $index );
    return $index;
  } else {
    return;
  }
}


sub _debug {

  my $self = shift;

  my $list   = $self->list;

  while ($list) {
    print STDERR
      $list->key||'undef', "=", $list->value||'undef'," ", $list,"\n";

    for(my $i=0; $i<$list->level; $i++) {

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

=item _set_node_class

=item _set_max_level

=item _set_p

=item _set_k

These methods are used during initialization of the object.

=item _debug

  $list->_debug;

Used for debugging skip lists by developer.  The output of this
function is subject to change.

=back

=head2 Node Methods

Methods for the L<Algorithm::SkipList::Node> object are documented in
that module.  They are for internal use by the main
C<Algorithm::SkipList> module.

t/02-merge_append.t  view on Meta::CPAN

ok( ref($g) eq "Algorithm::SkipList");

foreach my $i (qw( 2 4 6 8 10 )) {
  $g->insert($i, $i);
}
ok($g->size == 5);

$f->merge($g);
ok($f->size == 10);

# $f->_debug;
# $g->_debug;

foreach my $i (1..10) {
  ok($f->find($i) == $i);
}



# redefine $g

foreach my $i (qw( 2 4 6 8 10 )) {

t/02-merge_append.t  view on Meta::CPAN

  my ($k1,$v1) = $g->greatest;
  my ($k2,$v2) = $f->greatest;
  ok($k1 == $k2);
  ok($v1 == $v2);
}

my $z = $f->copy;
ok($z->size == $f->size);

# if ($z->size != $f->size) {
#   $z->_debug;
#   $f->_debug;
#   $g->_debug;
#   die;
# }

foreach my $i (-2..10) {
  ok($f->find($i) == (($i%2)?$i:-$i) ), if ($i);
  ok($z->find($i) == (($i%2)?$i:-$i) ), if ($i);
}

$z->clear;
ok($z->size == 0);