File Coverage

blib/lib/Netstack/Utils/Set.pm
Criterion Covered Total %
statement 57 71 80.2
branch 19 30 63.3
condition 4 9 44.4
subroutine 12 14 85.7
pod 1 9 11.1
total 93 133 69.9


line stmt bran cond sub pod time code
1             package Netstack::Utils::Set;
2              
3             #------------------------------------------------------------------------------
4             # 加载扩展模块功能
5             #------------------------------------------------------------------------------
6 2     2   213165 use 5.016;
  2         17  
7 2     2   419 use Moose;
  2         420616  
  2         15  
8 2     2   14143 use namespace::autoclean;
  2         7375  
  2         12  
9 2     2   1202 use POSIX;
  2         14720  
  2         13  
10 2     2   6642 use experimental 'smartmatch';
  2         6634  
  2         14  
11              
12             #------------------------------------------------------------------------------
13             # 定义 Netstack::Utils::Set 方法属性
14             #------------------------------------------------------------------------------
15             has mins => (
16             is => 'rw',
17             isa => 'ArrayRef[Int]',
18             default => sub { [] },
19             );
20              
21             has maxs => (
22             is => 'rw',
23             isa => 'ArrayRef[Int]',
24             default => sub { [] },
25             );
26              
27             #------------------------------------------------------------------------------
28             # Moose BUILDARGS 钩子函数
29             #------------------------------------------------------------------------------
30             around BUILDARGS => sub {
31             my $orig = shift;
32             my $class = shift;
33              
34             # 对象实例化钩子函数
35             if ( @_ == 0 ) {
36             return $class->$orig();
37             }
38             elsif ( @_ == 1 and ref( $_[0] ) eq __PACKAGE__ ) {
39             my $setObj = $_[0];
40             return $class->$orig(
41             mins => \$setObj->mins->@*,
42             maxs => \$setObj->maxs->@*
43             );
44             }
45             elsif ( @_ == 2
46             and defined $_[0]
47             and defined $_[1]
48             and $_[0] =~ /^\d+$/o
49             and $_[1] =~ /^\d+$/o )
50             {
51             # 确保 MIN MAX 按顺序存放
52             my ( $MIN, $MAX ) = $_[0] < $_[1] ? ( $_[0], $_[1] ) : ( $_[1], $_[0] );
53             return $class->$orig(
54             mins => [$MIN],
55             maxs => [$MAX]
56             );
57             }
58             else {
59             return $class->$orig(@_);
60             }
61             };
62              
63             #------------------------------------------------------------------------------
64             # Moose BUILD 钩子函数 | 确保实例化对象的min max 按顺序存放和长度相等
65             #------------------------------------------------------------------------------
66             sub BUILD {
67 71     71 0 90 my $self = shift;
68 71         87 my @ERROR;
69 71         1563 my $lengthOfMin = $self->mins->@*;
70 71         1398 my $lengthOfMax = $self->maxs->@*;
71              
72             # 约束性检查 | 集合对象成员数必须相等、确保集合对象的 min < max
73 71 50       130 if ( $lengthOfMin != $lengthOfMax ) {
74 0         0 push @ERROR, 'Attribute (mins) and (maxs) must has same length at constructor ' . __PACKAGE__;
75             }
76 71         130 for ( my $i = 0; $i < $lengthOfMin; $i++ ) {
77 133 50       2869 if ( $self->mins->[$i] > $self->maxs->[$i] ) {
78 0         0 push @ERROR, 'Attribute (mins) must not bigger than (maxs) in the same index at constructor ' . __PACKAGE__;
79 0         0 last;
80             }
81             }
82             # 异常拦截
83 71 50       1471 if ( @ERROR > 0 ) {
84 0         0 confess join( ', ', @ERROR );
85             }
86             }
87              
88             #------------------------------------------------------------------------------
89             # 集合对象空间长度
90             #------------------------------------------------------------------------------
91             sub length {
92 83     83 0 112 my $self = shift;
93             # 集合对象长度
94 83         1722 my $lengthOfMin = $self->mins->@*;
95 83         1652 my $lengthOfMax = $self->maxs->@*;
96              
97             # 边界条件检查
98 83 50       156 confess "ERROR: Attribute (mins) 's length($lengthOfMin) not equal (maxs) 's length($lengthOfMax)"
99             if $lengthOfMin != $lengthOfMax;
100             # 返回计算结果
101 83         278 return $lengthOfMin;
102             }
103              
104             #------------------------------------------------------------------------------
105             # min 集合对象最小值
106             #------------------------------------------------------------------------------
107             sub min {
108 3     3 0 17 my $self = shift;
109 3 50       8 return ( $self->length > 0 ? $self->mins->[0] : undef );
110             }
111              
112             #------------------------------------------------------------------------------
113             # max 集合对象最大值
114             #------------------------------------------------------------------------------
115             sub max {
116 3     3 0 18 my $self = shift;
117 3 50       8 return ( $self->length > 0 ? $self->maxs->[-1] : undef );
118             }
119              
120             #------------------------------------------------------------------------------
121             # dump 打印集合对象
122             #------------------------------------------------------------------------------
123             sub dump {
124 0     0 1 0 my $self = shift;
125 0         0 my $length = $self->length;
126 0         0 for ( my $i = 0; $i < $length; $i++ ) {
127 0         0 say $self->mins->[$i] . " " . $self->maxs->[$i];
128             }
129             }
130              
131             #------------------------------------------------------------------------------
132             # addToSet 不需要检查重复,需要检查排序,所以用这个的时候要特别慎重
133             # 只有在确定输入与set不重复的情况下才可使用,否则会有问题
134             #------------------------------------------------------------------------------
135             sub addToSet {
136             my ( $self, $MIN, $MAX ) = @_;
137             # 确保集合对象的顺序
138             ( $MIN, $MAX ) = $MIN > $MAX ? ( $MAX, $MIN ) : ( $MIN, $MAX );
139              
140             # 检查是否存在集合对象,空集合对象直接插入数据
141             my $length = $self->length;
142             if ( $length == 0 ) {
143             $self->mins( [$MIN] );
144             $self->maxs( [$MAX] );
145             return;
146             }
147              
148             my $minArray = $self->mins;
149             my $maxArray = $self->maxs;
150              
151             # 遍历集合对象 minArray(本身线性递增) | 非空集合则需要确定插入点
152             my $index;
153             for ( my $i = 0; $i < $length; $i++ ) {
154             # 从最小成员对象开始查找,插入点落在集合区间左开部分
155             if ( $MIN < $minArray->[$i] ) {
156             $index = $i;
157             last;
158             }
159             }
160              
161             # 找了一圈仍未确定插入点,则必定在最后一个集合区间
162             $index = $length if not defined $index;
163              
164             # 确定插入点填充实际数据
165             my ( @min, @max );
166             push @min, $minArray->@[ 0 .. $index - 1 ];
167             push @max, $maxArray->@[ 0 .. $index - 1 ];
168             push @min, $MIN;
169             push @max, $MAX;
170             push @min, $minArray->@[ $index .. $length - 1 ];
171             push @max, $maxArray->@[ $index .. $length - 1 ];
172              
173             # 数据绑定
174             $self->mins( \@min );
175             $self->maxs( \@max );
176             }
177              
178             #------------------------------------------------------------------------------
179             # mergeToSet 合并到已有集合对象,需要检查重复,也需要检查排序 | 支持传入集合对象、数组
180             #------------------------------------------------------------------------------
181             sub mergeToSet {
182 20     20 0 35 my $self = shift;
183             # 入参是否为一个集合对象
184 20 100 66     82 if ( @_ == 1 and ref( $_[0] ) eq __PACKAGE__ ) {
185 19         29 my $setObj = $_[0];
186 19         38 my $length = $setObj->length;
187             # 遍历集合对象并合并数据
188 19         47 for ( my $i = 0; $i < $length; $i++ ) {
189 39         782 $self->_mergeToSet( $setObj->mins->[$i], $setObj->maxs->[$i] );
190             }
191             }
192             else {
193 1         4 $self->_mergeToSet(@_);
194             }
195             }
196              
197             #------------------------------------------------------------------------------
198             # mergeToSet 合并到已有集合对象
199             #------------------------------------------------------------------------------
200             sub _mergeToSet {
201             my ( $self, $MIN, $MAX ) = @_;
202             # 检查排序
203             ( $MIN, $MAX ) = $MIN > $MAX ? ( $MAX, $MIN ) : ( $MIN, $MAX );
204              
205             # 判断是否已经初始化过 mins maxs 对象
206             my $length = $self->length;
207             if ( $length == 0 ) {
208             $self->mins( [$MIN] );
209             $self->maxs( [$MAX] );
210             return;
211             }
212              
213             my $minArray = $self->mins;
214             my $maxArray = $self->maxs;
215             # 索引位置在数组长度区间各偏移一个单位
216             my ( $minIndex, $maxIndex ) = ( -1, $length );
217              
218             # 边际递减确定合并数据的区间,合并数据可能跨界(分布在多个集合区间)
219             MIN: {
220             for ( my $i = 0; $i < $length; $i++ ) {
221             # 命中集合对象区间 ($minArray, $maxArray)
222             if ( $MIN >= $minArray->[$i] and $MIN <= $maxArray->[$i] ) {
223             $minIndex = $i;
224             last MIN;
225             }
226             # 命中集合对象区间 ($minArray, $maxArray) 左开区间 | 比最小还小
227             elsif ( $MIN < $minArray->[$i] ) {
228             $minIndex += 0.5;
229             last MIN;
230             }
231             # 命中集合对象区间 ($minArray, $maxArray) 右开区间 | 比最大还大
232             # 集合对象可能存在多个不连续区间,该动作代表移位计算(当前区间不满足要求)
233             else {
234             $minIndex++;
235             }
236             }
237             $minIndex += 0.5;
238             }
239             MAX: {
240             for ( my $j = $length - 1; $j >= $minIndex; $j-- ) {
241             # 命中集合对象区间 ($minArray, $maxArray)
242             if ( $MAX >= $minArray->[$j] and $MAX <= $maxArray->[$j] ) {
243             $maxIndex = $j;
244             last MAX;
245             }
246             # 命中集合对象区间 ($minArray, $maxArray) 右开区间,比最大还大
247             elsif ( $MAX > $maxArray->[$j] ) {
248             $maxIndex -= 0.5;
249             last MAX;
250             }
251             # 命中集合对象区间 ($minArray, $maxArray) 左开区间,比最小还小
252             # 集合对象可能存在多个不连续区间,该动作代表移位计算(当前区间不满足要求)
253             else {
254             $maxIndex--;
255             }
256             }
257             $maxIndex -= 0.5;
258             }
259              
260             # 分别向上向下取整 POSIX::ceil(0.5) = 1, POSIX::floor(-0.5) = -1
261             my $minIndexInt = POSIX::ceil($minIndex);
262             my $maxIndexInt = POSIX::floor($maxIndex);
263             # 是否命中已有集合区间
264             my $isMinIndexInSet = ( $minIndex == $minIndexInt ) ? 1 : 0;
265             my $isMaxIndexInSet = ( $maxIndex == $maxIndexInt ) ? 1 : 0;
266             # 已确定插入点合并数据
267             my ( @min, @max );
268             push @min, $minArray->@[ 0 .. $minIndexInt - 1 ];
269             push @max, $maxArray->@[ 0 .. $minIndexInt - 1 ];
270             push @min, $isMinIndexInSet ? $minArray->[$minIndex] : $MIN;
271             push @max, $isMaxIndexInSet ? $maxArray->[$maxIndex] : $MAX;
272             push @min, $minArray->@[ $maxIndexInt + 1 .. $length - 1 ];
273             push @max, $maxArray->@[ $maxIndexInt + 1 .. $length - 1 ];
274             # 数据绑定
275             $self->mins( \@min );
276             $self->maxs( \@max );
277             }
278              
279             #------------------------------------------------------------------------------
280             # compare 比对两个集合对象关系 | 包括完全相等、包含但不相等、属于另一个集合但不相等、其他
281             #------------------------------------------------------------------------------
282             sub compare {
283             my ( $self, $setObj ) = @_;
284             if ( $self->isEqual($setObj) ) {
285             return 'equal';
286             }
287             elsif ( $self->_isContain($setObj) ) {
288             return 'containButNotEqual';
289             }
290             elsif ( $self->_isBelong($setObj) ) {
291             return 'belongButNotEqual';
292             }
293             else {
294             return 'other';
295             }
296             }
297              
298             #------------------------------------------------------------------------------
299             # isEqual 两个集合对象完全相同 | "~~ 判断两个数组对象是否相等"
300             #------------------------------------------------------------------------------
301             sub isEqual {
302             my ( $self, $setObj ) = @_;
303             return ( $self->mins->@* ~~ $setObj->mins->@* and $self->maxs->@* ~~ $setObj->maxs->@* );
304             }
305              
306             #------------------------------------------------------------------------------
307             # notEqual 两个集合对象不等性判断 | 基于isEqual取反
308             #------------------------------------------------------------------------------
309             sub notEqual {
310 0     0 0 0 my ( $self, $setObj ) = @_;
311 0   0     0 return !( $self->mins->@* ~~ $setObj->mins->@* and $self->maxs->@* ~~ $setObj->maxs->@* );
312             }
313              
314             #------------------------------------------------------------------------------
315             # isContain A对象是否包含B对象
316             #------------------------------------------------------------------------------
317             sub isContain {
318             my ( $self, $setObj ) = @_;
319             # 完全一致
320             if ( $self->isEqual($setObj) ) {
321             return 1;
322             }
323             else {
324             return $self->_isContain($setObj);
325             }
326             }
327              
328             #------------------------------------------------------------------------------
329             # _isContain 两个对象相等也理解为包含另外一个对象
330             #------------------------------------------------------------------------------
331             sub _isContain {
332             my ( $self, $setObj ) = @_;
333             # 复刻一份self集合对象
334             my $copyOfSelf = Netstack::Utils::Set->new($self);
335             # 合并B集合对象到A集合对象
336             $copyOfSelf->mergeToSet($setObj);
337             # 将A集合与$copyOfSelf比较,合并B集合对象的没有发生改变,代表B为A的子集
338             return $self->isEqual($copyOfSelf);
339             }
340              
341             #------------------------------------------------------------------------------
342             # isContainButNotEqual A对象包含B对象,且两个对象不相等
343             #------------------------------------------------------------------------------
344             sub isContainButNotEqual {
345             my ( $self, $setObj ) = @_;
346             if ( $self->isEqual($setObj) ) {
347             return;
348             }
349             else {
350             return $self->_isContain($setObj);
351             }
352             }
353              
354             #------------------------------------------------------------------------------
355             # isBelong B对象是否包含A对象
356             #------------------------------------------------------------------------------
357             sub isBelong {
358             my ( $self, $setObj ) = @_;
359             if ( $self->isEqual($setObj) ) {
360             return 1;
361             }
362             else {
363             return $self->_isBelong($setObj);
364             }
365             }
366              
367             #------------------------------------------------------------------------------
368             # _isBelong B对象是否包含A对象
369             #------------------------------------------------------------------------------
370             sub _isBelong {
371             my ( $self, $setObj ) = @_;
372             # 复刻B集合对象
373             my $copyOfSetObj = Netstack::Utils::Set->new($setObj);
374             # 将A对象合并到复刻的B集合对象
375             $copyOfSetObj->mergeToSet($self);
376             # 判断B对象与合并A的复刻B对象是否相等,合并过来没发生改变,代表A为B的子集
377             return $setObj->isEqual($copyOfSetObj);
378             }
379              
380             #------------------------------------------------------------------------------
381             # isBelongButNotEqual B对象是否包含A对象,且两个对象不相等
382             #------------------------------------------------------------------------------
383             sub isBelongButNotEqual {
384             my ( $self, $setObj ) = @_;
385             if ( $self->isEqual($setObj) ) {
386             return;
387             }
388             else {
389             return $self->_isBelong($setObj);
390             }
391             }
392              
393             #------------------------------------------------------------------------------
394             # interSet B对象是否包含A对象,且两个对象不相等
395             #------------------------------------------------------------------------------
396             sub interSet {
397 1     1 0 3 my ( $self, $setObj ) = @_;
398             # 实例化集合对象
399 1         24 my $result = Netstack::Utils::Set->new;
400             # 检查是否已携带 min max 属性
401 1 50       4 if ( $self->length == 0 ) {
402 0         0 return $self;
403             }
404 1 50       3 if ( $setObj->length == 0 ) {
405 0         0 return $setObj;
406             }
407              
408             # 遍历两个集合对象
409 1         3 my $i = 0;
410 1         2 my $j = 0;
411 1   66     4 while ( $i < $self->length and $j < $setObj->length ) {
412 4         79 my @rangeSet1 = ( $self->mins->[$i], $self->maxs->[$i] );
413 4         87 my @rangeSet2 = ( $setObj->mins->[$j], $setObj->maxs->[$j] );
414             # 两个数组的最大最小值|可能返回 undef
415 4         11 my ( $min, $max ) = $self->interRange( \@rangeSet1, \@rangeSet2 );
416             # 如果定义了 min 则合并到初始化的集合对象
417 4 50       65 $result->_mergeToSet( $min, $max ) if defined $min;
418              
419             # B对象比A对象的最大值还大,自增A对象区间值
420 4 100       94 if ( $setObj->maxs->[$j] > $self->maxs->[$i] ) {
    50          
421 3         7 $i++;
422             }
423             # B对象的最大值和A对象的最大值相等
424             elsif ( $setObj->maxs->[$j] == $self->maxs->[$i] ) {
425 0         0 $i++;
426 0         0 $j++;
427             }
428             # B对象比A对象的最小值还小,自增B对象区间值
429             else {
430 1         3 $j++;
431             }
432             }
433 1         26 return $result;
434             }
435              
436             #------------------------------------------------------------------------------
437             # interRange 返回两个集合对象的最大最小值
438             #------------------------------------------------------------------------------
439             sub interRange {
440 4     4 0 18 my ( $self, $rangeSet1, $rangeSet2 ) = @_;
441 4 100       12 my $min
442             = ( $rangeSet1->[0] < $rangeSet2->[0] )
443             ? $rangeSet1->[0]
444             : $rangeSet2->[0];
445 4 100       10 my $max
446             = ( $rangeSet1->[1] > $rangeSet2->[1] )
447             ? $rangeSet1->[1]
448             : $rangeSet2->[1];
449              
450             # 返回计算结果
451 4 50       12 return ( $min > $max )
452             ? undef
453             : ( $min, $max );
454             }
455              
456             #------------------------------------------------------------------------------
457             # addToSet _mergeToSet 入参检查,必须传入2个数字
458             #------------------------------------------------------------------------------
459             for my $func (qw/ addToSet _mergeToSet /) {
460             before $func => sub {
461             my $self = shift;
462             unless ( @_ == 2 and $_[0] =~ /^\d+$/o and $_[1] =~ /^\d+$/o ) {
463             confess "ERROR: function $func can only has two numeric argument";
464             }
465             }
466             }
467              
468             #------------------------------------------------------------------------------
469             # 集合对象比较函数钩子函数,确保入参为集合对象
470             #------------------------------------------------------------------------------
471             for my $func (qw/ compare isEqual isContain _isContain isContainButNotEqual isBelong _isBelong isBelongButNotEqual /) {
472             before $func => sub {
473             my $self = shift;
474             confess "ERROR: the first param of function($func) is not a Netstack::Utils::Set"
475             if ref( $_[0] ) ne 'Netstack::Utils::Set';
476             }
477             }
478              
479             __PACKAGE__->meta->make_immutable;
480             1;