1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
use Test::More tests => 39;
use strict;
use warnings;
use Data::Dumper;
use_ok( 'Tree::RB' );
diag( "Testing Tree::RB $Tree::RB::VERSION" );
foreach my $m (qw[
new
put
iter
rev_iter
size
])
{
can_ok('Tree::RB', $m);
}
my $tree = Tree::RB->new;
isa_ok($tree, 'Tree::RB');
ok($tree->size == 0, 'New tree has size zero');
$tree->put('France' => 'Paris');
$tree->put('England' => 'London');
$tree->put('Hungary' => 'Budapest');
$tree->put('Ireland' => 'Dublin');
$tree->put('Egypt' => 'Cairo');
ok(! defined $tree->put('Germany' => 'Bonn'), 'put with non existing key');
is($tree->put('Germany' => 'Berlin'), 'Bonn', 'put with existing key');
ok($tree->size == 6, 'size check after inserts');
is($tree->min->key, 'Egypt', 'min');
is($tree->max->key, 'Ireland', 'max');
# Iterator tests
my $it;
$it = $tree->iter;
isa_ok($it, 'Tree::RB::Iterator');
can_ok($it, 'next');
my @iter_tests = (
sub {
my $node = $_[0]->next;
ok($node->key eq 'Egypt' && $node->val eq 'Cairo', 'iterator check');
},
sub {
my $node = $_[0]->next;
ok($node->key eq 'England' && $node->val eq 'London', 'iterator check');
},
sub {
my $node = $_[0]->next;
ok($node->key eq 'France' && $node->val eq 'Paris', 'iterator check');
},
sub {
my $node = $_[0]->next;
ok($node->key eq 'Germany' && $node->val eq 'Berlin', 'iterator check');
},
sub {
my $node = $_[0]->next;
ok($node->key eq 'Hungary' && $node->val eq 'Budapest', 'iterator check');
},
sub {
my $node = $_[0]->next;
ok($node->key eq 'Ireland' && $node->val eq 'Dublin', 'iterator check');
},
sub {
my $node = $_[0]->next;
ok(!defined $node, 'iterator check - no more items');
},
);
foreach my $t (@iter_tests) {
$t->($it);
}
# Reverse iterator tests
$it = $tree->rev_iter;
isa_ok($it, 'Tree::RB::Iterator');
can_ok($it, 'next');
my @rev_iter_tests = (reverse(@iter_tests[0 .. $#iter_tests-1]), $iter_tests[-1]);
=pod
Longer way to reverse
my @rev_iter_tests = @iter_tests;
@rev_iter_tests = (pop @rev_iter_tests, @rev_iter_tests);
@rev_iter_tests = reverse @rev_iter_tests;
=cut
foreach my $t (@rev_iter_tests) {
$t->($it);
}
# seeking
my $node;
$it = $tree->iter('France');
$node = $it->next;
is($node->key, 'France', 'seek check, key exists');
$it = $tree->iter('Iceland');
$node = $it->next;
is($node->key, 'Ireland', 'seek check, key does not exist but is lt max key');
$it = $tree->iter('Timbuktu');
$node = $it->next;
ok(!defined $node, 'seek check, non existant key gt all keys')
or diag(Dumper($node));
# seeking in reverse
$it = $tree->rev_iter('Hungary');
$node = $it->next;
is($node->key, 'Hungary', 'reverse seek check, key exists');
$node = $it->next;
is($node->key, 'Germany', 'reverse seek check, next key lt this one');
$it = $tree->rev_iter('Finland');
$node = $it->next;
is($node->key, 'England', 'reverse seek check, key does not exist but is gt min key');
$it = $tree->rev_iter('Albania');
$node = $it->next;
ok(!defined $node, 'reverse seek check, non existant key lt all keys');
$tree->put('Timbuktu' => '');
is($tree->get('Timbuktu'), '', 'False values can be stored');
__END__
|
