template <class T>
class Index
Like any other NTL container, Index is a moveable type with pick and optional deep copy transfer semantics.
Index adds associative capabilities to Vector.
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. Implementation is based on hash tables. Index stores hashvalues of elements, so it has no advantage to cache them externally.
Removing elements from an Index poses 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 invalidates 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 the Index, instead 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 socalled multikey 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 multikey ordering is almost always disjunct. For the rest of the cases, it is always possible to restore ordering using Sweep method.
Index()
Constructs empty Index.
Index(Index&& s)
Pick constructor.
Index(pick_ Vector<T>& s)
Pick operator. Transfers source Vector to Index in low constant time, but destroys it by picking.
Index(const Index& s, int)
Optional deep copy constructor.
Requires T to have deep copy constructor or optional deep copy constructor.
explicit Index(Vector<T>&& s)
Pick constructs Index from Vector.
Index(const Vector<T>& s, int)
Deepcopy constructs Index from Vector.
Requires T to have deep copy constructor or optional deep copy constructor.
Index& operator=(Vector<T>&& x)
Pick assignment from Vector.
Index& operator=(Index<T>&& x)
Pick assignment.
Index(std::initializer_list<T> init)
C++ 11 initialization.
T& Add(const T& x, unsigned _hash)
Adds a new element x with a precomputed hash value _hash. The performance benefit of this variant is that sometimes you can compute hashvalue as the part of other process, like fetching strings from an input stream. Returns a reference to the element.
Requires T to have deep copy constructor.
Invalidates iterators to Index.
Invalidates references to Index.
The precomputed _hash must be the same as the hash specified by HashFn.
T& Add(const T& x)
Adds a new element x to Index. Returns a reference to the element.
Requires T to have deep copy constructor.
Invalidates iterators to Index.
Invalidates references to Index.
Index& operator<<(const T& x)
Same as Add(x).
int Find(const T& x, unsigned _hash) const
Returns the position of the first element with value x in Index, using a precomputed _hash. If multikey ordering is not broken and more than one element with the same value exists in AIndex, the lowest position is returned. If the specified value does not exist in AIndex, a negative number is returned. Unlinked elements are ignored.
The precomputed _hash must be the same as the hash specified by HashFn.
int Find(const T& x) const
Returns the position of the first element with value x in AIndex. If multikey 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
Returns the position of the next element with the same value as the element at i. If multikey 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
Returns the position of the last element with value x in AIndex, using a precomputed _hash. If multikey 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.
The precomputed _hash must be the same as the hash specified by HashFn.
int FindLast(const T& x) const
Returns the position of the last element with value x in AIndex. If multikey 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
Returns the position of the previous element with the same value as the element at i. If multikey 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 value key in AIndex, using a precomputed _hash. If multikey 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, it is added to AIndex and position of this newly added element is returned. Unlinked elements are ignored.
Requires T to have deep copy constructor.
Invalidates iterators to AIndex.
Invalidates references to Index.
The precomputed _hash must be the same as the hash specified by HashFn.
int FindAdd(const T& key)
Retrieves position of first element with value key in AIndex. If multikey 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.
Requires T to have deep copy constructor.
Invalidates iterators to AIndex.
Invalidates references to Index.
void Unlink(int i)
Unlinks the element at i. 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 Index, one of them is replaced by x. If there are no unlinked elements, the element with the specified value is appended to the end of AIndex using Add. The position of newly placed element is returned.
Invalidates multikey ordering.
Requires T to have deep copy constructor.
Invalidates iterators to AIndex.
Invalidates references to Index.
The precomputed _hash must be the same as the hash specified by HashFn.
int Put(const T& x)
If there are any unlinked elements in AIndex, one of them is replaced by x. 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 newly placed element is returned.
Invalidates multikey ordering.
Requires T to have deep copy constructor.
Invalidates iterators to AIndex.
Invalidates references to Index.
int FindPut(const T& key, unsigned _hash)
Retrieves the position of the first element with the value key in AIndex, using a precomputed _hash. 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 multikey ordering.
Requires T to have deep copy constructor.
Invalidates iterators to AIndex.
Invalidates references to Index.
The precomputed _hash must be the same as the hash specified by HashFn.
int FindPut(const T& key)
Retrieves the position of the first element with value key 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 multikey ordering.
Requires T to have deep copy constructor.
Invalidates iterators to AIndex.
Invalidates references to Index.
T& Set(int i, const T& x, unsigned _hash)
Replaces the element at the specified position with a new element with value x, using a precomputed _hash. Speed of this operation depends on the total number of elements with the same value as the specified one. Returns a reference to the element.
Requires T to have deep copy constructor.
Invalidates iterators to AIndex.
Invalidates references to Index.
The precomputed _hash must be the same as the hash specified by HashFn.
T& Set(int i, const T& x)
Replaces the element at the specified position with a new element with value x. Speed of this operation depends on the total number of elements with the same value as the specified one. Returns a reference to the element.
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.
ConstIterator begin() const
ConstIterator end() const
Standard begin/end methods.
bool IsEmpty() const
Tests whether AIndex is empty. Same as GetCount() == 0.
unsigned GetHash(int i) const
Returns a hash of element i. This is perhaps only useful when making the exact copy of Index, e.g. in the persistent storage.
void Clear()
Removes all elements from AIndex.
int UnlinkKey(const T& k, unsigned _hash)
Unlinks all elements with value k using precomputed _hash. 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.
The precomputed _hash must be the same as the hash specified by HashFn.
int UnlinkKey(const T& k)
Unlinks all elements with value k. Unlinked elements remain in the AIndex but are ignored by any Find operations.
bool IsUnlinked(int i) const
Tests whether the element at i is unlinked.
Vector<int> GetUnlinked() const
Returns indices of all unlinked elements.
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 multikey ordering.
bool HasUnlinked() const
Returns true of AIndex has any unlinked elements.
T& Insert(int i, const T& k, unsigned h)
Inserts an element with value k at the specified position i, using a precomputed hash h. This is a slow O(n) operation. Returns a reference to the element.
Requires T to have deep copy constructor.
Invalidates iterators to AIndex.
Invalidates references to Index.
The precomputed _hash must be the same as the hash specified by HashFn.
T& Insert(int i, const T& k)
Inserts an element with value k at the specified position i. This is a slow O(n) operation. Returns a reference to the element.
Requires T to have deep copy constructor.
Invalidates iterators to AIndex.
Invalidates references to Index.
void Remove(int i)
Removes an element at the specified position i. This is a slow O(n) operation.
Invalidates iterators to AIndex.
Invalidates references to Index.
void Remove(int i, int count)
Removes count elements starting at i. This is a slow O(n) operation.
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 O(n) operation. sorted_list must point to count positions, sorted in ascending order.
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 value k using a precomputed hash h. Slow O(n).
Invalidates iterators to AIndex.
Invalidates references to Index.
The precomputed _hash must be the same as the hash specified by HashFn.
int RemoveKey(const T& k)
Removes all elements with value k. Slow O(n).
Invalidates iterators to AIndex.
Invalidates references to Index.
void Trim(int n)
Reduces the number of elements in AIndex to n. Requested number must be less than or equal to actual number of elements in AIndex.
void Drop(int n = 1)
Drops n 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.
T Pop()
Drops last element of the Index and returns its value.
Requires T to have deep copy constructor.
void Reserve(int n)
Reserves capacity. If n 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.
Requires T to have serialization operator defined.
V PickKeys()
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.
