6.50 ABA_SET Class Reference

class implements a data structure for collections of dynamic disjoint sets of integers

#include <set.h>

Inheritance diagram for ABA_SET::

Public Member Functions

• ABA_SET (ABA_GLOBAL *glob, int size)
• virtual ~ABA_SET ()

  The destructor.

• void makeSet (int x)
• bool unionSets (int x, int y)
• int findSet (int x)

Protected Attributes

• ABA_GLOBAL *glob_
• ABA_ARRAY< int > parent_

  The collection of sets is implemented by a collection of trees. parent [i] is the parent of node i in the tree representing the set containing i. If i is the root of a tree then parent [i] is i itself.

6.50.1 Detailed Description

class implements a data structure for collections of dynamic disjoint sets of integers

Definition at line 41 of file set.h.

6.50.2 Constructor & Destructor Documentation

6.50.2.1 ABA_SET::ABA_SET (ABA_GLOBAL * glob, int size)

The constructor.

Parameters:

glob

A pointer to the corresponding global object.

size

Only integers between 0 and size-1 can be inserted in the set.

6.50.2.2 virtual ABA_SET::~ABA_SET () [virtual]

The destructor.

6.50.3 Member Function Documentation

6.50.3.1 void ABA_SET::makeSet (int x)

Creates a set storing only one element and adds it to the collection of sets.

Parameters:

x

The single element of the new set.

6.50.3.2 bool ABA_SET::unionSets (int x, int y)

Unites the two sets which contain x and y, respectively.

This operation may only be performed if both x and y have earlier been added to the collection of sets by the function makeSet().

We do not use the heuristic attaching the smaller subtree to the bigger one, since we want to guarantee that the representative of x is always the representative of the two united sets.

Returns:

true If both sets have been disjoint before the function call,

false otherwise.

Parameters:

x

An element of the first set of the union operation.

y

An element in the second set of the union operation.

Reimplemented in ABA_FASTSET.

6.50.3.3 int ABA_SET::findSet (int x)

Finds the representative of the set containing x.

This operation may be only performed if x has been earlier added to the collection of sets by the function makeSet().

A path compression is performed, i.e., all nodes of the tree on the path from x to the root are directly attached to the root of the tree.

Returns:

The representative of the set containing x.

Parameters:

x

An element of the searched set.

6.50.4 Member Data Documentation

6.50.4.1 ABA_GLOBAL*ABA_SET::glob_ [protected]

A pointer to the corresponding global object.

Definition at line 101 of file set.h.

6.50.4.2 ABA_ARRAY<int> ABA_SET::parent_ [protected]

The collection of sets is implemented by a collection of trees. parent [i] is the parent of node i in the tree representing the set containing i. If i is the root of a tree then parent [i] is i itself.

Definition at line 108 of file set.h.

The documentation for this class was generated from the following file:

• Include/abacus/set.h