NAME

Set::IntegerFast - Sets of Integers

Easy and efficient manipulation of sets of integers (intervals from zero to some positive integer)

SYNOPSIS

use Set::IntegerFast;
$ver = Set::IntegerFast::Version();

returns the version number
$set = Set::IntegerFast::new('Set::IntegerFast',$elements);

the set object constructor method

(this way of calling the set object constructor method is deprecated, though, because it is error-prone and specifying the name of the class twice is unnecessary!)
$class = 'Set::IntegerFast'; $set = Set::IntegerFast::new($class,$elements);

(alternate way of calling the set object constructor)

(also deprecated)
$set = new Set::IntegerFast($elements);

(alternate way of calling the set object constructor)
$set = new Set::IntegerFast $elements;

(same as before, but without the parentheses)

(recommended)
$set = Set::IntegerFast->new($elements);

(alternate way of calling the set object constructor)

(recommended)
$set1 = Set::IntegerFast->new($elem1); $set2 = $set1->new($elem2);

(alternate way of calling the set object constructor)

(leaves the first set object intact)
$set = Set::IntegerFast->new($elem1); $set = $set->new($elem2);

(alternate way of calling the set object constructor)

(destroys the first set object, however)
$set->DESTROY();

destroys the set and releases the memory occupied by it

(Note that you don't need to call this method explicitly - Perl will do it automatically for you when the last reference to your set is deleted, for instance through assigning a different value to the Perl variable containing the reference to your set, like in "$set = 0;")
$set->Resize($elements);

changes the size of the given set
$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 set2 to set1
Hint: method names all in lower case indicate a boolean return value!

DESCRIPTION

This module allows you to create sets of arbitrary size (only limited by the size of a machine word and available memory on your system) of an interval of positive integers starting with zero, to dynamically change the size of such sets and to 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.

Note that it is extremely easy to implement sets of arbitrary intervals of integers using this module (negative indices are no obstacle), despite the fact that only intervals of positive integers (from zero to some positive integer) are supported directly.

Please refer to "ARBITRARY SETS" below to see how this can be done!

The module is mainly intended for mathematical or algorithmical computations. There are also a number of efficient algorithms that rely on sets.

An example of such an efficient algorithm (which uses a different representation for sets than this module, however) is Kruskal's algorithm for minimal spanning trees in graphs. (That algorithm is included in this distribution as a Perl module for those interested. Please refer to Graph::Kruskal(3) for more details!)

Another famous algorithm using sets is the "Seave of Erathostenes" for calculating prime numbers, which is included here as a demo program (see "primes.pl").

An important field of application is the computation of "first", "follow" and "look-ahead" character sets for the construction of LL, SLR, LR and LALR parsers for compilers (or a compiler-compiler, like "yacc", for instance).

(That's what the C library in this package was initially written for)

(See Aho, Hopcroft, Ullman, "The Design and Analysis of Computer Algorithms" for an excellent book on efficient algorithms and the famous "Dragon Book" on how to build compilers by Aho, Sethi, Ullman)

Therefore, this module is primarily designed for efficiency and not for a comfortable user interface (the latter can be added by additional modules, as shown by the "Set::IntegerRange" and "Math::MatrixBool" modules).

It only offers a basic functionality and leaves it up to your application to add whatever special handling it needs (for example, negative indices can be realized by biasing the whole range with an offset).

(Please refer to "ARBITRARY SETS" below and the "Set::IntegerRange" module in this package to see how!)

Sets in this package are implemented as bit vectors, and elements are positive integers from zero to the maximum number of elements (which you specify when creating the set) minus one.

Each element (i.e., number or "index") thus corresponds to one bit in the bit array. Bit number 0 of word number 0 corresponds to element number 0, element number 1 corresponds to bit number 1 of word number 0, and so on.

The module doesn't use bytes as basic storage unit, it rather uses machine words, assuming that a machine word is the most efficiently handled size of all scalar types on any machine (that's what the C standard proposes and assumes anyway).

In order to achieve this, it automatically determines the number of bits in a machine word on your system and then adjusts its internal constants accordingly.

The greater the size of this basic storage unit, the better the complexity of the methods in this module (but also the greater the average waste of unused bits in the last word).

See "COMPLEXITY" in this man page for an overview of the complexity of each method!

Note that the C library in this package (lib_set.c) is designed in such a way that it may be used independently from Perl and this Perl extension module. (!)

For this, you can use the file lib_set.o exactly as it is produced when building this module! It contains no references to Perl, and it doesn't need any Perl header files in order to compile. (It only needs lib_defs.h and some system header files)

Note however that this C library does not perform any bounds checking whatsoever! (This is left to your application!)

(See the corresponding explanation in the file lib_set.c for more details and the file IntegerFast.xs for an example of how this can be done!)

In this module, all bounds and type checking (which should be absolutely fool-proof, by the way!) is done in the XS subroutines.

ARBITRARY SETS

All that is required - given that "$lowerbound" and "$upperbound" contain the lower and upper limits, respectively, of the range of integers you want to cover with your set - is that you use

$set = new Set::IntegerFast($upperbound - $lowerbound + 1);
$set->Insert($index - $lowerbound);
$set->Delete($index - $lowerbound);
$set->flip($index - $lowerbound);
$set->in($index - $lowerbound);
$temp = $set->Min(); (($temp >= 0) && ($temp <= ($upperbound - $lowerbound))) ? ($temp + $lowerbound) : $temp;
$temp = $set->Max(); (($temp >= 0) && ($temp <= ($upperbound - $lowerbound))) ? ($temp + $lowerbound) : $temp;

(where "$index" is an integer in the range [$lowerbound..$upperbound])

instead of

$set = new Set::IntegerFast($elements);
$set->Insert($index);
$set->Delete($index);
$set->flip($index);
$set->in($index);
$set->Min();
$set->Max();

(where "$index" is an integer in the range [0..$elements-1])

It's as simple as that!

Note that if you don't want to go through the hassle ;-) of handling this yourself, you can use the "Set::IntegerRange" module in this package which provides exactly the same methods as this module (except for "Resize()", however), which stores the lower and upper limits along with a given set and provides the necessary translation as shown above.

Please refer to Set::IntegerRange(3) for more details!

Please refer to Math::MatrixBool(3) for yet another example on how to incorporate this module in your own applications!

DETAILS

$ver = Set::IntegerFast::Version();

This function returns a string with the (numeric) version number of the "Set::IntegerFast" extension package.

Since this function is not exported, you always have to qualify it explicitly (i.e., "Set::IntegerFast::Version()").

This is to avoid possible conflicts with version functions from other packages.
$set = new Set::IntegerFast($elements);

This is the set object constructor method.

Call this method to create a new set object able to contain "$elements" elements (all integers in the range [0..$elements-1]).

The method returns a reference to the newly created set object.

This set object is always initialized to an empty set.

Beware that every time you pass a reference to one of the other methods in this package it is checked if it's "blessed" (see the perlref(1), perlobj(1) and perlbot(1) man pages for more details on blessed references) into the right class (i.e., this package).

An error message occurs if the reference is not one that has been returned by this "Set::IntegerFast" object constructor method.

(See also "SUBCLASSING (INHERITANCE)" in this man page for more details on this subject!)

Note that this method returns the value "undef" if you try to create a set object with zero elements. This also occurs when the method is unable to allocate the necessary memory using "malloc()".

Any attempt to use such a "reference" either results in a warning about the use of an uninitialized value (if the -w switch is set) or an error message with program abortion if you try to invoke a method with it.

Note also that if you specify a negative number for "$elements" it will be interpreted as a large positive number due to its internal 2's complement binary representation and the set object constructor method will attempt to create a set of that size, probably resulting in an "out of memory" error message and program abortion.
$set->DESTROY();

This is the set object destructor method. It destroys the given set and releases the memory occupied by it.

Note that you don't need to call this method explicitly - Perl will do it automatically for you when the last reference to your set is deleted, for instance through assigning a different value to the Perl variable containing the reference to your set, like in "$set = 0;")

Note also that once you have called the destructor method explicitly, your Perl variable ("$set" in this example) no longer contains a valid set object reference. Any attempt to invoke a method with that variable after the set has been DESTROYed will result in an "Set::IntegerFast::<method>(): not a 'Set::IntegerFast' object reference in ..." error and program abortion.

(This will also happen if you inadvertently invoke "DESTROY" twice for the same object!)

Therefore, it is recommended to NEVER call this method explicitly!

Use "$set = 0;" or "undef $set;" (or the like) instead!

Note however that keeping copies of the reference prevents the destruction of the set object to take place until the last copy of the reference has also been deleted:
```
$set = new Set::IntegerFast(1000);
...
$ref = $set;
...
$set = 0;    # set object is NOT destroyed yet!
...
$ref = 0;    # NOW the set object gets killed!
```
$set->Resize($elements);

This method allows you to change the size of an existing set, keeping as many of the elements contained in it as will fit into the new set (i.e., all elements which are smaller than the minimum of the old maximum number of elements and the new maximum number of elements).

If the number of machine words needed to store the given maximum number of elements of the new set is smaller than or equal to the number of words needed to store the old set, the memory already allocated for the old set is kept and simply adjusted to hold the new set.

This means that even if the maximum number of elements increases, this does not necessarily mean that new memory needs to be allocated (if the old and the new maximum number of elements fit into the same number of machine words)!

If the number of machine words needed to store the given maximum number of elements of the new set is greater than the number of words needed to store the old set, new memory is allocated for the new set, the old set is copied to the new one and the old set is deleted, i.e., the memory allocated for it is freed.

This also means that if you decrease the size of a given set so that it will use fewer machine words, and increase it again later so that it will use more words than the downsized set but still less than the original set, new memory will be allocated anyway because the information about the size of the original set is lost when you downsize it.

When the maximum number of elements is increased (regardless of wether the number of machine words used to store the new set increases or stays the same), the new elements are all initialized to zero, i.e., they are not contained in the new set.

This does not affect those elements that have been copied from the old to the new set, of course.

Beware that when you invert the meaning of contained/not contained in your calculations (which you are free to do, of course), i.e., when you are calculating the complement of the set you're actually interested in, increasing the size of your set might not yield the result you'd expect!

I.e., doing this will not work as intended:
```
$set = Set::IntegerFast::Create(1000);
$set->Insert(0);
$set->Insert(1);
for ( $j = 4; $j <= $limit; $j += 2 ) { $set->Insert($j); }
for ( $i = 3; ($j = $i * $i) <= $limit; $i += 2 )
{
    for ( ; $j <= $limit; $j += $i ) { $set->Insert($j); }
}
$set->Resize(100000);
```
This calculates the prime numbers up to 1000 and then increases the size of the set to 100000. However, since the original set contains all the NON-prime numbers, increasing the size of the set ends up with a mess: if an element below 1000 is not contained in the set, it's a prime number, whereas all the numbers between 1000 and 100000 (which are not contained in the set due to the initialization of the new elements) may or may not be prime numbers.

If you calculate the set of primes instead and then increase the size of the set, there is no interpretation conflict:
```
$set = Set::IntegerFast::Create(1000);
$set->Fill();
$set->Delete(0);
$set->Delete(1);
for ( $j = 4; $j <= $limit; $j += 2 ) { $set->Delete($j); }
for ( $i = 3; ($j = $i * $i) <= $limit; $i += 2 )
{
    for ( ; $j <= $limit; $j += $i ) { $set->Delete($j); }
}
$set->Resize(100000);
```
In this case, all the elements which are contained in the new set definitely are prime numbers!

Finally, note that "$set->Resize(0);" is (internally) exactly the same as "$set->DESTROY();".

(Remember Larry Wall: "There is more than one way to do it!")

Beware that this leaves you with an invalid reference in the variable "$set"!

(See also the documentation of the "DESTROY" method above for more details)
$set->Empty();

This method removes all elements the set contains from the set, leaving an empty set ("{}").

The method "$set->in($i)" returns false (0) for every element after invoking this method for the given set.
$set->Fill();

This method adds all elements the set can potentially contain to the set, yielding a "full" set ("~{}", or the complement of the empty set).

The method "$set->in($i)" returns true (1) for every element after invoking this method for the given set.
$set->Insert($i);

This method adds the element "$i" to the given set, i.e., performs $set = $set + {$i} (where "+" stands for the "union" operator for sets, and where "{$i}" denotes a set that only contains the element "$i").

If "$i" is outside of the range of [0..$elements-1] (where "$elements" is the maximum number of elements the given set was created with), an error message occurs.

Note that negative indices "$i" will be interpreted as large positive numbers due to their internal 2's complement binary representation and most likely lie outside the permitted range (and cause an error message).
$set->Delete($i);

This method deletes the element "$i" from the given set, i.e., performs $set = $set \ {$i} (where "\" stands for the "difference" operator for sets, and where "{$i}" denotes a set that only contains the element "$i").

If "$i" is outside of the range of [0..$elements-1] (where "$elements" is the maximum number of elements the given set was created with), an error message occurs.

Note that negative indices "$i" will be interpreted as large positive numbers due to their internal 2's complement binary representation and most likely lie outside the permitted range (and cause an error message).
$set->flip($i);

This method flips the element "$i" in the given set, i.e. adds this element to the given set if it is not contained in the set, or removes this element from the given set if it is contained in the set.

In set theory terminology, this method performs the operation
```
$set = ( $set + {$i} ) \ ( $set * {$i} )
```
(where "+", "*" and "\" stand for the "union", "intersection" and "difference" operators for sets, respectively, and where "{$i}" denotes a set that only contains the element "$i").

After doing this, the method returns the new state of the given element, i.e. it returns true (1) if the element "$i" is now contained in the given set, or false (0) otherwise.

If "$i" is outside of the range of [0..$elements-1] (where "$elements" is the maximum number of elements the given set was created with), an error message occurs.

Note that negative indices "$i" will be interpreted as large positive numbers due to their internal 2's complement binary representation and most likely lie outside the permitted range (and cause an error message).
$set->in($i);

This method tests if the element "$i" is contained in the given set.

It returns true (1) if the given set contains element "$i" and false (0) otherwise.

If "$i" is outside of the range of [0..$elements-1] (where "$elements" is the maximum number of elements the given set was created with), an error message occurs.

Note that negative indices "$i" will be interpreted as large positive numbers due to their internal 2's complement binary representation and most likely lie outside the permitted range (and cause an error message).
$set->Norm();

This method computes the "norm" of the given set, i.e., the number of elements the given set contains.

When applied to the empty set (see also the method "Empty" above), this method returns zero.

When applied to the "all" set (see also the method "Fill" above), this method returns the maximum number "$elements" of elements the set can hold (which the set was initially created with).
$set->Min();

This method computes the minimum of (i.e., the smallest element contained in) the given set.

Note that the minimum of an empty set (see also the method "Empty" above) doesn't exist. Therefore, plus infinity (represented by the numeric constant "LONG_MAX" on your system) is returned as the minimum of an empty set.

The reason for this is that plus infinity is always greater than any minimum of any non-empty set, so that the minimum of the minima of several sets always yields a meaningful value.

If you need to know the value of the constant "LONG_MAX" (for instance for comparison), simply create a small, empty dummy set and determine its minimum, i.e., do something like this:
```
$dummy = Set::IntegerFast->new(1);
$LONG_MAX = $dummy->Min();
```
$set->Max();

This method computes the maximum of (i.e., the greatest element contained in) the given set.

Note that the maximum of an empty set (see also the method "Empty" above) doesn't exist. Therefore, minus infinity (represented by the numeric constant "LONG_MIN" on your system) is returned as the maximum of an empty set.

The reason for this is that minus infinity is always less than any maximum of any non-empty set, so that the maximum of the maxima of several sets always yields a meaningful value.

If you need to know the value of the constant "LONG_MIN" (for instance for comparison), simply create a small, empty dummy set and determine its maximum, i.e., do something like this:
```
$dummy = Set::IntegerFast->new(1);
$LONG_MIN = $dummy->Max();
```
$set1->Union($set2,$set3);

This method computes the union of the two argument sets (i.e., "$set2 + $set3") and stores the result in set "$set1".

The information that initially was stored in the resulting set "$set1" gets overwritten, i.e., lost.

In-place substitution is possible, i.e., the resulting set may also be identical with one (or both) of the two arguments.

Note that the two argument sets and the resulting set must all have the same size (i.e., they must have been created with the same maximum number "$elements" of elements) or you will get an error message.
$set1->Intersection($set2,$set3);

This method computes the intersection of the two argument sets (i.e., "$set2 * $set3") and stores the result in set "$set1".

The information that initially was stored in the resulting set "$set1" gets overwritten, i.e., lost.

In-place substitution is possible, i.e., the resulting set may also be identical with one (or both) of the two arguments.

Note that the two argument sets and the resulting set must all have the same size (i.e., they must have been created with the same maximum number "$elements" of elements) or you will get an error message.
$set1->Difference($set2,$set3);

This method computes the difference of the two argument sets (i.e., "$set2 \ $set3") and stores the result in set "$set1".

The information that initially was stored in the resulting set "$set1" gets overwritten, i.e., lost.

In-place substitution is possible, i.e., the resulting set may also be identical with one (or both) of the two arguments.

Note that the two argument sets and the resulting set must all have the same size (i.e., they must have been created with the same maximum number "$elements" of elements) or you will get an error message.
$set1->ExclusiveOr($set2,$set3);

This method computes the symmetric difference of the two argument sets, i.e., "( $set2 + $set3 ) \ ( $set2 * $set3 )", and stores the result in set "$set1".

Note that the above formula is equivalent to calculating the exclusive-or of the corresponding elements in the two argument sets, hence the name of this method.

Calculating the exclusive-or is much faster than evaluating the above formula because it uses a built-in machine language instruction.

The information that initially was stored in the resulting set "$set1" gets overwritten, i.e., lost.

In-place substitution is possible, i.e., the resulting set may also be identical with one (or both) of the two arguments.

Note that the two argument sets and the resulting set must all have the same size (i.e., they must have been created with the same maximum number "$elements" of elements) or you will get an error message.
$set1->Complement($set2);

This method computes the complement of the argument set (i.e., "~ $set2") and stores the result in set "$set1".

The information that initially was stored in the resulting set "$set1" gets overwritten, i.e., lost.

In-place substitution is possible, i.e., the resulting set may be the same as the argument.

Note that the argument set and the resulting set must have the same size (i.e., they must have been created with the same maximum number "$elements" of elements) or you will get an error message.
$set1->equal($set2);

This method tests if the two sets "$set1" and "$set2" are the same.

It returns true (1) if the given sets are the same and false (0) otherwise.

Note that the two sets must have the same size (i.e., they must have been created with the same maximum number "$elements" of elements) or you will get an error message.
$set1->inclusion($set2);

This method tests if the set "$set1" is included in the set "$set2", i.e., if "$set1" is a subset of "$set2" (or in other terms, if "$set2" is a superset of "$set1").

It returns true (1) if this condition is met and false (0) otherwise.

Note that the two sets must have the same size (i.e., they must have been created with the same maximum number "$elements" of elements) or you will get an error message.
$set1->lexorder($set2);

This method compares two sets as though they were two large numbers, stored in binary representation (unsigned), and returns true (1) if "$set1" is less than or equal to "$set2", and false (0) otherwise.

The element with index 0 thereby constitutes the least significant bit (LSB) and the element with index ($elements-1) (where "$elements" is the maximum number of elements the two sets were created with) the most significant bit (MSB).

In some algorithms, it may be necessary to have many sets at the same time, and it may be important to define some order relationship on them to process them all in a well-defined order.

This lexical order is completely arbitrary and has no meaning whatsoever in terms of set theory. (!)

Note that the two sets must have the same size (i.e., they must have been created with the same maximum number "$elements" of elements) or you will get an error message.
$set1->Compare($set2);

This method compares two sets as though they were two large numbers, stored in binary representation (unsigned), and returns the value "-1" if "$set1" is less than "$set2", "0" if "$set1" and "$set2" are the same and "1" if "$set1" is greater than "$set2".

The element with index 0 thereby constitutes the least significant bit (LSB) and the element with index ($elements-1) (where "$elements" is the maximum number of elements the two sets were created with) the most significant bit (MSB).

In some algorithms, it may be necessary to have many sets at the same time, and it may be important to define some order relationship on them to process them all in a well-defined order.

This lexical order is completely arbitrary and has no meaning whatsoever in terms of set theory. (!)

Note that the two sets must have the same size (i.e., they must have been created with the same maximum number "$elements" of elements) or you will get an error message.
$set1->Copy($set2);

This method allows you to make a copy of a given set, for instance to make the comparison possible between the initial and the final set after some computation.

Note that the "carbon copy" set "$set1" is NOT created by the "Copy" method, it rather must have been created beforehand, and the two sets must have the same size (i.e., they must have been created with the same maximum number "$elements" of elements), or you will get an error message.

The information that initially was stored in the set "$set1" gets overwritten, i.e., lost.

Note also that one could substitute this method by the following two method invocations (there are other possibilities as well):
```
$set0->Empty();
$set1->Union($set2,$set0);
```
provided that "$set0", "$set1" and "$set2" are all of the same size.

But of course this is extremely inefficient.

SUBCLASSING (INHERITANCE)

Currently, subclassing of the "Set::IntegerFast" class is disabled.

This is because you must know exactly what you are doing if you want to do this.

As a matter of fact, Perl doesn't know anything about the internals of a "Set::IntegerFast" object.

This is what is called "information hiding", "module opacity" or "module secret" in object oriented programming.

Perl only knows an (anonymous) scalar variable which holds a number. This number is a pointer that the C part of the "Set::IntegerFast" module uses to access a given set. The anonymous scalar is considered to be an object (of class "Set::IntegerFast") by Perl.

What the object constructor method "new" actually does is to call the C part of the module (function "Set_Create") to create a new set object. It then creates the anonymous scalar Perl variable and stores the pointer returned by "Set_Create" in it. This scalar is then blessed into an object of class "Set::IntegerFast". Finally "new" returns a reference to that scalar.

Beware that the C part of this module uses a fake pointer which points to a convenient location inside the set object (not to the beginning of the allocated block of memory!). This pointer is not the pointer returned by "malloc()" or passed to "free()"!

Therefore, it is dangerous (at the risk of segmentation faults and core dumps and possibly lost or overwritten data) to mingle with these things unless you completely understand all the mechanisms involved.

It is also very dangerous to mess around with the number stored in the anonymous scalar variable. Changing this number and then calling one of the methods of this class is a sure way to catastrophy.

To prevent this, the anonymous scalar is always write-protected.

If you still want to use subclasses of the "Set::IntegerFast" class, you must do the following:

-

Change directory to the "Set-IntegerFast-3.2/" distribution directory

-

Edit the file Set/Makefile.PL and change the line

'DEFINE'		=> '',     # e.g., '-DHAVE_SOMETHING'

'DEFINE'		=> '-DENABLE_SUBCLASSING',

-

Then rebuild the entire module:

Issue "make realclean", "perl Makefile.PL", "make test" and (if all goes well) "make install" at the shell prompt.

In most cases you won't need this, though. See the "Set::IntegerRange" and "Math::MatrixBool" modules for how to expand the functionality of this class without need for formal subclassing or inheritance!

(Without need for any kludge, either!)

COMPLEXITY

In the following, "n" is the maximum number of elements your set can hold, and "b" is the number of bits in a machine word on your system.

(If the maximum number of elements you specified when creating the set is not a multiple of "b", set "n" to the next greater multiple of "b" here)

                     worst       best       average
                     case        case        case

new                  n/b         n/b         n/b          1)
DESTROY              1           1           1
Resize               n/b         1           n+b/2b       2)
Empty                n/b         n/b         n/b
Fill                 n/b         n/b         n/b
Insert               1           1           1
Delete               1           1           1
flip                 1           1           1
in                   1           1           1
Norm                 n/b+n       n/b         <<P1>>       3)
Min                  n/b+b       2           <<P2>>       4)
Max                  n/b+b       2           <<P2>>       4)
Union                n/b         n/b         n/b
Intersection         n/b         n/b         n/b
Difference           n/b         n/b         n/b
ExclusiveOr          n/b         n/b         n/b
Complement           n/b         n/b         n/b
equal                n/b         1           <<P3>>       5)
inclusion            n/b         1           <<P4>>       5)
lexorder             n/b         1           <<P3>>       6)
Compare              n/b         1           <<P3>>       6)
Copy                 n/b         n/b         n/b

1): complexity is n/b here because a set is always initialized to an empty set (padded with zeros).
2): "n" is the maximum number of elements in the NEW set here. "best case" is when the new set is smaller than the old set. "worst case" is when the new set is larger than the old one, in which case the new set has to be initialized and the old set has to be copied to the new one. "average case" assumes that half of the time the new set is larger, half of the time it is smaller than the old set.
3): "worst case" is when the set is full, i.e., all elements are present. "best case" is when the set is empty.
4): "best case" is when the first (Min) or the last (Max) element is set. "worst case" is when ONLY the last (Min) or the first (Max) element is set. (The algorithm has complexity n/b for a completely empty set)
5): "best case" is when the condition is false at the first word.
6): "best case" is when the two sets differ at the first word.

For values of "n" not too large, the average case complexity of the methods Norm, Min, Max, equal, lexorder, Compare and inclusion can be calculated with the following Perl subroutines (note the terms "2**$n" and even "2**(2*$n)" below which limit the computable complexities!) according to the formula:

E[X]  =  SUM{ i=1..n } i * p(i)

(where 1..n are the possible values the stochastic variable X can have, p(i) is the probability of value i and E[X] the average outcome of X)

(The result is more or less close to n for Norm, vaguely in the range n/2b to n/b for Min and Max, and close to 1 for equal, lexorder, Compare and inclusion)

<<P1>> :

sub average_case     # method "Norm"
{
    my($n,$b) = @_;
    my($i,@j,$c,$k,$l,$p,$s,$sum);

    $k = int($n / $b);
    if (($k * $b) < $n) { $n = ++$k * $b; }
    $sum = 0;
    for ( $i = $k; $i >= 1; --$i )
    {
        $j[$i] = 0;
    }
    $c = 0;
    while (! $c)
    {
        $p = 1;
        $s = $k;
        for ( $i = $k; $i >= 1; --$i )
        {
            $l = $j[$i];
            $s += $l;
            if ($l >= 1) { --$l; }
            $p *= 2**$l;
        }
        $sum += $s * $p;
        $c = 1;
        for ( $i = $k; ($i >= 1) && $c; --$i )
        {
            if ($c = (++$j[$i] > $b)) { $j[$i] = 0; }
        }
    }
    return($sum / 2**$n);
}

<<P2>> :

sub average_case     # methods "Min" and "Max"
{
    my($n,$b) = @_;
    my($i,$j,$k,$l,$o,$p,$sum);

    $k = int($n / $b);
    if (($k * $b) < $n) { $n = ++$k * $b; }
    $sum = $k;
    for ( $l = 2; $l <= ($k+$b); ++$l )
    {
        $o = $l - 2;
        if ($o > $k - 1) { $o = $k - 1; }
        $p = 0;
        for ( $i = 0; $i <= $o; ++$i )
        {
            $j = $l - $i - 1;
            if ($j <= $b)
            {
                $p += 2**($n-$i*$b-$j);
            }
        }
        $sum += $l * $p;
    }
    return($sum / 2**$n);
}

<<P3>> :

sub average_case     # methods "equal", "lexorder", "Compare"
{
    my($n,$b) = @_;
    my($i,$k,$t1,$t2,$sum);

    $k = int($n / $b);
    if (($k * $b) < $n) { $n = ++$k * $b; }
    $t1 = 0;
    $t2 = 0;
    $sum = 0;
    for ( $i = $k; $i >= 1; --$i )
    {
        $t1 = 2**(($k-$i+1)*$b);
        $sum += ($t1 - $t2) * $i;
        $t2 = $t1;
    }
    return($sum / 2**$n);
}

<<P4>> :

sub average_case     # method "inclusion"
{
    my($n,$b) = @_;
    my($i,$j,$k,$l,$s,$t1,$t2,$sum);

    $k = int($n / $b);
    if (($k * $b) < $n) { $n = ++$k * $b; }
    $t1 = 0;
    $t2 = 0;
    $sum = 0;
    for ( $i = $k; $i >= 1; --$i )
    {
        $s = 0;
        $l = ($i - 1) * $b;
        for ( $j = 0; $j <= $l; ++$j )
        {
            $s += 2**$j * &binomial($l,$j);
        }
        $t1 = $s * 2**(2*($n-$l));
        $sum += ($t1 - $t2) * $i;
        $t2 = $t1;
    }
    return($sum / 2**(2*$n));
}

sub binomial
{
    my($n,$k) = @_;
    my($prod) = 1;
    my($j) = 0;

    if (($n <= 0) || ($k <= 0) || ($n <= $k)) { return(1); }
    if ($k > $n - $k) { $k = $n - $k; }
    while ($j < $k)
    {
        $prod *= $n--;
        $prod /= ++$j;
    }
    return(int($prod + 0.5));
}

EXAMPLE

#!perl -w

use strict;
no strict "vars";

use Set::IntegerFast;

print "\n***** Calculating Prime Numbers - The Seave Of Erathostenes *****\n";

$limit = 0;

if (-t STDIN)
{
    while ($limit < 16)
    {
        print "\nPlease enter an upper limit (>15): ";
        $limit = <STDIN>;
        chop($limit) while ($limit =~ /\n$/);
        $limit = 0 if (($limit eq "") || ($limit =~ /\D/));
    }
    print "\n";
}
else
{
    $limit = 100;
    print "\nRunning in batch mode - using $limit as upper limit.\n\n";
}

$set = new Set::IntegerFast($limit+1);

$set->Fill();

$set->Delete(0);
$set->Delete(1);

print "Calculating the prime numbers in the range [2..$limit]...\n\n";

$start = time;

for ( $j = 4; $j <= $limit; $j += 2 )
{
    $set->Delete($j);
}

for ( $i = 3; ($j = $i * $i) <= $limit; $i += 2 )
{
    for ( ; $j <= $limit; $j += $i )
    {
        $set->Delete($j);
    }
}

$stop = time;

&print_elapsed_time;

$min = $set->Min();
$max = $set->Max();
$norm = $set->Norm();

print "Found $norm prime numbers in the range [2..$limit]:\n\n";

for ( $i = $min, $j = 0; $i <= $max; $i++ )
{
    if ($set->in($i))
    {
        print "prime number #", ++$j, " = $i\n";
    }
}

print "\n";

exit;

sub print_elapsed_time
{
    ($sec,$min,$hour,$year,$yday) = (gmtime($stop - $start))[0,1,2,5,7];
    $year -= 70;
    $flag = 0;
    print "Elapsed time: ";
    if ($year > 0)
    {
        printf("%d year%s ", $year, ($year!=1)?"s":"");
        $flag = 1;
    }
    if (($yday > 0) || $flag)
    {
        printf("%d day%s ", $yday, ($yday!=1)?"s":"");
        $flag = 1;
    }
    if (($hour > 0) || $flag)
    {
        printf("%d hour%s ", $hour, ($hour!=1)?"s":"");
        $flag = 1;
    }
    if (($min > 0) || $flag)
    {
        printf("%d minute%s ", $min, ($min!=1)?"s":"");
    }
    printf("%d second%s.\n\n", $sec, ($sec!=1)?"s":"");
}

__END__

VERSION

This man page documents Set::IntegerFast version 3.0.

AUTHOR

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

COPYRIGHT

LICENSE AGREEMENT

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

To install Getopt::Long, copy and paste the appropriate command in to your terminal.

cpanm

cpanm Getopt::Long

CPAN shell

perl -MCPAN -e shell
install Getopt::Long

For more information on module installation, please visit the detailed CPAN module installation guide.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)

NAME

SYNOPSIS

DESCRIPTION

ARBITRARY SETS

DETAILS

SUBCLASSING (INHERITANCE)

COMPLEXITY

EXAMPLE

SEE ALSO

VERSION

AUTHOR

COPYRIGHT

LICENSE AGREEMENT

Module Install Instructions