![]() |
Murl Engine API
Version 2018.3
|
A generic index template base class. More...
#include <murl_index_base.h>
A generic index template base class.
The index class stores a number of (not necessarily unique) keys in a hash table.
This is the base class of the Index and ObjectIndex class.
This class is based on the NTL AIndex container, see http://www.ultimatepp.org
KeyType | The key's data type of the index. |
ArrayType | The array type of the keys. |
HashFunc | The hash function of the key. |
Public Types | |
typedef ArrayType::ConstIterator | ConstIterator |
Definition of the const iterator. | |
Public Member Functions | |
void | Clear () |
Clear the index object and remove the underlying storage. | |
void | ClearIndex () |
Clear the hash index. | |
void | Empty () |
Empty the index object, but keep the underlying storage. | |
void | RebuildHash (SInt32 n) |
Clear and rebuild the hash index for a given number of items. More... | |
void | RebuildHash () |
Clear and rebuild the hash index. | |
void | Shrink () |
Shrink the index object so that the underlying storage is only as large as necessary. | |
void | Trim (SInt32 n) |
Reduce the index object to a given number of items. More... | |
void | Drop (SInt32 n=1) |
Reduce the index object by removing a given number of items from the end. More... | |
void | Reserve (SInt32 n) |
Reserve storage space. More... | |
void | Unlink (SInt32 index) |
Unlink the item at a given index. More... | |
SInt32 | UnlinkKey (const KeyType &key) |
Unlink all items matching a given key. More... | |
SInt32 | UnlinkKey (const KeyType &key, UInt32 hash) |
Unlink all items matching a given key, using a precalculated hash value. More... | |
Bool | IsUnlinked (SInt32 index) const |
Check if the item at a given index is unlinked. More... | |
SInt32Array | GetUnlinked () const |
Get an array of indices of all unlinked items. More... | |
void | Sweep () |
Remove all unlinked items from the index. | |
KeyType & | Set (SInt32 index, const KeyType &key, UInt32 hash) |
Replace the item at a specified index using a precomputed hash. More... | |
KeyType & | Set (SInt32 index, const KeyType &key) |
Replace the item at a specified index. More... | |
KeyType & | Add (const KeyType &key, UInt32 hash) |
Add an item with a precomputed hash value. More... | |
KeyType & | Add (const KeyType &key) |
Add an item. More... | |
SInt32 | Put (const KeyType &key, UInt32 hash) |
Add an item or replace an unlinked item if present, using a precomputed hash value. More... | |
SInt32 | Put (const KeyType &key) |
Add an item or replace an unlinked item if present. More... | |
SInt32 | FindAdd (const KeyType &key, UInt32 hash) |
Find the first occurrence of a given item in the index, or add an item if the item was not found, using a precomputed hash value. More... | |
SInt32 | FindAdd (const KeyType &key) |
Find the first occurrence of a given item in the index, or add an item if the item was not found. More... | |
SInt32 | FindPut (const KeyType &key, UInt32 hash) |
Find the first occurrence of a given item or add the item if the item was not found, using a precomputed hash value. More... | |
SInt32 | FindPut (const KeyType &key) |
Find the first occurrence of a given item or put the item if the item was not found. More... | |
SInt32 | Find (const KeyType &key, UInt32 hash) const |
Find the first occurrence of a given item using a precomputed hash value. More... | |
SInt32 | Find (const KeyType &key) const |
Find the first occurrence of a given item. More... | |
SInt32 | FindNext (SInt32 index) const |
Find the next occurrence of an item that is specified by a given index. More... | |
SInt32 | FindPrev (SInt32 index) const |
Find the previous occurrence of an item that is specified by a given index. More... | |
SInt32 | FindLast (const KeyType &key, UInt32 hash) const |
Find the last occurrence of a given item, using a precomputed hash value. More... | |
SInt32 | FindLast (const KeyType &key) const |
Find the last occurrence of a given item. More... | |
KeyType & | Insert (SInt32 index, const KeyType &key, UInt32 hash) |
Insert an item at a given position, using a precomputed hash value. More... | |
KeyType & | Insert (SInt32 index, const KeyType &key) |
Insert an item at a given position. More... | |
void | Remove (SInt32 index) |
Remove the item at a given position. More... | |
void | Remove (SInt32 index, SInt32 count) |
Remove a number of items at a given starting position. More... | |
void | Remove (const SInt32 *sortedIndices, SInt32 count) |
Remove a number of items at given positions. More... | |
void | Remove (const SInt32Array &sortedIndices) |
Remove a number of items at given positions. More... | |
SInt32 | RemoveKey (const KeyType &key, UInt32 hash) |
Remove all items that match a given item, using a precomputed hash value. More... | |
SInt32 | RemoveKey (const KeyType &key) |
Remove all items that match a given item. More... | |
const KeyType & | Bottom () const |
Get a reference to the first item. More... | |
const KeyType & | Top () const |
Get a reference to the last item. More... | |
Bool | IsIndexValid (SInt32 index) const |
Check if a given index is a valid index. More... | |
const KeyType & | operator[] (SInt32 index) const |
Get a const reference to the item at a given index. More... | |
const KeyType & | Get (SInt32 index) const |
Get a const reference to the item at a given index. More... | |
SInt32 | GetAlloc () const |
Get the number of actually allocated items. More... | |
SInt32 | GetCount () const |
Get the number of items. More... | |
Bool | IsEmpty () const |
Check if the Index is empty. More... | |
const ArrayType & | GetKeys () const |
Get a const reference to the array of items. More... | |
void | Swap (IndexBase &other) |
Exchange the content of the index object with a given second one. More... | |
ConstIterator | Begin () const |
Get the const iterator to the first item. More... | |
ConstIterator | End () const |
Get the const iterator next to the last item. More... | |
ConstIterator | GetIter (SInt32 index) const |
Get the const iterator of a specified index. More... | |
SInt32 | GetIterIndex (ConstIterator iterator) const |
Get the item index by iterator. More... | |
UInt32 | CalculateHash (const KeyType &key) const |
Calculate the hash for an item. More... | |
Bool | IsEqual (const IndexBase &other) const |
Compare the index to another one. More... | |
bool | operator== (const IndexBase &rhs) const |
The "equal to" comparison operator, calls IsEqual(). More... | |
bool | operator!= (const IndexBase &rhs) const |
The "not equal to" comparison operator, calls IsEqual(). More... | |
|
inline |
Clear and rebuild the hash index for a given number of items.
n | The number of items to rebuild. |
|
inline |
Reduce the index object to a given number of items.
n | The new number of items in the index, must be smaller than the current item count. |
|
inline |
Reduce the index object by removing a given number of items from the end.
n | The number of items to remove from the end. |
|
inline |
Reserve storage space.
If the given size is less than the actual size, nothing is done.
n | The number of items the underlying storage should hold. |
|
inline |
Unlink the item at a given index.
Unlinked items remain in the Index, but are ignored by any search operations.
index | The index of the item to unlink. |
|
inline |
Unlink all items matching a given key.
Unlinked items remain in the Index, but are ignored by any search operations.
key | The key of the item(s) to unlink. |
|
inline |
Unlink all items matching a given key, using a precalculated hash value.
Unlinked items remain in the Index, but are ignored by any search operations.
key | The key of the item(s) to unlink. |
hash | The precalculated hash value. |
|
inline |
Check if the item at a given index is unlinked.
index | The index of the item to check. |
|
inline |
Get an array of indices of all unlinked items.
|
inline |
Replace the item at a specified index using a precomputed hash.
index | The index to set. |
key | The value to set. |
hash | The precomputed hash. |
|
inline |
Replace the item at a specified index.
index | The index to set. |
key | The value to set. |
|
inline |
Add an item with a precomputed hash value.
key | The item to add. |
hash | The precomputed hash. |
|
inline |
Add an item.
key | The item to add. |
|
inline |
Add an item or replace an unlinked item if present, using a precomputed hash value.
key | The item to add. |
hash | The precomputed hash. |
|
inline |
Add an item or replace an unlinked item if present.
key | The item to add. |
|
inline |
Find the first occurrence of a given item in the index, or add an item if the item was not found, using a precomputed hash value.
key | The item to search for and add. |
hash | The precomputed hash. |
|
inline |
Find the first occurrence of a given item in the index, or add an item if the item was not found.
key | The item to search for and add. |
|
inline |
Find the first occurrence of a given item or add the item if the item was not found, using a precomputed hash value.
Hereby replacing an unlinked element if possible.
key | The item to search for and add. |
hash | The precomputed hash. |
|
inline |
Find the first occurrence of a given item or put the item if the item was not found.
Hereby replacing an unlinked element if possible.
key | The item to search for and add. |
|
inline |
Find the first occurrence of a given item using a precomputed hash value.
key | The item to search for. |
hash | The precomputed hash. |
|
inline |
Find the first occurrence of a given item.
key | The item to search for. |
|
inline |
Find the next occurrence of an item that is specified by a given index.
index | The index of the item containing the key to search for. |
|
inline |
Find the previous occurrence of an item that is specified by a given index.
index | The index of the item containing the key to search for. |
|
inline |
Find the last occurrence of a given item, using a precomputed hash value.
key | The item to search for. |
hash | The precomputed hash value. |
|
inline |
Find the last occurrence of a given item.
key | The item to search for. |
|
inline |
Insert an item at a given position, using a precomputed hash value.
index | The index where to insert the item. |
key | The item to insert. |
hash | The precomputed hash value. |
|
inline |
Insert an item at a given position.
index | The index where to insert the item. |
key | The item to insert. |
|
inline |
Remove the item at a given position.
index | The index from where to remove the item. |
|
inline |
Remove a number of items at a given starting position.
index | The index from where to start removing the items. |
count | The number of subsequent items to remove. |
|
inline |
Remove a number of items at given positions.
sortedIndices | A pointer to sorted indices where to remove the items. |
count | The number of items to remove, i.e. the number of indices. |
|
inline |
Remove a number of items at given positions.
sortedIndices | A sorted array of indices where to remove the items. |
|
inline |
Remove all items that match a given item, using a precomputed hash value.
key | The item to remove. |
hash | The precomputed hash value. |
|
inline |
Remove all items that match a given item.
key | The item to remove. |
|
inline |
Get a reference to the first item.
|
inline |
Get a reference to the last item.
|
inline |
Check if a given index is a valid index.
index | The index to check. |
|
inline |
Get a const reference to the item at a given index.
If the index is out of range, the behaviour is undefined.
index | The index of the item to retrieve. |
|
inline |
Get a const reference to the item at a given index.
If the index is out of range, the behaviour is undefined.
index | The index of the item to retrieve. |
|
inline |
Get the number of actually allocated items.
|
inline |
Get the number of items.
|
inline |
|
inline |
Get a const reference to the array of items.
|
inline |
Exchange the content of the index object with a given second one.
other | The second index object. |
|
inline |
Get the const iterator to the first item.
|
inline |
Get the const iterator next to the last item.
|
inline |
Get the const iterator of a specified index.
index | The index for the iterator. |
|
inline |
Get the item index by iterator.
(!) Adding or removing items will invalidate iterators.
iterator | The iterator of the item. |
|
inline |
Calculate the hash for an item.
key | The item to calculate. |
|
inline |
Compare the index to another one.
other | The index to compare. |
|
inline |
The "equal to" comparison operator, calls IsEqual().
rhs | The right hand side index to compare. |
|
inline |
The "not equal to" comparison operator, calls IsEqual().
rhs | The right hand side index to compare. |