MAUtil::Dictionary< Key, Storage > Class Template Reference

#include <MAUtil/Dictionary.h>

List of all members.

---

Detailed Description

template<class Key, class Storage>
class MAUtil::Dictionary< Key, Storage >

Thin template sorted Dictionary.

The Dictionary is a data storage mechanism that stores unique values. The Dictionary is sorted, by a method selectable by the user. It has fairly fast insert, erase and lookup operations. (O(log n), specifically.) It has an Iterator, which allows you to access all elements in order.

This particular implementation is built on top of kazlib's dictionary system, which makes it quite small, even when used with multiple data types.

This class is not meant to be instantiated directly. It is the base class for Set and Map.

Warning:

It is techically possible to use an Iterator to change the Key of an element. DON'T DO THAT!. It would break the sorting order of the Dictionary. The consequenses are undefined, and will likely cause your program to crash.

If you must change a Key, erase the original element from the dictionary, make your change and then re-insert it.

Public Types
typedef int(*	CompareFunction )(const Key &, const Key &)
Public Member Functions
	Dictionary (const Dictionary &)
	Constructs a copy of another Dictionary. All elements are also copied.
Dictionary &	operator= (const Dictionary &)
	Clears this Dictionary, then copies the other Dictionary to this one.
	~Dictionary ()
	The destructor deletes all elements.
Iterator	find (const Key &)
ConstIterator	find (const Key &) const
bool	erase (const Key &)
void	erase (Iterator)
Iterator	begin ()
ConstIterator	begin () const
Iterator	end ()
ConstIterator	end () const
size_t	size () const
void	clear ()
Protected Member Functions
void	init (CompareFunction)
	Dictionary (CompareFunction cf, int keyOffset)
	Constructs an empty Dictionary.
Pair< Iterator, bool >	insert (const Storage &)
Static Protected Member Functions
static dnode_t *	alloc (void *)
static void	free (dnode_t *node, void *)
Protected Attributes
dict_t	mDict
int	mKeyOffset
Classes
class	ConstIterator
class	Iterator
struct	DictNode

---

Member Typedef Documentation

template<class Key, class Storage> typedef int(* MAUtil::Dictionary< Key, Storage >::CompareFunction)(const Key &, const Key &)

---

Constructor & Destructor Documentation

template<class Key, class Storage> MAUtil::Dictionary< Key, Storage >::Dictionary (  const Dictionary< Key, Storage > &   )

Constructs a copy of another Dictionary. All elements are also copied.

template<class Key, class Storage> MAUtil::Dictionary< Key, Storage >::~Dictionary (   )

The destructor deletes all elements.

template<class Key, class Storage> MAUtil::Dictionary< Key, Storage >::Dictionary (  CompareFunction  cf, int  keyOffset )  [protected]

Constructs an empty Dictionary.

---

Member Function Documentation

template<class Key, class Storage> MAUtil::Dictionary< Key, Storage > & MAUtil::Dictionary< Key, Storage >::operator= (  const Dictionary< Key, Storage > &   )

Clears this Dictionary, then copies the other Dictionary to this one.

template<class Key, class Storage> MAUtil::Dictionary< Key, Storage >::Iterator MAUtil::Dictionary< Key, Storage >::find (  const Key &   )

Searches the Dictionary for a specified Key. The returned Iterator points to the element matching the Key if one was found, or to Dictionary::end() if not.

template<class Key, class Storage> MAUtil::Dictionary< Key, Storage >::ConstIterator MAUtil::Dictionary< Key, Storage >::find (  const Key &   )  const

template<class Key, class Storage> bool MAUtil::Dictionary< Key, Storage >::erase (  const Key &   )

Deletes an element, matching the specified Key, from the Dictionary. Returns true if an element was erased, or false if there was no element matching the Key.

template<class Key, class Storage> void MAUtil::Dictionary< Key, Storage >::erase (  Iterator   )

Deletes an element, pointed to by the specified Iterator. The Iterator is invalidated, so if you want to continue iterating through the Dictionary, you must use a different Iterator instance. Warning: If the Iterator is bound to a different Dictionary, or if it points to end(), the system will crash.

template<class Key, class Storage> MAUtil::Dictionary< Key, Storage >::Iterator MAUtil::Dictionary< Key, Storage >::begin (   )

Returns an Iterator pointing to the first element in the Dictionary.

template<class Key, class Storage> MAUtil::Dictionary< Key, Storage >::ConstIterator MAUtil::Dictionary< Key, Storage >::begin (   )  const

template<class Key, class Storage> MAUtil::Dictionary< Key, Storage >::Iterator MAUtil::Dictionary< Key, Storage >::end (   )

Returns an Iterator pointing to a place beyond the last element of the Dictionary. This Iterator is often used to determine when another Iterator has reached its end.

template<class Key, class Storage> MAUtil::Dictionary< Key, Storage >::ConstIterator MAUtil::Dictionary< Key, Storage >::end (   )  const

template<class Key, class Storage> size_t MAUtil::Dictionary< Key, Storage >::size (   )  const

Returns the number of elements in the Dictionary.

template<class Key, class Storage> void MAUtil::Dictionary< Key, Storage >::clear (   )

Deletes all elements.

template<class Key, class Storage> static dnode_t* MAUtil::Dictionary< Key, Storage >::alloc (  void *   )  [inline, static, protected]

template<class Key, class Storage> static void MAUtil::Dictionary< Key, Storage >::free (  dnode_t *  node, void *  )  [inline, static, protected]

template<class Key, class Storage> void MAUtil::Dictionary< Key, Storage >::init (  CompareFunction   )  [protected]

template<class Key, class Storage> MAUtil::Pair< class MAUtil::Dictionary< Key, Storage >::Iterator, bool > MAUtil::Dictionary< Key, Storage >::insert (  const Storage &   )  [protected]

Inserts a new value into the Dictionary. Returns a Pair. The Pair's second element is true if the value was indeed inserted. The Pair's first element is an Iterator that points to the element in the Dictionary. An element which compares equal to the new one may already be present in the Dictionary; in that case, this operation does nothing, and the Iterator returned will point to the old element. Reimplemented in MAUtil::Set< Key >.

---

Member Data Documentation

template<class Key, class Storage> dict_t MAUtil::Dictionary< Key, Storage >::mDict [protected]

template<class Key, class Storage> int MAUtil::Dictionary< Key, Storage >::mKeyOffset [protected]

---