#include <BitTree.h>
Public Member Functions | |
| void | Add (size_t nBit) |
Adds bit nBit to the set. | |
| void | Remove (size_t nBit) |
Removes bit nBit from the set. | |
| bool | IsEmpty () const |
| Checks if the set is empty. | |
| bool | Contains (size_t nBit) const |
Checks if bit nBit is a member of the set. | |
| bool | IsEqual (const BitTree &rOther) const |
| Checks the two sets for equalness. | |
| void | Union (const BitTree &rOther) |
| Builds the union of the two sets in place. | |
| void | Intersect (const BitTree &rOther) |
| Builds the intersection of the two sets in place. | |
| void | Difference (const BitTree &rOther) |
| Builds the difference of the two sets in place. | |
| void | Clear () |
| Clears the set. | |
| Iterator | GetIterator () const |
| Creates an iterator for the set. | |
Classes | |
| class | Iterator |
| Implementation of the sps::Iterator interface for a sps::BitTree. More... | |
In this implementation of the BitSet interface the data is stored in the leaves of a binary tree. The position of the leaves in the tree encode the most significant bits of each set member, the least significant bits are stored in the leaves. Starting at the root and the most significant bit, the left subtree will contain all nodes where the next bit is 0, the right subtree all where the next bit is 1. For the leaves no special node type is used, but the links of the parents of the leave nodes are used to store the least significant 5-6 bits (depending on your machine word length).
Due to the fact that this implementation is based on a binary tree the runtime of the methods Add, Remove and Contains is in O(lg(n)) and the runtime of the methods Union, Intersect and Difference in O(n*lg(n)), where n is the biggest value ever stored in this instance of the tree.
| void sps::BitTree::Add | ( | size_t | nBit | ) | [inline] |
Adds bit nBit to the set.
The runtime of this method is in O(lg(n)). Where n is the biggest value ever stored in this instance of the sps::BitTree.
Example:
BitTree set; set.Add(3); set.Add(42); // the set now contains the elements 3, 42
| void sps::BitTree::Remove | ( | size_t | nBit | ) | [inline] |
Removes bit nBit from the set.
The runtime of this method is in O(lg(n)). Where n is the biggest value ever stored in this instance of the sps::BitTree.
Example:
BitTree set; set.Add(3); set.Add(42); set.Remove(3); // the set now contains only the element 42
| bool sps::BitTree::IsEmpty | ( | ) | const [inline] |
Checks if the set is empty.
Returns true if the set contains no elements, false otherwise. The runtime of this method is in O(1).
Example:
BitTree set; set.IsEmpty(); // will return true set.Add(3); set.Add(42); set.IsEmpty(); // will return false
| bool sps::BitTree::Contains | ( | size_t | nBit | ) | const [inline] |
Checks if bit nBit is a member of the set.
Returns true if the set contains nBit, false otherwise. The runtime of this method is in O(lg(n)). Where n is the biggest value ever stored in this instance of the sps::BitTree.
Example:
BitTree set; set.Add(3); set.Add(42); set.Contains(42); // will return true
| bool sps::BitTree::IsEqual | ( | const BitTree & | rOther | ) | const [inline] |
Checks the two sets for equalness.
Returns true if this and rOther contain exactly the same bits, false otherwise. The runtime of this method is in O(n*lg(n)). Where n is the biggest value ever stored in this instance of the sps::BitTree.
Example:
BitTree set1, set2;
set1.Add(3);
set1.Add(42);
set2.Add(3);
set1.IsEqual(set2); // will return false
set2.Add(42);
set1.IsEqual(set2); // will return true
| void sps::BitTree::Union | ( | const BitTree & | rOther | ) | [inline] |
Builds the union of the two sets in place.
The result set (this) will contain all bits that are set in this or in rOther. The runtime of this method is in O(n*lg(n)). Where n is the biggest value ever stored in this instance of the sps::BitTree.
Example:
BitTree set1, set2;
set1.Add(3);
set1.Add(42);
set2.Add(3);
set2.Add(43);
set1.Union(set2); // set1 now contains 3, 42 and 43
| void sps::BitTree::Intersect | ( | const BitTree & | rOther | ) | [inline] |
Builds the intersection of the two sets in place.
The result set (this) will contain all bits that are set in this and in rOther. The runtime of this method is in O(n*lg(n)). Where n is the biggest value ever stored in this instance of the sps::BitTree.
Example:
BitTree set1, set2;
set1.Add(3);
set1.Add(42);
set2.Add(3);
set2.Add(43);
set1.Intersect(set2); // set1 now contains only 3
| void sps::BitTree::Difference | ( | const BitTree & | rOther | ) | [inline] |
Builds the difference of the two sets in place.
The result set (this) will contain all bits that are set in this and not set in rOther. The runtime of this method is in O(n*lg(n)). Where n is the biggest value ever stored in this instance of the sps::BitTree.
Example:
BitTree set1, set2;
set1.Add(3);
set1.Add(42);
set2.Add(3);
set2.Add(43);
set1.Difference(set2); // set1 now contains only 42
| void sps::BitTree::Clear | ( | ) | [inline] |
Clears the set.
The result set (this) will be empty. The runtime of this method is in O(n). Where n is the number of nodes in the tree.
Example:
BitTree set; set.Add(3); set.Add(42); set.Clear(); // set is now empty
| BitTree::Iterator sps::BitTree::GetIterator | ( | ) | const [inline] |
Creates an iterator for the set.
An sps::BitTree::Iterator for the members of this set is returned. The runtime of this method is in O(1).
Example:
BitTree set; set.Add(3); set.Add(42); BitTree::Iterator it = set.GetIterator(); for(it.Begin(); it.HasMoreElement(); it.Next() ) { cout << *it << endl; }
1.5.2