A container is a data structure to store other data objects. Most container applications in this library concern queuing of nodes and arcs by their indices, and eliminating indices from queues in certain order.
Some algorithms can be equipped with different kinds of queues, so the push/relabel method for min-cost flow. To this end, there is a common interface class goblinQueue with methods for insertion and deletion of members.
Fixed index range containers are functional equivalent with the STL stack<TIndex> and STL queue<TIndex> classes. Other than in the STL, fixed index range containers are not really sequential. That is, the physical memory representation does not conform with the logical order of elements. The containers can only store unsigned integers (indices) of a range 0,1,..,r-1 which must be specified at the time of instanciation. The advantages are following:
- No memory reallocations occur
- The containers also specialize the indexSet interface and one can test for membership in constant time.
- Container objects can share physical memory, as long as the represented index sets are disjoint. Even more, when sharing the physical memory, data integrity of disjoint index sets can either be enforced by using the staticQueue::INSERT_NO_THROW option, or conflicting insertion operations will trigger an exception.
A priority queue stores indices with a numeric key value. Elements are deleted in the order of increasing key value. Key values are assigned when elements are added, but can also be modified later. In general, this goblinQueue::ChangeKey() method cannot be reduced to goblinQueue::Insert() / goblinQueue::Delete() pairs. All these operations roughly run in logarithmic time, depending on the actual goblinQueue::Cardinality(), not on the index range.
Return to main page