1IntSpan(3) User Contributed Perl Documentation IntSpan(3)
2
6 Set::IntSpan - Manages sets of integers
7
9 # BEGIN { $Set::IntSpan::integer = 1 }
10 use Set::IntSpan qw(grep_set map_set grep_spans map_spans);
11 # $Set::IntSpan::Empty_String = '-'; # or '';
13 $set = new Set::IntSpan $set_spec;
15 $set = new Set::IntSpan @set_specs;
16 $valid = valid Set::IntSpan $run_list;
17 $set = copy $set $set_spec;
18 $run_list = run_list $set;
20 @elements = elements $set;
21 @sets = sets $set;
22 @spans = spans $set;
23 $u_set = union $set $set_spec;
25 $i_set = intersect $set $set_spec;
26 $x_set = xor $set $set_spec;
27 $d_set = diff $set $set_spec;
28 $c_set = complement $set;
29 $set->U($set_spec); # Union
31 $set->I($set_spec); # Intersect
32 $set->X($set_spec); # Xor
33 $set->D($set_spec); # Diff
34 $set->C; # Complement
35 equal $set $set_spec
37 equivalent $set $set_spec
38 superset $set $set_spec
39 subset $set $set_spec
40 $n = cardinality $set;
42 $n = size $set;
43 empty $set
45 finite $set
46 neg_inf $set
47 pos_inf $set
48 infinite $set
49 universal $set
50 member $set $n;
52 insert $set $n;
53 remove $set $n;
54 $min = min $set;
56 $max = max $set;
57 $holes = holes $set;
59 $cover = cover $set;
60 $inset = inset $set $n;
61 $smaller = trim $set $n;
62 $bigger = pad $set $n;
63 $subset = grep_set { ... } $set;
65 $mapset = map_set { ... } $set;
66 $subset = grep_spans { ... } $set;
68 $mapset = map_spans { ... } $set;
69 for ($element=$set->first; defined $element; $element=$set->next) { ... }
71 for ($element=$set->last ; defined $element; $element=$set->prev) { ... }
72 $element = $set->start($n);
74 $element = $set->current;
75 $n = $set->at($i);
77 $slice = $set->slice($from, $to);
78 $i = $set->ord($n);
79 $i = $set->span_ord($n);
80 Operator overloads
82 $u_set = $set + $set_spec; # union
83 $i_set = $set * $set_spec; # intersect
84 $x_set = $set ^ $set_spec; # xor
85 $d_set = $set - $set_spec; # diff
86 $c_set = ~$set; # complement
87 $set += $set_spec; # union
89 $set *= $set_spec; # intersect
90 $set ^= $set_spec; # xor
91 $set -= $set_spec; # diff
92 $set eq $set_spec # equal
94 $set ne $set_spec # not equal
95 $set le $set_spec # subset
96 $set lt $set_spec # proper subset
97 $set ge $set_spec # superset
98 $set gt $set_spec # proper superset
99 # compare sets by cardinality
101 $set1 == $set2
102 $set1 != $set2
103 $set1 <= $set2
104 $set1 < $set2
105 $set1 >= $set2
106 $set1 > $set2
107 $set1 <=> $set2
108 # compare cardinality of set to an integer
110 $set1 == $n
111 $set1 != $n
112 $set1 <= $n
113 $set1 < $n
114 $set1 >= $n
115 $set1 > $n
116 $set1 <=> $n
117 @sorted = sort @sets; # sort sets by cardinality
119 if ($set) { ... } # true if $set is not empty
121 print "$set\n"; # stringizes to the run list
123
125 @EXPORT
126 Nothing
127 @EXPORT_OK
129 "grep_set", "map_set", "grep_spans", "map_spans"
130
132 "Set::IntSpan" manages sets of integers. It is optimized for sets that
133 have long runs of consecutive integers. These arise, for example, in
134 .newsrc files, which maintain lists of articles:
135 alt.foo: 1-21,28,31
137 alt.bar: 1-14192,14194,14196-14221
138 A run of consecutive integers is also called a span.
140 Sets are stored internally in a run-length coded form. This provides
142 for both compact storage and efficient computation. In particular, set
143 operations can be performed directly on the encoded representation.
144 "Set::IntSpan" is designed to manage finite sets. However, it can also
146 represent some simple infinite sets, such as { x | x>n }. This allows
147 operations involving complements to be carried out consistently,
148 without having to worry about the actual value of INT_MAX on your
149 machine.
150
152 A span is a run of consecutive integers. A span may be represented by
153 an array reference, in any of 5 forms:
154 Finite forms
156 Span Set
157 [ $n, $n ] { n }
158 [ $a, $b ] { x | a<=x && x<=b}
159 Infinite forms
161 Span Set
162 [ undef, $b ] { x | x<=b }
163 [ $a , undef ] { x | x>=a }
164 [ undef, undef ] The set of all integers
165 Some methods operate directly on spans.
167
169 Many of the methods take a set specification. There are four kinds of
170 set specifications.
171 Empty
173 If a set specification is omitted, then the empty set is assumed.
174 Thus,
175 $set = new Set::IntSpan;
177 creates a new, empty set. Similarly,
179 copy $set;
181 removes all elements from $set.
183 Object reference
185 If an object reference is given, it is taken to be a "Set::IntSpan"
186 object.
187 Run list
189 If a string is given, it is taken to be a run list. A run list
190 specifies a set using a syntax similar to that in newsrc files.
191 A run list is a comma-separated list of runs. Each run specifies a set
193 of consecutive integers. The set is the union of all the runs.
194 Runs may be written in any of 5 forms.
196 Finite forms
198 n { n }
200 a-b { x | a<=x && x<=b }
202 Infinite forms
204 (-n { x | x<=n }
206 n-) { x | x>=n }
208 (-) The set of all integers
210 Empty forms
212 The empty set is consistently written as '' (the null string). It is
214 also denoted by the special form '-' (a single dash).
215 Restrictions
217 The runs in a run list must be disjoint, and must be listed in
219 increasing order.
220 Valid characters in a run list are 0-9, '(', ')', '-' and ','. White
222 space and underscore (_) are ignored. Other characters are not
223 allowed.
224 Examples
226 Run list Set
228 "-" { }
229 "1" { 1 }
230 "1-2" { 1, 2 }
231 "-5--1" { -5, -4, -3, -2, -1 }
232 "(-)" the integers
233 "(--1" the negative integers
234 "1-3, 4, 18-21" { 1, 2, 3, 4, 18, 19, 20, 21 }
235 Array reference
237 If an array reference is given, then the elements of the array specify
238 the elements of the set. The array may contain
239 · integers
241 · spans
243 The set is the union of all the integers and spans in the array. The
245 integers and spans need not be disjoint. The integers and spans may be
246 in any order.
247 Examples
249 Array ref Set
251 [ ] { }
252 [ 1, 1 ] { 1 }
253 [ 1, 3, 2 ] { 1, 2, 3 }
254 [ 1, [ 5, 8 ], 5, [ 7, 9 ], 2 ] { 1, 2, 5, 6, 7, 8, 9 }
255 [ undef, undef ] the integers
256 [ undef, -1 ] the negative integers
257
259 Each set has a single iterator, which is shared by all calls to
260 "first", "last", "start", "next", "prev", and "current". At all times,
261 the iterator is either an element of the set, or "undef".
262 "first", "last", and "start" set the iterator; "next", and "prev" move
264 it; and "current" returns it. Calls to these methods may be freely
265 intermixed.
266 Using "next" and "prev", a single loop can move both forwards and
268 backwards through a set. Using "start", a loop can iterate over
269 portions of an infinite set.
270
272 Creation
273 $set = "new" "Set::IntSpan" $set_spec
274 $set = "new" "Set::IntSpan" @set_specs
275 Creates and returns a "Set::IntSpan" object.
276 The initial contents of the set are given by $set_spec, or by the
278 union of all the @set_specs.
279 $ok = "valid" "Set::IntSpan" $run_list
281 Returns true if $run_list is a valid run list. Otherwise, returns
282 false and leaves an error message in $@.
283 $set = "copy" $set $set_spec
285 Copies $set_spec into $set. The previous contents of $set are
286 lost. For convenience, "copy" returns $set.
287 $run_list = "run_list" $set
289 Returns a run list that represents $set. The run list will not
290 contain white space. $set is not affected.
291 By default, the empty set is formatted as '-'; a different string
293 may be specified in $Set::IntSpan::Empty_String.
294 @elements = "elements" $set
296 Returns an array containing the elements of $set. The elements
297 will be sorted in numerical order. In scalar context, returns an
298 array reference. $set is not affected.
299 @sets = "sets" $set
301 Returns the runs in $set, as a list of "Set::IntSpan" objects. The
302 sets in the list are in order.
303 @spans = "spans" $set
305 Returns the runs in $set, as a list of the form
306 ([$a1, $b1],
308 [$a2, $b2],
309 ...
310 [$aN, $bN])
311 If a run contains only a single integer, then the upper and lower
313 bounds of the corresponding span will be equal.
314 If the set has no lower bound, then $a1 will be "undef".
316 Similarly, if the set has no upper bound, then $bN will be "undef".
317 The runs in the list are in order.
319 Set operations
321 For these operations, a new "Set::IntSpan" object is created and
322 returned. The operands are not affected.
323 $u_set = "union" $set $set_spec
325 Returns the set of integers in either $set or $set_spec.
326 $i_set = "intersect" $set $set_spec
328 Returns the set of integers in both $set and $set_spec.
329 $x_set = "xor" $set $set_spec
331 Returns the set of integers in $set or $set_spec, but not both.
332 $d_set = "diff" $set $set_spec
334 Returns the set of integers in $set but not in $set_spec.
335 $c_set = "complement" $set
337 Returns the set of integers that are not in $set.
338 Mutators
340 By popular demand, "Set::IntSpan" now has mutating forms of the binary
341 set operations. These methods alter the object on which they are
342 called.
343 $set->"U"($set_spec)
345 Makes $set the union of $set and $set_spec. Returns $set.
346 $set->"I"($set_spec)
348 Makes $set the intersection of $set and $set_spec. Returns $set.
349 $set->"X"($set_spec)
351 Makes $set the symmetric difference of $set and $set_spec. Returns
352 $set.
353 $set->"D"($set_spec)
355 Makes $set the difference of $set and $set_spec. Returns $set.
356 $set->"C"
358 Converts $set to its own complement. Returns $set.
359 Comparison
361 "equal" $set $set_spec
362 Returns true iff $set and $set_spec contain the same elements.
363 "equivalent" $set $set_spec
365 Returns true iff $set and $set_spec contain the same number of
366 elements. All infinite sets are equivalent.
367 "superset" $set $set_spec
369 Returns true iff $set is a superset of $set_spec.
370 "subset" $set $set_spec
372 Returns true iff $set is a subset of $set_spec.
373 Cardinality
375 $n = "cardinality" $set
376 $n = "size" $set
377 Returns the number of elements in $set. Returns -1 for infinite
378 sets. "size" is provided as an alias for "cardinality".
379 "empty" $set
381 Returns true iff $set is empty.
382 "finite" $set
384 Returns true iff $set is finite.
385 "neg_inf" $set
387 Returns true iff $set contains {x | x<n} for some n.
388 "pos_inf" $set
390 Returns true iff $set contains {x | x>n} for some n.
391 "infinite" $set
393 Returns true iff $set is infinite.
394 "universal" $set
396 Returns true iff $set contains all integers.
397 Membership
399 "member" $set $n
400 Returns true iff the integer $n is a member of $set.
401 "insert" $set $n
403 Inserts the integer $n into $set. Does nothing if $n is already a
404 member of $set.
405 "remove" $set $n
407 Removes the integer $n from $set. Does nothing if $n is not a
408 member of $set.
409 Extrema
411 "min" $set
412 Returns the smallest element of $set, or "undef" if there is none.
413 "max" $set
415 Returns the largest element of $set, or "undef" if there is none.
416 Spans
418 $holes = "holes" $set
419 Returns a set containing all the holes in $set, that is, all the
420 integers that are in-between spans of $set.
421 "holes" is always a finite set.
423 $cover = "cover" $set
425 Returns a set consisting of a single span from $set->"min" to
426 $set->"max". This is the same as
427 union $set $set->holes
429 $inset = "inset" $set $n
431 $smaller = "trim" $set $n
432 $bigger = "pad" $set $n
433 "inset" returns a set constructed by removing $n integers from each
434 end of each span of $set. If $n is negative, then -$n integers are
435 added to each end of each span.
436 In the first case, spans may vanish from the set; in the second
438 case, holes may vanish.
439 "trim" is provided as a synonym for "inset".
441 "pad" $set $n is the same as "inset" $set -$n.
443 Iterators
445 $set->"first"
446 Sets the iterator for $set to the smallest element of $set. If
447 there is no smallest element, sets the iterator to "undef".
448 Returns the iterator.
449 $set->"last"
451 Sets the iterator for $set to the largest element of $set. If
452 there is no largest element, sets the iterator to "undef". Returns
453 the iterator.
454 $set->"start"($n)
456 Sets the iterator for $set to $n. If $n is not an element of $set,
457 sets the iterator to "undef". Returns the iterator.
458 $set->"next"
460 Sets the iterator for $set to the next element of $set. If there
461 is no next element, sets the iterator to "undef". Returns the
462 iterator.
463 "next" will return "undef" only once; the next call to "next" will
465 reset the iterator to the smallest element of $set.
466 $set->"prev"
468 Sets the iterator for $set to the previous element of $set. If
469 there is no previous element, sets the iterator to "undef".
470 Returns the iterator.
471 "prev" will return "undef" only once; the next call to "prev" will
473 reset the iterator to the largest element of $set.
474 $set->"current"
476 Returns the iterator for $set.
477 Indexing
479 The elements of a set are kept in numerical order. These methods index
480 into the set based on this ordering.
481 $n = $set->"at"($i)
483 Returns the $ith element of $set, or "undef" if there is no $ith
484 element. Negative indices count backwards from the end of the set.
485 Dies if
487 · $i is non-negative and $set is "neg_inf"
489 · $i is negative and $set is "pos_inf"
491 $slice = $set->"slice"($from, $to)
493 Returns a "Set::IntSpan" object containing the elements of $set at
494 indices $from..$to. Negative indices count backwards from the end
495 of the set.
496 Dies if
498 · $from is non-negative and $set is "neg_inf"
500 · $from is negative and $set is "pos_inf"
502 $i = $set->"ord"($n)
504 The inverse of "at".
505 Returns the index $i of the integer $n in $set, or "undef" if $n if
507 not an element of $set.
508 Dies if $set is "neg_inf".
510 $i = $set->"span_ord"($n)
512 Returns the index $i of the span containing the integer $n, or
513 "undef" if $n if not an element of $set.
514 To recover the span containing $n, write
516 ($set->spans)[$i]
518
520 For convenience, some operators are overloaded on "Set::IntSpan"
521 objects.
522 set operations
524 One operand must be a "Set::IntSpan" object. The other operand may be
525 a "Set::IntSpan" object or a set specification.
526 $u_set = $set + $set_spec; # union
528 $i_set = $set * $set_spec; # intersect
529 $x_set = $set ^ $set_spec; # xor
530 $d_set = $set - $set_spec; # diff
531 $c_set = ~$set; # complement
532 $set += $set_spec; # union
534 $set *= $set_spec; # intersect
535 $set ^= $set_spec; # xor
536 $set -= $set_spec; # diff
537 equality
539 The string comparison operations are overloaded to compare sets for
540 equality and containment. One operand must be a "Set::IntSpan" object.
541 The other operand may be a "Set::IntSpan" object or a set
542 specification.
543 $set eq $set_spec # equal
545 $set ne $set_spec # not equal
546 $set le $set_spec # subset
547 $set lt $set_spec # proper subset
548 $set ge $set_spec # superset
549 $set gt $set_spec # proper superset
550 equivalence
552 The numerical comparison operations are overloaded to compare sets by
553 cardinality. One operand must be a "Set::IntSpan" object. The other
554 operand may be a "Set::IntSpan" object or an integer.
555 $set1 == $set2
557 $set1 != $set2
558 $set1 <= $set2
559 $set1 < $set2
560 $set1 >= $set2
561 $set1 > $set2
562 $set1 <=> $set2
563 $set1 cmp $set2
564 $set1 == $n
566 $set1 != $n
567 $set1 <= $n
568 $set1 < $n
569 $set1 >= $n
570 $set1 > $n
571 $set1 <=> $n
572 $set1 cmp $n
573 N.B. The "cmp" operator is overloaded to compare sets by cardinality,
575 not containment. This is done so that
576 sort @sets
578 will sort a list of sets by cardinality.
580 conversion
582 In boolean context, a "Set::IntSpan" object evaluates to true if it is
583 not empty.
584 A "Set::IntSpan" object stringizes to its run list.
586
588 $sub_set = "grep_set" { ... } $set
589 Evaluates the BLOCK for each integer in $set (locally setting $_ to
590 each integer) and returns a "Set::IntSpan" object containing those
591 integers for which the BLOCK returns TRUE.
592 Returns "undef" if $set is infinite.
594 $map_set = "map_set" { ... } $set
596 Evaluates the BLOCK for each integer in $set (locally setting $_ to
597 each integer) and returns a "Set::IntSpan" object containing all
598 the integers returned as results of all those evaluations.
599 Evaluates the BLOCK in list context, so each element of $set may
601 produce zero, one, or more elements in the returned set. The
602 elements may be returned in any order, and need not be disjoint.
603 Returns "undef" if $set is infinite.
605 $sub_set = "grep_spans" { ... } $set
607 Evaluates the BLOCK for each span in $set and returns a
608 "Set::IntSpan" object containing those spans for which the BLOCK
609 returns TRUE.
610 Within BLOCK, $_ is locally set to an array ref of the form
612 [ $lower, $upper ]
614 where $lower and $upper are the bounds of the span. If the span
616 contains only one integer, then $lower and $upper will be equal.
617 If the span is unbounded, then the corresponding element(s) of the
618 array will be "undef".
619 $map_set = "map_spans" { ... } $set
621 Evaluates the BLOCK for each span in $set, and returns a
622 "Set::IntSpan" object consisting of the union of all the spans
623 returned as results of all those evaluations.
624 Within BLOCK, $_ is locally set to an array ref of the form
626 [ $lower, $upper ]
628 as described above for "grep_spans". Each evaluation of BLOCK must
630 return a list of spans. Each returned list may contain zero, one,
631 or more spans. Spans may be returned in any order, and need not be
632 disjoint. However, for each bounded span, the constraint
633 $lower <= $upper
635 must hold.
637
639 $Set::IntSpan::Empty_String
640 $Set::IntSpan::Empty_String contains the string that is returned
641 when "run_list" is called on the empty set. $Empty_String is
642 initially '-'; alternatively, it may be set to ''. Other values
643 should be avoided, to ensure that "run_list" always returns a valid
644 run list.
645 "run_list" accesses $Empty_String through a reference stored in
647 $set->{"empty_string"}. Subclasses that wish to override the value
648 of $Empty_String can reassign this reference.
649 $Set::IntSpan::integer
651 Up until version 1.16, "Set::IntSpan" specified "use integer",
652 because they were sets of...you know...integers. As of 2012, users
653 are reporting newsgroups with article numbers above 0x7fffffff,
654 which break "Set::IntSpan" on 32-bit processors.
655 Version 1.17 removes "use integer" by default. This extends the
657 usable range of "Set::IntSpan" to the number of bits in the
658 mantissa of your floating point representation. For IEEE 754
659 doubles, this is 53 bits, or around 9e15.
660 I benchmarked "Set::IntSpan" on a Pentium 4, and it looks like "use
662 integer" provides a 2% to 4% speedup, depending on the application.
663 If you want "use integer" back, either for performance, or because
665 you are somehow dependent on its semantics, write
666 BEGIN { $Set::IntSpan::integer = 1 }
668 use Set::IntSpan;
669
671 Any method (except "valid") will "die" if it is passed an invalid run
672 list.
673 "Set::IntSpan::_copy_run_list: Bad syntax:" $runList
675 (F) $run_list has bad syntax
676 "Set::IntSpan::_copy_run_list: Bad order:" $runList
678 (F) $run_list has overlapping runs or runs that are out of order.
679 "Set::IntSpan::elements: infinite set"
681 (F) An infinite set was passed to "elements".
682 "Set::IntSpan::at: negative infinite set"
684 (F) "at" was called with a non-negative index on a negative
685 infinite set.
686 "Set::IntSpan::at: positive infinite set"
688 (F) "at" was called with a negative index on a positive infinite
689 set.
690 "Set::IntSpan::slice: negative infinite set"
692 (F) "slice" was called with $from non-negative on a negative
693 infinite set.
694 "Set::IntSpan::slice: positive infinite set"
696 (F) "slice" was called with $from negative on a positive infinite
697 set.
698 "Set::IntSpan::ord: negative infinite set"
700 (F) "ord" was called on a negative infinite set.
701 Out of memory!
703 (X) "elements" $set can generate an "Out of memory!" message on
704 sufficiently large finite sets.
705
707 Traps
708 Beware of forms like
709 union $set [1..5];
711 This passes an element of @set to union, which is probably not what you
713 want. To force interpretation of $set and [1..5] as separate
714 arguments, use forms like
715 union $set +[1..5];
717 or
719 $set->union([1..5]);
721 grep_set and map_set
723 "grep_set" and "map_set" make it easy to construct sets for which the
724 internal representation used by "Set::IntSpan" is not small. Consider:
725 $billion = new Set::IntSpan '0-1_000_000_000'; # OK
727 $odd = grep_set { $_ & 1 } $billion; # trouble
728 $even = map_set { $_ * 2 } $billion; # double trouble
729 Error handling
731 There are two common approaches to error handling: exceptions and
732 return codes. There seems to be some religion on the topic, so
733 "Set::IntSpan" provides support for both.
734 To catch exceptions, protect method calls with an eval:
736 $run_list = <STDIN>;
738 eval { $set = new Set::IntSpan $run_list };
739 $@ and print "$@: try again\n";
740 To check return codes, use an appropriate method call to validate
742 arguments:
743 $run_list = <STDIN>;
745 if (valid Set::IntSpan $run_list)
746 { $set = new Set::IntSpan $run_list }
747 else
748 { print "$@ try again\n" }
749 Similarly, use "finite" to protect calls to "elements":
751 finite $set and @elements = elements $set;
753 Calling "elements" on a large, finite set can generate an "Out of
755 memory!" message, which cannot (easily) be trapped. Applications that
756 must retain control after an error can use "intersect" to protect calls
757 to "elements":
758 @elements = elements { intersect $set "-1_000_000 - 1_000_000" };
760 or check the size of $set first:
762 finite $set and cardinality $set < 2_000_000 and @elements = elements $set;
764 Limitations
766 Although "Set::IntSpan" can represent some infinite sets, it does not
767 perform infinite-precision arithmetic. Therefore, finite elements are
768 restricted to the range of integers on your machine.
769 Extensions
771 Users report that you can construct Set::IntSpan objects on anything
772 that behaves like an integer. For example:
773 $x = new Math::BigInt ...;
775 $set = new Set::Intspan [ [ $x, $x+5 ] ];
776 I'm not documenting this as supported behavior, because I don't have
778 the resources to test it, but I'll try not to break it. If anyone
779 finds problems with it, let me know.
780 Roots
782 The sets implemented here are based on a Macintosh data structure
783 called a region. See Inside Macintosh for more information.
784 "Set::IntSpan" was originally written to manage run lists for the
786 "News::Newsrc" module.
787
789 Steven McDougall <swmcd@world.std.com>
790
792 · Malcolm Cook <mec@stowers-institute.org>
793 · David Hawthorne <dsrthorne@hotmail.com>
795 · Martin Krzywinski <martink@bcgsc.ca>
797 · Marc Lehmann <schmorp@schmorp.de>
799 · Andrew Olson <aolson@me.com>
801 · Nicholas Redgrave <baron@bologrew.net>
803
805 Copyright (c) 1996-2013 by Steven McDougall. This module is free
806 software; you can redistribute it and/or modify it under the same terms
807 as Perl itself.
808perl v5.30.1 2020-01-30 IntSpan(3)