Murl::Index< KeyType, HashFunc > Class Template Reference

A generic index template class for moveable objects eg. structs or fundamental data types like UInt32, Real, etc. More...

#include "murl_index.h"

Inheritance diagram for Murl::Index< KeyType, HashFunc >:

Public Types

typedef KeyType KeyValueType
 The template key parameter value type. More...
 
typedef HashFunc HashValueType
 The template hash parameter value type. More...
 
- Public Types inherited from Murl::IndexBase< KeyType, Array< KeyType >, HashFunc >
typedef Array< KeyType > ::ConstIterator ConstIterator
 Definition of the const iterator.
 

Public Member Functions

 Index ()
 The default constructor. More...
 
 Index (const KeyType &item)
 Construct an index containing a single item. More...
 
 Index (const KeyType &item1, const KeyType &item2)
 Construct an index containing two items. More...
 
 Index (const KeyType &item1, const KeyType &item2, const KeyType &item3)
 Construct an index containing three items. More...
 
 Index (const Index &index)
 The copy constructor. More...
 
 Index (const Array< KeyType > &array)
 Constructor taking an array. More...
 
KeyType Pop ()
 Remove the last item. More...
 
- Public Member Functions inherited from Murl::IndexBase< KeyType, Array< KeyType >, HashFunc >
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 Array< KeyType > & 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...
 

Detailed Description

template<class KeyType, class HashFunc = StdHash<KeyType>>
class Murl::Index< KeyType, HashFunc >

A generic index template class for moveable objects eg. structs or fundamental data types like UInt32, Real, etc.

See IndexBase class for all index methods.
The index class stores a number of (not necessarily unique) keys in a hash table.
The index class works for moveable objects only, use ObjectIndex class for storing non-moveable objects.
This class is based on the NTL Index container, see http://www.ultimatepp.org

Template Parameters
KeyTypeThe key's data type of the index.
HashFuncThe hash function of the key.

Member Typedef Documentation

◆ KeyValueType

template<class KeyType, class HashFunc = StdHash<KeyType>>
typedef KeyType Murl::Index< KeyType, HashFunc >::KeyValueType

The template key parameter value type.

◆ HashValueType

template<class KeyType, class HashFunc = StdHash<KeyType>>
typedef HashFunc Murl::Index< KeyType, HashFunc >::HashValueType

The template hash parameter value type.

Constructor & Destructor Documentation

◆ Index() [1/6]

template<class KeyType, class HashFunc = StdHash<KeyType>>
Murl::Index< KeyType, HashFunc >::Index ( )
inline

The default constructor.

Create an empty index object.

◆ Index() [2/6]

template<class KeyType, class HashFunc = StdHash<KeyType>>
Murl::Index< KeyType, HashFunc >::Index ( const KeyType &  item)
inline

Construct an index containing a single item.

Parameters
itemThe item.

◆ Index() [3/6]

template<class KeyType, class HashFunc = StdHash<KeyType>>
Murl::Index< KeyType, HashFunc >::Index ( const KeyType &  item1,
const KeyType &  item2 
)
inline

Construct an index containing two items.

Parameters
item1The first item.
item2The second item.

◆ Index() [4/6]

template<class KeyType, class HashFunc = StdHash<KeyType>>
Murl::Index< KeyType, HashFunc >::Index ( const KeyType &  item1,
const KeyType &  item2,
const KeyType &  item3 
)
inline

Construct an index containing three items.

Parameters
item1The first item.
item2The second item.
item3The third item.

◆ Index() [5/6]

template<class KeyType, class HashFunc = StdHash<KeyType>>
Murl::Index< KeyType, HashFunc >::Index ( const Index< KeyType, HashFunc > &  index)
inline

The copy constructor.

Parameters
indexThe index object to copy.

◆ Index() [6/6]

template<class KeyType, class HashFunc = StdHash<KeyType>>
Murl::Index< KeyType, HashFunc >::Index ( const Array< KeyType > &  array)
inline

Constructor taking an array.

Parameters
arrayThe array object to copy.

Member Function Documentation

◆ Pop()

template<class KeyType, class HashFunc = StdHash<KeyType>>
KeyType Murl::Index< KeyType, HashFunc >::Pop ( )
inline

Remove the last item.

Returns
The the removed item.

The documentation for this class was generated from the following file:
  • murl_index.h


Copyright © 2011-2018 Spraylight GmbH.