template <class T, class V, class HashFn>  class AIndex

template <class T, class V, class HashFn>  class AIndex

class AIndex

T    Type of elements to store. T must satisfy requirements for container flavor identified by parameter V and must have operator== defined.

V    Basic random access container.

HashFn    Hashing class. Must have defined unsigned operator()(const T& x) method returning hash value for elements.

This template class adds associative capabilities to basic random access containers, forming flavors of Index. It is used as base class for concrete index flavors, Index and ArrayIndex.

It allows adding elements at the end of sequence in constant amortized time like basic random container. Additionally, it also allows fast retrieval of a position of the element with specified value. Hashing is used for this operation. AIndex stores hash-values of elements, so it has no sense to cache them externally.

Building of internal hash maps of AIndex is always deferred till search operation. This effectively avoids unneeded remapping if large number of elements is added.

Removing elements from an AIndex causes an interesting problem. While it is possible to simply remove (or insert) an element at a specified position, such operation has to move a lot of elements and also scratches internal hash maps. Thus removing elements this way is slow, especially when combined with searching.

The solution for this problem is unlinking of elements. Unlinked elements are not removed from index, but they are ignored by search operations. Unlinking is a simple, constant time, fast operation. Further, it is possible to place an element at the first available unlinked position (rather than to the end of sequence) using the Put method, reusing unlinked position in short constant time.

The only problem of unlinking is that it breaks the so-called multi-key ordering. This term means that if there are more elements with the same value in the index and they are iterated through using the FindNext method, their positions (got as the result of Find and subsequent FindNext methods) are in ascending order. The problem is that it is impossible to implement placing elements at unlinked positions in short time while preserving this ordering. On the other hand, usage scenarios for indexes show that need for unlinking elements and multi-key ordering is almost always disjunct. For the rest of the cases, it is always possible to restore ordering by the Reindex or the Sweep method.

Like any other NTL container, AIndex is moveable type with pick and optional deep copy transfer semantics, although these features are more important in derived concrete index flavors.

Members

void Add(const T& x, unsigned _hash)

Adds a new element with a precomputed hash value.The precomputed hash value must be the same as the hash value that would be the result of HashFn. The benefit of this variant is that sometimes you can compute hash-value as the part of an other process, like fetching strings from an input stream.

Requires T to have deep copy constructor.

Invalidates iterators to AIndex.

Invalidates references to Index.

void Add(const T& x)

Adds a new element to AIndex.

Requires T to have deep copy constructor.

Invalidates iterators to AIndex.

Invalidates references to Index.

int Find(const T& x, unsigned _hash) const

Retrieves the position of the first element with the specified value in AIndex, using a precomputed hash value. The precomputed hash value must be the same as the hash value that would be result of HashFn. If multi-key ordering is not broken and more than one element with the same value exists in AIndex, the lowest position is retrieved. If the specified value does not exist in AIndex, a negative number is returned. Unlinked elements are ignored.

int Find(const T& x) const

Retrieves the position of the first element with the specified value in AIndex. If multi-key ordering is not broken and more than one element with the same value exists in AIndex, lowest position is retrieved. If the specified value does not exist in AIndex, a negative number is returned. Unlinked elements are ignored.

int FindNext(int i) const

Retrieves the position of the next element with the same value as the element at specified position. If multi-key ordering is not broken and more than one element with that value exists in AIndex, the lowest position greater than specified one is retrieved, so positions returned by subsequent calls to FindNext are in ascending order. When there are no more elements with the required value, a negative number is returned. Unlinked elements are ignored.

int FindLast(const T& x, unsigned _hash) const

Retrieves the position of the last element with specified value in AIndex, using a precomputed hash value. The precomputed hash value must be the same as the hash value that would be the result of HashFn. If multi-key ordering is not broken and more than one element with the same value exists in AIndex, the greatest position is retrieved. If the specified value does not exist in AIndex, a negative number is returned. Unlinked elements are ignored.

int FindLast(const T& x) const

Retrieves the position of the last element with specified value in AIndex. If multi-key ordering is not broken and more than one element with the same value exists in AIndex, the greatest position is retrieved. If element does not exist in AIndex, a negative number is returned. Unlinked elements are ignored.

int FindPrev(int i) const

Retrieves the position of the previous element with the same value as the element at the specified position. If multi-key ordering is not broken and more than one element with that value exists in AIndex, the greatest position lower than specified one is retrieved (so that positions got by subsequent calls to FindNext are in descending order). When there are no more elements with required value, negative number is returned. Unlinked elements are ignored.

int FindAdd(const T& key, unsigned _hash)

Retrieves position of first element with specified value in AIndex, using a precomputed hash value. Precomputed hash value must be same as hash value that would be result of HashFn. If multi-key ordering is not broken and more than one element with the same value exists in AIndex, the lowest position is retrieved. If element does not exist in AIndex, it is added to AIndex and position of this newly added element is returned. Unlinked elements are ignored.

int FindAdd(const T& key)

Retrieves position of first element with specified value in AIndex. If multi-key ordering is not broken and more than one element with the same value exists in AIndex, lowest position is retrieved. If element does not exist in AIndex, it is added to AIndex and position of this newly added element is returned. Unlinked elements are ignored.

AIndex& operator<<(const T& x)

Operator replacement of void Add(const T& x). By returning reference to AIndex it allows adding multiple elements in a single expression, thus e.g. allowing to construct a temporary Index as part of an expression like Foo((Index<int>() << 1 << 2)).

Requires T to have deep copy constructor.

Invalidates iterators to AIndex.

Invalidates references to Index.

void Unlink(int i)

Unlinks the element at the specified position. The unlinked item stays in AIndex but is ignored by any Find operation.

int Put(const T& x, unsigned _hash)

If there are any unlinked elements in AIndex, one of them is replaced by specified value. If there are no unlinked elements, the element with the specified value is appended to the end of AIndex using Add. The precomputed hash should be same as the result of HashFn. The position of the placed element is returned.

Invalidates multi-key ordering.

Requires T to have deep copy constructor.

Invalidates iterators to AIndex.

Invalidates references to Index.

int Put(const T& x)

If there are any unlinked elements in AIndex, one of them is replaced by specified value. If there are no unlinked elements, the element with the specified value is appended to the end of AIndex using Add. The position of the placed element is returned.

Invalidates multi-key ordering.

Requires T to have deep copy constructor.

Invalidates iterators to AIndex.

int FindPut(const T& key, unsigned _hash)

Retrieves the position of the first element with the specified value in AIndex, using a precomputed hash value. The precomputed hash value must be the same as the hash value that would be the result of HashFn. If the specified value does not exist in the AIndex, it is placed to it using Put(const T& x, unsigned _hash). The position of the found or placed element is returned.

Invalidates multi-key ordering.

Requires T to have deep copy constructor.

Invalidates iterators to AIndex.

Invalidates references to Index.

int FindPut(const T& key)

Retrieves the position of the first element with the specified value in AIndex. If the element does not exist in the AIndex, it is placed to it using Put(const T& x). The position of the found or placed element is returned.

Invalidates multi-key ordering.

Requires T to have deep copy constructor.

Invalidates iterators to AIndex.

Invalidates references to Index.

void Set(int i, const T& x, unsigned _hash)

Replaces the element at the specified position with a new element with the specified value, using a precomputed hash-value. Speed of this operation depends on the total number of elements with the same value as the specified one.

Requires T to have deep copy constructor.

Invalidates iterators to AIndex.

Invalidates references to Index.

void Set(int i, const T& x)

Replaces the element at the specified position with a new element with the specified value. Speed of this operation depends on total number of elements with the same value as specified the specified one.

Requires T to have deep copy constructor.

Invalidates iterators to AIndex.

Invalidates references to Index.

const T& operator[](int i) const

Returns the element at the specified position.

int GetCount() const

Returns number of elements in AIndex.

bool IsEmpty() const

Tests whether AIndex is empty. Same as GetCount() == 0.

void Clear()

Removes all elements from AIndex.

void ClearIndex()

Restores multi-key ordering.

int UnlinkKey(const T& k, unsigned h)

Unlinks all elements with specified value using precomputed hash-value. Unlinked elements stay in AIndex but are ignored by any Find operations. Precomputed hash value must be same as hash value that would be result of HashFn.

int UnlinkKey(const T& k)

Unlinks all elements with specified value. Unlinked elements remain in the AIndex but are ignored by any Find operations.

bool IsUnlinked(int i) const

Tests whether the element at the specified position is unlinked.

void Sweep()

Removes all unlinked elements from AIndex. Complexity of the operation depends on the number of elements in AIndex, not on the number of unlinked elements. Also restores multi-key ordering.

void Insert(int i, const T& k, unsigned h)

Inserts an element with the specified value at the specified position, using a precomputed hash value. The precomputed hash value must be the same as the hash value that would be the result of HashFn. This is a slow operation, especially when combined with any search operations.

Requires T to have deep copy constructor.

Invalidates iterators to AIndex.

Invalidates references to Index.

void Insert(int i, const T& k)

Inserts an element with the specified value at the specified position. This is a slow operation, especially when combined with any search operations.

Requires T to have deep copy constructor.

Invalidates iterators to AIndex.

Invalidates references to Index.

void Remove(int i)

Removes the element at the specified position. This is a slow operation, especially when combined with any search operations.

Invalidates iterators to AIndex.

Invalidates references to Index.

void Remove(const int *sorted_list, int count)

Removes multiple elements from AIndex. Time of operation only slightly depends on the number of removed elements. This is a slow operation, especially when combined with any search operations.

Invalidates iterators to AIndex.

Invalidates references to Index.

void Remove(const Vector<int>& sorted_list)

Removes multiple elements from AIndex. Same as Remove(sorted_list, sorted_list.GetCount()).

Invalidates iterators to AIndex.

Invalidates references to Index.

int RemoveKey(const T& k, unsigned h)

Removes all elements with the specified value using a precomputed hash-value. The precomputed hash value must be the same as the hash value that would be the result of HashFn. This is a slow operation, especially when combined with any search operations.

int RemoveKey(const T& k)

Removes all elements with the specified value. This is a slow operation, especially when combined with any search operations.

void Trim(int n)

Reduces the number of elements in AIndex to the specified number. Requested number must be less than or equal to actual number of elements in AIndex.

void Drop(int n = 1)

Drops the specified number of elements from the end of the AIndex (same as Trim(GetCount() - n)).

const T& Top() const

Returns a reference to the last element in the AIndex.

void Reserve(int n)

Reserves capacity. If the requested capacity is greater than current capacity, capacity is increased to the requested value.

void Shrink()

Minimizes the memory consumption of AIndex by decreasing the capacity to the number of elements.

int GetAlloc() const

Returns the current capacity of AIndex.

void Serialize(Stream& s)

Serializes content of AIndex to/from Stream. Works only if NTL is used as part of UPP.

Requires T to have serialization operator defined.

V PickKeys() pick_

Returns a basic random access container of elements. Destroys AIndex by picking.

const V& GetKeys() const

Returns a constant reference to basic random access container of elements.

AIndex& operator=(pick_ V& s)

Assigns basic random access container to AIndex. Transfers the source container in short constant time, but destroys it by picking.

AIndex& operator<<=(const V& s)

Assigns the basic random access container to AIndex, while preserving the value of the source container.

Requires T to have deep copy constructor or optional deep copy.

Pick-constructs AIndex from a basic random access container. Transfers the source container in short constant time, but destroys it by picking.

Deep-copy constructs AIndex from basic random access container.

Requires T to have deep copy constructor or optional deep copy constructor.

typedef T ValueType

Typedef of T for use in templated algorithms.

typedef typename V::ConstIterator ConstIterator

Constant iterator type.

ConstIterator Begin() const

Returns a constant iterator to the first element in AIndex.

ConstIterator End() const

Returns a constant iterator to the position just beyond the last element in AIndex.

ConstIterator GetIter(int pos) const

Returns a constant iterator to the element at specified position. Same as Begin() + i. The benefit of this method is that pos is range checked in debug mode.

Constructor. Constructs an empty AIndex.

Optional deep copy constructor.

Requires T to have deep copy constructor or optional deep copy constructor.