Set::Infinite(3) 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]

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

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

    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)

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]);
            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 $_[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
  }

AUTHOR

Flavio S. Glock <[email protected]>

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.