#include <red_black_tree_map.h>

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

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

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

Public Member Functions inherited from dsac::search_tree::TreeMap< Key, Value, Compare >
	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

Protected Types
typedef TreeMap< Key, Value, Compare >	Base

typedef BalanceableBinaryTree::Node	Node

Protected Types inherited from dsac::search_tree::TreeMap< Key, Value, Compare >
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
void	make_black (Node *p)

void	make_red (Node *p)

void	set_color (Node *p, bool to_red)

bool	is_black (Node *p) const

bool	is_red (Node *p) const

bool	is_red_leaf (Node *p) const

Node *	get_red_child (Node *p)
	Return a red child of p (or nullptr, if no such child)

Node *	sibling (Node *p)

void	resolve_red (Node *p)
	Remedies potential double-red violation above red p.

void	rebalance_insert (Node *p)

void	fix_deficit (Node z, Node y)

void	rebalance_delete (Node *p)

int	aux (Node *nd) const

void	set_aux (Node *nd, int value)

Protected Member Functions inherited from dsac::search_tree::TreeMap< Key, Value, Compare >
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)

Protected Attributes
BalanceableBinaryTree	tree

Protected Attributes inherited from dsac::search_tree::TreeMap< Key, Value, Compare >
BalanceableBinaryTree	tree

Compare	less_than

Additional Inherited Members
Static Public Member Functions inherited from dsac::search_tree::TreeMap< Key, Value, Compare >
static void	_dumpNode (Node *p)

static void	_dump (Node *p, int depth)

Static Protected Member Functions inherited from dsac::search_tree::TreeMap< Key, Value, Compare >
static Node *	successor (Node *p)

Member Typedef Documentation

◆ Base

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

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

protected

◆ Node

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

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

protected

Member Function Documentation

◆ aux()

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

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

inlineprotected

◆ fix_deficit()

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

void dsac::search_tree::RedBlackTreeMap< Key, Value, Compare >::fix_deficit	(	Node *	z,
		Node *	y
	)

inlineprotected

Here is the call graph for this function:

◆ get_red_child()

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

Node * dsac::search_tree::RedBlackTreeMap< Key, Value, Compare >::get_red_child ( Node * p )

inlineprotected

Return a red child of p (or nullptr, if no such child)

Here is the call graph for this function:

◆ is_black()

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

bool dsac::search_tree::RedBlackTreeMap< Key, Value, Compare >::is_black ( Node * p ) const

inlineprotected

Here is the call graph for this function:

◆ is_red()

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

bool dsac::search_tree::RedBlackTreeMap< Key, Value, Compare >::is_red ( Node * p ) const

inlineprotected

Here is the call graph for this function:

◆ is_red_leaf()

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

bool dsac::search_tree::RedBlackTreeMap< Key, Value, Compare >::is_red_leaf ( Node * p ) const

inlineprotected

Here is the call graph for this function:

◆ make_black()

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

void dsac::search_tree::RedBlackTreeMap< Key, Value, Compare >::make_black ( Node * p )

inlineprotected

Here is the call graph for this function:

◆ make_red()

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

void dsac::search_tree::RedBlackTreeMap< Key, Value, Compare >::make_red ( Node * p )

inlineprotected

Here is the call graph for this function:

◆ rebalance_delete()

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

void dsac::search_tree::RedBlackTreeMap< Key, Value, Compare >::rebalance_delete ( Node * p )

inlineprotected

Here is the call graph for this function:

◆ rebalance_insert()

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

void dsac::search_tree::RedBlackTreeMap< Key, Value, Compare >::rebalance_insert ( Node * p )

inlineprotected

Here is the call graph for this function:

◆ resolve_red()

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

void dsac::search_tree::RedBlackTreeMap< Key, Value, Compare >::resolve_red ( Node * p )

inlineprotected

Remedies potential double-red violation above red p.

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

◆ set_color()

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

void dsac::search_tree::RedBlackTreeMap< Key, Value, Compare >::set_color	(	Node *	p,
		bool	to_red
	)

inlineprotected

Here is the call graph for this function:

◆ sibling()

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

Node * dsac::search_tree::RedBlackTreeMap< Key, Value, Compare >::sibling ( Node * p )

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 >.

Field Documentation

◆ 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/red_black_tree_map.h

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Additional Inherited Members

Member Typedef Documentation

◆ Base

◆ Node

Member Function Documentation

◆ aux()

◆ fix_deficit()

◆ get_red_child()

◆ is_black()

◆ is_red()

◆ is_red_leaf()

◆ make_black()

◆ make_red()

◆ rebalance_delete()

◆ rebalance_insert()

◆ resolve_red()

◆ set_aux()

◆ set_color()

◆ sibling()

◆ size()

Field Documentation

◆ tree