#include <tree_map.h>

Inheritance diagram for dsac::search_tree::TreeMap< Key, Value, Compare >:

Collaboration diagram for dsac::search_tree::TreeMap< Key, Value, Compare >:

Data Structures
class	BalanceableBinaryTree

class	iter_rep

Public Member Functions
	TreeMap ()
	Creates an empty map.

int	size () const
	Returns the number of entries in the map.

const_iterator	begin () const
	Returns a const_iterator to first entry.

const_iterator	end () const
	Returns a const_iterator representing the end.

const_iterator	find (const Key &k) const
	Returns a const_iterator to the entry with a given key, or end() if no such entry exists.

const_iterator	put (const Key &k, const Value &v)

const_iterator	erase (const_iterator loc)
	Removes the entry indicated by the given iterator, and returns const_iterator to next entry in iteration order.

const_iterator	lower_bound (const Key &k) const
	Returns a const_iterator to the first entry with key greater than or equal to k, or end() if no such entry exists.

const_iterator	upper_bound (const Key &k) const
	Returns a const_iterator to the first entry with key strictly greater than k, or end() if no such entry exists.

void	_dump () const
	used for debugging only

bool	empty () const
	Returns true if the map is empty, false otherwise.

bool	erase (const Key &k)

virtual const_iterator	erase (const_iterator loc)=0

Public Member Functions inherited from dsac::map::AbstractMap< Key, Value >
bool	empty () const
	Returns true if the map is empty, false otherwise.

bool	contains (const Key &k) const
	Returns true if the map contains an entry with the given key.

const Value &	at (const Key &k) const

bool	erase (const Key &k)

virtual	~AbstractMap ()

virtual int	size () const =0

virtual const_iterator	begin () const =0

virtual const_iterator	end () const =0

virtual const_iterator	find (const Key &k) const =0

virtual const_iterator	put (const Key &k, const Value &v)=0

virtual const_iterator	erase (const_iterator loc)=0

Static Public Member Functions
static void	_dumpNode (Node *p)

static void	_dump (Node *p, int depth)

Protected Types
typedef dsac::map::AbstractMap< Key, Value >	Base

typedef std::pair< Entry, int >	BSTEntry

typedef dsac::tree::LinkedBinaryTree< BSTEntry >	TreeBase

typedef BalanceableBinaryTree::Node	Node

typedef BalanceableBinaryTree::Position	Position

Protected Member Functions
virtual void	rebalance_access (Node *)

virtual void	rebalance_insert (Node *)

virtual void	rebalance_delete (Node *)

Key	key (Node *nd) const

int	aux (Node *nd) const

void	set_aux (Node *nd, int value)

bool	equals (Key a, Key b) const

Node *	search (Key k) const

abstract_iter_rep *	get_rep (const_iterator iter) const

Protected Member Functions inherited from dsac::map::AbstractMap< Key, Value >
abstract_iter_rep *	get_rep (const_iterator iter) const

void	update_value (const Entry &e, const Value &v)

Static Protected Member Functions
static Node *	successor (Node *p)

Protected Attributes
BalanceableBinaryTree	tree

Compare	less_than

Member Typedef Documentation

◆ Base

template<typename Key , typename Value , typename Compare = std::less<Key>>

typedef dsac::map::AbstractMap<Key,Value> dsac::search_tree::TreeMap< Key, Value, Compare >::Base

protected

◆ BSTEntry

template<typename Key , typename Value , typename Compare = std::less<Key>>

typedef std::pair<Entry,int> dsac::search_tree::TreeMap< Key, Value, Compare >::BSTEntry

protected

---------— nested BalanceableBinaryTree class ----------------— A specialized version of the LinkedBinaryTree class with additional mutators to support binary search tree operations, and with the tree element type storing an additional auxiliary instance variable for balancing data.

◆ Node

template<typename Key , typename Value , typename Compare = std::less<Key>>

typedef BalanceableBinaryTree::Node dsac::search_tree::TreeMap< Key, Value, Compare >::Node

protected

◆ Position

template<typename Key , typename Value , typename Compare = std::less<Key>>

typedef BalanceableBinaryTree::Position dsac::search_tree::TreeMap< Key, Value, Compare >::Position

protected

◆ TreeBase

template<typename Key , typename Value , typename Compare = std::less<Key>>

typedef dsac::tree::LinkedBinaryTree<BSTEntry> dsac::search_tree::TreeMap< Key, Value, Compare >::TreeBase

protected

Constructor & Destructor Documentation

◆ TreeMap()

template<typename Key , typename Value , typename Compare = std::less<Key>>

dsac::search_tree::TreeMap< Key, Value, Compare >::TreeMap ( )

inline

Creates an empty map.

Here is the call graph for this function:

Member Function Documentation

◆ _dump() [1/2]

template<typename Key , typename Value , typename Compare = std::less<Key>>

void dsac::search_tree::TreeMap< Key, Value, Compare >::_dump ( ) const

inline

used for debugging only

Here is the call graph for this function:

◆ _dump() [2/2]

template<typename Key , typename Value , typename Compare = std::less<Key>>

static void dsac::search_tree::TreeMap< Key, Value, Compare >::_dump	(	Node *	p,
		int	depth
	)

inlinestatic

Here is the call graph for this function:

◆ _dumpNode()

template<typename Key , typename Value , typename Compare = std::less<Key>>

static void dsac::search_tree::TreeMap< Key, Value, Compare >::_dumpNode ( Node * p )

inlinestatic

◆ aux()

template<typename Key , typename Value , typename Compare = std::less<Key>>

int dsac::search_tree::TreeMap< Key, Value, Compare >::aux ( Node * nd ) const

inlineprotected

◆ begin()

template<typename Key , typename Value , typename Compare = std::less<Key>>

const_iterator dsac::search_tree::TreeMap< Key, Value, Compare >::begin ( ) const

inlinevirtual

Returns a const_iterator to first entry.

Implements dsac::map::AbstractMap< Key, Value >.

Here is the call graph for this function:

◆ empty()

template<typename Key , typename Value , typename Compare = std::less<Key>>

bool dsac::map::AbstractMap< Key, Value >::empty ( ) const

inline

Returns true if the map is empty, false otherwise.

◆ end()

template<typename Key , typename Value , typename Compare = std::less<Key>>

const_iterator dsac::search_tree::TreeMap< Key, Value, Compare >::end ( ) const

inlinevirtual

Returns a const_iterator representing the end.

Implements dsac::map::AbstractMap< Key, Value >.

◆ equals()

template<typename Key , typename Value , typename Compare = std::less<Key>>

bool dsac::search_tree::TreeMap< Key, Value, Compare >::equals	(	Key	a,
		Key	b
	)		const

inlineprotected

◆ erase() [1/3]

template<typename Key , typename Value , typename Compare = std::less<Key>>

bool dsac::map::AbstractMap< Key, Value >::erase ( const Key & k )

inline

Erases entry with given key (if one exists) Returns true if an entry was removed, false otherwise

◆ erase() [2/3]

template<typename Key , typename Value , typename Compare = std::less<Key>>

const_iterator dsac::search_tree::TreeMap< Key, Value, Compare >::erase ( const_iterator loc )

inlinevirtual

Removes the entry indicated by the given iterator, and returns const_iterator to next entry in iteration order.

Implements dsac::map::AbstractMap< Key, Value >.

Here is the call graph for this function:

◆ erase() [3/3]

template<typename Key , typename Value , typename Compare = std::less<Key>>

virtual const_iterator dsac::map::AbstractMap< Key, Value >::erase ( const_iterator loc )

virtual

Implements dsac::map::AbstractMap< Key, Value >.

◆ find()

template<typename Key , typename Value , typename Compare = std::less<Key>>

const_iterator dsac::search_tree::TreeMap< Key, Value, Compare >::find ( const Key & k ) const

inlinevirtual

Returns a const_iterator to the entry with a given key, or end() if no such entry exists.

Implements dsac::map::AbstractMap< Key, Value >.

Here is the call graph for this function:

◆ get_rep()

template<typename Key , typename Value , typename Compare = std::less<Key>>

abstract_iter_rep * dsac::map::AbstractMap< Key, Value >::get_rep ( const_iterator iter ) const

inlineprotected

◆ key()

template<typename Key , typename Value , typename Compare = std::less<Key>>

Key dsac::search_tree::TreeMap< Key, Value, Compare >::key ( Node * nd ) const

inlineprotected

◆ lower_bound()

template<typename Key , typename Value , typename Compare = std::less<Key>>

const_iterator dsac::search_tree::TreeMap< Key, Value, Compare >::lower_bound ( const Key & k ) const

inline

Returns a const_iterator to the first entry with key greater than or equal to k, or end() if no such entry exists.

Here is the call graph for this function:

◆ put()

template<typename Key , typename Value , typename Compare = std::less<Key>>

const_iterator dsac::search_tree::TreeMap< Key, Value, Compare >::put	(	const Key &	k,
		const Value &	v
	)

inlinevirtual

Associates given key with given value. If key already exists previous value is overwritten. Returns a const_iterator to the entry associated with the key

Implements dsac::map::AbstractMap< Key, Value >.

Here is the call graph for this function:

◆ rebalance_access()

template<typename Key , typename Value , typename Compare = std::less<Key>>

virtual void dsac::search_tree::TreeMap< Key, Value, Compare >::rebalance_access ( Node * )

inlineprotectedvirtual

◆ rebalance_delete()

template<typename Key , typename Value , typename Compare = std::less<Key>>

virtual void dsac::search_tree::TreeMap< Key, Value, Compare >::rebalance_delete ( Node * )

inlineprotectedvirtual

◆ rebalance_insert()

template<typename Key , typename Value , typename Compare = std::less<Key>>

virtual void dsac::search_tree::TreeMap< Key, Value, Compare >::rebalance_insert ( Node * )

inlineprotectedvirtual

◆ search()

template<typename Key , typename Value , typename Compare = std::less<Key>>

Node * dsac::search_tree::TreeMap< Key, Value, Compare >::search ( Key k ) const

inlineprotected

Here is the call graph for this function:

◆ set_aux()

template<typename Key , typename Value , typename Compare = std::less<Key>>

void dsac::search_tree::TreeMap< Key, Value, Compare >::set_aux	(	Node *	nd,
		int	value
	)

inlineprotected

◆ size()

template<typename Key , typename Value , typename Compare = std::less<Key>>

int dsac::search_tree::TreeMap< Key, Value, Compare >::size ( ) const

inlinevirtual

Returns the number of entries in the map.

Implements dsac::map::AbstractMap< Key, Value >.

Here is the call graph for this function:

◆ successor()

template<typename Key , typename Value , typename Compare = std::less<Key>>

static Node * dsac::search_tree::TreeMap< Key, Value, Compare >::successor ( Node * p )

inlinestaticprotected

◆ upper_bound()

template<typename Key , typename Value , typename Compare = std::less<Key>>

const_iterator dsac::search_tree::TreeMap< Key, Value, Compare >::upper_bound ( const Key & k ) const

inline

Returns a const_iterator to the first entry with key strictly greater than k, or end() if no such entry exists.

Here is the call graph for this function:

Field Documentation

◆ less_than

template<typename Key , typename Value , typename Compare = std::less<Key>>

Compare dsac::search_tree::TreeMap< Key, Value, Compare >::less_than

protected

◆ tree

template<typename Key , typename Value , typename Compare = std::less<Key>>

BalanceableBinaryTree dsac::search_tree::TreeMap< Key, Value, Compare >::tree

protected

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

dsac/searchtree/tree_map.h

Data Structures

Public Member Functions

Static Public Member Functions

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Member Typedef Documentation

◆ Base

◆ BSTEntry

◆ Node

◆ Position

◆ TreeBase

Constructor & Destructor Documentation

◆ TreeMap()

Member Function Documentation

◆ _dump() [1/2]

◆ _dump() [2/2]

◆ _dumpNode()

◆ aux()

◆ begin()

◆ empty()

◆ end()

◆ equals()

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ find()

◆ get_rep()

◆ key()

◆ lower_bound()

◆ put()

◆ rebalance_access()

◆ rebalance_delete()

◆ rebalance_insert()

◆ search()

◆ set_aux()

◆ size()

◆ successor()

◆ upper_bound()

Field Documentation

◆ less_than

◆ tree