Indexed arrays using hashing for element access. More...

#include <ogdf/basic/HashArray.h>

Inheritance diagram for ogdf::HashArray< I, E, H >:

Public Types
using	const_iterator = HashConstIterator< I, E, H >
	The default value for elements. More...

Public Member Functions
	HashArray ()
	Creates a hashing array; the default value is the default value of the element type. More...

	HashArray (const E &defaultValue, const H &hashFunc=H())
	Creates a hashing array with default value `defaultValue`. More...

	HashArray (const HashArray< I, E, H > &A)
	Copy constructor. More...

HashConstIterator< I, E, H >	begin () const
	Returns an iterator to the first element in the list of all elements. More...

void	clear ()
	Undefines all indices. More...

int	empty () const
	Returns if any indices are defined (= if the hash table is empty) More...

bool	isDefined (const I &i) const
	Returns true iff index `i` is defined. More...

HashArray< I, E, H > &	operator= (const HashArray< I, E, H > &A)
	Assignment operator. More...

E &	operator[] (const I &i)
	Returns a reference to the element with index `i`. More...

const E &	operator[] (const I &i) const
	Returns the element with index `i`. More...

int	size () const
	Returns the number of defined indices (= number of elements in hash table). More...

void	undefine (const I &i)
	Undefines index `i`. More...

Private Attributes
E	m_defaultValue

Additional Inherited Members
Private Types inherited from ogdf::Hashing< I, E, DefHashFunc< I > >
using	const_iterator = HashConstIterator< I, E, DefHashFunc< I > >
	The type of const-iterators for hash tables. More...

Private Member Functions inherited from ogdf::Hashing< I, E, DefHashFunc< I > >
	Hashing (const Hashing< I, E, DefHashFunc< I > > &h)=default
	Copy constructor. More...

	Hashing (int minTableSize=256, const DefHashFunc< I > &hashFunc=DefHashFunc< I >())
	Creates a hash table for given initial table size `minTableSize`. More...

	~Hashing ()
	Destruction. More...

HashConstIterator< I, E, DefHashFunc< I > >	begin () const
	Returns an hash iterator to the first element in the list of all elements. More...

void	clear ()
	Removes all elements from the hash table. More...

void	del (const I &key)
	Removes the element with key `key` from the hash table (does nothing if no such element). More...

bool	empty () const
	Returns true iff the table is empty, i.e., contains no elements. More...

HashElement< I, E > *	fastInsert (const I &key, const E &info)
	Inserts a new element with key `key` and information `info` into the hash table. More...

HashElement< I, E > *	insert (const I &key, const E &info)
	Inserts a new element with key `key` and information `info` into the hash table. More...

HashElement< I, E > *	insertByNeed (const I &key, const E &info)
	Inserts a new element with key `key` and information `info` into the hash table. More...

HashElement< I, E > *	lookup (const I &key) const
	Returns the hash element with key `key` in the hash table; returns `nullptr` if no such element exists. More...

bool	member (const I &key) const
	Returns true iff the hash table contains an element with key `key`. More...

Hashing< I, E, DefHashFunc< I > > &	operator= (const Hashing< I, E, DefHashFunc< I > > &hashing)=default
	Assignment operator. More...

int	size () const
	Returns the number of elements in the hash table. More...

HashElement< I, E > *	firstElement (HashElement< I, E > ***pList) const
	Returns the first element in the list of all elements in the hash table. More...

HashElement< I, E > *	nextElement (HashElement< I, E > **pList, HashElement< I, E > pElement) const
	Returns the successor of `pElement` in the list of all elements in the hash table. More...

Detailed Description

template<class I, class E, class H = DefHashFunc>
class ogdf::HashArray< I, E, H >

Indexed arrays using hashing for element access.

Template Parameters

I	is the index type.
E	is the element type.
H	is the hash function type. Optional; its default uses the class DefHashFunc.

A hashing array can be used like a usual array but has a general index type.

The hashing array is only defined for a subset I_def of the index set (set of all elements of the index type). At construction, this set is empty. Whenever an index is assigned an element, this index is added to I_def. There are also method for testing if an index is defined (is in I_def).

Example

The following code snippet demonstrates how to use a hashing array. First, the example inserts elements into a hashing array simulating a tiny German–English dictionary, then it prints some elements via array access, and finally it iterates over all defined indices and prints the dictionary entries. We use a the const reference Hc, since we want to avoid that array access for undefined indices creates these elements.

HashArray<string,string> H("[undefined]");
const HashArray<string,string> &Hc = H;
 
H["Hund"]  = "dog";
H["Katze"] = "cat";
H["Maus"]  = "mouse";
 
std::cout << "Katze:   " << Hc["Katze"]   << std::endl;
std::cout << "Hamster: " << Hc["Hamster"] << std::endl;
 
std::cout << "\nAll elements:" << std::endl;
HashConstIterator<string,string> it;
for(it = Hc.begin(); it.valid(); ++it)
  std::cout << it.key() << " -> " << it.info() << std::endl;

The produced output is as follows:

Katze:   cat
Hamster: [undefined]
 
All elements:
Hund -> dog
Maus -> mouse
Katze -> cat

Definition at line 93 of file HashArray.h.

Member Typedef Documentation

◆ const_iterator

template<class I , class E , class H = DefHashFunc>

using ogdf::HashArray< I, E, H >::const_iterator = HashConstIterator<I, E, H>

The default value for elements.

The type of const-iterators for hash arrays.

Definition at line 98 of file HashArray.h.

Constructor & Destructor Documentation

◆ HashArray() [1/3]

template<class I , class E , class H = DefHashFunc>

ogdf::HashArray< I, E, H >::HashArray ( )

inline

Creates a hashing array; the default value is the default value of the element type.

Definition at line 101 of file HashArray.h.

◆ HashArray() [2/3]

template<class I , class E , class H = DefHashFunc>

ogdf::HashArray< I, E, H >::HashArray	(	const E &	defaultValue,
		const H &	hashFunc = `H()`
	)

inlineexplicit

Creates a hashing array with default value defaultValue.

Definition at line 104 of file HashArray.h.

◆ HashArray() [3/3]

template<class I , class E , class H = DefHashFunc>

ogdf::HashArray< I, E, H >::HashArray ( const HashArray< I, E, H > & A )

inline

Copy constructor.

Definition at line 108 of file HashArray.h.

Member Function Documentation

◆ begin()

template<class I , class E , class H = DefHashFunc>

HashConstIterator<I, E, H> ogdf::HashArray< I, E, H >::begin ( ) const

inline

Returns an iterator to the first element in the list of all elements.

Definition at line 112 of file HashArray.h.

◆ clear()

template<class I , class E , class H = DefHashFunc>

void ogdf::HashArray< I, E, H >::clear ( )

inline

Undefines all indices.

Definition at line 153 of file HashArray.h.

◆ empty()

template<class I , class E , class H = DefHashFunc>

int ogdf::HashArray< I, E, H >::empty ( ) const

inline

Returns if any indices are defined (= if the hash table is empty)

Definition at line 118 of file HashArray.h.

◆ isDefined()

template<class I , class E , class H = DefHashFunc>

bool ogdf::HashArray< I, E, H >::isDefined ( const I & i ) const

inline

Returns true iff index i is defined.

Definition at line 140 of file HashArray.h.

◆ operator=()

template<class I , class E , class H = DefHashFunc>

HashArray<I, E, H>& ogdf::HashArray< I, E, H >::operator= ( const HashArray< I, E, H > & A )

inline

Assignment operator.

Definition at line 146 of file HashArray.h.

◆ operator[]() [1/2]

template<class I , class E , class H = DefHashFunc>

E& ogdf::HashArray< I, E, H >::operator[] ( const I & i )

inline

Returns a reference to the element with index i.

Definition at line 131 of file HashArray.h.

◆ operator[]() [2/2]

template<class I , class E , class H = DefHashFunc>

const E& ogdf::HashArray< I, E, H >::operator[] ( const I & i ) const

inline

Returns the element with index i.

Definition at line 121 of file HashArray.h.

◆ size()

template<class I , class E , class H = DefHashFunc>

int ogdf::HashArray< I, E, H >::size ( ) const

inline

Returns the number of defined indices (= number of elements in hash table).

Definition at line 115 of file HashArray.h.

◆ undefine()

template<class I , class E , class H = DefHashFunc>

void ogdf::HashArray< I, E, H >::undefine ( const I & i )

inline

Undefines index i.

Definition at line 143 of file HashArray.h.

Member Data Documentation

◆ m_defaultValue

template<class I , class E , class H = DefHashFunc>

E ogdf::HashArray< I, E, H >::m_defaultValue

private

Definition at line 94 of file HashArray.h.

The documentation for this class was generated from the following file:

include/ogdf/basic/HashArray.h

Open
Graph Drawing
Framework

Public Types

Public Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

template<class I, class E, class H = DefHashFunc<I>>
class ogdf::HashArray< I, E, H >

Example

Member Typedef Documentation

◆ const_iterator

Constructor & Destructor Documentation

◆ HashArray() [1/3]

◆ HashArray() [2/3]

◆ HashArray() [3/3]

Member Function Documentation

◆ begin()

◆ clear()

◆ empty()

◆ isDefined()

◆ operator=()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ size()

◆ undefine()

Member Data Documentation

◆ m_defaultValue

OpenGraph DrawingFramework

Public Types

Public Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

template<class I, class E, class H = DefHashFunc<I>> class ogdf::HashArray< I, E, H >

Example

Member Typedef Documentation

◆ const_iterator

Constructor & Destructor Documentation

◆ HashArray() [1/3]

◆ HashArray() [2/3]

◆ HashArray() [3/3]

Member Function Documentation

◆ begin()

◆ clear()

◆ empty()

◆ isDefined()

◆ operator=()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ size()

◆ undefine()

Member Data Documentation

◆ m_defaultValue

Open
Graph Drawing
Framework

template<class I, class E, class H = DefHashFunc<I>>
class ogdf::HashArray< I, E, H >