File Coverage

blib/lib/Tree/SizeBalanced.pm
Criterion Covered Total %
statement 75 133 56.3
branch 1 4 25.0
condition n/a
subroutine 27 55 49.0
pod 34 34 100.0
total 137 226 60.6


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__