#!/usr/bin/perl
use strict;
use warnings;
use Test::More;
sub randomly {
if (rand > 0.5) {
return $a cmp $b;
} else {
return $b cmp $a;
}
}
my @List = sort randomly (1..20);
# print STDERR "\x23 @List\n";
plan
# skip_all => "tests disabled";
tests => 18 + (46 * scalar(@List));
use_ok("Algorithm::SkipList", 2.00);
{
my $l = Algorithm::SkipList->new();
ok(defined $l, "new defined");
ok($l->isa("Algorithm::SkipList"), "isa");
ok($l->list->isa("Tree::Node"), "list->isa");
ok($l->list->child_count >= $l->level, "list->level >= level");
my $count = 0;
foreach my $key (@List) {
ok($l->size == $count, "size (before insert)");
my ($n, $c, $f) = $l->_search($key);
ok($c != 0, "_search failed");
($n, $c, $f) = $l->_search_with_finger($key);
ok($c != 0, "_search_with_finger failed");
ok(!$l->exists($key), "!exists");
ok(!$l->find($key), "!find");
ok(!$l->find_with_finger($key), "!find_with_finger");
my $h = $l->level;
$l->insert($key, ++$count);
ok($l->size == $count, "size (after insert)");
ok($l->level >= $h, "level");
($n, $c, $f) = $l->_search($key);
ok($c == 0, "_search success");
ok($n->key eq $key, "key eq key");
ok($n->key_cmp($key) == 0, "key_cmp == 0");
ok(!defined $f, "no finger");
ok($n->value == $count, "value");
($n, $c, $f) = $l->_search_with_finger($key);
ok($c == 0, "_search_with_finger success");
ok($n->key eq $key, "key eq key");
ok($n->key_cmp($key) == 0, "key_cmp == 0");
ok(defined $f, "finger");
ok($n->value == $count, "value");
($n, $c, $f) = $l->_search_with_finger($key, $f);
ok($c == 0, "_search_with_finger (using finger) success");
ok($n->key eq $key, "key eq key");
ok($n->key_cmp($key) == 0, "key_cmp == 0");
ok(defined $f, "finger");
ok($n->value == $count, "value");
ok($l->exists($key), "exists");
ok($l->find($key), "find");
ok($l->find($key,$f), "find (using finger)");
ok($l->find_with_finger($key), "find_with_finger");
ok($l->find_with_finger($key,$f), "find_with_finger (using finger)");
my ($v, $u) = $l->find_with_finger($key);
ok($v, "find_with_finger (array context)");
ok($u, "find_with_finger (array context) returned finger");
($v, $u) = $l->find_with_finger($key,$f);
ok($v, "find_with_finger (array context, using finger)");
ok($u, "find_with_finger (array context, using finger) returned finger");
}
# Check that keys are in order
my $n = $l->list;
my $key = "";
do {
$n = $n->get_child(0);
if ($n) {
ok($n->key_cmp($key) == 1);
$key = $n->key;
}
} while ($n);
$key = "";
do {
$n = $l->_next_node;
if ($n) {
ok($n->key_cmp($key) == 1);
$key = $n->key;
}
} while ($n);
ok($l->_first_node->key eq $l->list->get_child(0)->key);
{
my @o = sort @List;
my ($a, $b) = $l->least;
my ($c, $d) = $l->greatest;
ok($a eq $o[0], "first key");
ok($c eq $o[-1], "last key");
ok($l->find($a) eq $b, "first value");
ok($l->find($c) eq $d, "last value");
my $s = $l->size;
ok($l->delete($c) eq $d, "delete last value");
ok($l->size == ($s-1), "size shrank");
my ($e, $f) = $l->greatest;
ok(defined $e, "next to last key not undef");
ok($e eq $o[-2], "next to last key less than last key");
$l->insert($c, $d); # so we can run normal tests on deletions...
my $m = Algorithm::SkipList->new();
ok(!defined $m->least, "least undef in empty list");
ok(!defined $m->greatest, "greatest undef in empty list");
ok($l->first_key eq shift @o);
while (@o) {
ok($l->next_key eq shift @o);
}
}
# test copies
my $k = $l->copy;
ok($k->isa("Algorithm::SkipList"), "copy isa");
ok($l->size == $k->size, "comparing sizes");
$l->_reset_iterator;
$k->_reset_iterator;
while (my $n = $l->_next_node) {
my $m = $k->_next_node;
ok(ref($n) eq ref($m), "comparing ref types");
ok($n->key eq $m->key, "comparing key copies");
ok($n->value eq $m->value, "comparing value copies");
}
# test truncate
foreach my $key (@List ){
my $copy = $l->copy;
my $tail = $copy->truncate($key);
is(($copy->size + $tail->size), $l->size, "sizes add up from truncate");
is($tail->first_key, $key, "expected first key of truncate");
my $n = $copy->_last_node;
is($n->key_cmp($key), -1, "copy->_last_node->key_cmp(key)");
$copy->append($tail);
is($copy->size, $l->size, "appended size correct");
is($tail->size, 0, "tail truncated");
}
# test deletions
$count = 0;
foreach my $key (@List) {
my $s = $l->size;
my $h = $l->level;
ok($l->delete($key) == ++$count, "delete");
ok($l->size == ($s-1), "size decreased");
ok($l->level == $h, "level decreases?");
}
# my $n = Algorithm::SkipList::Node->new("a", 1, [(undef) x 2]);
# for(my $i=0; $i<$n->level; $i++) {
# $n->set_next($i, $l->list->get_next($i));
# $l->list->set_next($i,$n);
# }
# my ($m, $c, $f) = $l->_search($n->key);
# ok(!$c, "_search success");
# ok($m->key eq "a", "keys match");
# ok($m == $n, "nodes match");
# ok(!defined $f, "no finger");
# ($m, $c, $f) = $l->_search_with_finger("a");
# ok($c==0, "_search_with_finger success");
# ok($m->key eq "a", "keys match");
# ok($m == $n, "nodes match");
# ok(defined $f, "finger");
# ok(UNIVERSAL::isa($f, "ARRAY"), "finger is an array ref");
# ok(defined $f->[0]);
# # This may change in optimisation
# # ok($f->[0]->get_next(0) == $n, "finger points to node");
# ($m, $c, $f) = $l->_search_with_finger("a", $f);
# ok($c==0, "_search_with_finger (using finger) success");
# ok($m->key eq "a", "keys match");
# ok($m == $n, "nodes match");
# ok(defined $f, "finger");
# ok(UNIVERSAL::isa($f, "ARRAY"), "finger is an array ref");
# ok(defined $f->[0]);
# # This may change in optimisation
# # ok($f->[0]->get_next(0) == $n, "finger points to node");
}