NAME

Set::IntegerRange - Sets of Integers

Easy manipulation of sets of integers (arbitrary intervals)

SYNOPSIS

• use Set::IntegerRange;

• $set = new Set::IntegerRange($lowerbound,$upperbound);

  the set object constructor method

  Note that this method returns undef if the necessary memory cannot be allocated.

• $set = Set::IntegerRange->new($lowerbound,$upperbound);

  alternate way of calling the set object constructor method

• $set2 = $set1->new($lowerbound,$upperbound);

  still another way of calling the set object constructor method ($set1 is not affected by this)

• $set->Empty();

  deletes all elements in the set

• $set->Fill();

  inserts all possible elements into the set

• $set->Insert($index);

  inserts a given element

• $set->Delete($index);

  deletes a given element

• $set->flip($index);

  flips a given element and returns its new value

• $set->in($index);

  tests the presence of a given element

• $set->Norm();

  calculates the norm (number of elements) of the set

• $set->Min();

  returns the minimum of the set ( min({}) := +infinity )

• $set->Max();

  returns the maximum of the set ( max({}) := -infinity )

• $set1->Union($set2,$set3);

  calculates the union of set2 and set3 and stores the result in set1 (in-place is also possible)

• $set1->Intersection($set2,$set3);

  calculates the intersection of set2 and set3 and stores the result in set1 (in-place is also possible)

• $set1->Difference($set2,$set3);

  calculates set2 "minus" set3 ( = set2 \ set3 ) and stores the result in set1 (in-place is also possible)

• $set1->ExclusiveOr($set2,$set3);

  calculates the symmetric difference of set2 and set3 and stores the result in set1 (in-place is also possible)

• $set1->Complement($set2);

  calculates the complement of set2 and stores the result in set1 (in-place is also possible)

• $set1->equal($set2);

  tests if set1 is the same as set2

• $set1->inclusion($set2);

  tests if set1 is contained in set2

• $set1->lexorder($set2);

  tests if set1 comes lexically before set2, i.e., if (set1 <= set2) holds, as though the two bit vectors used to represent the two sets were two large numbers in binary representation

  (Note that this is an arbitrary order relationship!)

• $set1->Compare($set2);

  lexically compares set1 and set2 and returns -1, 0 or 1 if (set1 < set2), (set1 == set2) or (set1 > set2) holds, respectively

  (Again, the two bit vectors representing the two sets are compared as though they were two large numbers in binary representation)

• $set1->Copy($set2);

  copies the contents of set2 to an ALREADY EXISTING set1

• $set1 = $set2->Shadow();

  returns an object reference to a NEW but EMPTY set of the SAME SIZE as set2

• $set1 = $set2->Clone();

  returns an object reference to a NEW set of the SAME SIZE as set2; the contents of set2 have ALREADY BEEN COPIED to the new set

• Hint: method names all in lower case indicate a boolean return value!

Please refer to "OVERLOADED OPERATORS" below for ways of using overloaded operators instead of explicit method calls in order to facilitate calculations with sets!

DESCRIPTION

This class lets you dynamically create sets of arbitrary intervals of integers and perform all the basic operations for sets on them, like

-

adding or removing elements,

-

testing for the presence of a certain element,

-

computing the union, intersection, difference, symmetric difference or complement of sets,

-

copying sets,

-

testing two sets for equality or inclusion, and

-

computing the minimum, the maximum and the norm (number of elements) of a set.

Please refer to Set::IntegerFast(3) for a detailed description of each of the methods mentioned above under SYNOPSIS!

Please refer to "OVERLOADED OPERATORS" below for ways of using overloaded operators instead of explicit method calls in order to facilitate calculations with sets!

Note that the method "Resize()" is not available in this class because extending an existing set at the lower end would require a very inefficient bitwise shift or copy of existing elements.

The method "Version()" is also unavailable in this module.

A method "DESTROY()" is not needed here since the destruction of objects which aren't used anymore is taken care of implicitly and automatically by Perl itself.

Note also that subclassing of this class is not impaired or disabled in any way (in contrast to the "Set::IntegerFast" class).

OVERLOADED OPERATORS

Calculations with sets can not only be performed with explicit method calls using this module, but also through "magical" overloaded arithmetic and relational operators.

For instance, instead of writing

$set1 = Set::IntegerRange->new($lower,$upper);
$set2 = Set::IntegerRange->new($lower,$upper);
$set3 = Set::IntegerRange->new($lower,$upper);

[...]

$set3->Union($set1,$set2);

you can just say

$set1 = Set::IntegerRange->new($lower,$upper);
$set2 = Set::IntegerRange->new($lower,$upper);

[...]

$set3 = $set1 + $set2;

That's all!

Here is the list of all "magical" overloaded operators and their semantics (meaning):

Unary operators: '-', '~', 'abs', testing, '!'

Binary (arithmetic) operators: '+' ('|'), '-', '*' ('&'), '^'

Binary (relational) operators: '==', '!=', '<', '<=', '>', '>='

(semantics are the same as common from set theory)

Binary (relational) operators: 'cmp', 'eq', 'ne', 'lt', 'le', 'gt', 'ge'

(special meaning)

'-'

Unary Minus ( $set2 = -$set1; )

Same as "Complement". See "Complement" below.

'~'

Complement ( $set2 = ~$set1; )

The operator '~' (or unary '-') computes the complement of the given set.

Example:

print( ( $odd == ~$even ) ? "true!\n" : "NOT true!\n" );

abs

Absolute Value ( $norm = abs($set); )

In set theory, the absolute value of a set is defined as the number of elements the given set contains. This is also called the "norm" of the set.

Example:

$set = new Set::IntegerRange(-42,42);
print abs($set), "\n";
$set->Fill();
print abs($set), "\n";

This prints "0" and "85".

test

Boolean Test ( if ($set) { ... } )

You can actually test a set as though it were a boolean value.

No special operator is needed for this; Perl automatically calls the appropriate method in this package if "$set" is a blessed reference to an object of the "Set::IntegerRange" class or one of its derived classes.

This method returns "true" (1) if the given set is not empty and "false" ('') otherwise.

'!'

Negated Boolean Test ( if (! $set) { ... } )

You can also perform a negated test on a set as though it were a boolean value. For example:

if (! $set) { ... }

unless ($set) { ... }     #  internally, same as above!

This operator returns "true" (1) if the given set is empty and "false" ('') otherwise.

'+'

Union ( $set3 = $set1 + $set2; )

The '+' operator is used to denote the union of two sets, as in

$all   =  $odd + $even;

Note that you can also use the assignment form of the '+' operator, i.e.

$all  +=  $odd;
$all  +=  $even;

Even the use of the '++' operator is possible, although it doesn't make much sense:

$set++;

and

++$set;

This inserts element "1" into the set.

If one of the two arguments of the '+' operator is a number, this number is inserted into the set. As the union of two sets is a commutative operation, it doesn't matter wether the left or the right argument is numeric:

$set2  =  $set1 +   5;
$set2  =  $set1 +  -1;
$set2  =    0   + $set1;
$set2  =   -2   + $set1;

or (as before)

$set  +=   5;
$set  +=  -1;
$set  +=   0; # remember that this is element "0", not addition!
$set  +=  -2;

Important Note:

In fact, when you are using a number as one of the two arguments to any of the (binary) overloaded operators in this package, this number denotes the set containing just that single element, i.e. {5}, {-1}, {0}, {-2}. (!)

Except for the '+', '-', '*' and '^' operator, this set (containing just a single element) is explicitly constructed before the requested operation is carried out. (!)

In the case of the '+', '-', '*' and '^' operator, however, this has been optimized so that the "Insert", "Delete" and "flip" method is called directly (complexity of 1) as appropriate, instead of a costly set operation (complexity of n/b).

'-'

Difference ( $set3 = $set1 - $set2; )

In set theory, the difference of two sets is usually denoted by the operator '\', i.e. $primes \ $odd == {2}.

Unfortunately, '\' is not an operator that Perl would recognize as such and allow overloading of, so '-' is used instead.

Again, you have several possible ways of using this operator:

$odd   =  $all  - $even;

$all  -=  $even;

$set2  =  $set1 -   5;
$set2  =  $set1 -  -1;
$set2  =    0   - $set1;
$set2  =   -2   - $set1;

$set  -=   5;
$set  -=  -1;
$set  -=   0;
$set  -=  -2;

$set--;
--$set;

Note that $set2 = -2 - $set1; for instance will yield either {} or {-2} for $set2, depending on wether "-2" is contained in $set1 or not, because this statement is equivalent to $set2 = {-2} \ $set1;!

Note also that $set--; and --$set; just removes element "1" from the set.

'*'

Intersection ( $set3 = $set1 * $set2; )

The '*' operator is used to denote the intersection of two sets.

Again, you have several possibilities of using this operator:

$two     =  $primes * $even;

$primes *=  $even;

$set2    =  $set1 *   5;
$set2    =  $set1 *  -1;
$set2    =    0   * $set1;
$set2    =   -2   * $set1;

$set    *=   5;
$set    *=  -1;
$set    *=   0;
$set    *=  -2;

'^'

ExclusiveOr ( $set3 = $set1 ^ $set2; )

(= "Symmetric Difference")

The '^' operator is used to denote the "exclusive-or" or symmetric difference of two sets.

In fact this operation can be expressed in terms of the union, intersection and difference of two sets as follows:

$xor = ( $set1 + $set2 ) - ( $set1 * $set2 );

(Verify it!)

print( ( $set1 ^ $set2 ) == ( ( $set1 + $set2 ) - ( $set1 * $set2 ) ) ?
    "true!\n" : "NOT true!\n" );

Providing an explicit operator for this operation is advantageous, though, because it uses a built-in machine language instruction internally, which is much faster than evaluating the above expression.

You have the following alternatives for using this operator:

$odd   =  $all  ^ $even;

$all  ^=  $even;

$set2  =  $set1 ^   5;
$set2  =  $set1 ^  -1;
$set2  =    0   ^ $set1;
$set2  =   -2   ^ $set1;

$set  ^=   5;
$set  ^=  -1;
$set  ^=   0;
$set  ^=  -2;

'=='

Test For Equality ( if ($set1 == $set2) { ... } )

This operator tests two sets for equality.

Note that without operator overloading, ( $set1 == $set2 ) would test wether the two references pointed to the same object! (!)

With operator overloading in effect, ( $set1 == $set2 ) tests wether the two set objects contain exactly the same elements!

Example:

$set1 = new Set::IntegerRange(-42,42);
$set2 = new Set::IntegerRange(-42,42);

&test( $set1, $set2 );

$set2 = $set1;

&test( $set1, $set2 );

exit;

sub test
{
    my($set1,$set2) = @_;

    $set1->Empty();
    $set2->Empty();

    for ( $i = -42; $i <= 42; $i += 5 )
    {
        $set1 += $i;
        $set2 += $i;
    }

    print( ( $set1 == $set2 ) ?
        "sets are the same\n" : "references are NOT the same\n" );

    $set1 ^= -42;

    print( ( $set1 == $set2 ) ?
        "objects are the same\n" : "objects are NOT the same\n" );
}

At the first call of "&test(...);" above, this will either print "sets are the same" or "references are NOT the same", depending on wether the '==' operator is overloaded or not, respectively.

It will also print "objects are NOT the same" in either case because (at that time) the two references as well as the contents of the two sets differ.

At the second call of "&test(...);" above, "sets are the same" will be printed in either case because the two references point to the same object (therefore, '==' evaluates to "true" if operator overloading is not in effect) or the two objects pointed to by the two references have the same contents, and so '==' also evaluates to "true" if operator overloading is in effect.

(There a actually two distinct objects involved here if operator overloading is in effect, for reasons explained further below!)

Depending on wether operator overloading is in effect or not, this will then print "objects are NOT the same" or "objects are the same", respectively.

This is easy to understand when operator overloading is not in effect because then the two references point to the same object, so changing one of the two objects also changes the other. So the two references as well as the contents of the two sets (which really are only one!) are the same.

If operator overloading is in effect, though, matters are a bit more complicated: When there are two or more references pointing to the same object, and an attempt is made to change that object via the assignment variant of one of the overloaded operators using one of the references pointing to that object, a clone copy of the object in question is created first and the reference pointing to this clone copy is assigned to the variable which held the reference to the original object, before the requested operation is finally carried out on the clone copy of the original object!

Example:

$b = new Set::IntegerRange($lower,$upper);
$c = new Set::IntegerRange($lower,$upper);

[...]

$a = $b;

[...]

$a += $c;

Before the statement $a += $c; actually gets executed, the following code is executed internally:

$temp = $a->new($lower,$upper); # creates an empty new set of same size
$temp->Copy($a);                # copies the contents to the new set
$a = $temp;                     # assigns the new reference to $a
undef $temp;

This means that after the statement $a += $c;, $a effectively points to a different set than $b!

And probably (depending on $c) the contents of the two sets $a and $b also differ! (Because the set pointed to by $b remains unaffected by the operation performed on $a!)

This mechanism is intended to avoid (almost certainly) unwanted side effects.

You can also regard this as a delayed ("lazy") form of execution of the object copy operation you probably intended when writing $a = $b;!

This means that when the first $set1 += $i; is executed in the body of the loop in the "test" subroutine above, $set1 gets assigned a clone copy of $set2. This means that from that point on, $set1 and $set2 contain different references to different objects!

(With the same contents, however, at first!)

Only when the statement $set1 ^= -42; (above) gets executed this becomes apparent, however.

'!='

Test For Non-Equality ( if ($set1 != $set2) { ... } )

This operator tests wether two sets are different.

Note again that this tests wether the contents of the two sets are not the same, and not wether the two references are different!

'<'

Test For True Subset ( if ($set1 < $set2) { ... } )

This operator tests wether $set1 is a true subset of $set2, i.e. wether all elements contained in $set1 are also contained in $set2, but not all elements contained in $set2 are contained in $set1.

'<='

Test For Subset ( if ($set1 <= $set2) { ... } )

This operator tests wether $set1 is a subset of $set2, i.e. wether all elements contained in $set1 are also contained in $set2.

This also evaluates to "true" when the two sets contain exactly the same elements, i.e. when the two sets are equal.

'>'

Test For True Superset ( if ($set1 > $set2) { ... } )

This operator tests wether $set1 is a true superset of $set2, i.e. wether all elements contained in $set2 are also contained in $set1, but not all elements contained in $set1 are contained in $set2.

Note that ($set1 > $set2) is exactly the same as ($set2 < $set1).

'>='

Test For Superset ( if ($set1 >= $set2) { ... } )

This operator tests wether $set1 is a superset of $set2, i.e. wether all elements contained in $set2 are also contained in $set1.

This also evaluates to "true" when the two sets contain exactly the same elements, i.e. when the two sets are equal.

Note that ($set1 >= $set2) is exactly the same as ($set2 <= $set1).

cmp

Compare ( $result = $set1 cmp $set2; )

This operator compares the two sets lexically, i.e. it regards the two bit vectors representing the two sets as two large (unsigned) numbers in binary representation and returns "-1" if the number for $set1 is smaller than that for $set2, "0" if the two numbers are the same (i.e., when the two sets are equal!) or "1" if the number representing $set1 is larger than the number representing $set2.

Note that this comparison has nothing to do whatsoever with set theory, it is just an arbitrary order relationship!

It is only intended to provide an (arbitrary) order by which (for example) an array of sets can be sorted, for instance to find out quickly (using binary search) if a specific set has already been produced before in some set-producing process or not.

eq

"equal"

ne

"not equal"

lt

"less than"

le

"less than or equal"

gt

"greater than"

ge

"greater than or equal"

These are all operators derived from the "cmp" operator (see above).

They can be used instead of the "cmp" operator to make the intended type of comparison more obvious in your code.

For instance, ($set1 le $set2) is much more readable and clearer than (($set1 cmp $set2) <= 0)!

SEE ALSO

Set::IntegerFast(3), Math::MatrixBool(3), Math::MatrixReal(3), DFA::Kleene(3), Kleene(3), Graph::Kruskal(3).

VERSION

This man page documents Set::IntegerRange version 2.0.

AUTHOR

Steffen Beyer <sb@sdm.de> (sd&m GmbH&Co.KG, Munich, Germany)

COPYRIGHT

Copyright (c) 1996, 1997 by Steffen Beyer. All rights reserved.

LICENSE AGREEMENT

This package is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

cpanm Getopt::Long

perl -MCPAN -e shell
install Getopt::Long