can be stored, where n is the machine word length of your system. E.g. for a 32 bit system the highest possible value is 
and each node can store 32 bits.
#include <BitList.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 BitList &rOther) const |
| Checks the two sets for equalness. | |
| void | Union (const BitList &rOther) |
| Builds the union of the two sets in place. | |
| void | Intersect (const BitList &rOther) |
| Builds the intersection of the two sets in place. | |
| void | Difference (const BitList &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::BitList. More... | |
In this implementation of the BitSet interface the data is stored in a sorted linked list, each node consisting of an offset and an integer for storing the actual bits. Values in the range of can be stored, where n is the machine word length of your system. E.g. for a 32 bit system the highest possible value is and each node can store 32 bits.
Due to the fact that this implementation is based on a sorted linked list the methods Add, Remove and Contains have all a runtime in O(n), rather the average runtime is proportional to n/2. The runtime of the Union, Intersect and Difference methods are all in O(n).
| void sps::BitList::Add | ( | size_t | nBit | ) | [inline] |
Adds bit nBit to the set.
The runtime of this method is in O(n). Where n is the number of nodes in the list.
Example:
BitList set; set.Add(3); set.Add(42); // the set now contains the elements 3, 42
| void sps::BitList::Remove | ( | size_t | nBit | ) | [inline] |
Removes bit nBit from the set.
The runtime of this method is in O(n). Where n is the number of nodes in the list.
Example:
BitList set; set.Add(3); set.Add(42); set.Remove(3); // the set now contains only the element 42
| bool sps::BitList::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:
BitList set; set.IsEmpty(); // will return true set.Add(3); set.Add(42); set.IsEmpty(); // will return false
| bool sps::BitList::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(n). Where n is the number of nodes in the list.
Example:
BitList set; set.Add(3); set.Add(42); set.Contains(42); // will return true
| bool sps::BitList::IsEqual | ( | const BitList & | 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:
BitList 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::BitList::Union | ( | const BitList & | 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 lists.
Example:
BitList 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::BitList::Intersect | ( | const BitList & | 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 lists.
Example:
BitList set1, set2;
set1.Add(3);
set1.Add(42);
set2.Add(3);
set2.Add(43);
set1.Intersect(set2); // set1 now contains only 3
| void sps::BitList::Difference | ( | const BitList & | 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 lists.
Example:
BitList set1, set2;
set1.Add(3);
set1.Add(42);
set2.Add(3);
set2.Add(43);
set1.Difference(set2); // set1 now contains only 42
| void sps::BitList::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 list.
Example:
BitList set; set.Add(3); set.Add(42); set.Clear(); // set is now empty
| BitList::Iterator sps::BitList::GetIterator | ( | ) | const [inline] |
Creates an iterator for the set.
An sps::BitList::Iterator for the members of this set is returned. The runtime of this method is in O(1).
Example:
BitList set; set.Add(3); set.Add(42); BitList::Iterator it = set.GetIterator(); for(it.Begin(); it.HasMoreElement(); it.Next() ) { cout << *it << endl; }
1.5.2