#include <DenseBitVector.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 DenseBitVector &rOther) const |
| Checks the two sets for equalness. | |
| void | Union (const DenseBitVector &rOther) |
| Builds the union of the two sets in place. | |
| void | Intersect (const DenseBitVector &rOther) |
| Builds the intersection of the two sets in place. | |
| void | Difference (const DenseBitVector &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::DenseBitVector. More... | |
In this implementation of the BitSet interface the data is stored in a simple dynamic vector. Each node of the vector holds an integer to store 32/64 bit (depending on the machine word length of your system). The position of each node in the vector is used to calculate the offset. E.g. for storing the single value of 32767, 1024 nodes are needed, 1023 beeing empty (on 32 bit system).
The runtime of Remove and Contains is always in O(1), the runtime of Add is in O(1) if no resizing of the vector is needed in O(n) otherwise, where n is the new 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::DenseBitVector::Add | ( | size_t | nBit | ) | [inline] |
Adds bit nBit to the set.
The runtime of this method is in O(1) if no resizing is necessary, in O(n) otherwise, where n is the new vector size.
Example:
DenseBitVector set; set.Add(3); set.Add(42); // the set now contains the elements 3, 42
| void sps::DenseBitVector::Remove | ( | size_t | nBit | ) | [inline] |
Removes bit nBit from the set.
The runtime of this method is in O(1).
Example:
DenseBitVector set; set.Add(3); set.Add(42); set.Remove(3); // the set now contains only the element 42
| bool sps::DenseBitVector::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(n), where n is the vector size.
Example:
DenseBitVector set; set.IsEmpty(); // will return true set.Add(3); set.Add(42); set.IsEmpty(); // will return false
| bool sps::DenseBitVector::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:
DenseBitVector set; set.Add(3); set.Add(42); set.Contains(42); // will return true
| bool sps::DenseBitVector::IsEqual | ( | const DenseBitVector & | 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 vector size.
Example:
DenseBitVector 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::DenseBitVector::Union | ( | const DenseBitVector & | 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 vector size.
Example:
DenseBitVector 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::DenseBitVector::Intersect | ( | const DenseBitVector & | 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 vector size.
Example:
DenseBitVector set1, set2;
set1.Add(3);
set1.Add(42);
set2.Add(3);
set2.Add(43);
set1.Intersect(set2); // set1 now contains only 3
| void sps::DenseBitVector::Difference | ( | const DenseBitVector & | 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 vector size.
Example:
DenseBitVector set1, set2;
set1.Add(3);
set1.Add(42);
set2.Add(3);
set2.Add(43);
set1.Difference(set2); // set1 now contains only 42
| void sps::DenseBitVector::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 vector.
Example:
DenseBitVector set; set.Add(3); set.Add(42); set.Clear(); // set is now empty
| DenseBitVector::Iterator sps::DenseBitVector::GetIterator | ( | ) | const [inline] |
Creates an iterator for the set.
An sps::DenseBitVector::Iterator for the members of this set is returned. The runtime of this method is in O(1).
Example:
DenseBitVector set; set.Add(3); set.Add(42); DenseBitVector::Iterator it = set.GetIterator(); for(it.Begin(); it.HasMoreElement(); it.Next() ) { cout << *it << endl; }
1.5.2