#include <RiceSet.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 RiceSet &rOther) const |
| Checks the two sets for equalness. | |
| void | Union (const RiceSet &rOther) |
| Builds the union of the two sets in place. | |
| void | Intersect (const RiceSet &rOther) |
| Builds the intersection of the two sets in place. | |
| void | Difference (const RiceSet &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::RiceSet. More... | |
The sparse set representation was published in "ACM Letters on Programming Languages and Systems", Vol. 2, Nos. 1-4, March-December 1993, Pages 59-69.
Two vectors - a sparse and a dense one - are used to store the members of the set. Each node of the sparse vector links to a node of the dense vector and vice versa.
The method of Briggs and Torczon is explicitly designed for a fixed size universy, and thus static vectors can be used as underlying data structures. To achieve compatibility to the other BitSet implementations and to satisfy the requirements of the actual use case for the BitSets implemented in this library, the original method was changed to use dynamic vectors as underlying data structure. This has an negative impact on the performance.
The runtime of Remove and Contains is in O(1). The runtime of Add is in O(1) if no vector resizing is necessary, in O(v) (where v is the value of the member) otherwise. The Intersect and Difference methods have all runtime in O(n) (where n is the number of members in the set). The Union method has also a runtime of O(n), but only if no resizing is necessary, in the worst case the runtime is in O(v*n) where v is the biggest value added to the set.
| void sps::RiceSet::Add | ( | size_t | nBit | ) | [inline] |
Adds bit nBit to the set.
The runtime of this method is in O(1) of no resizing is necessary, in O(nBit) otherwise.
Example:
RiceSet set; set.Add(3); set.Add(42); // the set now contains the elements 3, 42
| void sps::RiceSet::Remove | ( | size_t | nBit | ) | [inline] |
Removes bit nBit from the set.
The runtime of this method is in O(1).
Example:
RiceSet set; set.Add(3); set.Add(42); set.Remove(3); // the set now contains only the element 42
| bool sps::RiceSet::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:
RiceSet set; set.IsEmpty(); // will return true set.Add(3); set.Add(42); set.IsEmpty(); // will return false
| bool sps::RiceSet::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(1).
Example:
RiceSet set; set.Add(3); set.Add(42); set.Contains(42); // will return true
| bool sps::RiceSet::IsEqual | ( | const RiceSet & | 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). Where n is the number of nodes in the set.
Example:
RiceSet 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::RiceSet::Union | ( | const RiceSet & | 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). Where n is the number of nodes in the bigger of the two sets.
Example:
RiceSet 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::RiceSet::Intersect | ( | const RiceSet & | 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). Where n is the number of nodes in the bigger of the two sets.
Example:
RiceSet set1, set2;
set1.Add(3);
set1.Add(42);
set2.Add(3);
set2.Add(43);
set1.Intersect(set2); // set1 now contains only 3
| void sps::RiceSet::Difference | ( | const RiceSet & | 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). Where n is the number of nodes in the bigger of the two sets.
Example:
RiceSet set1, set2;
set1.Add(3);
set1.Add(42);
set2.Add(3);
set2.Add(43);
set1.Difference(set2); // set1 now contains only 42
| void sps::RiceSet::Clear | ( | ) | [inline] |
Clears the set.
The result set (this) will be empty. The runtime of this method is in O(1).
Example:
RiceSet set; set.Add(3); set.Add(42); set.Clear(); // set is now empty
| RiceSet::Iterator sps::RiceSet::GetIterator | ( | ) | const [inline] |
Creates an iterator for the set.
An sps::RiceSet::Iterator for the members of this set is returned. The runtime of this method is in O(1).
Example:
RiceSet set; set.Add(3); set.Add(42); RiceSet::Iterator it = set.GetIterator(); for(it.Begin(); it.HasMoreElement(); it.Next() ) { cout << *it << endl; }
1.5.2