Algorithm-SkipList

 view release on metacpan or  search on metacpan

Changes  view on Meta::CPAN

Revision history for Perl extension Algorithm::SkipList. (Changes which may
not be backwards compatible are marked with an asterisk '*'.)

1.02	Wed Jan  4 2005
	* removed validate_key and validate_value methods from node types
	- removed commented-out assertions
	- added _search_nodes method
	- keys and values methods rewritten, and can retrieve keys or
	  values between key ranges ranges 
	- copy method rewritten
	- corrected typo in error message
	- added missing test to MANIFEST
	- added additional tests
	- added SIGNATURE to distribution

Changes  view on Meta::CPAN

	- added documentation and tests about memoization

0.20  Wed Nov 26 2003
	- if no last_key specified for next_key, it returns first_key
	- search fingers added
	- find, first_key, next_key return a list in list context as part of
	  support for search fingers
	- minor changes to documentation

0.13  Wed Nov 19 2003
	- added call to validate_key in key_cmp in Node

0.12  Wed Nov 19 2003
	- 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

README  view on Meta::CPAN

    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 v1.01:

    1.02 Wed Jan  4 2005
	* removed validate_key and validate_value methods from node types
	- removed commented-out assertions
	- added _search_nodes method
	- keys and values methods rewritten, and can retrieve keys or
	  values between key ranges ranges 
	- copy method rewritten
	- corrected typo in error message
	- added missing test to MANIFEST
	- added additional tests
	- added SIGNATURE to distribution

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

=item last_key

  $key = $list->last_key;

  ($key, $finger, $value) = $list->last_key;

Returns the last key or the last key and finger returned by a call to
L</first_key>, L</next_key>, L</index_by_key>, L</key_by_index> or
L</value_by_index>.  This is not the greatest key.

Deletions and inserts may invalidate the L</last_key> value.
(Deletions will actually L</reset> the value.)

Values for L</last_key> can also be set by including parameters,
however this feature is meant for I<internal use only>:

  $list->last_key( $node );

Note that this is a change form versions prior to 0.71.

=item reset

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

  package NumericNode;

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

  sub key_cmp {
    my $self = shift;

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

    unless ($self->validate_key($right)) {
      die "Invalid key: \'$right\'"; }

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

  sub validate_key {
    my $self = shift;
    my $key  = shift;
    return ($key =~ s/\-?\d+(\.\d+)?$/); # test if key is numeric
  }

To use this, we say simply

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

This skip list should work normally, except that the keys must be

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

#-*- mode: perl;-*-

package NumericNode;

# use Carp::Assert;

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

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

  my $key = shift;
  return ($key =~ /^\-?\d+$/); # make sure key is simple natural number
}

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