*Learning objectives*

The class int_set |

As an example we present a sorting algorithm which works on certain sets of integer numbers and which is particularly fast thereon.

Suppose we have stored non-negative integer numbers from a
range [0..N] in a file `SomeInts.txt`. All
numbers are different. It could for example be a large list of phone
numbers. We want to output the list in sorted order. Since our
main memory is scarce, we cannot afford to make every number an
element of an ordinary array. An array of N `int`s
would be too large but we can afford N/32 `int`s. (We
assume a machine with M=32 bits per `int` here.) In
addition, we must sort the rapidly changing list repeatedly in
short time intervals so that an ordinary sorting algorithm would
be too slow here. How we can solve this problem?^{[31]}

We understand every number of the file as the number of a bit
in an `int_set`. We read the file twice. In
the first pass, we only determine the minimum and the maximum of
the file's integer numbers to be able to create the
`int_set`. When reading through for the
second time, we set the bit at position i if we read the number
i. After this, we run over the complete set from the minimum up
to the maximum and output all elements contained in it. These
are then exactly the numbers of the file in a sorted order. This
algorithm needs linear time. (It is linear in the sum of
the number of numbers entered and their interval size.)

#include <LEDA/int_set.h> #include <fstream> #include <iostream> #include <limits> using leda::int_set; int main() { std::ifstream is("Data/SomeInts.txt"); int n; int min = std::numeric_limits<int>::max(); int max = std::numeric_limits<int>::min(); while (is >> n) { if(n < min) min = n; else if(n > max) max = n; } int_set S(min, max); is.clear(); // set state of stream to 'good' is.seekg(0); // rewind file while (is >> n) S.insert(n); for(int i = S.min(); i <= S.max(); i++) if(S.member(i)) std::cout << i << "\n"; }

The constructor of the class
`int_set` expects the minimum and the
maximum of the numbers to be stored in this set:

int_set S(min, max);

If, in contrast, only one argument `N` is passed to
it, the class supposes the interval [0..N-1] as the range from
which the elements originate.

As in the case of the class `set`
the insert operation is called

S.insert(i);

S.member(i);

it can be checked whether a certain number `i` is an
element of the set and by

S.del(i);

the number `i` can be deleted from the set. All these operations take constant time.

A call of

S.clear();

deletes all numbers from the `int_set`.

The methods

S.min(); S.max();

return the minimum and the maximum, respectively, of the numbers stored in the `set`.

Furthermore, by the overloaded operators
`|` and `&`

S | T; S & T;

two sets can be united and intersected, respectively. These operations
are also particularly fast since they are implemented as the logical
Or and And of the individual `int`s of the underlying bit
vector.

The operator

~S;

returns the *complement* of
the set with respect to the underlying interval, that is a bit vector in
which all bits are toggled. These operations have a time complexity
which is proportional to the length of the bit vector.

Due to the implementation as a bit vector, the set
operations perform particularly fast: If a is the minimum and
b the maximum of the values stored, then intersection, union,
complementation and emptying by `clear()`
take time O(b-a+1). All other operations take constant time.

One finds more information about the class
`int_set` on the corresponding manual page.