#include <SparseBitVector.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 SparseBitVector &rOther) const |
| Checks the two sets for equalness. | |
| void | Union (const SparseBitVector &rOther) |
| Builds the union of the two sets in place. | |
| void | Intersect (const SparseBitVector &rOther) |
| Builds the intersection of the two sets in place. | |
| void | Difference (const SparseBitVector &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::SparseBitVector. More... | |
In this implementation of the BitSet interface the data is stored in a sorted dynamic vector. Each node of the vector consists of an offset and an integer to store the actual bits.
The runtime of Add, Remove and Contains is always in O(lg(n)), where n is the size of the vector. The runtime of Union, Intersect and Difference is in O(n) where n is the vector size of the bigger of the two sets.
| void sps::SparseBitVector::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 number of nodes in the vector.
Example:
SparseBitVector set; set.Add(3); set.Add(42); // the set now contains the elements 3, 42
| void sps::SparseBitVector::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 number of nodes in the vector.
Example:
SparseBitVector set; set.Add(3); set.Add(42); set.Remove(3); // the set now contains only the element 42
| bool sps::SparseBitVector::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:
SparseBitVector set; set.IsEmpty(); // will return true set.Add(3); set.Add(42); set.IsEmpty(); // will return false
| bool sps::SparseBitVector::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 number of nodes in the vector.
Example:
SparseBitVector set; set.Add(3); set.Add(42); set.Contains(42); // will return true
| bool sps::SparseBitVector::IsEqual | ( | const SparseBitVector & | 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 list.
Example:
SparseBitVector 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::SparseBitVector::Union | ( | const SparseBitVector & | 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 vectors.
Example:
SparseBitVector 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::SparseBitVector::Intersect | ( | const SparseBitVector & | 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 vectors.
Example:
SparseBitVector set1, set2;
set1.Add(3);
set1.Add(42);
set2.Add(3);
set2.Add(43);
set1.Intersect(set2); // set1 now contains only 3
| void sps::SparseBitVector::Difference | ( | const SparseBitVector & | 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 vectors.
Example:
SparseBitVector set1, set2;
set1.Add(3);
set1.Add(42);
set2.Add(3);
set2.Add(43);
set1.Difference(set2); // set1 now contains only 42
| void sps::SparseBitVector::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 of the vector.
Example:
SparseBitVector set; set.Add(3); set.Add(42); set.Clear(); // set is now empty
| SparseBitVector::Iterator sps::SparseBitVector::GetIterator | ( | ) | const [inline] |
Creates an iterator for the set.
An sps::SparseBitVector::Iterator for the members of this set is returned. The runtime of this method is in O(1).
Example:
SparseBitVector set; set.Add(3); set.Add(42); SparseBitVector::Iterator it = set.GetIterator(); for(it.Begin(); it.HasMoreElement(); it.Next() ) { cout << *it << endl; }
1.5.2