UnionList

Template defines a data structure to handle union finds. The structure can be used to collect elements into unions. The unions may be represented by a different type from its elements.

Quick Index

AUTHORS

CHANGES LOG

GOALS

USAGE

Class Summary

class UnionList

{

public:
	UnionList();
iterator	addUnion(const Key& key);
iterator	addUnion(const Key& key, const Union& unionData);
bool	unite(const Key& key1, const Key& key2);
const_iterator	getUnion(const Key& key) const;
iterator	getUnion(const Key& key);
const_iterator	begin() const;
iterator	begin();
const_iterator	end() const;
iterator	end();
size_type	size() const;
protected:

}; // UnionList

Back to the top of UnionList

AUTHORS

Meir Fuchs (meirfux@math.tau.ac.il).

Back to the top of UnionList

CHANGES LOG

Back to the top of UnionList

GOALS

UnionList was written as a data structure holding union elements and their representatives and implementing an efficient union-find algorithm. Elements may be clustered into unions. These unions may be represented by a single element from its unions or by a union representative or a given type.

Back to the top of UnionList

USAGE

A UnionList template class must be declared using a union element type (Key) and union type (Union). Unions are clustered using the unite method. unite recieves two union elements and makes sure that all elements of the two unions to which the two elements belong, are now of the same union. (Check out UnionFind in any algorithms book).

The union elements are called Keys since they are used to access the unions. Since the union elements are stored in a hash table a hash function object must be supplied as the 3rd template argument or defined as hash. hash<> is predefined in the standard C++ library for several basic data types (basically integers and strings) so you need not redefine it.

The simplest UnionList:

    typedef UnionList<int> IntUnion;

The following defines a UnionList of ints where each union is represented by a float (instead of the default int>. If the union elements and the union representative are not of the same type then the representative type must have a constructor taking a single union element (Key) as its argument.

    typedef UnionList<int, float>

The following defines a UnionList of floats. In this case hash must be defined.

    struct hash<float>
    {
      size_t operator()(const float f) const { return (size_t)f; }
    };
    typedef UnionList<float> FloatsUnion;

The following example defines a int UnionList and uses it to create a single union for all non-prime numbers (whose repressentative is the integer 4) and a union for each prime number between 1 and 100:

    UnionList<int> intUnion;
    for (int i=1; i<=10000; ++i)  // Define unions. This step is not necessary
      intUnion.addUnion(i);

    for(int i=100; i>=2; --i)  // unite all non-prime numbers.
      for(int j=2; j*i<=10000; ++j)
        intUnion.unite(j*i, i*2);
    
    for (UnionList<int>::iterator it = intUnion.begin(); // print results
         it != intUnion.end();
         ++it)
      cout << (*it) << ' ';
    cout << '\n' << '\n';

Back to the top of UnionList

UnionList();

Constructor. Initialize an empty union list.

  UnionList();

Back to the top of UnionList

iterator addUnion(const Key& key);

Add a union containing a single data element.

  iterator addUnion(const Key& key);

Back to the top of UnionList

iterator addUnion(const Key& key, const Union& unionData);

Add a union containing a single data element.

  iterator addUnion(const Key& key, const Union& unionData);

Back to the top of UnionList

bool unite(const Key& key1, const Key& key2);

Unite the two unions which contain key1 and key2. If key1 or key2 are not found a new single union is created. If key1 or key2 are in the same union no action is taken. The new representative of the new union is always the one that was used to represent key2's union. key1's union is deleted.

  bool unite(const Key& key1, const Key& key2);

Back to the top of UnionList

const_iterator getUnion(const Key& key) const;

Gets the representative data element of the union which contains key.

  const_iterator getUnion(const Key& key) const;

Back to the top of UnionList

iterator getUnion(const Key& key);

Gets the union which contains key. If key is not found returns end()

  iterator getUnion(const Key& key);

Back to the top of UnionList

const_iterator begin() const;

Returns an iterator used to iterate over the list of union representatives.

  const_iterator begin() const;

Back to the top of UnionList

iterator begin();

Returns an iterator used to iterate over the list of union representatives.

  iterator begin();

Back to the top of UnionList

const_iterator end() const;

Returns an iterator used to iterate over the list of union representatives.

  const_iterator end() const;

Back to the top of UnionList

iterator end();

Returns an iterator used to iterate over the list of union representatives.

  iterator end();

Back to the top of UnionList

size_type size() const;

Number of unions in the list.

  size_type size() const;

Back to the top of UnionList

All Members

public:
iterator	addUnion(const Key& key);
iterator	addUnion(const Key& key, const Union& unionData);
bool	unite(const Key& key1, const Key& key2);
const_iterator	getUnion(const Key& key) const;
iterator	getUnion(const Key& key);
const_iterator	begin() const;
iterator	begin();
const_iterator	end() const;
iterator	end();
size_type	size() const;
protected:

Back to the top of UnionList

Ancestors

Class does not inherit from any other class.

Back to the top of UnionList

Descendants

Class is not inherited by any others.

Back to the top of UnionList

Generated from source by the Cocoon utilities on Sun Nov 15 13:35:26 2009 .

Report problems to jkotula@unimax.com