NAME
Set::Infinite - Sets of intervals
SYNOPSIS
DESCRIPTION
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 "elements".
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}.
CONSTRUCTOR
new
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
- empty set
-
$set
= Set::Infinite->new;
- set with a single element
-
$set
= Set::Infinite->new( 10 );
$set
= Set::Infinite->new( [ 10 ] );
- set with a single span
-
$set
= Set::Infinite->new( 10, 20 );
$set
= Set::Infinite->new( [ 10, 20 ] );
# 10 <= x <= 20
- set with a single, open span
-
$set
= Set::Infinite->new(
{
a
=> 10,
open_begin
=> 0,
b
=> 20,
open_end
=> 1,
}
);
# 10 <= x < 20
- set with multiple spans
-
$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 new()
method expects ordered parameters.
If you have unordered ranges, you can build the set using union
:
@ranges
= ( [ 10, 20 ], [ -10, 1 ] );
$set
= Set::Infinite->new;
$set
=
$set
->union(
@$_
)
for
@ranges
;
The data structures passed to new
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 );
clone / copy
Creates a new object, and copy the object data.
empty_set
Creates an empty set.
If called from an existing set, the empty set inherits the "type" and "density" characteristics.
universal_set
Creates a set containing "all" possible elements.
If called from an existing set, the universal set inherits the "type" and "density" characteristics.
SET FUNCTIONS
union
$set
=
$set
->union(
$b
);
Returns the set of all elements from both sets.
This function behaves like an "OR" operation.
$set1
= new Set::Infinite( [ 1, 4 ], [ 8, 12 ] );
$set2
= new Set::Infinite( [ 7, 20 ] );
$set1
->union(
$set2
);
# output: [1..4],[7..20]
intersection
$set
=
$set
->intersection(
$b
);
Returns the set of elements common to both sets.
This function behaves like an "AND" operation.
$set1
= new Set::Infinite( [ 1, 4 ], [ 8, 12 ] );
$set2
= new Set::Infinite( [ 7, 20 ] );
$set1
->intersection(
$set2
);
# output: [8..12]
complement
minus
difference
$set
=
$set
->complement;
Returns the set of all elements that don't belong to the set.
$set1
= new Set::Infinite( [ 1, 4 ], [ 8, 12 ] );
$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 ] );
$set1
->minus(
$set2
);
# output: [1..4]
symmetric_difference
Returns a set containing elements that are in either set, but not in both. This is the "set" version of "XOR".
DENSITY METHODS
real
$set1
=
$set
->real;
Returns a set with density "0".
integer
$set1
=
$set
->integer;
Returns a set with density "1".
LOGIC FUNCTIONS
intersects
$logic
=
$set
->intersects(
$b
);
contains
$logic
=
$set
->contains(
$b
);
is_empty
is_null
$logic
=
$set
->is_null;
is_nonempty
This set that has at least 1 element.
is_span
This set that has a single span or interval.
is_singleton
This set that has a single element.
is_subset( $set )
Every element of this set is a member of the given set.
is_proper_subset( $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.
is_disjoint( $set )
The given set has no elements in common with this set.
is_too_complex
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: count
method.
SCALAR FUNCTIONS
min
$i
=
$set
->min;
max
$i
=
$set
->max;
size
$i
=
$set
->size;
count
$i
=
$set
->count;
OVERLOADED OPERATORS
stringification
$set
;
$str
=
"$set"
;
See also: as_string
.
comparison
sort
> < == >= <= <=>
See also: spaceship
method.
CLASS METHODS
Set::Infinite->separators(
@i
)
chooses the interval separators
for
stringification.
default
are [ ] ( )
'..'
','
.
inf
returns an
'Infinity'
number.
minus_inf
returns
'-Infinity'
number.
type
type(
"My::Class::Name"
)
Chooses a default object data type.
Default is none (a normal Perl SCALAR).
SPECIAL SET FUNCTIONS
span
$set1
=
$set
->span;
Returns the set span.
until
Extends a set until another:
0,5,7 ->
until
2,6,10
gives
[0..2), [5..6), [7..10)
start_set
end_set
These methods do the inverse of the "until" method.
Given:
[0..2), [5..6), [7..10)
start_set is:
0,5,7
end_set is:
2,6,10
intersected_spans
$set
=
$set1
->intersected_spans(
$set2
);
The method returns a new set, containing all spans that are intersected by the given set.
Unlike the intersection
method, the spans are not modified. See diagram below:
set1 [....] [....] [....] [....]
set2 [................]
intersection [.] [....] [.]
intersected_spans [....] [....] [....]
quantize
quantize( parameters )
Makes equal-sized subsets.
Returns an ordered set of equal-sized subsets.
Example:
$set
= Set::Infinite->new([1,3]);
join
(
" "
,
$set
->quantize(
quant
=> 1 ) );
Gives:
[1..2) [2..3) [3..4)
select
select
( parameters )
Selects set spans based on their ordered positions
select
has a behaviour similar to an array slice
.
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
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
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 Set::Infinite::Basic
), a scalar, an object, or undef
.
[EXPERIMENTAL] iterate
accepts an optional backtrack_callback
argument. The purpose of the backtrack_callback
is to reverse the iterate() function, overcoming the limitations of the internal backtracking algorithm. The syntax is:
iterate (
sub
{ } ,
backtrack_callback
=>
sub
{ },
@args
)
The backtrack_callback
can return a span, a hashref, a scalar, an object, or undef
.
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
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: min
, max
, min_a
, max_a
methods.
type
type(
"My::Class::Name"
)
Chooses a default object data type.
default is none (a normal perl SCALAR).
INTERNAL FUNCTIONS
_backtrack
$set
->_backtrack(
'intersection'
,
$b
);
Internal function to evaluate recurrences.
numeric
$set
->numeric;
Internal function to ignore the set "type". It is used in some internal optimizations, when it is possible to use scalar values instead of objects.
fixtype
$set
->fixtype;
Internal function to fix the result of operations that use the numeric() function.
tolerance
$set
=
$set
->tolerance(0)
# defaults to real sets (default)
$set
=
$set
->tolerance(1)
# defaults to integer sets
Internal function for changing the set "density".
min_a
(
$min
,
$min_is_open
) =
$set
->min_a;
max_a
(
$max
,
$max_is_open
) =
$set
->max_a;
as_string
Implements the "stringification" operator.
Stringification of unbounded recurrences is not implemented.
Unbounded recurrences are stringified as "function descriptions", if the class variable $PRETTY_PRINT is set.
spaceship
Implements the "comparison" operator.
Comparison of unbounded recurrences is not implemented.
CAVEATS
constructor "span" notation
$set
= Set::Infinite->new(10,1);
Will be interpreted as [1..10]
constructor "multiple-span" 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)
"range operator"
$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.
INTERNALS
The base set object, without recurrences, is a Set::Infinite::Basic
.
A recurrence-set is represented by a method name, one or two parent objects, and extra arguments. The list
key is set to an empty array, and the too_complex
key is set to 1
.
This is a structure that holds the union of two "complex sets":
{
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 "complex set":
{
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 ALSO
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>
AUTHOR
Flavio S. Glock <fglock@gmail.com>
COPYRIGHT
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 LICENSE file included with this module.