line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
1
|
|
|
|
|
|
|
package Tree::SizeBalanced; |
2
|
|
|
|
|
|
|
|
3
|
|
|
|
|
|
|
# vim: filetype=perl |
4
|
|
|
|
|
|
|
|
5
|
1
|
|
|
1
|
|
13537
|
use 5.008009; |
|
1
|
|
|
|
|
2
|
|
6
|
1
|
|
|
1
|
|
4
|
use strict; |
|
1
|
|
|
|
|
1
|
|
|
1
|
|
|
|
|
20
|
|
7
|
1
|
|
|
1
|
|
3
|
use warnings; |
|
1
|
|
|
|
|
4
|
|
|
1
|
|
|
|
|
24
|
|
8
|
1
|
|
|
1
|
|
3
|
use Carp; |
|
1
|
|
|
|
|
1
|
|
|
1
|
|
|
|
|
67
|
|
9
|
|
|
|
|
|
|
|
10
|
|
|
|
|
|
|
require Exporter; |
11
|
1
|
|
|
1
|
|
540
|
use AutoLoader; |
|
1
|
|
|
|
|
1124
|
|
|
1
|
|
|
|
|
4
|
|
12
|
|
|
|
|
|
|
|
13
|
|
|
|
|
|
|
our @ISA = qw(Exporter); |
14
|
|
|
|
|
|
|
|
15
|
|
|
|
|
|
|
# Items to export into callers namespace by default. Note: do not export |
16
|
|
|
|
|
|
|
# names by default without a very good reason. Use EXPORT_OK instead. |
17
|
|
|
|
|
|
|
# Do not simply export all your public functions/methods/constants. |
18
|
|
|
|
|
|
|
|
19
|
|
|
|
|
|
|
# This allows declaration use Tree::SizeBalanced ':all'; |
20
|
|
|
|
|
|
|
# If you do not need this, moving things directly into @EXPORT or @EXPORT_OK |
21
|
|
|
|
|
|
|
# will save memory. |
22
|
|
|
|
|
|
|
|
23
|
|
|
|
|
|
|
our $VERSION = '2.006002'; |
24
|
|
|
|
|
|
|
|
25
|
|
|
|
|
|
|
=head1 NAME |
26
|
|
|
|
|
|
|
|
27
|
|
|
|
|
|
|
Tree::SizeBalanced - Size balanced binary search tree (XS implementation) |
28
|
|
|
|
|
|
|
|
29
|
|
|
|
|
|
|
Handy for in-memory realtime ranking systems. |
30
|
|
|
|
|
|
|
|
31
|
|
|
|
|
|
|
=head1 SYNOPSIS |
32
|
|
|
|
|
|
|
|
33
|
|
|
|
|
|
|
use Tree::SizeBalanced; # use $tree = Tree::SizeBalanced::int_any->new |
34
|
|
|
|
|
|
|
use Tree::SizeBalanced qw(:long); # use $tree = sbtree_int_any; |
35
|
|
|
|
|
|
|
use Tree::SizeBalanced qw(:short); # use $tree = sbtreeia; |
36
|
|
|
|
|
|
|
use Tree::SizeBalanced qw(:all); # export :short and :long |
37
|
|
|
|
|
|
|
|
38
|
|
|
|
|
|
|
my $tree_map_any_any = sbtree_any_any { length($b) <=> length($a) }; |
39
|
|
|
|
|
|
|
my $tree_map_any_any = sbtreeaa { length($b) <=> length($a) }; # shorter form |
40
|
|
|
|
|
|
|
my $tree_map_any_any = Tree::SizeBalanced::any_any->new |
41
|
|
|
|
|
|
|
sub { length($b) <=> length($a) }; # full form |
42
|
|
|
|
|
|
|
# tree map with any scalars as keys |
43
|
|
|
|
|
|
|
|
44
|
|
|
|
|
|
|
my $tree_set_num = sbtree_num_void; |
45
|
|
|
|
|
|
|
my $tree_set_num = sbtreen; # shorter form |
46
|
|
|
|
|
|
|
my $tree_set_num = Tree::SizeBalanced::num_void->new; # full form |
47
|
|
|
|
|
|
|
# or set version. |
48
|
|
|
|
|
|
|
# This one use numeric values (floating point numbers) as keys |
49
|
|
|
|
|
|
|
|
50
|
|
|
|
|
|
|
my $tree = sbtree_int_any; |
51
|
|
|
|
|
|
|
my $tree = sbtreeia; # shorter form |
52
|
|
|
|
|
|
|
my $tree = Tree::SizeBalanced::int_any->new; # full form |
53
|
|
|
|
|
|
|
# tree map (key value pairs) |
54
|
|
|
|
|
|
|
# the keys are signed integers |
55
|
|
|
|
|
|
|
# the values are any scalars |
56
|
|
|
|
|
|
|
|
57
|
|
|
|
|
|
|
$tree->insert(1, {a => 3}); |
58
|
|
|
|
|
|
|
|
59
|
|
|
|
|
|
|
... |
60
|
|
|
|
|
|
|
|
61
|
|
|
|
|
|
|
my $count = $tree->count_lt(25); |
62
|
|
|
|
|
|
|
# how many entries in the tree whose key is less than 25 |
63
|
|
|
|
|
|
|
my $count = $tree->count_gt(25); |
64
|
|
|
|
|
|
|
# how many entries in the tree whose key is greater than 25 |
65
|
|
|
|
|
|
|
|
66
|
|
|
|
|
|
|
($key, $value) = $tree->skip_l(23); |
67
|
|
|
|
|
|
|
$key = $tree->skip_l(23); |
68
|
|
|
|
|
|
|
# Get the first (smallest) entry whose key is greater than 23 |
69
|
|
|
|
|
|
|
|
70
|
|
|
|
|
|
|
($key, $value) = $tree->skip_g(23); |
71
|
|
|
|
|
|
|
$key = $tree->skip_g(23); |
72
|
|
|
|
|
|
|
# Get the first (largest) entry whose key is less than 23 |
73
|
|
|
|
|
|
|
|
74
|
|
|
|
|
|
|
($key, $value) = $tree->find_min; |
75
|
|
|
|
|
|
|
$key = $tree->find_min; |
76
|
|
|
|
|
|
|
($key, $value) = $tree->find_max; |
77
|
|
|
|
|
|
|
$key = $tree->find_max; |
78
|
|
|
|
|
|
|
|
79
|
|
|
|
|
|
|
($k1, $v1, $k2, $v2) = $tree->find_min(2); |
80
|
|
|
|
|
|
|
($k1, $v1, $k2, $v2, $k3, $v3) = $tree->find_min(3); |
81
|
|
|
|
|
|
|
($k1, $v1, $k2, $v2, $k3, $v3, ...) = $tree->find_min(-1); |
82
|
|
|
|
|
|
|
|
83
|
|
|
|
|
|
|
($k1, $v1, ...= $tree->find_lt_gt($lower_bound, $upper_bound); |
84
|
|
|
|
|
|
|
|
85
|
|
|
|
|
|
|
... |
86
|
|
|
|
|
|
|
|
87
|
|
|
|
|
|
|
$tree->delete(1); |
88
|
|
|
|
|
|
|
|
89
|
|
|
|
|
|
|
=head1 DESCRIPTION |
90
|
|
|
|
|
|
|
|
91
|
|
|
|
|
|
|
Quoted from L: |
92
|
|
|
|
|
|
|
|
93
|
|
|
|
|
|
|
=encoding UTF-8 |
94
|
|
|
|
|
|
|
|
95
|
|
|
|
|
|
|
> A size balanced tree (SBT) is a self-balancing binary search tree (BBST) first published by Chinese student Qifeng Chen in 2007. The tree is rebalanced by examining the sizes of each node's subtrees. Its abbreviation resulted in many nicknames given by Chinese informatics competitors, including "sha bi" tree (Chinese: 傻屄树; pinyin: shǎ bī shù; literally meaning "dumb cunt tree") and "super BT", which is a homophone to the Chinese term for snot (Chinese: 鼻涕; pinyin: bítì) suggesting that it is messy to implement. Contrary to what its nicknames suggest, this data structure can be very useful, and is also known to be easy to implement. Since the only extra piece of information that needs to be stored is sizes of the nodes (instead of other "useless" fields such as randomized weights in treaps or colours in red–black tress), this makes it very convenient to implement the select-by-rank and get-rank operations (easily transforming it into an order statistic tree). It supports standard binary search tree operations such as insertion, deletion, and searching in O(log n) time. According to Chen's paper, "it works much faster than many other famous BSTs due to the tendency of a perfect BST in practice." |
96
|
|
|
|
|
|
|
|
97
|
|
|
|
|
|
|
For performance consideration, this module provides trees with many stricter types. |
98
|
|
|
|
|
|
|
|
99
|
|
|
|
|
|
|
If you choose any scalar as the key type, you must provide a comparing sub. |
100
|
|
|
|
|
|
|
The comparing sub should exammed localized C<$a> and C<$b> (or C<$::a> and C<$::b> if there are introduced lexical <$a> and <$b> right outside the sub). |
101
|
|
|
|
|
|
|
And if your comparing sub using an indirect way to judge the size of the keys, |
102
|
|
|
|
|
|
|
don't do anything that will change the judge result. Or, the tree will be confused and give you incorrect results. |
103
|
|
|
|
|
|
|
|
104
|
|
|
|
|
|
|
If you put more than one entries with equal-sized keys, |
105
|
|
|
|
|
|
|
the insertion order is preserved by treating the first one as the smallest one among them. |
106
|
|
|
|
|
|
|
|
107
|
|
|
|
|
|
|
PS. Qifeng Chen is 陈启峰 in simplified Chinese. |
108
|
|
|
|
|
|
|
|
109
|
|
|
|
|
|
|
This module has been tested on perl version 5.8.9, 5.10.1, 5.12.5, 5.14.4, 5.16.3, 5.18.4, 5.20.3, 5.22.2 |
110
|
|
|
|
|
|
|
|
111
|
|
|
|
|
|
|
=head2 EXPORT |
112
|
|
|
|
|
|
|
|
113
|
|
|
|
|
|
|
All exported subs are different style ways to create new trees. |
114
|
|
|
|
|
|
|
|
115
|
|
|
|
|
|
|
=over 4 |
116
|
|
|
|
|
|
|
|
117
|
|
|
|
|
|
|
=item (nothing) |
118
|
|
|
|
|
|
|
|
119
|
|
|
|
|
|
|
Without importing anything, you can use the full form to obtain a new tree: |
120
|
|
|
|
|
|
|
|
121
|
|
|
|
|
|
|
my $tree = Tree::SizeBalanced::str_any->new; |
122
|
|
|
|
|
|
|
|
123
|
|
|
|
|
|
|
=item :long |
124
|
|
|
|
|
|
|
|
125
|
|
|
|
|
|
|
With the long form: |
126
|
|
|
|
|
|
|
|
127
|
|
|
|
|
|
|
my $tree = sbtree_any_str { length($a) <=> length($b) || $a cmp $b }; |
128
|
|
|
|
|
|
|
|
129
|
|
|
|
|
|
|
=item :short |
130
|
|
|
|
|
|
|
|
131
|
|
|
|
|
|
|
With the short form: |
132
|
|
|
|
|
|
|
|
133
|
|
|
|
|
|
|
my $tree = sbtreei; |
134
|
|
|
|
|
|
|
|
135
|
|
|
|
|
|
|
=item :all = :short + :long |
136
|
|
|
|
|
|
|
|
137
|
|
|
|
|
|
|
=back |
138
|
|
|
|
|
|
|
|
139
|
|
|
|
|
|
|
=head2 Different trees with different types |
140
|
|
|
|
|
|
|
|
141
|
|
|
|
|
|
|
=cut |
142
|
|
|
|
|
|
|
|
143
|
|
|
|
|
|
|
our @EXPORT_OK = qw(sbtree); |
144
|
|
|
|
|
|
|
our %EXPORT_TAGS = ( |
145
|
|
|
|
|
|
|
'all' => ['sbtree'], |
146
|
|
|
|
|
|
|
'short' => ['sbtree'], |
147
|
|
|
|
|
|
|
'long' => [], |
148
|
|
|
|
|
|
|
); |
149
|
|
|
|
|
|
|
|
150
|
|
|
|
|
|
|
|
151
|
|
|
|
|
|
|
=head3 Tree::SizeBalanced::int_void |
152
|
|
|
|
|
|
|
|
153
|
|
|
|
|
|
|
Tree set with key type signed integers (32bits or 64bits according to your perl version). |
154
|
|
|
|
|
|
|
|
155
|
|
|
|
|
|
|
=over 4 |
156
|
|
|
|
|
|
|
|
157
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced::int_void->new |
158
|
|
|
|
|
|
|
|
159
|
|
|
|
|
|
|
=item $tree = sbtree_int_void |
160
|
|
|
|
|
|
|
|
161
|
|
|
|
|
|
|
=item $tree = sbtreei |
162
|
|
|
|
|
|
|
|
163
|
|
|
|
|
|
|
Creat a new empty tree. |
164
|
|
|
|
|
|
|
|
165
|
|
|
|
|
|
|
=item $tree->insert($key) |
166
|
|
|
|
|
|
|
|
167
|
|
|
|
|
|
|
=item $tree->insert_after($key) |
168
|
|
|
|
|
|
|
|
169
|
|
|
|
|
|
|
Insert an entry into the tree. |
170
|
|
|
|
|
|
|
If there are any entries with the same key size, |
171
|
|
|
|
|
|
|
insert the new one after them. |
172
|
|
|
|
|
|
|
|
173
|
|
|
|
|
|
|
=item $tree->insert_before($key) |
174
|
|
|
|
|
|
|
|
175
|
|
|
|
|
|
|
Insert an entry into the tree. |
176
|
|
|
|
|
|
|
If there are any entries with the same key size, |
177
|
|
|
|
|
|
|
insert the new one before them. |
178
|
|
|
|
|
|
|
|
179
|
|
|
|
|
|
|
=item $tree->delete($key) |
180
|
|
|
|
|
|
|
|
181
|
|
|
|
|
|
|
=item $tree->delete_last($key) |
182
|
|
|
|
|
|
|
|
183
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
184
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
185
|
|
|
|
|
|
|
delete the last inserted one. |
186
|
|
|
|
|
|
|
|
187
|
|
|
|
|
|
|
=item $tree->delete_first($key) |
188
|
|
|
|
|
|
|
|
189
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
190
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
191
|
|
|
|
|
|
|
delete the first inserted one. |
192
|
|
|
|
|
|
|
|
193
|
|
|
|
|
|
|
=item $size = $tree->size |
194
|
|
|
|
|
|
|
|
195
|
|
|
|
|
|
|
Get the number of entries in the tree |
196
|
|
|
|
|
|
|
|
197
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find($key, $limit=1) |
198
|
|
|
|
|
|
|
|
199
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_first($key, $limit=1) |
200
|
|
|
|
|
|
|
|
201
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
202
|
|
|
|
|
|
|
from the first inserted one to the last inserted one. |
203
|
|
|
|
|
|
|
|
204
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
205
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
206
|
|
|
|
|
|
|
|
207
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_last($key, $limit=1) |
208
|
|
|
|
|
|
|
|
209
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
210
|
|
|
|
|
|
|
from the last inserted one to the first inserted one. |
211
|
|
|
|
|
|
|
|
212
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
213
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
214
|
|
|
|
|
|
|
|
215
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_lt($key, $limit=1) |
216
|
|
|
|
|
|
|
|
217
|
|
|
|
|
|
|
Get entries, whose keys are smaller than $key, from the largest entry. |
218
|
|
|
|
|
|
|
|
219
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
220
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
221
|
|
|
|
|
|
|
|
222
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_le($key, $limit=1) |
223
|
|
|
|
|
|
|
|
224
|
|
|
|
|
|
|
Get entries, whose keys are smaller than or equal to $key, from the largest entry. |
225
|
|
|
|
|
|
|
|
226
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
227
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
228
|
|
|
|
|
|
|
|
229
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_gt($key, $limit=1) |
230
|
|
|
|
|
|
|
|
231
|
|
|
|
|
|
|
Get entries, whose keys are greater than $key, from the smallest one. |
232
|
|
|
|
|
|
|
|
233
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
234
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
235
|
|
|
|
|
|
|
|
236
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_ge($key, $limit=1) |
237
|
|
|
|
|
|
|
|
238
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $key, from the smallest one. |
239
|
|
|
|
|
|
|
|
240
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
241
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
242
|
|
|
|
|
|
|
|
243
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_gt_lt($lower_key, $upper_key) |
244
|
|
|
|
|
|
|
|
245
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than $upper_key, |
246
|
|
|
|
|
|
|
from the smallest one to the largest one. |
247
|
|
|
|
|
|
|
|
248
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_gt_le($lower_key, $upper_key) |
249
|
|
|
|
|
|
|
|
250
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, |
251
|
|
|
|
|
|
|
from the smallest one to the largest one. |
252
|
|
|
|
|
|
|
|
253
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_ge_lt($lower_key, $upper_key) |
254
|
|
|
|
|
|
|
|
255
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, |
256
|
|
|
|
|
|
|
from the smallest one to the largest one. |
257
|
|
|
|
|
|
|
|
258
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_ge_le($lower_key, $upper_key) |
259
|
|
|
|
|
|
|
|
260
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, |
261
|
|
|
|
|
|
|
from the smallest one to the largest one. |
262
|
|
|
|
|
|
|
|
263
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_min($limit=1) |
264
|
|
|
|
|
|
|
|
265
|
|
|
|
|
|
|
Get entries from the one with smallest key. |
266
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
267
|
|
|
|
|
|
|
begin from the first inserted one. |
268
|
|
|
|
|
|
|
|
269
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
270
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
271
|
|
|
|
|
|
|
|
272
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_max($limit=1) |
273
|
|
|
|
|
|
|
|
274
|
|
|
|
|
|
|
Get entries from the one with largest key. |
275
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
276
|
|
|
|
|
|
|
begin from the last inserted one. |
277
|
|
|
|
|
|
|
|
278
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
279
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
280
|
|
|
|
|
|
|
|
281
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = &tree->skip_l($offset, $limit=1) |
282
|
|
|
|
|
|
|
|
283
|
|
|
|
|
|
|
Get the first entry from one with the smallest key after skipping $offset entries. |
284
|
|
|
|
|
|
|
|
285
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
286
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
287
|
|
|
|
|
|
|
|
288
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = &tree->skip_g($offset, $limit=1) |
289
|
|
|
|
|
|
|
|
290
|
|
|
|
|
|
|
Get the first entry from one with the largest key after skipping $offset entries. |
291
|
|
|
|
|
|
|
|
292
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
293
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
294
|
|
|
|
|
|
|
|
295
|
|
|
|
|
|
|
=item $count = $tree->count_lt($key) |
296
|
|
|
|
|
|
|
|
297
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than $key. |
298
|
|
|
|
|
|
|
|
299
|
|
|
|
|
|
|
=item $count = $tree->count_le($key) |
300
|
|
|
|
|
|
|
|
301
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than or equal to $key. |
302
|
|
|
|
|
|
|
|
303
|
|
|
|
|
|
|
=item $count = $tree->count_gt($key) |
304
|
|
|
|
|
|
|
|
305
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than $key. |
306
|
|
|
|
|
|
|
|
307
|
|
|
|
|
|
|
=item $count = $tree->count_ge($key) |
308
|
|
|
|
|
|
|
|
309
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than or equal to $key. |
310
|
|
|
|
|
|
|
|
311
|
|
|
|
|
|
|
=item $dump_str = $tree->dump |
312
|
|
|
|
|
|
|
|
313
|
|
|
|
|
|
|
Get a string which represent the whole tree structure. For debug use. |
314
|
|
|
|
|
|
|
|
315
|
|
|
|
|
|
|
=item ($order_consistent, $size_consistent, $balanced) = $tree->check |
316
|
|
|
|
|
|
|
|
317
|
|
|
|
|
|
|
Check the tree property. For debug use. |
318
|
|
|
|
|
|
|
|
319
|
|
|
|
|
|
|
=item $ever_height = $tree->ever_height |
320
|
|
|
|
|
|
|
|
321
|
|
|
|
|
|
|
Get the maximum height the tree has ever been. For debug use |
322
|
|
|
|
|
|
|
|
323
|
|
|
|
|
|
|
=back |
324
|
|
|
|
|
|
|
|
325
|
|
|
|
|
|
|
=cut |
326
|
|
|
|
|
|
|
|
327
|
1
|
|
|
1
|
|
412
|
use Tree::SizeBalanced::int_void; |
|
1
|
|
|
|
|
2
|
|
|
1
|
|
|
|
|
127
|
|
328
|
|
|
|
|
|
|
|
329
|
|
|
|
|
|
|
sub sbtree_int_void() { |
330
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::int_void'; |
331
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::int_void::new; |
332
|
|
|
|
|
|
|
} |
333
|
|
|
|
|
|
|
|
334
|
|
|
|
|
|
|
sub sbtreei() { |
335
|
1
|
|
|
1
|
1
|
5
|
unshift @_, 'Tree::SizeBalanced::int_void'; |
336
|
1
|
|
|
|
|
22
|
goto \&Tree::SizeBalanced::int_void::new; |
337
|
|
|
|
|
|
|
} |
338
|
|
|
|
|
|
|
|
339
|
|
|
|
|
|
|
push @EXPORT_OK, qw(sbtree_int_void sbtreei); |
340
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'all'}}, qw(sbtree_int_void sbtreei); |
341
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'short'}}, qw(sbtreei); |
342
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'long'}}, qw(sbtree_int_void); |
343
|
|
|
|
|
|
|
|
344
|
|
|
|
|
|
|
|
345
|
|
|
|
|
|
|
=head3 Tree::SizeBalanced::int_int |
346
|
|
|
|
|
|
|
|
347
|
|
|
|
|
|
|
Tree map with key type signed integers (32bits or 64bits according to your perl version) and value type signed integers (32bits or 64bits according to your perl version). |
348
|
|
|
|
|
|
|
|
349
|
|
|
|
|
|
|
=over 4 |
350
|
|
|
|
|
|
|
|
351
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced::int_int->new |
352
|
|
|
|
|
|
|
|
353
|
|
|
|
|
|
|
=item $tree = sbtree_int_int |
354
|
|
|
|
|
|
|
|
355
|
|
|
|
|
|
|
=item $tree = sbtreeii |
356
|
|
|
|
|
|
|
|
357
|
|
|
|
|
|
|
Creat a new empty tree. |
358
|
|
|
|
|
|
|
|
359
|
|
|
|
|
|
|
=item $tree->insert($key, $value) |
360
|
|
|
|
|
|
|
|
361
|
|
|
|
|
|
|
=item $tree->insert_after($key, $value) |
362
|
|
|
|
|
|
|
|
363
|
|
|
|
|
|
|
Insert an entry into the tree. |
364
|
|
|
|
|
|
|
If there are any entries with the same key size, |
365
|
|
|
|
|
|
|
insert the new one after them. |
366
|
|
|
|
|
|
|
|
367
|
|
|
|
|
|
|
=item $tree->insert_before($key, $value) |
368
|
|
|
|
|
|
|
|
369
|
|
|
|
|
|
|
Insert an entry into the tree. |
370
|
|
|
|
|
|
|
If there are any entries with the same key size, |
371
|
|
|
|
|
|
|
insert the new one before them. |
372
|
|
|
|
|
|
|
|
373
|
|
|
|
|
|
|
=item $tree->delete($key) |
374
|
|
|
|
|
|
|
|
375
|
|
|
|
|
|
|
=item $tree->delete_last($key) |
376
|
|
|
|
|
|
|
|
377
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
378
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
379
|
|
|
|
|
|
|
delete the last inserted one. |
380
|
|
|
|
|
|
|
|
381
|
|
|
|
|
|
|
=item $tree->delete_first($key) |
382
|
|
|
|
|
|
|
|
383
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
384
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
385
|
|
|
|
|
|
|
delete the first inserted one. |
386
|
|
|
|
|
|
|
|
387
|
|
|
|
|
|
|
=item $size = $tree->size |
388
|
|
|
|
|
|
|
|
389
|
|
|
|
|
|
|
Get the number of entries in the tree |
390
|
|
|
|
|
|
|
|
391
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find($key, $limit=1) |
392
|
|
|
|
|
|
|
|
393
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_first($key, $limit=1) |
394
|
|
|
|
|
|
|
|
395
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
396
|
|
|
|
|
|
|
from the first inserted one to the last inserted one. |
397
|
|
|
|
|
|
|
|
398
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
399
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
400
|
|
|
|
|
|
|
|
401
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_last($key, $limit=1) |
402
|
|
|
|
|
|
|
|
403
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
404
|
|
|
|
|
|
|
from the last inserted one to the first inserted one. |
405
|
|
|
|
|
|
|
|
406
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
407
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
408
|
|
|
|
|
|
|
|
409
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_lt($key, $limit=1) |
410
|
|
|
|
|
|
|
|
411
|
|
|
|
|
|
|
Get entries, whose keys are smaller than $key, from the largest entry. |
412
|
|
|
|
|
|
|
|
413
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
414
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
415
|
|
|
|
|
|
|
|
416
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_le($key, $limit=1) |
417
|
|
|
|
|
|
|
|
418
|
|
|
|
|
|
|
Get entries, whose keys are smaller than or equal to $key, from the largest entry. |
419
|
|
|
|
|
|
|
|
420
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
421
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
422
|
|
|
|
|
|
|
|
423
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt($key, $limit=1) |
424
|
|
|
|
|
|
|
|
425
|
|
|
|
|
|
|
Get entries, whose keys are greater than $key, from the smallest one. |
426
|
|
|
|
|
|
|
|
427
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
428
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
429
|
|
|
|
|
|
|
|
430
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge($key, $limit=1) |
431
|
|
|
|
|
|
|
|
432
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $key, from the smallest one. |
433
|
|
|
|
|
|
|
|
434
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
435
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
436
|
|
|
|
|
|
|
|
437
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_lt($lower_key, $upper_key) |
438
|
|
|
|
|
|
|
|
439
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than $upper_key, |
440
|
|
|
|
|
|
|
from the smallest one to the largest one. |
441
|
|
|
|
|
|
|
|
442
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_le($lower_key, $upper_key) |
443
|
|
|
|
|
|
|
|
444
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, |
445
|
|
|
|
|
|
|
from the smallest one to the largest one. |
446
|
|
|
|
|
|
|
|
447
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_lt($lower_key, $upper_key) |
448
|
|
|
|
|
|
|
|
449
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, |
450
|
|
|
|
|
|
|
from the smallest one to the largest one. |
451
|
|
|
|
|
|
|
|
452
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_le($lower_key, $upper_key) |
453
|
|
|
|
|
|
|
|
454
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, |
455
|
|
|
|
|
|
|
from the smallest one to the largest one. |
456
|
|
|
|
|
|
|
|
457
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_min($limit=1) |
458
|
|
|
|
|
|
|
|
459
|
|
|
|
|
|
|
Get entries from the one with smallest key. |
460
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
461
|
|
|
|
|
|
|
begin from the first inserted one. |
462
|
|
|
|
|
|
|
|
463
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
464
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
465
|
|
|
|
|
|
|
|
466
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_max($limit=1) |
467
|
|
|
|
|
|
|
|
468
|
|
|
|
|
|
|
Get entries from the one with largest key. |
469
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
470
|
|
|
|
|
|
|
begin from the last inserted one. |
471
|
|
|
|
|
|
|
|
472
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
473
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
474
|
|
|
|
|
|
|
|
475
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_l($offset, $limit=1) |
476
|
|
|
|
|
|
|
|
477
|
|
|
|
|
|
|
Get the first entry from one with the smallest key after skipping $offset entries. |
478
|
|
|
|
|
|
|
|
479
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
480
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
481
|
|
|
|
|
|
|
|
482
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_g($offset, $limit=1) |
483
|
|
|
|
|
|
|
|
484
|
|
|
|
|
|
|
Get the first entry from one with the largest key after skipping $offset entries. |
485
|
|
|
|
|
|
|
|
486
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
487
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
488
|
|
|
|
|
|
|
|
489
|
|
|
|
|
|
|
=item $count = $tree->count_lt($key) |
490
|
|
|
|
|
|
|
|
491
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than $key. |
492
|
|
|
|
|
|
|
|
493
|
|
|
|
|
|
|
=item $count = $tree->count_le($key) |
494
|
|
|
|
|
|
|
|
495
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than or equal to $key. |
496
|
|
|
|
|
|
|
|
497
|
|
|
|
|
|
|
=item $count = $tree->count_gt($key) |
498
|
|
|
|
|
|
|
|
499
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than $key. |
500
|
|
|
|
|
|
|
|
501
|
|
|
|
|
|
|
=item $count = $tree->count_ge($key) |
502
|
|
|
|
|
|
|
|
503
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than or equal to $key. |
504
|
|
|
|
|
|
|
|
505
|
|
|
|
|
|
|
=item $dump_str = $tree->dump |
506
|
|
|
|
|
|
|
|
507
|
|
|
|
|
|
|
Get a string which represent the whole tree structure. For debug use. |
508
|
|
|
|
|
|
|
|
509
|
|
|
|
|
|
|
=item ($order_consistent, $size_consistent, $balanced) = $tree->check |
510
|
|
|
|
|
|
|
|
511
|
|
|
|
|
|
|
Check the tree property. For debug use. |
512
|
|
|
|
|
|
|
|
513
|
|
|
|
|
|
|
=item $ever_height = $tree->ever_height |
514
|
|
|
|
|
|
|
|
515
|
|
|
|
|
|
|
Get the maximum height the tree has ever been. For debug use |
516
|
|
|
|
|
|
|
|
517
|
|
|
|
|
|
|
=back |
518
|
|
|
|
|
|
|
|
519
|
|
|
|
|
|
|
=cut |
520
|
|
|
|
|
|
|
|
521
|
1
|
|
|
1
|
|
309
|
use Tree::SizeBalanced::int_int; |
|
1
|
|
|
|
|
1
|
|
|
1
|
|
|
|
|
132
|
|
522
|
|
|
|
|
|
|
|
523
|
|
|
|
|
|
|
sub sbtree_int_int() { |
524
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::int_int'; |
525
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::int_int::new; |
526
|
|
|
|
|
|
|
} |
527
|
|
|
|
|
|
|
|
528
|
|
|
|
|
|
|
sub sbtreeii() { |
529
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::int_int'; |
530
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::int_int::new; |
531
|
|
|
|
|
|
|
} |
532
|
|
|
|
|
|
|
|
533
|
|
|
|
|
|
|
push @EXPORT_OK, qw(sbtree_int_int sbtreeii); |
534
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'all'}}, qw(sbtree_int_int sbtreeii); |
535
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'short'}}, qw(sbtreeii); |
536
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'long'}}, qw(sbtree_int_int); |
537
|
|
|
|
|
|
|
|
538
|
|
|
|
|
|
|
|
539
|
|
|
|
|
|
|
=head3 Tree::SizeBalanced::int_num |
540
|
|
|
|
|
|
|
|
541
|
|
|
|
|
|
|
Tree map with key type signed integers (32bits or 64bits according to your perl version) and value type numeric numbers (floating point numbers). |
542
|
|
|
|
|
|
|
|
543
|
|
|
|
|
|
|
=over 4 |
544
|
|
|
|
|
|
|
|
545
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced::int_num->new |
546
|
|
|
|
|
|
|
|
547
|
|
|
|
|
|
|
=item $tree = sbtree_int_num |
548
|
|
|
|
|
|
|
|
549
|
|
|
|
|
|
|
=item $tree = sbtreein |
550
|
|
|
|
|
|
|
|
551
|
|
|
|
|
|
|
Creat a new empty tree. |
552
|
|
|
|
|
|
|
|
553
|
|
|
|
|
|
|
=item $tree->insert($key, $value) |
554
|
|
|
|
|
|
|
|
555
|
|
|
|
|
|
|
=item $tree->insert_after($key, $value) |
556
|
|
|
|
|
|
|
|
557
|
|
|
|
|
|
|
Insert an entry into the tree. |
558
|
|
|
|
|
|
|
If there are any entries with the same key size, |
559
|
|
|
|
|
|
|
insert the new one after them. |
560
|
|
|
|
|
|
|
|
561
|
|
|
|
|
|
|
=item $tree->insert_before($key, $value) |
562
|
|
|
|
|
|
|
|
563
|
|
|
|
|
|
|
Insert an entry into the tree. |
564
|
|
|
|
|
|
|
If there are any entries with the same key size, |
565
|
|
|
|
|
|
|
insert the new one before them. |
566
|
|
|
|
|
|
|
|
567
|
|
|
|
|
|
|
=item $tree->delete($key) |
568
|
|
|
|
|
|
|
|
569
|
|
|
|
|
|
|
=item $tree->delete_last($key) |
570
|
|
|
|
|
|
|
|
571
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
572
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
573
|
|
|
|
|
|
|
delete the last inserted one. |
574
|
|
|
|
|
|
|
|
575
|
|
|
|
|
|
|
=item $tree->delete_first($key) |
576
|
|
|
|
|
|
|
|
577
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
578
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
579
|
|
|
|
|
|
|
delete the first inserted one. |
580
|
|
|
|
|
|
|
|
581
|
|
|
|
|
|
|
=item $size = $tree->size |
582
|
|
|
|
|
|
|
|
583
|
|
|
|
|
|
|
Get the number of entries in the tree |
584
|
|
|
|
|
|
|
|
585
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find($key, $limit=1) |
586
|
|
|
|
|
|
|
|
587
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_first($key, $limit=1) |
588
|
|
|
|
|
|
|
|
589
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
590
|
|
|
|
|
|
|
from the first inserted one to the last inserted one. |
591
|
|
|
|
|
|
|
|
592
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
593
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
594
|
|
|
|
|
|
|
|
595
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_last($key, $limit=1) |
596
|
|
|
|
|
|
|
|
597
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
598
|
|
|
|
|
|
|
from the last inserted one to the first inserted one. |
599
|
|
|
|
|
|
|
|
600
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
601
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
602
|
|
|
|
|
|
|
|
603
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_lt($key, $limit=1) |
604
|
|
|
|
|
|
|
|
605
|
|
|
|
|
|
|
Get entries, whose keys are smaller than $key, from the largest entry. |
606
|
|
|
|
|
|
|
|
607
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
608
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
609
|
|
|
|
|
|
|
|
610
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_le($key, $limit=1) |
611
|
|
|
|
|
|
|
|
612
|
|
|
|
|
|
|
Get entries, whose keys are smaller than or equal to $key, from the largest entry. |
613
|
|
|
|
|
|
|
|
614
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
615
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
616
|
|
|
|
|
|
|
|
617
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt($key, $limit=1) |
618
|
|
|
|
|
|
|
|
619
|
|
|
|
|
|
|
Get entries, whose keys are greater than $key, from the smallest one. |
620
|
|
|
|
|
|
|
|
621
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
622
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
623
|
|
|
|
|
|
|
|
624
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge($key, $limit=1) |
625
|
|
|
|
|
|
|
|
626
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $key, from the smallest one. |
627
|
|
|
|
|
|
|
|
628
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
629
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
630
|
|
|
|
|
|
|
|
631
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_lt($lower_key, $upper_key) |
632
|
|
|
|
|
|
|
|
633
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than $upper_key, |
634
|
|
|
|
|
|
|
from the smallest one to the largest one. |
635
|
|
|
|
|
|
|
|
636
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_le($lower_key, $upper_key) |
637
|
|
|
|
|
|
|
|
638
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, |
639
|
|
|
|
|
|
|
from the smallest one to the largest one. |
640
|
|
|
|
|
|
|
|
641
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_lt($lower_key, $upper_key) |
642
|
|
|
|
|
|
|
|
643
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, |
644
|
|
|
|
|
|
|
from the smallest one to the largest one. |
645
|
|
|
|
|
|
|
|
646
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_le($lower_key, $upper_key) |
647
|
|
|
|
|
|
|
|
648
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, |
649
|
|
|
|
|
|
|
from the smallest one to the largest one. |
650
|
|
|
|
|
|
|
|
651
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_min($limit=1) |
652
|
|
|
|
|
|
|
|
653
|
|
|
|
|
|
|
Get entries from the one with smallest key. |
654
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
655
|
|
|
|
|
|
|
begin from the first inserted one. |
656
|
|
|
|
|
|
|
|
657
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
658
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
659
|
|
|
|
|
|
|
|
660
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_max($limit=1) |
661
|
|
|
|
|
|
|
|
662
|
|
|
|
|
|
|
Get entries from the one with largest key. |
663
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
664
|
|
|
|
|
|
|
begin from the last inserted one. |
665
|
|
|
|
|
|
|
|
666
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
667
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
668
|
|
|
|
|
|
|
|
669
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_l($offset, $limit=1) |
670
|
|
|
|
|
|
|
|
671
|
|
|
|
|
|
|
Get the first entry from one with the smallest key after skipping $offset entries. |
672
|
|
|
|
|
|
|
|
673
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
674
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
675
|
|
|
|
|
|
|
|
676
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_g($offset, $limit=1) |
677
|
|
|
|
|
|
|
|
678
|
|
|
|
|
|
|
Get the first entry from one with the largest key after skipping $offset entries. |
679
|
|
|
|
|
|
|
|
680
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
681
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
682
|
|
|
|
|
|
|
|
683
|
|
|
|
|
|
|
=item $count = $tree->count_lt($key) |
684
|
|
|
|
|
|
|
|
685
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than $key. |
686
|
|
|
|
|
|
|
|
687
|
|
|
|
|
|
|
=item $count = $tree->count_le($key) |
688
|
|
|
|
|
|
|
|
689
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than or equal to $key. |
690
|
|
|
|
|
|
|
|
691
|
|
|
|
|
|
|
=item $count = $tree->count_gt($key) |
692
|
|
|
|
|
|
|
|
693
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than $key. |
694
|
|
|
|
|
|
|
|
695
|
|
|
|
|
|
|
=item $count = $tree->count_ge($key) |
696
|
|
|
|
|
|
|
|
697
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than or equal to $key. |
698
|
|
|
|
|
|
|
|
699
|
|
|
|
|
|
|
=item $dump_str = $tree->dump |
700
|
|
|
|
|
|
|
|
701
|
|
|
|
|
|
|
Get a string which represent the whole tree structure. For debug use. |
702
|
|
|
|
|
|
|
|
703
|
|
|
|
|
|
|
=item ($order_consistent, $size_consistent, $balanced) = $tree->check |
704
|
|
|
|
|
|
|
|
705
|
|
|
|
|
|
|
Check the tree property. For debug use. |
706
|
|
|
|
|
|
|
|
707
|
|
|
|
|
|
|
=item $ever_height = $tree->ever_height |
708
|
|
|
|
|
|
|
|
709
|
|
|
|
|
|
|
Get the maximum height the tree has ever been. For debug use |
710
|
|
|
|
|
|
|
|
711
|
|
|
|
|
|
|
=back |
712
|
|
|
|
|
|
|
|
713
|
|
|
|
|
|
|
=cut |
714
|
|
|
|
|
|
|
|
715
|
1
|
|
|
1
|
|
320
|
use Tree::SizeBalanced::int_num; |
|
1
|
|
|
|
|
1
|
|
|
1
|
|
|
|
|
120
|
|
716
|
|
|
|
|
|
|
|
717
|
|
|
|
|
|
|
sub sbtree_int_num() { |
718
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::int_num'; |
719
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::int_num::new; |
720
|
|
|
|
|
|
|
} |
721
|
|
|
|
|
|
|
|
722
|
|
|
|
|
|
|
sub sbtreein() { |
723
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::int_num'; |
724
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::int_num::new; |
725
|
|
|
|
|
|
|
} |
726
|
|
|
|
|
|
|
|
727
|
|
|
|
|
|
|
push @EXPORT_OK, qw(sbtree_int_num sbtreein); |
728
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'all'}}, qw(sbtree_int_num sbtreein); |
729
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'short'}}, qw(sbtreein); |
730
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'long'}}, qw(sbtree_int_num); |
731
|
|
|
|
|
|
|
|
732
|
|
|
|
|
|
|
|
733
|
|
|
|
|
|
|
=head3 Tree::SizeBalanced::int_any |
734
|
|
|
|
|
|
|
|
735
|
|
|
|
|
|
|
Tree map with key type signed integers (32bits or 64bits according to your perl version) and value type any scalars. |
736
|
|
|
|
|
|
|
|
737
|
|
|
|
|
|
|
=over 4 |
738
|
|
|
|
|
|
|
|
739
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced::int_any->new |
740
|
|
|
|
|
|
|
|
741
|
|
|
|
|
|
|
=item $tree = sbtree_int_any |
742
|
|
|
|
|
|
|
|
743
|
|
|
|
|
|
|
=item $tree = sbtreeia |
744
|
|
|
|
|
|
|
|
745
|
|
|
|
|
|
|
Creat a new empty tree. |
746
|
|
|
|
|
|
|
|
747
|
|
|
|
|
|
|
=item $tree->insert($key, $value) |
748
|
|
|
|
|
|
|
|
749
|
|
|
|
|
|
|
=item $tree->insert_after($key, $value) |
750
|
|
|
|
|
|
|
|
751
|
|
|
|
|
|
|
Insert an entry into the tree. |
752
|
|
|
|
|
|
|
If there are any entries with the same key size, |
753
|
|
|
|
|
|
|
insert the new one after them. |
754
|
|
|
|
|
|
|
|
755
|
|
|
|
|
|
|
=item $tree->insert_before($key, $value) |
756
|
|
|
|
|
|
|
|
757
|
|
|
|
|
|
|
Insert an entry into the tree. |
758
|
|
|
|
|
|
|
If there are any entries with the same key size, |
759
|
|
|
|
|
|
|
insert the new one before them. |
760
|
|
|
|
|
|
|
|
761
|
|
|
|
|
|
|
=item $tree->delete($key) |
762
|
|
|
|
|
|
|
|
763
|
|
|
|
|
|
|
=item $tree->delete_last($key) |
764
|
|
|
|
|
|
|
|
765
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
766
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
767
|
|
|
|
|
|
|
delete the last inserted one. |
768
|
|
|
|
|
|
|
|
769
|
|
|
|
|
|
|
=item $tree->delete_first($key) |
770
|
|
|
|
|
|
|
|
771
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
772
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
773
|
|
|
|
|
|
|
delete the first inserted one. |
774
|
|
|
|
|
|
|
|
775
|
|
|
|
|
|
|
=item $size = $tree->size |
776
|
|
|
|
|
|
|
|
777
|
|
|
|
|
|
|
Get the number of entries in the tree |
778
|
|
|
|
|
|
|
|
779
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find($key, $limit=1) |
780
|
|
|
|
|
|
|
|
781
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_first($key, $limit=1) |
782
|
|
|
|
|
|
|
|
783
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
784
|
|
|
|
|
|
|
from the first inserted one to the last inserted one. |
785
|
|
|
|
|
|
|
|
786
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
787
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
788
|
|
|
|
|
|
|
|
789
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_last($key, $limit=1) |
790
|
|
|
|
|
|
|
|
791
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
792
|
|
|
|
|
|
|
from the last inserted one to the first inserted one. |
793
|
|
|
|
|
|
|
|
794
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
795
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
796
|
|
|
|
|
|
|
|
797
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_lt($key, $limit=1) |
798
|
|
|
|
|
|
|
|
799
|
|
|
|
|
|
|
Get entries, whose keys are smaller than $key, from the largest entry. |
800
|
|
|
|
|
|
|
|
801
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
802
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
803
|
|
|
|
|
|
|
|
804
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_le($key, $limit=1) |
805
|
|
|
|
|
|
|
|
806
|
|
|
|
|
|
|
Get entries, whose keys are smaller than or equal to $key, from the largest entry. |
807
|
|
|
|
|
|
|
|
808
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
809
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
810
|
|
|
|
|
|
|
|
811
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt($key, $limit=1) |
812
|
|
|
|
|
|
|
|
813
|
|
|
|
|
|
|
Get entries, whose keys are greater than $key, from the smallest one. |
814
|
|
|
|
|
|
|
|
815
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
816
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
817
|
|
|
|
|
|
|
|
818
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge($key, $limit=1) |
819
|
|
|
|
|
|
|
|
820
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $key, from the smallest one. |
821
|
|
|
|
|
|
|
|
822
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
823
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
824
|
|
|
|
|
|
|
|
825
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_lt($lower_key, $upper_key) |
826
|
|
|
|
|
|
|
|
827
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than $upper_key, |
828
|
|
|
|
|
|
|
from the smallest one to the largest one. |
829
|
|
|
|
|
|
|
|
830
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_le($lower_key, $upper_key) |
831
|
|
|
|
|
|
|
|
832
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, |
833
|
|
|
|
|
|
|
from the smallest one to the largest one. |
834
|
|
|
|
|
|
|
|
835
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_lt($lower_key, $upper_key) |
836
|
|
|
|
|
|
|
|
837
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, |
838
|
|
|
|
|
|
|
from the smallest one to the largest one. |
839
|
|
|
|
|
|
|
|
840
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_le($lower_key, $upper_key) |
841
|
|
|
|
|
|
|
|
842
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, |
843
|
|
|
|
|
|
|
from the smallest one to the largest one. |
844
|
|
|
|
|
|
|
|
845
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_min($limit=1) |
846
|
|
|
|
|
|
|
|
847
|
|
|
|
|
|
|
Get entries from the one with smallest key. |
848
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
849
|
|
|
|
|
|
|
begin from the first inserted one. |
850
|
|
|
|
|
|
|
|
851
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
852
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
853
|
|
|
|
|
|
|
|
854
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_max($limit=1) |
855
|
|
|
|
|
|
|
|
856
|
|
|
|
|
|
|
Get entries from the one with largest key. |
857
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
858
|
|
|
|
|
|
|
begin from the last inserted one. |
859
|
|
|
|
|
|
|
|
860
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
861
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
862
|
|
|
|
|
|
|
|
863
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_l($offset, $limit=1) |
864
|
|
|
|
|
|
|
|
865
|
|
|
|
|
|
|
Get the first entry from one with the smallest key after skipping $offset entries. |
866
|
|
|
|
|
|
|
|
867
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
868
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
869
|
|
|
|
|
|
|
|
870
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_g($offset, $limit=1) |
871
|
|
|
|
|
|
|
|
872
|
|
|
|
|
|
|
Get the first entry from one with the largest key after skipping $offset entries. |
873
|
|
|
|
|
|
|
|
874
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
875
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
876
|
|
|
|
|
|
|
|
877
|
|
|
|
|
|
|
=item $count = $tree->count_lt($key) |
878
|
|
|
|
|
|
|
|
879
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than $key. |
880
|
|
|
|
|
|
|
|
881
|
|
|
|
|
|
|
=item $count = $tree->count_le($key) |
882
|
|
|
|
|
|
|
|
883
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than or equal to $key. |
884
|
|
|
|
|
|
|
|
885
|
|
|
|
|
|
|
=item $count = $tree->count_gt($key) |
886
|
|
|
|
|
|
|
|
887
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than $key. |
888
|
|
|
|
|
|
|
|
889
|
|
|
|
|
|
|
=item $count = $tree->count_ge($key) |
890
|
|
|
|
|
|
|
|
891
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than or equal to $key. |
892
|
|
|
|
|
|
|
|
893
|
|
|
|
|
|
|
=item $dump_str = $tree->dump |
894
|
|
|
|
|
|
|
|
895
|
|
|
|
|
|
|
Get a string which represent the whole tree structure. For debug use. |
896
|
|
|
|
|
|
|
|
897
|
|
|
|
|
|
|
=item ($order_consistent, $size_consistent, $balanced) = $tree->check |
898
|
|
|
|
|
|
|
|
899
|
|
|
|
|
|
|
Check the tree property. For debug use. |
900
|
|
|
|
|
|
|
|
901
|
|
|
|
|
|
|
=item $ever_height = $tree->ever_height |
902
|
|
|
|
|
|
|
|
903
|
|
|
|
|
|
|
Get the maximum height the tree has ever been. For debug use |
904
|
|
|
|
|
|
|
|
905
|
|
|
|
|
|
|
=back |
906
|
|
|
|
|
|
|
|
907
|
|
|
|
|
|
|
=cut |
908
|
|
|
|
|
|
|
|
909
|
1
|
|
|
1
|
|
300
|
use Tree::SizeBalanced::int_any; |
|
1
|
|
|
|
|
1
|
|
|
1
|
|
|
|
|
134
|
|
910
|
|
|
|
|
|
|
|
911
|
|
|
|
|
|
|
sub sbtree_int_any() { |
912
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::int_any'; |
913
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::int_any::new; |
914
|
|
|
|
|
|
|
} |
915
|
|
|
|
|
|
|
|
916
|
|
|
|
|
|
|
sub sbtreeia() { |
917
|
3
|
|
|
3
|
1
|
17333
|
unshift @_, 'Tree::SizeBalanced::int_any'; |
918
|
3
|
|
|
|
|
29
|
goto \&Tree::SizeBalanced::int_any::new; |
919
|
|
|
|
|
|
|
} |
920
|
|
|
|
|
|
|
|
921
|
|
|
|
|
|
|
push @EXPORT_OK, qw(sbtree_int_any sbtreeia); |
922
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'all'}}, qw(sbtree_int_any sbtreeia); |
923
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'short'}}, qw(sbtreeia); |
924
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'long'}}, qw(sbtree_int_any); |
925
|
|
|
|
|
|
|
|
926
|
|
|
|
|
|
|
|
927
|
|
|
|
|
|
|
=head3 Tree::SizeBalanced::num_void |
928
|
|
|
|
|
|
|
|
929
|
|
|
|
|
|
|
Tree set with key type numeric numbers (floating point numbers). |
930
|
|
|
|
|
|
|
|
931
|
|
|
|
|
|
|
=over 4 |
932
|
|
|
|
|
|
|
|
933
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced::num_void->new |
934
|
|
|
|
|
|
|
|
935
|
|
|
|
|
|
|
=item $tree = sbtree_num_void |
936
|
|
|
|
|
|
|
|
937
|
|
|
|
|
|
|
=item $tree = sbtreen |
938
|
|
|
|
|
|
|
|
939
|
|
|
|
|
|
|
Creat a new empty tree. |
940
|
|
|
|
|
|
|
|
941
|
|
|
|
|
|
|
=item $tree->insert($key) |
942
|
|
|
|
|
|
|
|
943
|
|
|
|
|
|
|
=item $tree->insert_after($key) |
944
|
|
|
|
|
|
|
|
945
|
|
|
|
|
|
|
Insert an entry into the tree. |
946
|
|
|
|
|
|
|
If there are any entries with the same key size, |
947
|
|
|
|
|
|
|
insert the new one after them. |
948
|
|
|
|
|
|
|
|
949
|
|
|
|
|
|
|
=item $tree->insert_before($key) |
950
|
|
|
|
|
|
|
|
951
|
|
|
|
|
|
|
Insert an entry into the tree. |
952
|
|
|
|
|
|
|
If there are any entries with the same key size, |
953
|
|
|
|
|
|
|
insert the new one before them. |
954
|
|
|
|
|
|
|
|
955
|
|
|
|
|
|
|
=item $tree->delete($key) |
956
|
|
|
|
|
|
|
|
957
|
|
|
|
|
|
|
=item $tree->delete_last($key) |
958
|
|
|
|
|
|
|
|
959
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
960
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
961
|
|
|
|
|
|
|
delete the last inserted one. |
962
|
|
|
|
|
|
|
|
963
|
|
|
|
|
|
|
=item $tree->delete_first($key) |
964
|
|
|
|
|
|
|
|
965
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
966
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
967
|
|
|
|
|
|
|
delete the first inserted one. |
968
|
|
|
|
|
|
|
|
969
|
|
|
|
|
|
|
=item $size = $tree->size |
970
|
|
|
|
|
|
|
|
971
|
|
|
|
|
|
|
Get the number of entries in the tree |
972
|
|
|
|
|
|
|
|
973
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find($key, $limit=1) |
974
|
|
|
|
|
|
|
|
975
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_first($key, $limit=1) |
976
|
|
|
|
|
|
|
|
977
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
978
|
|
|
|
|
|
|
from the first inserted one to the last inserted one. |
979
|
|
|
|
|
|
|
|
980
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
981
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
982
|
|
|
|
|
|
|
|
983
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_last($key, $limit=1) |
984
|
|
|
|
|
|
|
|
985
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
986
|
|
|
|
|
|
|
from the last inserted one to the first inserted one. |
987
|
|
|
|
|
|
|
|
988
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
989
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
990
|
|
|
|
|
|
|
|
991
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_lt($key, $limit=1) |
992
|
|
|
|
|
|
|
|
993
|
|
|
|
|
|
|
Get entries, whose keys are smaller than $key, from the largest entry. |
994
|
|
|
|
|
|
|
|
995
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
996
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
997
|
|
|
|
|
|
|
|
998
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_le($key, $limit=1) |
999
|
|
|
|
|
|
|
|
1000
|
|
|
|
|
|
|
Get entries, whose keys are smaller than or equal to $key, from the largest entry. |
1001
|
|
|
|
|
|
|
|
1002
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1003
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1004
|
|
|
|
|
|
|
|
1005
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_gt($key, $limit=1) |
1006
|
|
|
|
|
|
|
|
1007
|
|
|
|
|
|
|
Get entries, whose keys are greater than $key, from the smallest one. |
1008
|
|
|
|
|
|
|
|
1009
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1010
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1011
|
|
|
|
|
|
|
|
1012
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_ge($key, $limit=1) |
1013
|
|
|
|
|
|
|
|
1014
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $key, from the smallest one. |
1015
|
|
|
|
|
|
|
|
1016
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1017
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1018
|
|
|
|
|
|
|
|
1019
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_gt_lt($lower_key, $upper_key) |
1020
|
|
|
|
|
|
|
|
1021
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than $upper_key, |
1022
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1023
|
|
|
|
|
|
|
|
1024
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_gt_le($lower_key, $upper_key) |
1025
|
|
|
|
|
|
|
|
1026
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, |
1027
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1028
|
|
|
|
|
|
|
|
1029
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_ge_lt($lower_key, $upper_key) |
1030
|
|
|
|
|
|
|
|
1031
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, |
1032
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1033
|
|
|
|
|
|
|
|
1034
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_ge_le($lower_key, $upper_key) |
1035
|
|
|
|
|
|
|
|
1036
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, |
1037
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1038
|
|
|
|
|
|
|
|
1039
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_min($limit=1) |
1040
|
|
|
|
|
|
|
|
1041
|
|
|
|
|
|
|
Get entries from the one with smallest key. |
1042
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
1043
|
|
|
|
|
|
|
begin from the first inserted one. |
1044
|
|
|
|
|
|
|
|
1045
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1046
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1047
|
|
|
|
|
|
|
|
1048
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_max($limit=1) |
1049
|
|
|
|
|
|
|
|
1050
|
|
|
|
|
|
|
Get entries from the one with largest key. |
1051
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
1052
|
|
|
|
|
|
|
begin from the last inserted one. |
1053
|
|
|
|
|
|
|
|
1054
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1055
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1056
|
|
|
|
|
|
|
|
1057
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = &tree->skip_l($offset, $limit=1) |
1058
|
|
|
|
|
|
|
|
1059
|
|
|
|
|
|
|
Get the first entry from one with the smallest key after skipping $offset entries. |
1060
|
|
|
|
|
|
|
|
1061
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1062
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1063
|
|
|
|
|
|
|
|
1064
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = &tree->skip_g($offset, $limit=1) |
1065
|
|
|
|
|
|
|
|
1066
|
|
|
|
|
|
|
Get the first entry from one with the largest key after skipping $offset entries. |
1067
|
|
|
|
|
|
|
|
1068
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1069
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1070
|
|
|
|
|
|
|
|
1071
|
|
|
|
|
|
|
=item $count = $tree->count_lt($key) |
1072
|
|
|
|
|
|
|
|
1073
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than $key. |
1074
|
|
|
|
|
|
|
|
1075
|
|
|
|
|
|
|
=item $count = $tree->count_le($key) |
1076
|
|
|
|
|
|
|
|
1077
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than or equal to $key. |
1078
|
|
|
|
|
|
|
|
1079
|
|
|
|
|
|
|
=item $count = $tree->count_gt($key) |
1080
|
|
|
|
|
|
|
|
1081
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than $key. |
1082
|
|
|
|
|
|
|
|
1083
|
|
|
|
|
|
|
=item $count = $tree->count_ge($key) |
1084
|
|
|
|
|
|
|
|
1085
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than or equal to $key. |
1086
|
|
|
|
|
|
|
|
1087
|
|
|
|
|
|
|
=item $dump_str = $tree->dump |
1088
|
|
|
|
|
|
|
|
1089
|
|
|
|
|
|
|
Get a string which represent the whole tree structure. For debug use. |
1090
|
|
|
|
|
|
|
|
1091
|
|
|
|
|
|
|
=item ($order_consistent, $size_consistent, $balanced) = $tree->check |
1092
|
|
|
|
|
|
|
|
1093
|
|
|
|
|
|
|
Check the tree property. For debug use. |
1094
|
|
|
|
|
|
|
|
1095
|
|
|
|
|
|
|
=item $ever_height = $tree->ever_height |
1096
|
|
|
|
|
|
|
|
1097
|
|
|
|
|
|
|
Get the maximum height the tree has ever been. For debug use |
1098
|
|
|
|
|
|
|
|
1099
|
|
|
|
|
|
|
=back |
1100
|
|
|
|
|
|
|
|
1101
|
|
|
|
|
|
|
=cut |
1102
|
|
|
|
|
|
|
|
1103
|
1
|
|
|
1
|
|
317
|
use Tree::SizeBalanced::num_void; |
|
1
|
|
|
|
|
1
|
|
|
1
|
|
|
|
|
120
|
|
1104
|
|
|
|
|
|
|
|
1105
|
|
|
|
|
|
|
sub sbtree_num_void() { |
1106
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::num_void'; |
1107
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::num_void::new; |
1108
|
|
|
|
|
|
|
} |
1109
|
|
|
|
|
|
|
|
1110
|
|
|
|
|
|
|
sub sbtreen() { |
1111
|
1
|
|
|
1
|
1
|
99132
|
unshift @_, 'Tree::SizeBalanced::num_void'; |
1112
|
1
|
|
|
|
|
24
|
goto \&Tree::SizeBalanced::num_void::new; |
1113
|
|
|
|
|
|
|
} |
1114
|
|
|
|
|
|
|
|
1115
|
|
|
|
|
|
|
push @EXPORT_OK, qw(sbtree_num_void sbtreen); |
1116
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'all'}}, qw(sbtree_num_void sbtreen); |
1117
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'short'}}, qw(sbtreen); |
1118
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'long'}}, qw(sbtree_num_void); |
1119
|
|
|
|
|
|
|
|
1120
|
|
|
|
|
|
|
|
1121
|
|
|
|
|
|
|
=head3 Tree::SizeBalanced::num_int |
1122
|
|
|
|
|
|
|
|
1123
|
|
|
|
|
|
|
Tree map with key type numeric numbers (floating point numbers) and value type signed integers (32bits or 64bits according to your perl version). |
1124
|
|
|
|
|
|
|
|
1125
|
|
|
|
|
|
|
=over 4 |
1126
|
|
|
|
|
|
|
|
1127
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced::num_int->new |
1128
|
|
|
|
|
|
|
|
1129
|
|
|
|
|
|
|
=item $tree = sbtree_num_int |
1130
|
|
|
|
|
|
|
|
1131
|
|
|
|
|
|
|
=item $tree = sbtreeni |
1132
|
|
|
|
|
|
|
|
1133
|
|
|
|
|
|
|
Creat a new empty tree. |
1134
|
|
|
|
|
|
|
|
1135
|
|
|
|
|
|
|
=item $tree->insert($key, $value) |
1136
|
|
|
|
|
|
|
|
1137
|
|
|
|
|
|
|
=item $tree->insert_after($key, $value) |
1138
|
|
|
|
|
|
|
|
1139
|
|
|
|
|
|
|
Insert an entry into the tree. |
1140
|
|
|
|
|
|
|
If there are any entries with the same key size, |
1141
|
|
|
|
|
|
|
insert the new one after them. |
1142
|
|
|
|
|
|
|
|
1143
|
|
|
|
|
|
|
=item $tree->insert_before($key, $value) |
1144
|
|
|
|
|
|
|
|
1145
|
|
|
|
|
|
|
Insert an entry into the tree. |
1146
|
|
|
|
|
|
|
If there are any entries with the same key size, |
1147
|
|
|
|
|
|
|
insert the new one before them. |
1148
|
|
|
|
|
|
|
|
1149
|
|
|
|
|
|
|
=item $tree->delete($key) |
1150
|
|
|
|
|
|
|
|
1151
|
|
|
|
|
|
|
=item $tree->delete_last($key) |
1152
|
|
|
|
|
|
|
|
1153
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
1154
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
1155
|
|
|
|
|
|
|
delete the last inserted one. |
1156
|
|
|
|
|
|
|
|
1157
|
|
|
|
|
|
|
=item $tree->delete_first($key) |
1158
|
|
|
|
|
|
|
|
1159
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
1160
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
1161
|
|
|
|
|
|
|
delete the first inserted one. |
1162
|
|
|
|
|
|
|
|
1163
|
|
|
|
|
|
|
=item $size = $tree->size |
1164
|
|
|
|
|
|
|
|
1165
|
|
|
|
|
|
|
Get the number of entries in the tree |
1166
|
|
|
|
|
|
|
|
1167
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find($key, $limit=1) |
1168
|
|
|
|
|
|
|
|
1169
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_first($key, $limit=1) |
1170
|
|
|
|
|
|
|
|
1171
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
1172
|
|
|
|
|
|
|
from the first inserted one to the last inserted one. |
1173
|
|
|
|
|
|
|
|
1174
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1175
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1176
|
|
|
|
|
|
|
|
1177
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_last($key, $limit=1) |
1178
|
|
|
|
|
|
|
|
1179
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
1180
|
|
|
|
|
|
|
from the last inserted one to the first inserted one. |
1181
|
|
|
|
|
|
|
|
1182
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1183
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1184
|
|
|
|
|
|
|
|
1185
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_lt($key, $limit=1) |
1186
|
|
|
|
|
|
|
|
1187
|
|
|
|
|
|
|
Get entries, whose keys are smaller than $key, from the largest entry. |
1188
|
|
|
|
|
|
|
|
1189
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1190
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1191
|
|
|
|
|
|
|
|
1192
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_le($key, $limit=1) |
1193
|
|
|
|
|
|
|
|
1194
|
|
|
|
|
|
|
Get entries, whose keys are smaller than or equal to $key, from the largest entry. |
1195
|
|
|
|
|
|
|
|
1196
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1197
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1198
|
|
|
|
|
|
|
|
1199
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt($key, $limit=1) |
1200
|
|
|
|
|
|
|
|
1201
|
|
|
|
|
|
|
Get entries, whose keys are greater than $key, from the smallest one. |
1202
|
|
|
|
|
|
|
|
1203
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1204
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1205
|
|
|
|
|
|
|
|
1206
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge($key, $limit=1) |
1207
|
|
|
|
|
|
|
|
1208
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $key, from the smallest one. |
1209
|
|
|
|
|
|
|
|
1210
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1211
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1212
|
|
|
|
|
|
|
|
1213
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_lt($lower_key, $upper_key) |
1214
|
|
|
|
|
|
|
|
1215
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than $upper_key, |
1216
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1217
|
|
|
|
|
|
|
|
1218
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_le($lower_key, $upper_key) |
1219
|
|
|
|
|
|
|
|
1220
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, |
1221
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1222
|
|
|
|
|
|
|
|
1223
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_lt($lower_key, $upper_key) |
1224
|
|
|
|
|
|
|
|
1225
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, |
1226
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1227
|
|
|
|
|
|
|
|
1228
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_le($lower_key, $upper_key) |
1229
|
|
|
|
|
|
|
|
1230
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, |
1231
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1232
|
|
|
|
|
|
|
|
1233
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_min($limit=1) |
1234
|
|
|
|
|
|
|
|
1235
|
|
|
|
|
|
|
Get entries from the one with smallest key. |
1236
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
1237
|
|
|
|
|
|
|
begin from the first inserted one. |
1238
|
|
|
|
|
|
|
|
1239
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1240
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1241
|
|
|
|
|
|
|
|
1242
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_max($limit=1) |
1243
|
|
|
|
|
|
|
|
1244
|
|
|
|
|
|
|
Get entries from the one with largest key. |
1245
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
1246
|
|
|
|
|
|
|
begin from the last inserted one. |
1247
|
|
|
|
|
|
|
|
1248
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1249
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1250
|
|
|
|
|
|
|
|
1251
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_l($offset, $limit=1) |
1252
|
|
|
|
|
|
|
|
1253
|
|
|
|
|
|
|
Get the first entry from one with the smallest key after skipping $offset entries. |
1254
|
|
|
|
|
|
|
|
1255
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1256
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1257
|
|
|
|
|
|
|
|
1258
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_g($offset, $limit=1) |
1259
|
|
|
|
|
|
|
|
1260
|
|
|
|
|
|
|
Get the first entry from one with the largest key after skipping $offset entries. |
1261
|
|
|
|
|
|
|
|
1262
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1263
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1264
|
|
|
|
|
|
|
|
1265
|
|
|
|
|
|
|
=item $count = $tree->count_lt($key) |
1266
|
|
|
|
|
|
|
|
1267
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than $key. |
1268
|
|
|
|
|
|
|
|
1269
|
|
|
|
|
|
|
=item $count = $tree->count_le($key) |
1270
|
|
|
|
|
|
|
|
1271
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than or equal to $key. |
1272
|
|
|
|
|
|
|
|
1273
|
|
|
|
|
|
|
=item $count = $tree->count_gt($key) |
1274
|
|
|
|
|
|
|
|
1275
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than $key. |
1276
|
|
|
|
|
|
|
|
1277
|
|
|
|
|
|
|
=item $count = $tree->count_ge($key) |
1278
|
|
|
|
|
|
|
|
1279
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than or equal to $key. |
1280
|
|
|
|
|
|
|
|
1281
|
|
|
|
|
|
|
=item $dump_str = $tree->dump |
1282
|
|
|
|
|
|
|
|
1283
|
|
|
|
|
|
|
Get a string which represent the whole tree structure. For debug use. |
1284
|
|
|
|
|
|
|
|
1285
|
|
|
|
|
|
|
=item ($order_consistent, $size_consistent, $balanced) = $tree->check |
1286
|
|
|
|
|
|
|
|
1287
|
|
|
|
|
|
|
Check the tree property. For debug use. |
1288
|
|
|
|
|
|
|
|
1289
|
|
|
|
|
|
|
=item $ever_height = $tree->ever_height |
1290
|
|
|
|
|
|
|
|
1291
|
|
|
|
|
|
|
Get the maximum height the tree has ever been. For debug use |
1292
|
|
|
|
|
|
|
|
1293
|
|
|
|
|
|
|
=back |
1294
|
|
|
|
|
|
|
|
1295
|
|
|
|
|
|
|
=cut |
1296
|
|
|
|
|
|
|
|
1297
|
1
|
|
|
1
|
|
312
|
use Tree::SizeBalanced::num_int; |
|
1
|
|
|
|
|
1
|
|
|
1
|
|
|
|
|
114
|
|
1298
|
|
|
|
|
|
|
|
1299
|
|
|
|
|
|
|
sub sbtree_num_int() { |
1300
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::num_int'; |
1301
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::num_int::new; |
1302
|
|
|
|
|
|
|
} |
1303
|
|
|
|
|
|
|
|
1304
|
|
|
|
|
|
|
sub sbtreeni() { |
1305
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::num_int'; |
1306
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::num_int::new; |
1307
|
|
|
|
|
|
|
} |
1308
|
|
|
|
|
|
|
|
1309
|
|
|
|
|
|
|
push @EXPORT_OK, qw(sbtree_num_int sbtreeni); |
1310
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'all'}}, qw(sbtree_num_int sbtreeni); |
1311
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'short'}}, qw(sbtreeni); |
1312
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'long'}}, qw(sbtree_num_int); |
1313
|
|
|
|
|
|
|
|
1314
|
|
|
|
|
|
|
|
1315
|
|
|
|
|
|
|
=head3 Tree::SizeBalanced::num_num |
1316
|
|
|
|
|
|
|
|
1317
|
|
|
|
|
|
|
Tree map with key type numeric numbers (floating point numbers) and value type numeric numbers (floating point numbers). |
1318
|
|
|
|
|
|
|
|
1319
|
|
|
|
|
|
|
=over 4 |
1320
|
|
|
|
|
|
|
|
1321
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced::num_num->new |
1322
|
|
|
|
|
|
|
|
1323
|
|
|
|
|
|
|
=item $tree = sbtree_num_num |
1324
|
|
|
|
|
|
|
|
1325
|
|
|
|
|
|
|
=item $tree = sbtreenn |
1326
|
|
|
|
|
|
|
|
1327
|
|
|
|
|
|
|
Creat a new empty tree. |
1328
|
|
|
|
|
|
|
|
1329
|
|
|
|
|
|
|
=item $tree->insert($key, $value) |
1330
|
|
|
|
|
|
|
|
1331
|
|
|
|
|
|
|
=item $tree->insert_after($key, $value) |
1332
|
|
|
|
|
|
|
|
1333
|
|
|
|
|
|
|
Insert an entry into the tree. |
1334
|
|
|
|
|
|
|
If there are any entries with the same key size, |
1335
|
|
|
|
|
|
|
insert the new one after them. |
1336
|
|
|
|
|
|
|
|
1337
|
|
|
|
|
|
|
=item $tree->insert_before($key, $value) |
1338
|
|
|
|
|
|
|
|
1339
|
|
|
|
|
|
|
Insert an entry into the tree. |
1340
|
|
|
|
|
|
|
If there are any entries with the same key size, |
1341
|
|
|
|
|
|
|
insert the new one before them. |
1342
|
|
|
|
|
|
|
|
1343
|
|
|
|
|
|
|
=item $tree->delete($key) |
1344
|
|
|
|
|
|
|
|
1345
|
|
|
|
|
|
|
=item $tree->delete_last($key) |
1346
|
|
|
|
|
|
|
|
1347
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
1348
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
1349
|
|
|
|
|
|
|
delete the last inserted one. |
1350
|
|
|
|
|
|
|
|
1351
|
|
|
|
|
|
|
=item $tree->delete_first($key) |
1352
|
|
|
|
|
|
|
|
1353
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
1354
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
1355
|
|
|
|
|
|
|
delete the first inserted one. |
1356
|
|
|
|
|
|
|
|
1357
|
|
|
|
|
|
|
=item $size = $tree->size |
1358
|
|
|
|
|
|
|
|
1359
|
|
|
|
|
|
|
Get the number of entries in the tree |
1360
|
|
|
|
|
|
|
|
1361
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find($key, $limit=1) |
1362
|
|
|
|
|
|
|
|
1363
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_first($key, $limit=1) |
1364
|
|
|
|
|
|
|
|
1365
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
1366
|
|
|
|
|
|
|
from the first inserted one to the last inserted one. |
1367
|
|
|
|
|
|
|
|
1368
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1369
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1370
|
|
|
|
|
|
|
|
1371
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_last($key, $limit=1) |
1372
|
|
|
|
|
|
|
|
1373
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
1374
|
|
|
|
|
|
|
from the last inserted one to the first inserted one. |
1375
|
|
|
|
|
|
|
|
1376
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1377
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1378
|
|
|
|
|
|
|
|
1379
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_lt($key, $limit=1) |
1380
|
|
|
|
|
|
|
|
1381
|
|
|
|
|
|
|
Get entries, whose keys are smaller than $key, from the largest entry. |
1382
|
|
|
|
|
|
|
|
1383
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1384
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1385
|
|
|
|
|
|
|
|
1386
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_le($key, $limit=1) |
1387
|
|
|
|
|
|
|
|
1388
|
|
|
|
|
|
|
Get entries, whose keys are smaller than or equal to $key, from the largest entry. |
1389
|
|
|
|
|
|
|
|
1390
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1391
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1392
|
|
|
|
|
|
|
|
1393
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt($key, $limit=1) |
1394
|
|
|
|
|
|
|
|
1395
|
|
|
|
|
|
|
Get entries, whose keys are greater than $key, from the smallest one. |
1396
|
|
|
|
|
|
|
|
1397
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1398
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1399
|
|
|
|
|
|
|
|
1400
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge($key, $limit=1) |
1401
|
|
|
|
|
|
|
|
1402
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $key, from the smallest one. |
1403
|
|
|
|
|
|
|
|
1404
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1405
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1406
|
|
|
|
|
|
|
|
1407
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_lt($lower_key, $upper_key) |
1408
|
|
|
|
|
|
|
|
1409
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than $upper_key, |
1410
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1411
|
|
|
|
|
|
|
|
1412
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_le($lower_key, $upper_key) |
1413
|
|
|
|
|
|
|
|
1414
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, |
1415
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1416
|
|
|
|
|
|
|
|
1417
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_lt($lower_key, $upper_key) |
1418
|
|
|
|
|
|
|
|
1419
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, |
1420
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1421
|
|
|
|
|
|
|
|
1422
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_le($lower_key, $upper_key) |
1423
|
|
|
|
|
|
|
|
1424
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, |
1425
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1426
|
|
|
|
|
|
|
|
1427
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_min($limit=1) |
1428
|
|
|
|
|
|
|
|
1429
|
|
|
|
|
|
|
Get entries from the one with smallest key. |
1430
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
1431
|
|
|
|
|
|
|
begin from the first inserted one. |
1432
|
|
|
|
|
|
|
|
1433
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1434
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1435
|
|
|
|
|
|
|
|
1436
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_max($limit=1) |
1437
|
|
|
|
|
|
|
|
1438
|
|
|
|
|
|
|
Get entries from the one with largest key. |
1439
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
1440
|
|
|
|
|
|
|
begin from the last inserted one. |
1441
|
|
|
|
|
|
|
|
1442
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1443
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1444
|
|
|
|
|
|
|
|
1445
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_l($offset, $limit=1) |
1446
|
|
|
|
|
|
|
|
1447
|
|
|
|
|
|
|
Get the first entry from one with the smallest key after skipping $offset entries. |
1448
|
|
|
|
|
|
|
|
1449
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1450
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1451
|
|
|
|
|
|
|
|
1452
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_g($offset, $limit=1) |
1453
|
|
|
|
|
|
|
|
1454
|
|
|
|
|
|
|
Get the first entry from one with the largest key after skipping $offset entries. |
1455
|
|
|
|
|
|
|
|
1456
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1457
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1458
|
|
|
|
|
|
|
|
1459
|
|
|
|
|
|
|
=item $count = $tree->count_lt($key) |
1460
|
|
|
|
|
|
|
|
1461
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than $key. |
1462
|
|
|
|
|
|
|
|
1463
|
|
|
|
|
|
|
=item $count = $tree->count_le($key) |
1464
|
|
|
|
|
|
|
|
1465
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than or equal to $key. |
1466
|
|
|
|
|
|
|
|
1467
|
|
|
|
|
|
|
=item $count = $tree->count_gt($key) |
1468
|
|
|
|
|
|
|
|
1469
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than $key. |
1470
|
|
|
|
|
|
|
|
1471
|
|
|
|
|
|
|
=item $count = $tree->count_ge($key) |
1472
|
|
|
|
|
|
|
|
1473
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than or equal to $key. |
1474
|
|
|
|
|
|
|
|
1475
|
|
|
|
|
|
|
=item $dump_str = $tree->dump |
1476
|
|
|
|
|
|
|
|
1477
|
|
|
|
|
|
|
Get a string which represent the whole tree structure. For debug use. |
1478
|
|
|
|
|
|
|
|
1479
|
|
|
|
|
|
|
=item ($order_consistent, $size_consistent, $balanced) = $tree->check |
1480
|
|
|
|
|
|
|
|
1481
|
|
|
|
|
|
|
Check the tree property. For debug use. |
1482
|
|
|
|
|
|
|
|
1483
|
|
|
|
|
|
|
=item $ever_height = $tree->ever_height |
1484
|
|
|
|
|
|
|
|
1485
|
|
|
|
|
|
|
Get the maximum height the tree has ever been. For debug use |
1486
|
|
|
|
|
|
|
|
1487
|
|
|
|
|
|
|
=back |
1488
|
|
|
|
|
|
|
|
1489
|
|
|
|
|
|
|
=cut |
1490
|
|
|
|
|
|
|
|
1491
|
1
|
|
|
1
|
|
300
|
use Tree::SizeBalanced::num_num; |
|
1
|
|
|
|
|
1
|
|
|
1
|
|
|
|
|
124
|
|
1492
|
|
|
|
|
|
|
|
1493
|
|
|
|
|
|
|
sub sbtree_num_num() { |
1494
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::num_num'; |
1495
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::num_num::new; |
1496
|
|
|
|
|
|
|
} |
1497
|
|
|
|
|
|
|
|
1498
|
|
|
|
|
|
|
sub sbtreenn() { |
1499
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::num_num'; |
1500
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::num_num::new; |
1501
|
|
|
|
|
|
|
} |
1502
|
|
|
|
|
|
|
|
1503
|
|
|
|
|
|
|
push @EXPORT_OK, qw(sbtree_num_num sbtreenn); |
1504
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'all'}}, qw(sbtree_num_num sbtreenn); |
1505
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'short'}}, qw(sbtreenn); |
1506
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'long'}}, qw(sbtree_num_num); |
1507
|
|
|
|
|
|
|
|
1508
|
|
|
|
|
|
|
|
1509
|
|
|
|
|
|
|
=head3 Tree::SizeBalanced::num_any |
1510
|
|
|
|
|
|
|
|
1511
|
|
|
|
|
|
|
Tree map with key type numeric numbers (floating point numbers) and value type any scalars. |
1512
|
|
|
|
|
|
|
|
1513
|
|
|
|
|
|
|
=over 4 |
1514
|
|
|
|
|
|
|
|
1515
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced::num_any->new |
1516
|
|
|
|
|
|
|
|
1517
|
|
|
|
|
|
|
=item $tree = sbtree_num_any |
1518
|
|
|
|
|
|
|
|
1519
|
|
|
|
|
|
|
=item $tree = sbtreena |
1520
|
|
|
|
|
|
|
|
1521
|
|
|
|
|
|
|
Creat a new empty tree. |
1522
|
|
|
|
|
|
|
|
1523
|
|
|
|
|
|
|
=item $tree->insert($key, $value) |
1524
|
|
|
|
|
|
|
|
1525
|
|
|
|
|
|
|
=item $tree->insert_after($key, $value) |
1526
|
|
|
|
|
|
|
|
1527
|
|
|
|
|
|
|
Insert an entry into the tree. |
1528
|
|
|
|
|
|
|
If there are any entries with the same key size, |
1529
|
|
|
|
|
|
|
insert the new one after them. |
1530
|
|
|
|
|
|
|
|
1531
|
|
|
|
|
|
|
=item $tree->insert_before($key, $value) |
1532
|
|
|
|
|
|
|
|
1533
|
|
|
|
|
|
|
Insert an entry into the tree. |
1534
|
|
|
|
|
|
|
If there are any entries with the same key size, |
1535
|
|
|
|
|
|
|
insert the new one before them. |
1536
|
|
|
|
|
|
|
|
1537
|
|
|
|
|
|
|
=item $tree->delete($key) |
1538
|
|
|
|
|
|
|
|
1539
|
|
|
|
|
|
|
=item $tree->delete_last($key) |
1540
|
|
|
|
|
|
|
|
1541
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
1542
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
1543
|
|
|
|
|
|
|
delete the last inserted one. |
1544
|
|
|
|
|
|
|
|
1545
|
|
|
|
|
|
|
=item $tree->delete_first($key) |
1546
|
|
|
|
|
|
|
|
1547
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
1548
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
1549
|
|
|
|
|
|
|
delete the first inserted one. |
1550
|
|
|
|
|
|
|
|
1551
|
|
|
|
|
|
|
=item $size = $tree->size |
1552
|
|
|
|
|
|
|
|
1553
|
|
|
|
|
|
|
Get the number of entries in the tree |
1554
|
|
|
|
|
|
|
|
1555
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find($key, $limit=1) |
1556
|
|
|
|
|
|
|
|
1557
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_first($key, $limit=1) |
1558
|
|
|
|
|
|
|
|
1559
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
1560
|
|
|
|
|
|
|
from the first inserted one to the last inserted one. |
1561
|
|
|
|
|
|
|
|
1562
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1563
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1564
|
|
|
|
|
|
|
|
1565
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_last($key, $limit=1) |
1566
|
|
|
|
|
|
|
|
1567
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
1568
|
|
|
|
|
|
|
from the last inserted one to the first inserted one. |
1569
|
|
|
|
|
|
|
|
1570
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1571
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1572
|
|
|
|
|
|
|
|
1573
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_lt($key, $limit=1) |
1574
|
|
|
|
|
|
|
|
1575
|
|
|
|
|
|
|
Get entries, whose keys are smaller than $key, from the largest entry. |
1576
|
|
|
|
|
|
|
|
1577
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1578
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1579
|
|
|
|
|
|
|
|
1580
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_le($key, $limit=1) |
1581
|
|
|
|
|
|
|
|
1582
|
|
|
|
|
|
|
Get entries, whose keys are smaller than or equal to $key, from the largest entry. |
1583
|
|
|
|
|
|
|
|
1584
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1585
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1586
|
|
|
|
|
|
|
|
1587
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt($key, $limit=1) |
1588
|
|
|
|
|
|
|
|
1589
|
|
|
|
|
|
|
Get entries, whose keys are greater than $key, from the smallest one. |
1590
|
|
|
|
|
|
|
|
1591
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1592
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1593
|
|
|
|
|
|
|
|
1594
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge($key, $limit=1) |
1595
|
|
|
|
|
|
|
|
1596
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $key, from the smallest one. |
1597
|
|
|
|
|
|
|
|
1598
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1599
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1600
|
|
|
|
|
|
|
|
1601
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_lt($lower_key, $upper_key) |
1602
|
|
|
|
|
|
|
|
1603
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than $upper_key, |
1604
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1605
|
|
|
|
|
|
|
|
1606
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_le($lower_key, $upper_key) |
1607
|
|
|
|
|
|
|
|
1608
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, |
1609
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1610
|
|
|
|
|
|
|
|
1611
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_lt($lower_key, $upper_key) |
1612
|
|
|
|
|
|
|
|
1613
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, |
1614
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1615
|
|
|
|
|
|
|
|
1616
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_le($lower_key, $upper_key) |
1617
|
|
|
|
|
|
|
|
1618
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, |
1619
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1620
|
|
|
|
|
|
|
|
1621
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_min($limit=1) |
1622
|
|
|
|
|
|
|
|
1623
|
|
|
|
|
|
|
Get entries from the one with smallest key. |
1624
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
1625
|
|
|
|
|
|
|
begin from the first inserted one. |
1626
|
|
|
|
|
|
|
|
1627
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1628
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1629
|
|
|
|
|
|
|
|
1630
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_max($limit=1) |
1631
|
|
|
|
|
|
|
|
1632
|
|
|
|
|
|
|
Get entries from the one with largest key. |
1633
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
1634
|
|
|
|
|
|
|
begin from the last inserted one. |
1635
|
|
|
|
|
|
|
|
1636
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1637
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1638
|
|
|
|
|
|
|
|
1639
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_l($offset, $limit=1) |
1640
|
|
|
|
|
|
|
|
1641
|
|
|
|
|
|
|
Get the first entry from one with the smallest key after skipping $offset entries. |
1642
|
|
|
|
|
|
|
|
1643
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1644
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1645
|
|
|
|
|
|
|
|
1646
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_g($offset, $limit=1) |
1647
|
|
|
|
|
|
|
|
1648
|
|
|
|
|
|
|
Get the first entry from one with the largest key after skipping $offset entries. |
1649
|
|
|
|
|
|
|
|
1650
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1651
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1652
|
|
|
|
|
|
|
|
1653
|
|
|
|
|
|
|
=item $count = $tree->count_lt($key) |
1654
|
|
|
|
|
|
|
|
1655
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than $key. |
1656
|
|
|
|
|
|
|
|
1657
|
|
|
|
|
|
|
=item $count = $tree->count_le($key) |
1658
|
|
|
|
|
|
|
|
1659
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than or equal to $key. |
1660
|
|
|
|
|
|
|
|
1661
|
|
|
|
|
|
|
=item $count = $tree->count_gt($key) |
1662
|
|
|
|
|
|
|
|
1663
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than $key. |
1664
|
|
|
|
|
|
|
|
1665
|
|
|
|
|
|
|
=item $count = $tree->count_ge($key) |
1666
|
|
|
|
|
|
|
|
1667
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than or equal to $key. |
1668
|
|
|
|
|
|
|
|
1669
|
|
|
|
|
|
|
=item $dump_str = $tree->dump |
1670
|
|
|
|
|
|
|
|
1671
|
|
|
|
|
|
|
Get a string which represent the whole tree structure. For debug use. |
1672
|
|
|
|
|
|
|
|
1673
|
|
|
|
|
|
|
=item ($order_consistent, $size_consistent, $balanced) = $tree->check |
1674
|
|
|
|
|
|
|
|
1675
|
|
|
|
|
|
|
Check the tree property. For debug use. |
1676
|
|
|
|
|
|
|
|
1677
|
|
|
|
|
|
|
=item $ever_height = $tree->ever_height |
1678
|
|
|
|
|
|
|
|
1679
|
|
|
|
|
|
|
Get the maximum height the tree has ever been. For debug use |
1680
|
|
|
|
|
|
|
|
1681
|
|
|
|
|
|
|
=back |
1682
|
|
|
|
|
|
|
|
1683
|
|
|
|
|
|
|
=cut |
1684
|
|
|
|
|
|
|
|
1685
|
1
|
|
|
1
|
|
308
|
use Tree::SizeBalanced::num_any; |
|
1
|
|
|
|
|
1
|
|
|
1
|
|
|
|
|
135
|
|
1686
|
|
|
|
|
|
|
|
1687
|
|
|
|
|
|
|
sub sbtree_num_any() { |
1688
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::num_any'; |
1689
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::num_any::new; |
1690
|
|
|
|
|
|
|
} |
1691
|
|
|
|
|
|
|
|
1692
|
|
|
|
|
|
|
sub sbtreena() { |
1693
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::num_any'; |
1694
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::num_any::new; |
1695
|
|
|
|
|
|
|
} |
1696
|
|
|
|
|
|
|
|
1697
|
|
|
|
|
|
|
push @EXPORT_OK, qw(sbtree_num_any sbtreena); |
1698
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'all'}}, qw(sbtree_num_any sbtreena); |
1699
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'short'}}, qw(sbtreena); |
1700
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'long'}}, qw(sbtree_num_any); |
1701
|
|
|
|
|
|
|
|
1702
|
|
|
|
|
|
|
|
1703
|
|
|
|
|
|
|
=head3 Tree::SizeBalanced::str_void |
1704
|
|
|
|
|
|
|
|
1705
|
|
|
|
|
|
|
Tree set with key type strings. |
1706
|
|
|
|
|
|
|
|
1707
|
|
|
|
|
|
|
=over 4 |
1708
|
|
|
|
|
|
|
|
1709
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced::str_void->new |
1710
|
|
|
|
|
|
|
|
1711
|
|
|
|
|
|
|
=item $tree = sbtree_str_void |
1712
|
|
|
|
|
|
|
|
1713
|
|
|
|
|
|
|
=item $tree = sbtrees |
1714
|
|
|
|
|
|
|
|
1715
|
|
|
|
|
|
|
Creat a new empty tree. |
1716
|
|
|
|
|
|
|
|
1717
|
|
|
|
|
|
|
=item $tree->insert($key) |
1718
|
|
|
|
|
|
|
|
1719
|
|
|
|
|
|
|
=item $tree->insert_after($key) |
1720
|
|
|
|
|
|
|
|
1721
|
|
|
|
|
|
|
Insert an entry into the tree. |
1722
|
|
|
|
|
|
|
If there are any entries with the same key size, |
1723
|
|
|
|
|
|
|
insert the new one after them. |
1724
|
|
|
|
|
|
|
|
1725
|
|
|
|
|
|
|
=item $tree->insert_before($key) |
1726
|
|
|
|
|
|
|
|
1727
|
|
|
|
|
|
|
Insert an entry into the tree. |
1728
|
|
|
|
|
|
|
If there are any entries with the same key size, |
1729
|
|
|
|
|
|
|
insert the new one before them. |
1730
|
|
|
|
|
|
|
|
1731
|
|
|
|
|
|
|
=item $tree->delete($key) |
1732
|
|
|
|
|
|
|
|
1733
|
|
|
|
|
|
|
=item $tree->delete_last($key) |
1734
|
|
|
|
|
|
|
|
1735
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
1736
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
1737
|
|
|
|
|
|
|
delete the last inserted one. |
1738
|
|
|
|
|
|
|
|
1739
|
|
|
|
|
|
|
=item $tree->delete_first($key) |
1740
|
|
|
|
|
|
|
|
1741
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
1742
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
1743
|
|
|
|
|
|
|
delete the first inserted one. |
1744
|
|
|
|
|
|
|
|
1745
|
|
|
|
|
|
|
=item $size = $tree->size |
1746
|
|
|
|
|
|
|
|
1747
|
|
|
|
|
|
|
Get the number of entries in the tree |
1748
|
|
|
|
|
|
|
|
1749
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find($key, $limit=1) |
1750
|
|
|
|
|
|
|
|
1751
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_first($key, $limit=1) |
1752
|
|
|
|
|
|
|
|
1753
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
1754
|
|
|
|
|
|
|
from the first inserted one to the last inserted one. |
1755
|
|
|
|
|
|
|
|
1756
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1757
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1758
|
|
|
|
|
|
|
|
1759
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_last($key, $limit=1) |
1760
|
|
|
|
|
|
|
|
1761
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
1762
|
|
|
|
|
|
|
from the last inserted one to the first inserted one. |
1763
|
|
|
|
|
|
|
|
1764
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1765
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1766
|
|
|
|
|
|
|
|
1767
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_lt($key, $limit=1) |
1768
|
|
|
|
|
|
|
|
1769
|
|
|
|
|
|
|
Get entries, whose keys are smaller than $key, from the largest entry. |
1770
|
|
|
|
|
|
|
|
1771
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1772
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1773
|
|
|
|
|
|
|
|
1774
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_le($key, $limit=1) |
1775
|
|
|
|
|
|
|
|
1776
|
|
|
|
|
|
|
Get entries, whose keys are smaller than or equal to $key, from the largest entry. |
1777
|
|
|
|
|
|
|
|
1778
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1779
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1780
|
|
|
|
|
|
|
|
1781
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_gt($key, $limit=1) |
1782
|
|
|
|
|
|
|
|
1783
|
|
|
|
|
|
|
Get entries, whose keys are greater than $key, from the smallest one. |
1784
|
|
|
|
|
|
|
|
1785
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1786
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1787
|
|
|
|
|
|
|
|
1788
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_ge($key, $limit=1) |
1789
|
|
|
|
|
|
|
|
1790
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $key, from the smallest one. |
1791
|
|
|
|
|
|
|
|
1792
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1793
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1794
|
|
|
|
|
|
|
|
1795
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_gt_lt($lower_key, $upper_key) |
1796
|
|
|
|
|
|
|
|
1797
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than $upper_key, |
1798
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1799
|
|
|
|
|
|
|
|
1800
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_gt_le($lower_key, $upper_key) |
1801
|
|
|
|
|
|
|
|
1802
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, |
1803
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1804
|
|
|
|
|
|
|
|
1805
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_ge_lt($lower_key, $upper_key) |
1806
|
|
|
|
|
|
|
|
1807
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, |
1808
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1809
|
|
|
|
|
|
|
|
1810
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_ge_le($lower_key, $upper_key) |
1811
|
|
|
|
|
|
|
|
1812
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, |
1813
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1814
|
|
|
|
|
|
|
|
1815
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_min($limit=1) |
1816
|
|
|
|
|
|
|
|
1817
|
|
|
|
|
|
|
Get entries from the one with smallest key. |
1818
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
1819
|
|
|
|
|
|
|
begin from the first inserted one. |
1820
|
|
|
|
|
|
|
|
1821
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1822
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1823
|
|
|
|
|
|
|
|
1824
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_max($limit=1) |
1825
|
|
|
|
|
|
|
|
1826
|
|
|
|
|
|
|
Get entries from the one with largest key. |
1827
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
1828
|
|
|
|
|
|
|
begin from the last inserted one. |
1829
|
|
|
|
|
|
|
|
1830
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1831
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1832
|
|
|
|
|
|
|
|
1833
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = &tree->skip_l($offset, $limit=1) |
1834
|
|
|
|
|
|
|
|
1835
|
|
|
|
|
|
|
Get the first entry from one with the smallest key after skipping $offset entries. |
1836
|
|
|
|
|
|
|
|
1837
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1838
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1839
|
|
|
|
|
|
|
|
1840
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = &tree->skip_g($offset, $limit=1) |
1841
|
|
|
|
|
|
|
|
1842
|
|
|
|
|
|
|
Get the first entry from one with the largest key after skipping $offset entries. |
1843
|
|
|
|
|
|
|
|
1844
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1845
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1846
|
|
|
|
|
|
|
|
1847
|
|
|
|
|
|
|
=item $count = $tree->count_lt($key) |
1848
|
|
|
|
|
|
|
|
1849
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than $key. |
1850
|
|
|
|
|
|
|
|
1851
|
|
|
|
|
|
|
=item $count = $tree->count_le($key) |
1852
|
|
|
|
|
|
|
|
1853
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than or equal to $key. |
1854
|
|
|
|
|
|
|
|
1855
|
|
|
|
|
|
|
=item $count = $tree->count_gt($key) |
1856
|
|
|
|
|
|
|
|
1857
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than $key. |
1858
|
|
|
|
|
|
|
|
1859
|
|
|
|
|
|
|
=item $count = $tree->count_ge($key) |
1860
|
|
|
|
|
|
|
|
1861
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than or equal to $key. |
1862
|
|
|
|
|
|
|
|
1863
|
|
|
|
|
|
|
=item $dump_str = $tree->dump |
1864
|
|
|
|
|
|
|
|
1865
|
|
|
|
|
|
|
Get a string which represent the whole tree structure. For debug use. |
1866
|
|
|
|
|
|
|
|
1867
|
|
|
|
|
|
|
=item ($order_consistent, $size_consistent, $balanced) = $tree->check |
1868
|
|
|
|
|
|
|
|
1869
|
|
|
|
|
|
|
Check the tree property. For debug use. |
1870
|
|
|
|
|
|
|
|
1871
|
|
|
|
|
|
|
=item $ever_height = $tree->ever_height |
1872
|
|
|
|
|
|
|
|
1873
|
|
|
|
|
|
|
Get the maximum height the tree has ever been. For debug use |
1874
|
|
|
|
|
|
|
|
1875
|
|
|
|
|
|
|
=back |
1876
|
|
|
|
|
|
|
|
1877
|
|
|
|
|
|
|
=cut |
1878
|
|
|
|
|
|
|
|
1879
|
1
|
|
|
1
|
|
318
|
use Tree::SizeBalanced::str_void; |
|
1
|
|
|
|
|
1
|
|
|
1
|
|
|
|
|
156
|
|
1880
|
|
|
|
|
|
|
|
1881
|
|
|
|
|
|
|
sub sbtree_str_void() { |
1882
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::str_void'; |
1883
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::str_void::new; |
1884
|
|
|
|
|
|
|
} |
1885
|
|
|
|
|
|
|
|
1886
|
|
|
|
|
|
|
sub sbtrees() { |
1887
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::str_void'; |
1888
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::str_void::new; |
1889
|
|
|
|
|
|
|
} |
1890
|
|
|
|
|
|
|
|
1891
|
|
|
|
|
|
|
push @EXPORT_OK, qw(sbtree_str_void sbtrees); |
1892
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'all'}}, qw(sbtree_str_void sbtrees); |
1893
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'short'}}, qw(sbtrees); |
1894
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'long'}}, qw(sbtree_str_void); |
1895
|
|
|
|
|
|
|
|
1896
|
|
|
|
|
|
|
|
1897
|
|
|
|
|
|
|
=head3 Tree::SizeBalanced::str_int |
1898
|
|
|
|
|
|
|
|
1899
|
|
|
|
|
|
|
Tree map with key type strings and value type signed integers (32bits or 64bits according to your perl version). |
1900
|
|
|
|
|
|
|
|
1901
|
|
|
|
|
|
|
=over 4 |
1902
|
|
|
|
|
|
|
|
1903
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced::str_int->new |
1904
|
|
|
|
|
|
|
|
1905
|
|
|
|
|
|
|
=item $tree = sbtree_str_int |
1906
|
|
|
|
|
|
|
|
1907
|
|
|
|
|
|
|
=item $tree = sbtreesi |
1908
|
|
|
|
|
|
|
|
1909
|
|
|
|
|
|
|
Creat a new empty tree. |
1910
|
|
|
|
|
|
|
|
1911
|
|
|
|
|
|
|
=item $tree->insert($key, $value) |
1912
|
|
|
|
|
|
|
|
1913
|
|
|
|
|
|
|
=item $tree->insert_after($key, $value) |
1914
|
|
|
|
|
|
|
|
1915
|
|
|
|
|
|
|
Insert an entry into the tree. |
1916
|
|
|
|
|
|
|
If there are any entries with the same key size, |
1917
|
|
|
|
|
|
|
insert the new one after them. |
1918
|
|
|
|
|
|
|
|
1919
|
|
|
|
|
|
|
=item $tree->insert_before($key, $value) |
1920
|
|
|
|
|
|
|
|
1921
|
|
|
|
|
|
|
Insert an entry into the tree. |
1922
|
|
|
|
|
|
|
If there are any entries with the same key size, |
1923
|
|
|
|
|
|
|
insert the new one before them. |
1924
|
|
|
|
|
|
|
|
1925
|
|
|
|
|
|
|
=item $tree->delete($key) |
1926
|
|
|
|
|
|
|
|
1927
|
|
|
|
|
|
|
=item $tree->delete_last($key) |
1928
|
|
|
|
|
|
|
|
1929
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
1930
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
1931
|
|
|
|
|
|
|
delete the last inserted one. |
1932
|
|
|
|
|
|
|
|
1933
|
|
|
|
|
|
|
=item $tree->delete_first($key) |
1934
|
|
|
|
|
|
|
|
1935
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
1936
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
1937
|
|
|
|
|
|
|
delete the first inserted one. |
1938
|
|
|
|
|
|
|
|
1939
|
|
|
|
|
|
|
=item $size = $tree->size |
1940
|
|
|
|
|
|
|
|
1941
|
|
|
|
|
|
|
Get the number of entries in the tree |
1942
|
|
|
|
|
|
|
|
1943
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find($key, $limit=1) |
1944
|
|
|
|
|
|
|
|
1945
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_first($key, $limit=1) |
1946
|
|
|
|
|
|
|
|
1947
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
1948
|
|
|
|
|
|
|
from the first inserted one to the last inserted one. |
1949
|
|
|
|
|
|
|
|
1950
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1951
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1952
|
|
|
|
|
|
|
|
1953
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_last($key, $limit=1) |
1954
|
|
|
|
|
|
|
|
1955
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
1956
|
|
|
|
|
|
|
from the last inserted one to the first inserted one. |
1957
|
|
|
|
|
|
|
|
1958
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1959
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1960
|
|
|
|
|
|
|
|
1961
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_lt($key, $limit=1) |
1962
|
|
|
|
|
|
|
|
1963
|
|
|
|
|
|
|
Get entries, whose keys are smaller than $key, from the largest entry. |
1964
|
|
|
|
|
|
|
|
1965
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1966
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1967
|
|
|
|
|
|
|
|
1968
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_le($key, $limit=1) |
1969
|
|
|
|
|
|
|
|
1970
|
|
|
|
|
|
|
Get entries, whose keys are smaller than or equal to $key, from the largest entry. |
1971
|
|
|
|
|
|
|
|
1972
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1973
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1974
|
|
|
|
|
|
|
|
1975
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt($key, $limit=1) |
1976
|
|
|
|
|
|
|
|
1977
|
|
|
|
|
|
|
Get entries, whose keys are greater than $key, from the smallest one. |
1978
|
|
|
|
|
|
|
|
1979
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1980
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1981
|
|
|
|
|
|
|
|
1982
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge($key, $limit=1) |
1983
|
|
|
|
|
|
|
|
1984
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $key, from the smallest one. |
1985
|
|
|
|
|
|
|
|
1986
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
1987
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
1988
|
|
|
|
|
|
|
|
1989
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_lt($lower_key, $upper_key) |
1990
|
|
|
|
|
|
|
|
1991
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than $upper_key, |
1992
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1993
|
|
|
|
|
|
|
|
1994
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_le($lower_key, $upper_key) |
1995
|
|
|
|
|
|
|
|
1996
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, |
1997
|
|
|
|
|
|
|
from the smallest one to the largest one. |
1998
|
|
|
|
|
|
|
|
1999
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_lt($lower_key, $upper_key) |
2000
|
|
|
|
|
|
|
|
2001
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, |
2002
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2003
|
|
|
|
|
|
|
|
2004
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_le($lower_key, $upper_key) |
2005
|
|
|
|
|
|
|
|
2006
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, |
2007
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2008
|
|
|
|
|
|
|
|
2009
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_min($limit=1) |
2010
|
|
|
|
|
|
|
|
2011
|
|
|
|
|
|
|
Get entries from the one with smallest key. |
2012
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
2013
|
|
|
|
|
|
|
begin from the first inserted one. |
2014
|
|
|
|
|
|
|
|
2015
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2016
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2017
|
|
|
|
|
|
|
|
2018
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_max($limit=1) |
2019
|
|
|
|
|
|
|
|
2020
|
|
|
|
|
|
|
Get entries from the one with largest key. |
2021
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
2022
|
|
|
|
|
|
|
begin from the last inserted one. |
2023
|
|
|
|
|
|
|
|
2024
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2025
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2026
|
|
|
|
|
|
|
|
2027
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_l($offset, $limit=1) |
2028
|
|
|
|
|
|
|
|
2029
|
|
|
|
|
|
|
Get the first entry from one with the smallest key after skipping $offset entries. |
2030
|
|
|
|
|
|
|
|
2031
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2032
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2033
|
|
|
|
|
|
|
|
2034
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_g($offset, $limit=1) |
2035
|
|
|
|
|
|
|
|
2036
|
|
|
|
|
|
|
Get the first entry from one with the largest key after skipping $offset entries. |
2037
|
|
|
|
|
|
|
|
2038
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2039
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2040
|
|
|
|
|
|
|
|
2041
|
|
|
|
|
|
|
=item $count = $tree->count_lt($key) |
2042
|
|
|
|
|
|
|
|
2043
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than $key. |
2044
|
|
|
|
|
|
|
|
2045
|
|
|
|
|
|
|
=item $count = $tree->count_le($key) |
2046
|
|
|
|
|
|
|
|
2047
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than or equal to $key. |
2048
|
|
|
|
|
|
|
|
2049
|
|
|
|
|
|
|
=item $count = $tree->count_gt($key) |
2050
|
|
|
|
|
|
|
|
2051
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than $key. |
2052
|
|
|
|
|
|
|
|
2053
|
|
|
|
|
|
|
=item $count = $tree->count_ge($key) |
2054
|
|
|
|
|
|
|
|
2055
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than or equal to $key. |
2056
|
|
|
|
|
|
|
|
2057
|
|
|
|
|
|
|
=item $dump_str = $tree->dump |
2058
|
|
|
|
|
|
|
|
2059
|
|
|
|
|
|
|
Get a string which represent the whole tree structure. For debug use. |
2060
|
|
|
|
|
|
|
|
2061
|
|
|
|
|
|
|
=item ($order_consistent, $size_consistent, $balanced) = $tree->check |
2062
|
|
|
|
|
|
|
|
2063
|
|
|
|
|
|
|
Check the tree property. For debug use. |
2064
|
|
|
|
|
|
|
|
2065
|
|
|
|
|
|
|
=item $ever_height = $tree->ever_height |
2066
|
|
|
|
|
|
|
|
2067
|
|
|
|
|
|
|
Get the maximum height the tree has ever been. For debug use |
2068
|
|
|
|
|
|
|
|
2069
|
|
|
|
|
|
|
=back |
2070
|
|
|
|
|
|
|
|
2071
|
|
|
|
|
|
|
=cut |
2072
|
|
|
|
|
|
|
|
2073
|
1
|
|
|
1
|
|
304
|
use Tree::SizeBalanced::str_int; |
|
1
|
|
|
|
|
1
|
|
|
1
|
|
|
|
|
117
|
|
2074
|
|
|
|
|
|
|
|
2075
|
|
|
|
|
|
|
sub sbtree_str_int() { |
2076
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::str_int'; |
2077
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::str_int::new; |
2078
|
|
|
|
|
|
|
} |
2079
|
|
|
|
|
|
|
|
2080
|
|
|
|
|
|
|
sub sbtreesi() { |
2081
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::str_int'; |
2082
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::str_int::new; |
2083
|
|
|
|
|
|
|
} |
2084
|
|
|
|
|
|
|
|
2085
|
|
|
|
|
|
|
push @EXPORT_OK, qw(sbtree_str_int sbtreesi); |
2086
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'all'}}, qw(sbtree_str_int sbtreesi); |
2087
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'short'}}, qw(sbtreesi); |
2088
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'long'}}, qw(sbtree_str_int); |
2089
|
|
|
|
|
|
|
|
2090
|
|
|
|
|
|
|
|
2091
|
|
|
|
|
|
|
=head3 Tree::SizeBalanced::str_num |
2092
|
|
|
|
|
|
|
|
2093
|
|
|
|
|
|
|
Tree map with key type strings and value type numeric numbers (floating point numbers). |
2094
|
|
|
|
|
|
|
|
2095
|
|
|
|
|
|
|
=over 4 |
2096
|
|
|
|
|
|
|
|
2097
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced::str_num->new |
2098
|
|
|
|
|
|
|
|
2099
|
|
|
|
|
|
|
=item $tree = sbtree_str_num |
2100
|
|
|
|
|
|
|
|
2101
|
|
|
|
|
|
|
=item $tree = sbtreesn |
2102
|
|
|
|
|
|
|
|
2103
|
|
|
|
|
|
|
Creat a new empty tree. |
2104
|
|
|
|
|
|
|
|
2105
|
|
|
|
|
|
|
=item $tree->insert($key, $value) |
2106
|
|
|
|
|
|
|
|
2107
|
|
|
|
|
|
|
=item $tree->insert_after($key, $value) |
2108
|
|
|
|
|
|
|
|
2109
|
|
|
|
|
|
|
Insert an entry into the tree. |
2110
|
|
|
|
|
|
|
If there are any entries with the same key size, |
2111
|
|
|
|
|
|
|
insert the new one after them. |
2112
|
|
|
|
|
|
|
|
2113
|
|
|
|
|
|
|
=item $tree->insert_before($key, $value) |
2114
|
|
|
|
|
|
|
|
2115
|
|
|
|
|
|
|
Insert an entry into the tree. |
2116
|
|
|
|
|
|
|
If there are any entries with the same key size, |
2117
|
|
|
|
|
|
|
insert the new one before them. |
2118
|
|
|
|
|
|
|
|
2119
|
|
|
|
|
|
|
=item $tree->delete($key) |
2120
|
|
|
|
|
|
|
|
2121
|
|
|
|
|
|
|
=item $tree->delete_last($key) |
2122
|
|
|
|
|
|
|
|
2123
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
2124
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
2125
|
|
|
|
|
|
|
delete the last inserted one. |
2126
|
|
|
|
|
|
|
|
2127
|
|
|
|
|
|
|
=item $tree->delete_first($key) |
2128
|
|
|
|
|
|
|
|
2129
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
2130
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
2131
|
|
|
|
|
|
|
delete the first inserted one. |
2132
|
|
|
|
|
|
|
|
2133
|
|
|
|
|
|
|
=item $size = $tree->size |
2134
|
|
|
|
|
|
|
|
2135
|
|
|
|
|
|
|
Get the number of entries in the tree |
2136
|
|
|
|
|
|
|
|
2137
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find($key, $limit=1) |
2138
|
|
|
|
|
|
|
|
2139
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_first($key, $limit=1) |
2140
|
|
|
|
|
|
|
|
2141
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
2142
|
|
|
|
|
|
|
from the first inserted one to the last inserted one. |
2143
|
|
|
|
|
|
|
|
2144
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2145
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2146
|
|
|
|
|
|
|
|
2147
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_last($key, $limit=1) |
2148
|
|
|
|
|
|
|
|
2149
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
2150
|
|
|
|
|
|
|
from the last inserted one to the first inserted one. |
2151
|
|
|
|
|
|
|
|
2152
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2153
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2154
|
|
|
|
|
|
|
|
2155
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_lt($key, $limit=1) |
2156
|
|
|
|
|
|
|
|
2157
|
|
|
|
|
|
|
Get entries, whose keys are smaller than $key, from the largest entry. |
2158
|
|
|
|
|
|
|
|
2159
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2160
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2161
|
|
|
|
|
|
|
|
2162
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_le($key, $limit=1) |
2163
|
|
|
|
|
|
|
|
2164
|
|
|
|
|
|
|
Get entries, whose keys are smaller than or equal to $key, from the largest entry. |
2165
|
|
|
|
|
|
|
|
2166
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2167
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2168
|
|
|
|
|
|
|
|
2169
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt($key, $limit=1) |
2170
|
|
|
|
|
|
|
|
2171
|
|
|
|
|
|
|
Get entries, whose keys are greater than $key, from the smallest one. |
2172
|
|
|
|
|
|
|
|
2173
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2174
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2175
|
|
|
|
|
|
|
|
2176
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge($key, $limit=1) |
2177
|
|
|
|
|
|
|
|
2178
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $key, from the smallest one. |
2179
|
|
|
|
|
|
|
|
2180
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2181
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2182
|
|
|
|
|
|
|
|
2183
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_lt($lower_key, $upper_key) |
2184
|
|
|
|
|
|
|
|
2185
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than $upper_key, |
2186
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2187
|
|
|
|
|
|
|
|
2188
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_le($lower_key, $upper_key) |
2189
|
|
|
|
|
|
|
|
2190
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, |
2191
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2192
|
|
|
|
|
|
|
|
2193
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_lt($lower_key, $upper_key) |
2194
|
|
|
|
|
|
|
|
2195
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, |
2196
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2197
|
|
|
|
|
|
|
|
2198
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_le($lower_key, $upper_key) |
2199
|
|
|
|
|
|
|
|
2200
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, |
2201
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2202
|
|
|
|
|
|
|
|
2203
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_min($limit=1) |
2204
|
|
|
|
|
|
|
|
2205
|
|
|
|
|
|
|
Get entries from the one with smallest key. |
2206
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
2207
|
|
|
|
|
|
|
begin from the first inserted one. |
2208
|
|
|
|
|
|
|
|
2209
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2210
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2211
|
|
|
|
|
|
|
|
2212
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_max($limit=1) |
2213
|
|
|
|
|
|
|
|
2214
|
|
|
|
|
|
|
Get entries from the one with largest key. |
2215
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
2216
|
|
|
|
|
|
|
begin from the last inserted one. |
2217
|
|
|
|
|
|
|
|
2218
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2219
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2220
|
|
|
|
|
|
|
|
2221
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_l($offset, $limit=1) |
2222
|
|
|
|
|
|
|
|
2223
|
|
|
|
|
|
|
Get the first entry from one with the smallest key after skipping $offset entries. |
2224
|
|
|
|
|
|
|
|
2225
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2226
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2227
|
|
|
|
|
|
|
|
2228
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_g($offset, $limit=1) |
2229
|
|
|
|
|
|
|
|
2230
|
|
|
|
|
|
|
Get the first entry from one with the largest key after skipping $offset entries. |
2231
|
|
|
|
|
|
|
|
2232
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2233
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2234
|
|
|
|
|
|
|
|
2235
|
|
|
|
|
|
|
=item $count = $tree->count_lt($key) |
2236
|
|
|
|
|
|
|
|
2237
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than $key. |
2238
|
|
|
|
|
|
|
|
2239
|
|
|
|
|
|
|
=item $count = $tree->count_le($key) |
2240
|
|
|
|
|
|
|
|
2241
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than or equal to $key. |
2242
|
|
|
|
|
|
|
|
2243
|
|
|
|
|
|
|
=item $count = $tree->count_gt($key) |
2244
|
|
|
|
|
|
|
|
2245
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than $key. |
2246
|
|
|
|
|
|
|
|
2247
|
|
|
|
|
|
|
=item $count = $tree->count_ge($key) |
2248
|
|
|
|
|
|
|
|
2249
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than or equal to $key. |
2250
|
|
|
|
|
|
|
|
2251
|
|
|
|
|
|
|
=item $dump_str = $tree->dump |
2252
|
|
|
|
|
|
|
|
2253
|
|
|
|
|
|
|
Get a string which represent the whole tree structure. For debug use. |
2254
|
|
|
|
|
|
|
|
2255
|
|
|
|
|
|
|
=item ($order_consistent, $size_consistent, $balanced) = $tree->check |
2256
|
|
|
|
|
|
|
|
2257
|
|
|
|
|
|
|
Check the tree property. For debug use. |
2258
|
|
|
|
|
|
|
|
2259
|
|
|
|
|
|
|
=item $ever_height = $tree->ever_height |
2260
|
|
|
|
|
|
|
|
2261
|
|
|
|
|
|
|
Get the maximum height the tree has ever been. For debug use |
2262
|
|
|
|
|
|
|
|
2263
|
|
|
|
|
|
|
=back |
2264
|
|
|
|
|
|
|
|
2265
|
|
|
|
|
|
|
=cut |
2266
|
|
|
|
|
|
|
|
2267
|
1
|
|
|
1
|
|
308
|
use Tree::SizeBalanced::str_num; |
|
1
|
|
|
|
|
2
|
|
|
1
|
|
|
|
|
120
|
|
2268
|
|
|
|
|
|
|
|
2269
|
|
|
|
|
|
|
sub sbtree_str_num() { |
2270
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::str_num'; |
2271
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::str_num::new; |
2272
|
|
|
|
|
|
|
} |
2273
|
|
|
|
|
|
|
|
2274
|
|
|
|
|
|
|
sub sbtreesn() { |
2275
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::str_num'; |
2276
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::str_num::new; |
2277
|
|
|
|
|
|
|
} |
2278
|
|
|
|
|
|
|
|
2279
|
|
|
|
|
|
|
push @EXPORT_OK, qw(sbtree_str_num sbtreesn); |
2280
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'all'}}, qw(sbtree_str_num sbtreesn); |
2281
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'short'}}, qw(sbtreesn); |
2282
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'long'}}, qw(sbtree_str_num); |
2283
|
|
|
|
|
|
|
|
2284
|
|
|
|
|
|
|
|
2285
|
|
|
|
|
|
|
=head3 Tree::SizeBalanced::str_any |
2286
|
|
|
|
|
|
|
|
2287
|
|
|
|
|
|
|
Tree map with key type strings and value type any scalars. |
2288
|
|
|
|
|
|
|
|
2289
|
|
|
|
|
|
|
=over 4 |
2290
|
|
|
|
|
|
|
|
2291
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced::str_any->new |
2292
|
|
|
|
|
|
|
|
2293
|
|
|
|
|
|
|
=item $tree = sbtree_str_any |
2294
|
|
|
|
|
|
|
|
2295
|
|
|
|
|
|
|
=item $tree = sbtreesa |
2296
|
|
|
|
|
|
|
|
2297
|
|
|
|
|
|
|
Creat a new empty tree. |
2298
|
|
|
|
|
|
|
|
2299
|
|
|
|
|
|
|
=item $tree->insert($key, $value) |
2300
|
|
|
|
|
|
|
|
2301
|
|
|
|
|
|
|
=item $tree->insert_after($key, $value) |
2302
|
|
|
|
|
|
|
|
2303
|
|
|
|
|
|
|
Insert an entry into the tree. |
2304
|
|
|
|
|
|
|
If there are any entries with the same key size, |
2305
|
|
|
|
|
|
|
insert the new one after them. |
2306
|
|
|
|
|
|
|
|
2307
|
|
|
|
|
|
|
=item $tree->insert_before($key, $value) |
2308
|
|
|
|
|
|
|
|
2309
|
|
|
|
|
|
|
Insert an entry into the tree. |
2310
|
|
|
|
|
|
|
If there are any entries with the same key size, |
2311
|
|
|
|
|
|
|
insert the new one before them. |
2312
|
|
|
|
|
|
|
|
2313
|
|
|
|
|
|
|
=item $tree->delete($key) |
2314
|
|
|
|
|
|
|
|
2315
|
|
|
|
|
|
|
=item $tree->delete_last($key) |
2316
|
|
|
|
|
|
|
|
2317
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
2318
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
2319
|
|
|
|
|
|
|
delete the last inserted one. |
2320
|
|
|
|
|
|
|
|
2321
|
|
|
|
|
|
|
=item $tree->delete_first($key) |
2322
|
|
|
|
|
|
|
|
2323
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
2324
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
2325
|
|
|
|
|
|
|
delete the first inserted one. |
2326
|
|
|
|
|
|
|
|
2327
|
|
|
|
|
|
|
=item $size = $tree->size |
2328
|
|
|
|
|
|
|
|
2329
|
|
|
|
|
|
|
Get the number of entries in the tree |
2330
|
|
|
|
|
|
|
|
2331
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find($key, $limit=1) |
2332
|
|
|
|
|
|
|
|
2333
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_first($key, $limit=1) |
2334
|
|
|
|
|
|
|
|
2335
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
2336
|
|
|
|
|
|
|
from the first inserted one to the last inserted one. |
2337
|
|
|
|
|
|
|
|
2338
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2339
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2340
|
|
|
|
|
|
|
|
2341
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_last($key, $limit=1) |
2342
|
|
|
|
|
|
|
|
2343
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
2344
|
|
|
|
|
|
|
from the last inserted one to the first inserted one. |
2345
|
|
|
|
|
|
|
|
2346
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2347
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2348
|
|
|
|
|
|
|
|
2349
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_lt($key, $limit=1) |
2350
|
|
|
|
|
|
|
|
2351
|
|
|
|
|
|
|
Get entries, whose keys are smaller than $key, from the largest entry. |
2352
|
|
|
|
|
|
|
|
2353
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2354
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2355
|
|
|
|
|
|
|
|
2356
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_le($key, $limit=1) |
2357
|
|
|
|
|
|
|
|
2358
|
|
|
|
|
|
|
Get entries, whose keys are smaller than or equal to $key, from the largest entry. |
2359
|
|
|
|
|
|
|
|
2360
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2361
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2362
|
|
|
|
|
|
|
|
2363
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt($key, $limit=1) |
2364
|
|
|
|
|
|
|
|
2365
|
|
|
|
|
|
|
Get entries, whose keys are greater than $key, from the smallest one. |
2366
|
|
|
|
|
|
|
|
2367
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2368
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2369
|
|
|
|
|
|
|
|
2370
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge($key, $limit=1) |
2371
|
|
|
|
|
|
|
|
2372
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $key, from the smallest one. |
2373
|
|
|
|
|
|
|
|
2374
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2375
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2376
|
|
|
|
|
|
|
|
2377
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_lt($lower_key, $upper_key) |
2378
|
|
|
|
|
|
|
|
2379
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than $upper_key, |
2380
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2381
|
|
|
|
|
|
|
|
2382
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_le($lower_key, $upper_key) |
2383
|
|
|
|
|
|
|
|
2384
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, |
2385
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2386
|
|
|
|
|
|
|
|
2387
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_lt($lower_key, $upper_key) |
2388
|
|
|
|
|
|
|
|
2389
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, |
2390
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2391
|
|
|
|
|
|
|
|
2392
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_le($lower_key, $upper_key) |
2393
|
|
|
|
|
|
|
|
2394
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, |
2395
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2396
|
|
|
|
|
|
|
|
2397
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_min($limit=1) |
2398
|
|
|
|
|
|
|
|
2399
|
|
|
|
|
|
|
Get entries from the one with smallest key. |
2400
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
2401
|
|
|
|
|
|
|
begin from the first inserted one. |
2402
|
|
|
|
|
|
|
|
2403
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2404
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2405
|
|
|
|
|
|
|
|
2406
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_max($limit=1) |
2407
|
|
|
|
|
|
|
|
2408
|
|
|
|
|
|
|
Get entries from the one with largest key. |
2409
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
2410
|
|
|
|
|
|
|
begin from the last inserted one. |
2411
|
|
|
|
|
|
|
|
2412
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2413
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2414
|
|
|
|
|
|
|
|
2415
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_l($offset, $limit=1) |
2416
|
|
|
|
|
|
|
|
2417
|
|
|
|
|
|
|
Get the first entry from one with the smallest key after skipping $offset entries. |
2418
|
|
|
|
|
|
|
|
2419
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2420
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2421
|
|
|
|
|
|
|
|
2422
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_g($offset, $limit=1) |
2423
|
|
|
|
|
|
|
|
2424
|
|
|
|
|
|
|
Get the first entry from one with the largest key after skipping $offset entries. |
2425
|
|
|
|
|
|
|
|
2426
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2427
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2428
|
|
|
|
|
|
|
|
2429
|
|
|
|
|
|
|
=item $count = $tree->count_lt($key) |
2430
|
|
|
|
|
|
|
|
2431
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than $key. |
2432
|
|
|
|
|
|
|
|
2433
|
|
|
|
|
|
|
=item $count = $tree->count_le($key) |
2434
|
|
|
|
|
|
|
|
2435
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than or equal to $key. |
2436
|
|
|
|
|
|
|
|
2437
|
|
|
|
|
|
|
=item $count = $tree->count_gt($key) |
2438
|
|
|
|
|
|
|
|
2439
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than $key. |
2440
|
|
|
|
|
|
|
|
2441
|
|
|
|
|
|
|
=item $count = $tree->count_ge($key) |
2442
|
|
|
|
|
|
|
|
2443
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than or equal to $key. |
2444
|
|
|
|
|
|
|
|
2445
|
|
|
|
|
|
|
=item $dump_str = $tree->dump |
2446
|
|
|
|
|
|
|
|
2447
|
|
|
|
|
|
|
Get a string which represent the whole tree structure. For debug use. |
2448
|
|
|
|
|
|
|
|
2449
|
|
|
|
|
|
|
=item ($order_consistent, $size_consistent, $balanced) = $tree->check |
2450
|
|
|
|
|
|
|
|
2451
|
|
|
|
|
|
|
Check the tree property. For debug use. |
2452
|
|
|
|
|
|
|
|
2453
|
|
|
|
|
|
|
=item $ever_height = $tree->ever_height |
2454
|
|
|
|
|
|
|
|
2455
|
|
|
|
|
|
|
Get the maximum height the tree has ever been. For debug use |
2456
|
|
|
|
|
|
|
|
2457
|
|
|
|
|
|
|
=back |
2458
|
|
|
|
|
|
|
|
2459
|
|
|
|
|
|
|
=cut |
2460
|
|
|
|
|
|
|
|
2461
|
1
|
|
|
1
|
|
312
|
use Tree::SizeBalanced::str_any; |
|
1
|
|
|
|
|
2
|
|
|
1
|
|
|
|
|
119
|
|
2462
|
|
|
|
|
|
|
|
2463
|
|
|
|
|
|
|
sub sbtree_str_any() { |
2464
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::str_any'; |
2465
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::str_any::new; |
2466
|
|
|
|
|
|
|
} |
2467
|
|
|
|
|
|
|
|
2468
|
|
|
|
|
|
|
sub sbtreesa() { |
2469
|
1
|
|
|
1
|
1
|
4770
|
unshift @_, 'Tree::SizeBalanced::str_any'; |
2470
|
1
|
|
|
|
|
32
|
goto \&Tree::SizeBalanced::str_any::new; |
2471
|
|
|
|
|
|
|
} |
2472
|
|
|
|
|
|
|
|
2473
|
|
|
|
|
|
|
push @EXPORT_OK, qw(sbtree_str_any sbtreesa); |
2474
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'all'}}, qw(sbtree_str_any sbtreesa); |
2475
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'short'}}, qw(sbtreesa); |
2476
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'long'}}, qw(sbtree_str_any); |
2477
|
|
|
|
|
|
|
|
2478
|
|
|
|
|
|
|
|
2479
|
|
|
|
|
|
|
=head3 Tree::SizeBalanced::any_void |
2480
|
|
|
|
|
|
|
|
2481
|
|
|
|
|
|
|
Tree set with key type any scalars. |
2482
|
|
|
|
|
|
|
|
2483
|
|
|
|
|
|
|
=over 4 |
2484
|
|
|
|
|
|
|
|
2485
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced::any_void->new sub { $a cmp $b } |
2486
|
|
|
|
|
|
|
|
2487
|
|
|
|
|
|
|
=item $tree = sbtree_any_void { $a cmp $b } |
2488
|
|
|
|
|
|
|
|
2489
|
|
|
|
|
|
|
=item $tree = sbtreea { $a cmp $b } |
2490
|
|
|
|
|
|
|
|
2491
|
|
|
|
|
|
|
Creat a new empty tree. |
2492
|
|
|
|
|
|
|
|
2493
|
|
|
|
|
|
|
=item $tree->insert($key) |
2494
|
|
|
|
|
|
|
|
2495
|
|
|
|
|
|
|
=item $tree->insert_after($key) |
2496
|
|
|
|
|
|
|
|
2497
|
|
|
|
|
|
|
Insert an entry into the tree. |
2498
|
|
|
|
|
|
|
If there are any entries with the same key size, |
2499
|
|
|
|
|
|
|
insert the new one after them. |
2500
|
|
|
|
|
|
|
|
2501
|
|
|
|
|
|
|
=item $tree->insert_before($key) |
2502
|
|
|
|
|
|
|
|
2503
|
|
|
|
|
|
|
Insert an entry into the tree. |
2504
|
|
|
|
|
|
|
If there are any entries with the same key size, |
2505
|
|
|
|
|
|
|
insert the new one before them. |
2506
|
|
|
|
|
|
|
|
2507
|
|
|
|
|
|
|
=item $tree->delete($key) |
2508
|
|
|
|
|
|
|
|
2509
|
|
|
|
|
|
|
=item $tree->delete_last($key) |
2510
|
|
|
|
|
|
|
|
2511
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
2512
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
2513
|
|
|
|
|
|
|
delete the last inserted one. |
2514
|
|
|
|
|
|
|
|
2515
|
|
|
|
|
|
|
=item $tree->delete_first($key) |
2516
|
|
|
|
|
|
|
|
2517
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
2518
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
2519
|
|
|
|
|
|
|
delete the first inserted one. |
2520
|
|
|
|
|
|
|
|
2521
|
|
|
|
|
|
|
=item $size = $tree->size |
2522
|
|
|
|
|
|
|
|
2523
|
|
|
|
|
|
|
Get the number of entries in the tree |
2524
|
|
|
|
|
|
|
|
2525
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find($key, $limit=1) |
2526
|
|
|
|
|
|
|
|
2527
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_first($key, $limit=1) |
2528
|
|
|
|
|
|
|
|
2529
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
2530
|
|
|
|
|
|
|
from the first inserted one to the last inserted one. |
2531
|
|
|
|
|
|
|
|
2532
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2533
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2534
|
|
|
|
|
|
|
|
2535
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_last($key, $limit=1) |
2536
|
|
|
|
|
|
|
|
2537
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
2538
|
|
|
|
|
|
|
from the last inserted one to the first inserted one. |
2539
|
|
|
|
|
|
|
|
2540
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2541
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2542
|
|
|
|
|
|
|
|
2543
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_lt($key, $limit=1) |
2544
|
|
|
|
|
|
|
|
2545
|
|
|
|
|
|
|
Get entries, whose keys are smaller than $key, from the largest entry. |
2546
|
|
|
|
|
|
|
|
2547
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2548
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2549
|
|
|
|
|
|
|
|
2550
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_le($key, $limit=1) |
2551
|
|
|
|
|
|
|
|
2552
|
|
|
|
|
|
|
Get entries, whose keys are smaller than or equal to $key, from the largest entry. |
2553
|
|
|
|
|
|
|
|
2554
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2555
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2556
|
|
|
|
|
|
|
|
2557
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_gt($key, $limit=1) |
2558
|
|
|
|
|
|
|
|
2559
|
|
|
|
|
|
|
Get entries, whose keys are greater than $key, from the smallest one. |
2560
|
|
|
|
|
|
|
|
2561
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2562
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2563
|
|
|
|
|
|
|
|
2564
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_ge($key, $limit=1) |
2565
|
|
|
|
|
|
|
|
2566
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $key, from the smallest one. |
2567
|
|
|
|
|
|
|
|
2568
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2569
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2570
|
|
|
|
|
|
|
|
2571
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_gt_lt($lower_key, $upper_key) |
2572
|
|
|
|
|
|
|
|
2573
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than $upper_key, |
2574
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2575
|
|
|
|
|
|
|
|
2576
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_gt_le($lower_key, $upper_key) |
2577
|
|
|
|
|
|
|
|
2578
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, |
2579
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2580
|
|
|
|
|
|
|
|
2581
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_ge_lt($lower_key, $upper_key) |
2582
|
|
|
|
|
|
|
|
2583
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, |
2584
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2585
|
|
|
|
|
|
|
|
2586
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_ge_le($lower_key, $upper_key) |
2587
|
|
|
|
|
|
|
|
2588
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, |
2589
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2590
|
|
|
|
|
|
|
|
2591
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_min($limit=1) |
2592
|
|
|
|
|
|
|
|
2593
|
|
|
|
|
|
|
Get entries from the one with smallest key. |
2594
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
2595
|
|
|
|
|
|
|
begin from the first inserted one. |
2596
|
|
|
|
|
|
|
|
2597
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2598
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2599
|
|
|
|
|
|
|
|
2600
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = $tree->find_max($limit=1) |
2601
|
|
|
|
|
|
|
|
2602
|
|
|
|
|
|
|
Get entries from the one with largest key. |
2603
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
2604
|
|
|
|
|
|
|
begin from the last inserted one. |
2605
|
|
|
|
|
|
|
|
2606
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2607
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2608
|
|
|
|
|
|
|
|
2609
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = &tree->skip_l($offset, $limit=1) |
2610
|
|
|
|
|
|
|
|
2611
|
|
|
|
|
|
|
Get the first entry from one with the smallest key after skipping $offset entries. |
2612
|
|
|
|
|
|
|
|
2613
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2614
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2615
|
|
|
|
|
|
|
|
2616
|
|
|
|
|
|
|
=item $key or ($key1, $key2, ...) = &tree->skip_g($offset, $limit=1) |
2617
|
|
|
|
|
|
|
|
2618
|
|
|
|
|
|
|
Get the first entry from one with the largest key after skipping $offset entries. |
2619
|
|
|
|
|
|
|
|
2620
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2621
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2622
|
|
|
|
|
|
|
|
2623
|
|
|
|
|
|
|
=item $count = $tree->count_lt($key) |
2624
|
|
|
|
|
|
|
|
2625
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than $key. |
2626
|
|
|
|
|
|
|
|
2627
|
|
|
|
|
|
|
=item $count = $tree->count_le($key) |
2628
|
|
|
|
|
|
|
|
2629
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than or equal to $key. |
2630
|
|
|
|
|
|
|
|
2631
|
|
|
|
|
|
|
=item $count = $tree->count_gt($key) |
2632
|
|
|
|
|
|
|
|
2633
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than $key. |
2634
|
|
|
|
|
|
|
|
2635
|
|
|
|
|
|
|
=item $count = $tree->count_ge($key) |
2636
|
|
|
|
|
|
|
|
2637
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than or equal to $key. |
2638
|
|
|
|
|
|
|
|
2639
|
|
|
|
|
|
|
=item $dump_str = $tree->dump |
2640
|
|
|
|
|
|
|
|
2641
|
|
|
|
|
|
|
Get a string which represent the whole tree structure. For debug use. |
2642
|
|
|
|
|
|
|
|
2643
|
|
|
|
|
|
|
=item ($order_consistent, $size_consistent, $balanced) = $tree->check |
2644
|
|
|
|
|
|
|
|
2645
|
|
|
|
|
|
|
Check the tree property. For debug use. |
2646
|
|
|
|
|
|
|
|
2647
|
|
|
|
|
|
|
=item $ever_height = $tree->ever_height |
2648
|
|
|
|
|
|
|
|
2649
|
|
|
|
|
|
|
Get the maximum height the tree has ever been. For debug use |
2650
|
|
|
|
|
|
|
|
2651
|
|
|
|
|
|
|
=back |
2652
|
|
|
|
|
|
|
|
2653
|
|
|
|
|
|
|
=cut |
2654
|
|
|
|
|
|
|
|
2655
|
1
|
|
|
1
|
|
301
|
use Tree::SizeBalanced::any_void; |
|
1
|
|
|
|
|
1
|
|
|
1
|
|
|
|
|
113
|
|
2656
|
|
|
|
|
|
|
|
2657
|
|
|
|
|
|
|
sub sbtree_any_void(&) { |
2658
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::any_void'; |
2659
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::any_void::new; |
2660
|
|
|
|
|
|
|
} |
2661
|
|
|
|
|
|
|
|
2662
|
|
|
|
|
|
|
sub sbtreea(&) { |
2663
|
2
|
|
|
2
|
1
|
7260
|
unshift @_, 'Tree::SizeBalanced::any_void'; |
2664
|
2
|
|
|
|
|
24
|
goto \&Tree::SizeBalanced::any_void::new; |
2665
|
|
|
|
|
|
|
} |
2666
|
|
|
|
|
|
|
|
2667
|
|
|
|
|
|
|
push @EXPORT_OK, qw(sbtree_any_void sbtreea); |
2668
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'all'}}, qw(sbtree_any_void sbtreea); |
2669
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'short'}}, qw(sbtreea); |
2670
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'long'}}, qw(sbtree_any_void); |
2671
|
|
|
|
|
|
|
|
2672
|
|
|
|
|
|
|
|
2673
|
|
|
|
|
|
|
=head3 Tree::SizeBalanced::any_int |
2674
|
|
|
|
|
|
|
|
2675
|
|
|
|
|
|
|
Tree map with key type any scalars and value type signed integers (32bits or 64bits according to your perl version). |
2676
|
|
|
|
|
|
|
|
2677
|
|
|
|
|
|
|
=over 4 |
2678
|
|
|
|
|
|
|
|
2679
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced::any_int->new sub { $a cmp $b } |
2680
|
|
|
|
|
|
|
|
2681
|
|
|
|
|
|
|
=item $tree = sbtree_any_int { $a cmp $b } |
2682
|
|
|
|
|
|
|
|
2683
|
|
|
|
|
|
|
=item $tree = sbtreeai { $a cmp $b } |
2684
|
|
|
|
|
|
|
|
2685
|
|
|
|
|
|
|
Creat a new empty tree. |
2686
|
|
|
|
|
|
|
|
2687
|
|
|
|
|
|
|
=item $tree->insert($key, $value) |
2688
|
|
|
|
|
|
|
|
2689
|
|
|
|
|
|
|
=item $tree->insert_after($key, $value) |
2690
|
|
|
|
|
|
|
|
2691
|
|
|
|
|
|
|
Insert an entry into the tree. |
2692
|
|
|
|
|
|
|
If there are any entries with the same key size, |
2693
|
|
|
|
|
|
|
insert the new one after them. |
2694
|
|
|
|
|
|
|
|
2695
|
|
|
|
|
|
|
=item $tree->insert_before($key, $value) |
2696
|
|
|
|
|
|
|
|
2697
|
|
|
|
|
|
|
Insert an entry into the tree. |
2698
|
|
|
|
|
|
|
If there are any entries with the same key size, |
2699
|
|
|
|
|
|
|
insert the new one before them. |
2700
|
|
|
|
|
|
|
|
2701
|
|
|
|
|
|
|
=item $tree->delete($key) |
2702
|
|
|
|
|
|
|
|
2703
|
|
|
|
|
|
|
=item $tree->delete_last($key) |
2704
|
|
|
|
|
|
|
|
2705
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
2706
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
2707
|
|
|
|
|
|
|
delete the last inserted one. |
2708
|
|
|
|
|
|
|
|
2709
|
|
|
|
|
|
|
=item $tree->delete_first($key) |
2710
|
|
|
|
|
|
|
|
2711
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
2712
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
2713
|
|
|
|
|
|
|
delete the first inserted one. |
2714
|
|
|
|
|
|
|
|
2715
|
|
|
|
|
|
|
=item $size = $tree->size |
2716
|
|
|
|
|
|
|
|
2717
|
|
|
|
|
|
|
Get the number of entries in the tree |
2718
|
|
|
|
|
|
|
|
2719
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find($key, $limit=1) |
2720
|
|
|
|
|
|
|
|
2721
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_first($key, $limit=1) |
2722
|
|
|
|
|
|
|
|
2723
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
2724
|
|
|
|
|
|
|
from the first inserted one to the last inserted one. |
2725
|
|
|
|
|
|
|
|
2726
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2727
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2728
|
|
|
|
|
|
|
|
2729
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_last($key, $limit=1) |
2730
|
|
|
|
|
|
|
|
2731
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
2732
|
|
|
|
|
|
|
from the last inserted one to the first inserted one. |
2733
|
|
|
|
|
|
|
|
2734
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2735
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2736
|
|
|
|
|
|
|
|
2737
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_lt($key, $limit=1) |
2738
|
|
|
|
|
|
|
|
2739
|
|
|
|
|
|
|
Get entries, whose keys are smaller than $key, from the largest entry. |
2740
|
|
|
|
|
|
|
|
2741
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2742
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2743
|
|
|
|
|
|
|
|
2744
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_le($key, $limit=1) |
2745
|
|
|
|
|
|
|
|
2746
|
|
|
|
|
|
|
Get entries, whose keys are smaller than or equal to $key, from the largest entry. |
2747
|
|
|
|
|
|
|
|
2748
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2749
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2750
|
|
|
|
|
|
|
|
2751
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt($key, $limit=1) |
2752
|
|
|
|
|
|
|
|
2753
|
|
|
|
|
|
|
Get entries, whose keys are greater than $key, from the smallest one. |
2754
|
|
|
|
|
|
|
|
2755
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2756
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2757
|
|
|
|
|
|
|
|
2758
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge($key, $limit=1) |
2759
|
|
|
|
|
|
|
|
2760
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $key, from the smallest one. |
2761
|
|
|
|
|
|
|
|
2762
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2763
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2764
|
|
|
|
|
|
|
|
2765
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_lt($lower_key, $upper_key) |
2766
|
|
|
|
|
|
|
|
2767
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than $upper_key, |
2768
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2769
|
|
|
|
|
|
|
|
2770
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_le($lower_key, $upper_key) |
2771
|
|
|
|
|
|
|
|
2772
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, |
2773
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2774
|
|
|
|
|
|
|
|
2775
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_lt($lower_key, $upper_key) |
2776
|
|
|
|
|
|
|
|
2777
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, |
2778
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2779
|
|
|
|
|
|
|
|
2780
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_le($lower_key, $upper_key) |
2781
|
|
|
|
|
|
|
|
2782
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, |
2783
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2784
|
|
|
|
|
|
|
|
2785
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_min($limit=1) |
2786
|
|
|
|
|
|
|
|
2787
|
|
|
|
|
|
|
Get entries from the one with smallest key. |
2788
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
2789
|
|
|
|
|
|
|
begin from the first inserted one. |
2790
|
|
|
|
|
|
|
|
2791
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2792
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2793
|
|
|
|
|
|
|
|
2794
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_max($limit=1) |
2795
|
|
|
|
|
|
|
|
2796
|
|
|
|
|
|
|
Get entries from the one with largest key. |
2797
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
2798
|
|
|
|
|
|
|
begin from the last inserted one. |
2799
|
|
|
|
|
|
|
|
2800
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2801
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2802
|
|
|
|
|
|
|
|
2803
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_l($offset, $limit=1) |
2804
|
|
|
|
|
|
|
|
2805
|
|
|
|
|
|
|
Get the first entry from one with the smallest key after skipping $offset entries. |
2806
|
|
|
|
|
|
|
|
2807
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2808
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2809
|
|
|
|
|
|
|
|
2810
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_g($offset, $limit=1) |
2811
|
|
|
|
|
|
|
|
2812
|
|
|
|
|
|
|
Get the first entry from one with the largest key after skipping $offset entries. |
2813
|
|
|
|
|
|
|
|
2814
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2815
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2816
|
|
|
|
|
|
|
|
2817
|
|
|
|
|
|
|
=item $count = $tree->count_lt($key) |
2818
|
|
|
|
|
|
|
|
2819
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than $key. |
2820
|
|
|
|
|
|
|
|
2821
|
|
|
|
|
|
|
=item $count = $tree->count_le($key) |
2822
|
|
|
|
|
|
|
|
2823
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than or equal to $key. |
2824
|
|
|
|
|
|
|
|
2825
|
|
|
|
|
|
|
=item $count = $tree->count_gt($key) |
2826
|
|
|
|
|
|
|
|
2827
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than $key. |
2828
|
|
|
|
|
|
|
|
2829
|
|
|
|
|
|
|
=item $count = $tree->count_ge($key) |
2830
|
|
|
|
|
|
|
|
2831
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than or equal to $key. |
2832
|
|
|
|
|
|
|
|
2833
|
|
|
|
|
|
|
=item $dump_str = $tree->dump |
2834
|
|
|
|
|
|
|
|
2835
|
|
|
|
|
|
|
Get a string which represent the whole tree structure. For debug use. |
2836
|
|
|
|
|
|
|
|
2837
|
|
|
|
|
|
|
=item ($order_consistent, $size_consistent, $balanced) = $tree->check |
2838
|
|
|
|
|
|
|
|
2839
|
|
|
|
|
|
|
Check the tree property. For debug use. |
2840
|
|
|
|
|
|
|
|
2841
|
|
|
|
|
|
|
=item $ever_height = $tree->ever_height |
2842
|
|
|
|
|
|
|
|
2843
|
|
|
|
|
|
|
Get the maximum height the tree has ever been. For debug use |
2844
|
|
|
|
|
|
|
|
2845
|
|
|
|
|
|
|
=back |
2846
|
|
|
|
|
|
|
|
2847
|
|
|
|
|
|
|
=cut |
2848
|
|
|
|
|
|
|
|
2849
|
1
|
|
|
1
|
|
326
|
use Tree::SizeBalanced::any_int; |
|
1
|
|
|
|
|
2
|
|
|
1
|
|
|
|
|
139
|
|
2850
|
|
|
|
|
|
|
|
2851
|
|
|
|
|
|
|
sub sbtree_any_int(&) { |
2852
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::any_int'; |
2853
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::any_int::new; |
2854
|
|
|
|
|
|
|
} |
2855
|
|
|
|
|
|
|
|
2856
|
|
|
|
|
|
|
sub sbtreeai(&) { |
2857
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::any_int'; |
2858
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::any_int::new; |
2859
|
|
|
|
|
|
|
} |
2860
|
|
|
|
|
|
|
|
2861
|
|
|
|
|
|
|
push @EXPORT_OK, qw(sbtree_any_int sbtreeai); |
2862
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'all'}}, qw(sbtree_any_int sbtreeai); |
2863
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'short'}}, qw(sbtreeai); |
2864
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'long'}}, qw(sbtree_any_int); |
2865
|
|
|
|
|
|
|
|
2866
|
|
|
|
|
|
|
|
2867
|
|
|
|
|
|
|
=head3 Tree::SizeBalanced::any_num |
2868
|
|
|
|
|
|
|
|
2869
|
|
|
|
|
|
|
Tree map with key type any scalars and value type numeric numbers (floating point numbers). |
2870
|
|
|
|
|
|
|
|
2871
|
|
|
|
|
|
|
=over 4 |
2872
|
|
|
|
|
|
|
|
2873
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced::any_num->new sub { $a cmp $b } |
2874
|
|
|
|
|
|
|
|
2875
|
|
|
|
|
|
|
=item $tree = sbtree_any_num { $a cmp $b } |
2876
|
|
|
|
|
|
|
|
2877
|
|
|
|
|
|
|
=item $tree = sbtreean { $a cmp $b } |
2878
|
|
|
|
|
|
|
|
2879
|
|
|
|
|
|
|
Creat a new empty tree. |
2880
|
|
|
|
|
|
|
|
2881
|
|
|
|
|
|
|
=item $tree->insert($key, $value) |
2882
|
|
|
|
|
|
|
|
2883
|
|
|
|
|
|
|
=item $tree->insert_after($key, $value) |
2884
|
|
|
|
|
|
|
|
2885
|
|
|
|
|
|
|
Insert an entry into the tree. |
2886
|
|
|
|
|
|
|
If there are any entries with the same key size, |
2887
|
|
|
|
|
|
|
insert the new one after them. |
2888
|
|
|
|
|
|
|
|
2889
|
|
|
|
|
|
|
=item $tree->insert_before($key, $value) |
2890
|
|
|
|
|
|
|
|
2891
|
|
|
|
|
|
|
Insert an entry into the tree. |
2892
|
|
|
|
|
|
|
If there are any entries with the same key size, |
2893
|
|
|
|
|
|
|
insert the new one before them. |
2894
|
|
|
|
|
|
|
|
2895
|
|
|
|
|
|
|
=item $tree->delete($key) |
2896
|
|
|
|
|
|
|
|
2897
|
|
|
|
|
|
|
=item $tree->delete_last($key) |
2898
|
|
|
|
|
|
|
|
2899
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
2900
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
2901
|
|
|
|
|
|
|
delete the last inserted one. |
2902
|
|
|
|
|
|
|
|
2903
|
|
|
|
|
|
|
=item $tree->delete_first($key) |
2904
|
|
|
|
|
|
|
|
2905
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
2906
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
2907
|
|
|
|
|
|
|
delete the first inserted one. |
2908
|
|
|
|
|
|
|
|
2909
|
|
|
|
|
|
|
=item $size = $tree->size |
2910
|
|
|
|
|
|
|
|
2911
|
|
|
|
|
|
|
Get the number of entries in the tree |
2912
|
|
|
|
|
|
|
|
2913
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find($key, $limit=1) |
2914
|
|
|
|
|
|
|
|
2915
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_first($key, $limit=1) |
2916
|
|
|
|
|
|
|
|
2917
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
2918
|
|
|
|
|
|
|
from the first inserted one to the last inserted one. |
2919
|
|
|
|
|
|
|
|
2920
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2921
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2922
|
|
|
|
|
|
|
|
2923
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_last($key, $limit=1) |
2924
|
|
|
|
|
|
|
|
2925
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
2926
|
|
|
|
|
|
|
from the last inserted one to the first inserted one. |
2927
|
|
|
|
|
|
|
|
2928
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2929
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2930
|
|
|
|
|
|
|
|
2931
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_lt($key, $limit=1) |
2932
|
|
|
|
|
|
|
|
2933
|
|
|
|
|
|
|
Get entries, whose keys are smaller than $key, from the largest entry. |
2934
|
|
|
|
|
|
|
|
2935
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2936
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2937
|
|
|
|
|
|
|
|
2938
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_le($key, $limit=1) |
2939
|
|
|
|
|
|
|
|
2940
|
|
|
|
|
|
|
Get entries, whose keys are smaller than or equal to $key, from the largest entry. |
2941
|
|
|
|
|
|
|
|
2942
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2943
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2944
|
|
|
|
|
|
|
|
2945
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt($key, $limit=1) |
2946
|
|
|
|
|
|
|
|
2947
|
|
|
|
|
|
|
Get entries, whose keys are greater than $key, from the smallest one. |
2948
|
|
|
|
|
|
|
|
2949
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2950
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2951
|
|
|
|
|
|
|
|
2952
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge($key, $limit=1) |
2953
|
|
|
|
|
|
|
|
2954
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $key, from the smallest one. |
2955
|
|
|
|
|
|
|
|
2956
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2957
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2958
|
|
|
|
|
|
|
|
2959
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_lt($lower_key, $upper_key) |
2960
|
|
|
|
|
|
|
|
2961
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than $upper_key, |
2962
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2963
|
|
|
|
|
|
|
|
2964
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_le($lower_key, $upper_key) |
2965
|
|
|
|
|
|
|
|
2966
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, |
2967
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2968
|
|
|
|
|
|
|
|
2969
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_lt($lower_key, $upper_key) |
2970
|
|
|
|
|
|
|
|
2971
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, |
2972
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2973
|
|
|
|
|
|
|
|
2974
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_le($lower_key, $upper_key) |
2975
|
|
|
|
|
|
|
|
2976
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, |
2977
|
|
|
|
|
|
|
from the smallest one to the largest one. |
2978
|
|
|
|
|
|
|
|
2979
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_min($limit=1) |
2980
|
|
|
|
|
|
|
|
2981
|
|
|
|
|
|
|
Get entries from the one with smallest key. |
2982
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
2983
|
|
|
|
|
|
|
begin from the first inserted one. |
2984
|
|
|
|
|
|
|
|
2985
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2986
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2987
|
|
|
|
|
|
|
|
2988
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_max($limit=1) |
2989
|
|
|
|
|
|
|
|
2990
|
|
|
|
|
|
|
Get entries from the one with largest key. |
2991
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
2992
|
|
|
|
|
|
|
begin from the last inserted one. |
2993
|
|
|
|
|
|
|
|
2994
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
2995
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
2996
|
|
|
|
|
|
|
|
2997
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_l($offset, $limit=1) |
2998
|
|
|
|
|
|
|
|
2999
|
|
|
|
|
|
|
Get the first entry from one with the smallest key after skipping $offset entries. |
3000
|
|
|
|
|
|
|
|
3001
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
3002
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
3003
|
|
|
|
|
|
|
|
3004
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_g($offset, $limit=1) |
3005
|
|
|
|
|
|
|
|
3006
|
|
|
|
|
|
|
Get the first entry from one with the largest key after skipping $offset entries. |
3007
|
|
|
|
|
|
|
|
3008
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
3009
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
3010
|
|
|
|
|
|
|
|
3011
|
|
|
|
|
|
|
=item $count = $tree->count_lt($key) |
3012
|
|
|
|
|
|
|
|
3013
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than $key. |
3014
|
|
|
|
|
|
|
|
3015
|
|
|
|
|
|
|
=item $count = $tree->count_le($key) |
3016
|
|
|
|
|
|
|
|
3017
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than or equal to $key. |
3018
|
|
|
|
|
|
|
|
3019
|
|
|
|
|
|
|
=item $count = $tree->count_gt($key) |
3020
|
|
|
|
|
|
|
|
3021
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than $key. |
3022
|
|
|
|
|
|
|
|
3023
|
|
|
|
|
|
|
=item $count = $tree->count_ge($key) |
3024
|
|
|
|
|
|
|
|
3025
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than or equal to $key. |
3026
|
|
|
|
|
|
|
|
3027
|
|
|
|
|
|
|
=item $dump_str = $tree->dump |
3028
|
|
|
|
|
|
|
|
3029
|
|
|
|
|
|
|
Get a string which represent the whole tree structure. For debug use. |
3030
|
|
|
|
|
|
|
|
3031
|
|
|
|
|
|
|
=item ($order_consistent, $size_consistent, $balanced) = $tree->check |
3032
|
|
|
|
|
|
|
|
3033
|
|
|
|
|
|
|
Check the tree property. For debug use. |
3034
|
|
|
|
|
|
|
|
3035
|
|
|
|
|
|
|
=item $ever_height = $tree->ever_height |
3036
|
|
|
|
|
|
|
|
3037
|
|
|
|
|
|
|
Get the maximum height the tree has ever been. For debug use |
3038
|
|
|
|
|
|
|
|
3039
|
|
|
|
|
|
|
=back |
3040
|
|
|
|
|
|
|
|
3041
|
|
|
|
|
|
|
=cut |
3042
|
|
|
|
|
|
|
|
3043
|
1
|
|
|
1
|
|
340
|
use Tree::SizeBalanced::any_num; |
|
1
|
|
|
|
|
1
|
|
|
1
|
|
|
|
|
121
|
|
3044
|
|
|
|
|
|
|
|
3045
|
|
|
|
|
|
|
sub sbtree_any_num(&) { |
3046
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::any_num'; |
3047
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::any_num::new; |
3048
|
|
|
|
|
|
|
} |
3049
|
|
|
|
|
|
|
|
3050
|
|
|
|
|
|
|
sub sbtreean(&) { |
3051
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::any_num'; |
3052
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::any_num::new; |
3053
|
|
|
|
|
|
|
} |
3054
|
|
|
|
|
|
|
|
3055
|
|
|
|
|
|
|
push @EXPORT_OK, qw(sbtree_any_num sbtreean); |
3056
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'all'}}, qw(sbtree_any_num sbtreean); |
3057
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'short'}}, qw(sbtreean); |
3058
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'long'}}, qw(sbtree_any_num); |
3059
|
|
|
|
|
|
|
|
3060
|
|
|
|
|
|
|
|
3061
|
|
|
|
|
|
|
=head3 Tree::SizeBalanced::any_any |
3062
|
|
|
|
|
|
|
|
3063
|
|
|
|
|
|
|
Tree map with key type any scalars and value type any scalars. |
3064
|
|
|
|
|
|
|
|
3065
|
|
|
|
|
|
|
=over 4 |
3066
|
|
|
|
|
|
|
|
3067
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced::any_any->new sub { $a cmp $b } |
3068
|
|
|
|
|
|
|
|
3069
|
|
|
|
|
|
|
=item $tree = sbtree_any_any { $a cmp $b } |
3070
|
|
|
|
|
|
|
|
3071
|
|
|
|
|
|
|
=item $tree = sbtreeaa { $a cmp $b } |
3072
|
|
|
|
|
|
|
|
3073
|
|
|
|
|
|
|
Creat a new empty tree. |
3074
|
|
|
|
|
|
|
|
3075
|
|
|
|
|
|
|
=item $tree->insert($key, $value) |
3076
|
|
|
|
|
|
|
|
3077
|
|
|
|
|
|
|
=item $tree->insert_after($key, $value) |
3078
|
|
|
|
|
|
|
|
3079
|
|
|
|
|
|
|
Insert an entry into the tree. |
3080
|
|
|
|
|
|
|
If there are any entries with the same key size, |
3081
|
|
|
|
|
|
|
insert the new one after them. |
3082
|
|
|
|
|
|
|
|
3083
|
|
|
|
|
|
|
=item $tree->insert_before($key, $value) |
3084
|
|
|
|
|
|
|
|
3085
|
|
|
|
|
|
|
Insert an entry into the tree. |
3086
|
|
|
|
|
|
|
If there are any entries with the same key size, |
3087
|
|
|
|
|
|
|
insert the new one before them. |
3088
|
|
|
|
|
|
|
|
3089
|
|
|
|
|
|
|
=item $tree->delete($key) |
3090
|
|
|
|
|
|
|
|
3091
|
|
|
|
|
|
|
=item $tree->delete_last($key) |
3092
|
|
|
|
|
|
|
|
3093
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
3094
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
3095
|
|
|
|
|
|
|
delete the last inserted one. |
3096
|
|
|
|
|
|
|
|
3097
|
|
|
|
|
|
|
=item $tree->delete_first($key) |
3098
|
|
|
|
|
|
|
|
3099
|
|
|
|
|
|
|
Delete one entry whose key is equal to $key. |
3100
|
|
|
|
|
|
|
If there ary more than one entry with the same key size, |
3101
|
|
|
|
|
|
|
delete the first inserted one. |
3102
|
|
|
|
|
|
|
|
3103
|
|
|
|
|
|
|
=item $size = $tree->size |
3104
|
|
|
|
|
|
|
|
3105
|
|
|
|
|
|
|
Get the number of entries in the tree |
3106
|
|
|
|
|
|
|
|
3107
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find($key, $limit=1) |
3108
|
|
|
|
|
|
|
|
3109
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_first($key, $limit=1) |
3110
|
|
|
|
|
|
|
|
3111
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
3112
|
|
|
|
|
|
|
from the first inserted one to the last inserted one. |
3113
|
|
|
|
|
|
|
|
3114
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
3115
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
3116
|
|
|
|
|
|
|
|
3117
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_last($key, $limit=1) |
3118
|
|
|
|
|
|
|
|
3119
|
|
|
|
|
|
|
Get entries with key sizes equal to $key, |
3120
|
|
|
|
|
|
|
from the last inserted one to the first inserted one. |
3121
|
|
|
|
|
|
|
|
3122
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
3123
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
3124
|
|
|
|
|
|
|
|
3125
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_lt($key, $limit=1) |
3126
|
|
|
|
|
|
|
|
3127
|
|
|
|
|
|
|
Get entries, whose keys are smaller than $key, from the largest entry. |
3128
|
|
|
|
|
|
|
|
3129
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
3130
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
3131
|
|
|
|
|
|
|
|
3132
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_le($key, $limit=1) |
3133
|
|
|
|
|
|
|
|
3134
|
|
|
|
|
|
|
Get entries, whose keys are smaller than or equal to $key, from the largest entry. |
3135
|
|
|
|
|
|
|
|
3136
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
3137
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
3138
|
|
|
|
|
|
|
|
3139
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt($key, $limit=1) |
3140
|
|
|
|
|
|
|
|
3141
|
|
|
|
|
|
|
Get entries, whose keys are greater than $key, from the smallest one. |
3142
|
|
|
|
|
|
|
|
3143
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
3144
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
3145
|
|
|
|
|
|
|
|
3146
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge($key, $limit=1) |
3147
|
|
|
|
|
|
|
|
3148
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $key, from the smallest one. |
3149
|
|
|
|
|
|
|
|
3150
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
3151
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
3152
|
|
|
|
|
|
|
|
3153
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_lt($lower_key, $upper_key) |
3154
|
|
|
|
|
|
|
|
3155
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than $upper_key, |
3156
|
|
|
|
|
|
|
from the smallest one to the largest one. |
3157
|
|
|
|
|
|
|
|
3158
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_gt_le($lower_key, $upper_key) |
3159
|
|
|
|
|
|
|
|
3160
|
|
|
|
|
|
|
Get entries, whose keys are greater than $lower_key and smaller than or equal to $upper_key, |
3161
|
|
|
|
|
|
|
from the smallest one to the largest one. |
3162
|
|
|
|
|
|
|
|
3163
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_lt($lower_key, $upper_key) |
3164
|
|
|
|
|
|
|
|
3165
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than $upper_key, |
3166
|
|
|
|
|
|
|
from the smallest one to the largest one. |
3167
|
|
|
|
|
|
|
|
3168
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_ge_le($lower_key, $upper_key) |
3169
|
|
|
|
|
|
|
|
3170
|
|
|
|
|
|
|
Get entries, whose keys are greater than or equal to $lower_key and smaller than or equal to $upper_key, |
3171
|
|
|
|
|
|
|
from the smallest one to the largest one. |
3172
|
|
|
|
|
|
|
|
3173
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_min($limit=1) |
3174
|
|
|
|
|
|
|
|
3175
|
|
|
|
|
|
|
Get entries from the one with smallest key. |
3176
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
3177
|
|
|
|
|
|
|
begin from the first inserted one. |
3178
|
|
|
|
|
|
|
|
3179
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
3180
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
3181
|
|
|
|
|
|
|
|
3182
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = $tree->find_max($limit=1) |
3183
|
|
|
|
|
|
|
|
3184
|
|
|
|
|
|
|
Get entries from the one with largest key. |
3185
|
|
|
|
|
|
|
If there are more than one entries with smallest key, |
3186
|
|
|
|
|
|
|
begin from the last inserted one. |
3187
|
|
|
|
|
|
|
|
3188
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
3189
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
3190
|
|
|
|
|
|
|
|
3191
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_l($offset, $limit=1) |
3192
|
|
|
|
|
|
|
|
3193
|
|
|
|
|
|
|
Get the first entry from one with the smallest key after skipping $offset entries. |
3194
|
|
|
|
|
|
|
|
3195
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
3196
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
3197
|
|
|
|
|
|
|
|
3198
|
|
|
|
|
|
|
=item $key or ($key1, $value1, $key2, $value2, ...) = &tree->skip_g($offset, $limit=1) |
3199
|
|
|
|
|
|
|
|
3200
|
|
|
|
|
|
|
Get the first entry from one with the largest key after skipping $offset entries. |
3201
|
|
|
|
|
|
|
|
3202
|
|
|
|
|
|
|
The optional $limit (default 1) indicates the maximum entry number you will get, |
3203
|
|
|
|
|
|
|
$limit=-1 means unlimited. |
3204
|
|
|
|
|
|
|
|
3205
|
|
|
|
|
|
|
=item $count = $tree->count_lt($key) |
3206
|
|
|
|
|
|
|
|
3207
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than $key. |
3208
|
|
|
|
|
|
|
|
3209
|
|
|
|
|
|
|
=item $count = $tree->count_le($key) |
3210
|
|
|
|
|
|
|
|
3211
|
|
|
|
|
|
|
Get the number of entries whose keys are smaller than or equal to $key. |
3212
|
|
|
|
|
|
|
|
3213
|
|
|
|
|
|
|
=item $count = $tree->count_gt($key) |
3214
|
|
|
|
|
|
|
|
3215
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than $key. |
3216
|
|
|
|
|
|
|
|
3217
|
|
|
|
|
|
|
=item $count = $tree->count_ge($key) |
3218
|
|
|
|
|
|
|
|
3219
|
|
|
|
|
|
|
Get the number of entries whose keys are greater than or equal to $key. |
3220
|
|
|
|
|
|
|
|
3221
|
|
|
|
|
|
|
=item $dump_str = $tree->dump |
3222
|
|
|
|
|
|
|
|
3223
|
|
|
|
|
|
|
Get a string which represent the whole tree structure. For debug use. |
3224
|
|
|
|
|
|
|
|
3225
|
|
|
|
|
|
|
=item ($order_consistent, $size_consistent, $balanced) = $tree->check |
3226
|
|
|
|
|
|
|
|
3227
|
|
|
|
|
|
|
Check the tree property. For debug use. |
3228
|
|
|
|
|
|
|
|
3229
|
|
|
|
|
|
|
=item $ever_height = $tree->ever_height |
3230
|
|
|
|
|
|
|
|
3231
|
|
|
|
|
|
|
Get the maximum height the tree has ever been. For debug use |
3232
|
|
|
|
|
|
|
|
3233
|
|
|
|
|
|
|
=back |
3234
|
|
|
|
|
|
|
|
3235
|
|
|
|
|
|
|
=cut |
3236
|
|
|
|
|
|
|
|
3237
|
1
|
|
|
1
|
|
299
|
use Tree::SizeBalanced::any_any; |
|
1
|
|
|
|
|
2
|
|
|
1
|
|
|
|
|
216
|
|
3238
|
|
|
|
|
|
|
|
3239
|
|
|
|
|
|
|
sub sbtree_any_any(&) { |
3240
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::any_any'; |
3241
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::any_any::new; |
3242
|
|
|
|
|
|
|
} |
3243
|
|
|
|
|
|
|
|
3244
|
|
|
|
|
|
|
sub sbtreeaa(&) { |
3245
|
0
|
|
|
0
|
1
|
0
|
unshift @_, 'Tree::SizeBalanced::any_any'; |
3246
|
0
|
|
|
|
|
0
|
goto \&Tree::SizeBalanced::any_any::new; |
3247
|
|
|
|
|
|
|
} |
3248
|
|
|
|
|
|
|
|
3249
|
|
|
|
|
|
|
push @EXPORT_OK, qw(sbtree_any_any sbtreeaa); |
3250
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'all'}}, qw(sbtree_any_any sbtreeaa); |
3251
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'short'}}, qw(sbtreeaa); |
3252
|
|
|
|
|
|
|
push @{$EXPORT_TAGS{'long'}}, qw(sbtree_any_any); |
3253
|
|
|
|
|
|
|
|
3254
|
|
|
|
|
|
|
sub sbtree(;&) { |
3255
|
0
|
0
|
|
0
|
1
|
0
|
if( ref() eq 'CODE' ) { |
3256
|
0
|
|
|
|
|
0
|
goto \&sbtreeaa; |
3257
|
|
|
|
|
|
|
} else { |
3258
|
0
|
|
|
|
|
0
|
goto \&sbtreeia; |
3259
|
|
|
|
|
|
|
} |
3260
|
|
|
|
|
|
|
} |
3261
|
|
|
|
|
|
|
|
3262
|
|
|
|
|
|
|
sub new { |
3263
|
1
|
|
|
1
|
1
|
118315
|
shift; |
3264
|
1
|
50
|
|
|
|
3
|
if( ref() eq 'CODE' ) { |
3265
|
0
|
|
|
|
|
0
|
goto \&sbtreeaa; |
3266
|
|
|
|
|
|
|
} else { |
3267
|
1
|
|
|
|
|
5
|
goto \&sbtreeia; |
3268
|
|
|
|
|
|
|
} |
3269
|
|
|
|
|
|
|
} |
3270
|
|
|
|
|
|
|
|
3271
|
|
|
|
|
|
|
|
3272
|
|
|
|
|
|
|
=head3 Default type constructors |
3273
|
|
|
|
|
|
|
|
3274
|
|
|
|
|
|
|
=over 4 |
3275
|
|
|
|
|
|
|
|
3276
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced->new; |
3277
|
|
|
|
|
|
|
|
3278
|
|
|
|
|
|
|
equivalent to C<< $tree = Tree::SizeBalanced::int_any->new; >> |
3279
|
|
|
|
|
|
|
|
3280
|
|
|
|
|
|
|
=item $tree = Tree::SizeBalanced->new sub { $a cmp $b }; |
3281
|
|
|
|
|
|
|
|
3282
|
|
|
|
|
|
|
equivalent to C<< $tree = Tree::SizeBalanced::any_any->new; >> |
3283
|
|
|
|
|
|
|
|
3284
|
|
|
|
|
|
|
=item $tree = sbtree; |
3285
|
|
|
|
|
|
|
|
3286
|
|
|
|
|
|
|
equivalent to C<$tree = sbtreeia> |
3287
|
|
|
|
|
|
|
|
3288
|
|
|
|
|
|
|
=item $tree = sbtree { $a cmp $b }; |
3289
|
|
|
|
|
|
|
|
3290
|
|
|
|
|
|
|
equivalent to C<$tree = sbtreeaa> |
3291
|
|
|
|
|
|
|
|
3292
|
|
|
|
|
|
|
=back |
3293
|
|
|
|
|
|
|
|
3294
|
|
|
|
|
|
|
=head1 BENCHMARK |
3295
|
|
|
|
|
|
|
|
3296
|
|
|
|
|
|
|
test result: (perl 5.22.2, Tree::SizeBalanced 2.6) |
3297
|
|
|
|
|
|
|
|
3298
|
|
|
|
|
|
|
L seed_count=10, data_size=100_000, verbose=0 |
3299
|
|
|
|
|
|
|
|
3300
|
|
|
|
|
|
|
Benchmark: timing 1 iterations of Sorted array, Static array, tree set any, tree set int... |
3301
|
|
|
|
|
|
|
Sorted array: 12 wallclock secs (12.60 usr + 0.00 sys = 12.60 CPU) @ 0.08/s (n=1) |
3302
|
|
|
|
|
|
|
(warning: too few iterations for a reliable count) |
3303
|
|
|
|
|
|
|
^CSIGINT! |
3304
|
|
|
|
|
|
|
Static array: 737 wallclock secs (736.96 usr + 0.14 sys = 737.10 CPU) @ 0.00/s (n=1) |
3305
|
|
|
|
|
|
|
(warning: too few iterations for a reliable count) |
3306
|
|
|
|
|
|
|
tree set any: 5 wallclock secs ( 4.70 usr + 0.01 sys = 4.71 CPU) @ 0.21/s (n=1) |
3307
|
|
|
|
|
|
|
(warning: too few iterations for a reliable count) |
3308
|
|
|
|
|
|
|
tree set int: 1 wallclock secs ( 0.69 usr + 0.01 sys = 0.70 CPU) @ 1.43/s (n=1) |
3309
|
|
|
|
|
|
|
(warning: too few iterations for a reliable count) |
3310
|
|
|
|
|
|
|
|
3311
|
|
|
|
|
|
|
(Note that "Static array" didn't complete. It's interrupted) |
3312
|
|
|
|
|
|
|
|
3313
|
|
|
|
|
|
|
L seed_count=10, data_size=100_000, verbose=0 |
3314
|
|
|
|
|
|
|
|
3315
|
|
|
|
|
|
|
Benchmark: timing 1 iterations of Sorted array, Static array, tree set any, tree set str... |
3316
|
|
|
|
|
|
|
Sorted array: 15 wallclock secs (15.28 usr + 0.00 sys = 15.28 CPU) @ 0.07/s (n=1) |
3317
|
|
|
|
|
|
|
(warning: too few iterations for a reliable count) |
3318
|
|
|
|
|
|
|
^CSIGINT! |
3319
|
|
|
|
|
|
|
Static array: 673 wallclock secs (672.08 usr + 0.15 sys = 672.23 CPU) @ 0.00/s (n=1) |
3320
|
|
|
|
|
|
|
(warning: too few iterations for a reliable count) |
3321
|
|
|
|
|
|
|
tree set any: 6 wallclock secs ( 6.65 usr + 0.00 sys = 6.65 CPU) @ 0.15/s (n=1) |
3322
|
|
|
|
|
|
|
(warning: too few iterations for a reliable count) |
3323
|
|
|
|
|
|
|
tree set str: 2 wallclock secs ( 1.88 usr + 0.00 sys = 1.88 CPU) @ 0.53/s (n=1) |
3324
|
|
|
|
|
|
|
(warning: too few iterations for a reliable count) |
3325
|
|
|
|
|
|
|
|
3326
|
|
|
|
|
|
|
(Note that "Static array" didn't complete. It's interrupted) |
3327
|
|
|
|
|
|
|
|
3328
|
|
|
|
|
|
|
L seed_count=10, data_size=100_000, verbose=0 |
3329
|
|
|
|
|
|
|
|
3330
|
|
|
|
|
|
|
Benchmark: timing 1 iterations of Sorted array, Static array, tree set any, tree set int... |
3331
|
|
|
|
|
|
|
Sorted array: 3 wallclock secs ( 2.99 usr + 0.00 sys = 2.99 CPU) @ 0.33/s (n=1) |
3332
|
|
|
|
|
|
|
(warning: too few iterations for a reliable count) |
3333
|
|
|
|
|
|
|
^CSIGINT! |
3334
|
|
|
|
|
|
|
Static array: 251 wallclock secs (251.85 usr + 0.02 sys = 251.87 CPU) @ 0.00/s (n=1) |
3335
|
|
|
|
|
|
|
(warning: too few iterations for a reliable count) |
3336
|
|
|
|
|
|
|
tree set any: 6 wallclock secs ( 5.24 usr + 0.00 sys = 5.24 CPU) @ 0.19/s (n=1) |
3337
|
|
|
|
|
|
|
(warning: too few iterations for a reliable count) |
3338
|
|
|
|
|
|
|
tree set int: 1 wallclock secs ( 0.86 usr + 0.00 sys = 0.86 CPU) @ 1.16/s (n=1) |
3339
|
|
|
|
|
|
|
(warning: too few iterations for a reliable count) |
3340
|
|
|
|
|
|
|
|
3341
|
|
|
|
|
|
|
(Note that "Static array" didn't complete. It's interrupted) |
3342
|
|
|
|
|
|
|
|
3343
|
|
|
|
|
|
|
L seed_count=10, data_size=100_000, verbose=0 |
3344
|
|
|
|
|
|
|
|
3345
|
|
|
|
|
|
|
Benchmark: timing 1 iterations of Sorted array, Static array, tree set any, tree set int... |
3346
|
|
|
|
|
|
|
Sorted array: 5 wallclock secs ( 5.59 usr + 0.00 sys = 5.59 CPU) @ 0.18/s (n=1) |
3347
|
|
|
|
|
|
|
(warning: too few iterations for a reliable count) |
3348
|
|
|
|
|
|
|
^CSIGINT! |
3349
|
|
|
|
|
|
|
Static array: 363 wallclock secs (361.56 usr + 0.07 sys = 361.63 CPU) @ 0.00/s (n=1) |
3350
|
|
|
|
|
|
|
(warning: too few iterations for a reliable count) |
3351
|
|
|
|
|
|
|
tree set any: 8 wallclock secs ( 7.85 usr + 0.00 sys = 7.85 CPU) @ 0.13/s (n=1) |
3352
|
|
|
|
|
|
|
(warning: too few iterations for a reliable count) |
3353
|
|
|
|
|
|
|
tree set int: 3 wallclock secs ( 3.27 usr + 0.01 sys = 3.28 CPU) @ 0.30/s (n=1) |
3354
|
|
|
|
|
|
|
(warning: too few iterations for a reliable count) |
3355
|
|
|
|
|
|
|
|
3356
|
|
|
|
|
|
|
(Note that "Static array" didn't complete. It's interrupted) |
3357
|
|
|
|
|
|
|
|
3358
|
|
|
|
|
|
|
=head1 SEE ALSO |
3359
|
|
|
|
|
|
|
|
3360
|
|
|
|
|
|
|
This mod's github L. |
3361
|
|
|
|
|
|
|
It's welcome to discuss with me when you encounter bugs, or |
3362
|
|
|
|
|
|
|
if you think that some patterns are also useful but the mod didn't provide them yet. |
3363
|
|
|
|
|
|
|
|
3364
|
|
|
|
|
|
|
Introduction to Size Balanced Tree L. |
3365
|
|
|
|
|
|
|
|
3366
|
|
|
|
|
|
|
陈启峰's original paper L, |
3367
|
|
|
|
|
|
|
I found it from L. |
3368
|
|
|
|
|
|
|
|
3369
|
|
|
|
|
|
|
=head1 AUTHOR |
3370
|
|
|
|
|
|
|
|
3371
|
|
|
|
|
|
|
Cindy Wang (CindyLinz) |
3372
|
|
|
|
|
|
|
|
3373
|
|
|
|
|
|
|
=head1 COPYRIGHT AND LICENSE |
3374
|
|
|
|
|
|
|
|
3375
|
|
|
|
|
|
|
Copyright (C) 2016 by CindyLinz |
3376
|
|
|
|
|
|
|
|
3377
|
|
|
|
|
|
|
This library is free software; you can redistribute it and/or modify |
3378
|
|
|
|
|
|
|
it under the same terms as Perl itself, either Perl version 5.22.1 or, |
3379
|
|
|
|
|
|
|
at your option, any later version of Perl 5 you may have available. |
3380
|
|
|
|
|
|
|
|
3381
|
|
|
|
|
|
|
=head1 ACKNOWLEDGEMENT |
3382
|
|
|
|
|
|
|
|
3383
|
|
|
|
|
|
|
Thank TDYa127 L who tell me size balanced tree. |
3384
|
|
|
|
|
|
|
|
3385
|
|
|
|
|
|
|
=cut |
3386
|
|
|
|
|
|
|
|
3387
|
|
|
|
|
|
|
require XSLoader; |
3388
|
|
|
|
|
|
|
XSLoader::load('Tree::SizeBalanced', $VERSION); |
3389
|
|
|
|
|
|
|
|
3390
|
|
|
|
|
|
|
1; |
3391
|
|
|
|
|
|
|
__END__ |