Sets of intervals
use Set::Infinite; $set = Set::Infinite->new(1,2); # [1..2] print $set->union(5,6); # [1..2],[5..6]
Set::Infinite is a Set Theory module for infinite sets.
A set is a collection of objects. The objects that belong to a set are called its members, or \*(L"elements\*(R".
As objects we allow (almost) anything: reals, integers, and objects (such as dates).
We allow sets to be infinite.
There is no account for the order of elements. For example, {1,2} = {2,1}.
There is no account for repetition of elements. For example, {1,2,2} = {1,1,1,2} = {1,2}.
\$1
Creates a new set object:
$set = Set::Infinite->new; # empty set $set = Set::Infinite->new( 10 ); # single element $set = Set::Infinite->new( 10, 20 ); # single range $set = Set::Infinite->new( [ 10, 20 ], [ 50, 70 ] ); # two ranges
$set = Set::Infinite->new;
$set = Set::Infinite->new( 10 );
$set = Set::Infinite->new( [ 10 ] );
$set = Set::Infinite->new( 10, 20 );
$set = Set::Infinite->new( [ 10, 20 ] ); # 10 <= x <= 20
$set = Set::Infinite->new( { a => 10, open_begin => 0, b => 20, open_end => 1, } ); # 10 <= x < 20
$set = Set::Infinite->new( 10, 20, 100, 200 );
$set = Set::Infinite->new( [ 10, 20 ], [ 100, 200 ] );
$set = Set::Infinite->new( { a => 10, open_begin => 0, b => 20, open_end => 0, }, { a => 100, open_begin => 0, b => 200, open_end => 0, } );
The \*(C`new()\*(C' method expects ordered parameters.
If you have unordered ranges, you can build the set using \*(C`union\*(C':
@ranges = ( [ 10, 20 ], [ -10, 1 ] ); $set = Set::Infinite->new; $set = $set->union( @$_ ) for @ranges;
The data structures passed to \*(C`new\*(C' must be immutable. So this is not good practice:
$set = Set::Infinite->new( $object_a, $object_b ); $object_a->set_value( 10 );
This is the recommended way to do it:
$set = Set::Infinite->new( $object_a->clone, $object_b->clone ); $object_a->set_value( 10 ); Creates a new object, and copy the object data. Creates an empty set.
If called from an existing set, the empty set inherits the \*(L"type\*(R" and \*(L"density\*(R" characteristics. Creates a set containing \*(L"all\*(R" possible elements.
If called from an existing set, the universal set inherits the \*(L"type\*(R" and \*(L"density\*(R" characteristics.
$set = $set->union($b);
Returns the set of all elements from both sets.
This function behaves like an \*(L"\s-1OR\s0\*(R" operation.
$set1 = new Set::Infinite( [ 1, 4 ], [ 8, 12 ] ); $set2 = new Set::Infinite( [ 7, 20 ] ); print $set1->union( $set2 ); # output: [1..4],[7..20] $set = $set->intersection($b);
Returns the set of elements common to both sets.
This function behaves like an \*(L"\s-1AND\s0\*(R" operation.
$set1 = new Set::Infinite( [ 1, 4 ], [ 8, 12 ] ); $set2 = new Set::Infinite( [ 7, 20 ] ); print $set1->intersection( $set2 ); # output: [8..12] $set = $set->complement;
Returns the set of all elements that don't belong to the set.
$set1 = new Set::Infinite( [ 1, 4 ], [ 8, 12 ] ); print $set1->complement; # output: (-inf..1),(4..8),(12..inf)
The complement function might take a parameter:
$set = $set->minus($b);
Returns the set-difference, that is, the elements that don't belong to the given set.
$set1 = new Set::Infinite( [ 1, 4 ], [ 8, 12 ] ); $set2 = new Set::Infinite( [ 7, 20 ] ); print $set1->minus( $set2 ); # output: [1..4] Returns a set containing elements that are in either set, but not in both. This is the \*(L"set\*(R" version of \*(L"\s-1XOR\s0\*(R".
$set1 = $set->real;
Returns a set with density \*(L"0\*(R". $set1 = $set->integer;
Returns a set with density \*(L"1\*(R".
$logic = $set->intersects($b); $logic = $set->contains($b); $logic = $set->is_null; This set that has at least 1 element. This set that has a single span or interval. This set that has a single element. Every element of this set is a member of the given set. Every element of this set is a member of the given set. Some members of the given set are not elements of this set. The given set has no elements in common with this set. Sometimes a set might be too complex to enumerate or print.
This happens with sets that represent infinite recurrences, such as when you ask for a quantization on a set bounded by -inf or inf.
See also: \*(C`count\*(C' method.
$i = $set->min; $i = $set->max; $i = $set->size; $i = $set->count;
print $set;
$str = "$set";
See also: \*(C`as_string\*(C'. sort
> < == >= <= <=>
See also: \*(C`spaceship\*(C' method.
Set::Infinite->separators(@i)
chooses the interval separators for stringification.
default are [ ] ( ) '..' ','.
inf
returns an 'Infinity' number.
minus_inf
returns '-Infinity' number. type( "My::Class::Name" )
Chooses a default object data type.
Default is none (a normal Perl \s-1SCALAR\s0).
$set1 = $set->span;
Returns the set span. Extends a set until another:
0,5,7 -> until 2,6,10
gives
[0..2), [5..6), [7..10) These methods do the inverse of the \*(L"until\*(R" method.
Given:
[0..2), [5..6), [7..10)
start_set is:
0,5,7
end_set is:
2,6,10 $set = $set1->intersected_spans( $set2 );
The method returns a new set, containing all spans that are intersected by the given set.
Unlike the \*(C`intersection\*(C' method, the spans are not modified. See diagram below:
set1 [....] [....] [....] [....] set2 [................]
intersection [.] [....] [.]
intersected_spans [....] [....] [....] quantize( parameters )
Makes equal-sized subsets.
Returns an ordered set of equal-sized subsets.
Example:
$set = Set::Infinite->new([1,3]); print join (" ", $set->quantize( quant => 1 ) );
Gives:
[1..2) [2..3) [3..4) select( parameters )
Selects set spans based on their ordered positions
\*(C`select\*(C' has a behaviour similar to an array \*(C`slice\*(C'.
by - default=All count - default=Infinity
0 1 2 3 4 5 6 7 8 # original set 0 1 2 # count => 3 1 6 # by => [ -2, 1 ] offset ( parameters )
Offsets the subsets. Parameters:
value - default=[0,0] mode - default='offset'. Possible values are: 'offset', 'begin', 'end'. unit - type of value. Can be 'days', 'weeks', 'hours', 'minutes', 'seconds'. iterate ( sub { } , @args )
Iterates on the set spans, over a callback subroutine. Returns the union of all partial results.
The callback argument $_[0] is a span. If there are additional arguments they are passed to the callback.
The callback can return a span, a hashref (see \*(C`Set::Infinite::Basic\*(C'), a scalar, an object, or \*(C`undef\*(C'.
[\s-1EXPERIMENTAL\s0] \*(C`iterate\*(C' accepts an optional \*(C`backtrack_callback\*(C' argument. The purpose of the \*(C`backtrack_callback\*(C' is to reverse the iterate() function, overcoming the limitations of the internal backtracking algorithm. The syntax is:
iterate ( sub { } , backtrack_callback => sub { }, @args )
The \*(C`backtrack_callback\*(C' can return a span, a hashref, a scalar, an object, or \*(C`undef\*(C'.
For example, the following snippet adds a constant to each element of an unbounded set:
$set1 = $set->iterate( sub { $_[0]->min + 54, $_[0]->max + 54 }, backtrack_callback => sub { $_[0]->min - 54, $_[0]->max - 54 }, ); first / last
In scalar context returns the first or last interval of a set.
In list context returns the first or last interval of a set, and the remaining set (the 'tail').
See also: \*(C`min\*(C', \*(C`max\*(C', \*(C`min_a\*(C', \*(C`max_a\*(C' methods. type( "My::Class::Name" )
Chooses a default object data type.
default is none (a normal perl \s-1SCALAR\s0).
$set->_backtrack( 'intersection', $b );
Internal function to evaluate recurrences. $set->numeric;
Internal function to ignore the set \*(L"type\*(R". It is used in some internal optimizations, when it is possible to use scalar values instead of objects. $set->fixtype;
Internal function to fix the result of operations that use the numeric() function. $set = $set->tolerance(0) # defaults to real sets (default) $set = $set->tolerance(1) # defaults to integer sets
Internal function for changing the set \*(L"density\*(R". ($min, $min_is_open) = $set->min_a; ($max, $max_is_open) = $set->max_a; Implements the \*(L"stringification\*(R" operator.
Stringification of unbounded recurrences is not implemented.
Unbounded recurrences are stringified as \*(L"function descriptions\*(R", if the class variable $PRETTY_PRINT is set. Implements the \*(L"comparison\*(R" operator.
Comparison of unbounded recurrences is not implemented.
constructor \*(L"span\*(R" notation $set = Set::Infinite->new(10,1); Will be interpreted as [1..10]
constructor \*(L"multiple-span\*(R" notation $set = Set::Infinite->new(1,2,3,4); Will be interpreted as [1..2],[3..4] instead of [1,2,3,4]. You probably want ->new([1],[2],[3],[4]) instead, or maybe ->new(1,4)
\*(L"range operator\*(R" $set = Set::Infinite->new(1..3); Will be interpreted as [1..2],3 instead of [1,2,3]. You probably want ->new(1,3) instead.
The base set object, without recurrences, is a \*(C`Set::Infinite::Basic\*(C'.
A recurrence-set is represented by a method name, one or two parent objects, and extra arguments. The \*(C`list\*(C' key is set to an empty array, and the \*(C`too_complex\*(C' key is set to 1.
This is a structure that holds the union of two \*(L"complex sets\*(R":
{ too_complex => 1, # "this is a recurrence" list => [ ], # not used method => 'union', # function name parent => [ $set1, $set2 ], # "leaves" in the syntax-tree param => [ ] # optional arguments for the function }
This is a structure that holds the complement of a \*(L"complex set\*(R":
{ too_complex => 1, # "this is a recurrence" list => [ ], # not used method => 'complement', # function name parent => $set, # "leaf" in the syntax-tree param => [ ] # optional arguments for the function }
See modules DateTime::Set, DateTime::Event::Recurrence, DateTime::Event::ICal, DateTime::Event::Cron for up-to-date information on date-sets.
The perl-date-time project <http://datetime.perl.org>
Flavio S. Glock <[email protected]>
Copyright (c) 2003 Flavio Soibelmann Glock. All rights reserved. This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
The full text of the license can be found in the \s-1LICENSE\s0 file included with this module.