Set::Infinite - Sets of intervals

# NAME

Set::Infinite - Sets of intervals

# SYNOPSIS

`  use Set::Infinite;`
```  \$set = Set::Infinite->new(1,2);    # [1..2]
print \$set->union(5,6);            # [1..2],[5..6]```

# 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 ] );
print \$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 ] );
print \$set1->intersection( \$set2 );
# output: [8..12]```

## 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 ] );
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]```

## simmetric_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_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

`    print \$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)`

## 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]);
print 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 `\$_` 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 { \$_->min + 54, \$_->max + 54 },
backtrack_callback =>
sub { \$_->min - 54, \$_->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(,,,)` 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 Soibelmann Glock <fglock@pucrs.br>

# 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.

 Set::Infinite - Sets of intervals