pfc::avltree_t< t_storage, t_comparator >

#include <avltree.h>

Public Types
typedef pfc::const_iterator< t_storage >	const_iterator
typedef pfc::iterator< t_storage >	iterator
typedef t_storage	t_item
typedef avltree_t< t_storage, t_comparator >	t_self

Public Member Functions
	avltree_t ()
	avltree_t (const t_self &p_other)
template<typename t_other >
	avltree_t (const t_other &p_other)
	~avltree_t ()
template<typename t_callback >
void	_enumerate_var (t_callback &p_callback)
iterator	_first_var ()
iterator	_last_var ()
template<typename t_param >
t_storage &	add (const t_param &p_item)
template<typename t_param >
t_storage &	add_ex (const t_param &p_item, bool &p_isnew)
template<typename t_param >
t_storage &	add_item (t_param const &p_item)
template<typename t_param >
bool	add_item_check (t_param const &item)
template<typename t_param >
t_storage &	add_item_ex (t_param const &p_item, bool &p_isnew)
template<typename t_param >
bool	contains (const t_param &p_item) const
template<typename t_callback >
void	enumerate (t_callback &p_callback) const
template<typename t_param >
bool	exists (t_param const &p_item) const
template<typename t_param >
const_iterator	find (t_param const &item) const
template<typename t_param >
iterator	find (t_param const &item)
template<typename t_param >
const t_storage *	find_item_ptr (t_param const &p_item) const
template<typename t_param >
t_storage *	find_item_ptr (t_param const &p_item)
template<bool inclusive, bool above, typename t_search >
const t_storage *	find_nearest_item (const t_search &p_search) const
template<bool inclusive, bool above, typename t_search >
t_storage *	find_nearest_item (const t_search &p_search)
template<typename t_param >
const t_storage *	find_ptr (t_param const &p_item) const
template<typename t_param >
t_storage *	find_ptr (t_param const &p_item)
const_iterator	first () const throw ()
t_size	get_count () const throw ()
template<typename t_param >
bool	get_first (t_param &p_item) const throw ()
template<typename t_param >
bool	get_last (t_param &p_item) const throw ()
template<typename t_param >
bool	have_item (const t_param &p_item) const
template<typename t_param >
iterator	insert (const t_param &p_item)
const_iterator	last () const throw ()
bool	operator!= (const t_self &other) const
template<typename t_param >
t_self &	operator+= (const t_param &p_item)
template<typename t_param >
t_self &	operator-= (const t_param &p_item)
const t_self &	operator= (const t_self &p_other)
template<typename t_other >
const t_self &	operator= (const t_other &p_other)
bool	operator== (const t_self &other) const
bool	remove (const_iterator const &iter)
void	remove_all () throw ()
template<typename t_param >
bool	remove_item (t_param const &p_item)
void	reset ()
template<typename t_param >
void	set_item (const t_param &p_item)

Static Public Member Functions
static bool	equals (const t_self &v1, const t_self &v2)

Private Types
typedef _avltree_node< t_storage >	t_node
typedef refcounted_object_ptr_t< t_node >	t_nodeptr
typedef t_node::t_ptr	t_nodeptr
typedef t_node *	t_noderawptr
typedef t_node::t_rawptr	t_noderawptr

Private Member Functions
void	__copy (const t_self &p_other)
template<bool inclusive, bool above, typename t_search >
t_storage *	__find_nearest (const t_search &p_search) const
template<typename t_param >
t_storage *	_find_item_ptr (t_param const &p_item) const
template<typename t_param >
t_node *	_find_node_ptr (t_param const &p_item) const
t_node *	_firstlast (bool which) const throw ()

Static Private Member Functions
static t_nodeptr	__copy_recur (t_node *p_source, t_node *parent)
template<typename t_nodewalk , typename t_callback >
static void	__enum_items_recur (t_nodewalk *p_node, t_callback &p_callback)
static void	_unlink_recur (t_nodeptr &node)
static void	assert_children (t_nodeptr ptr)
static t_size	calc_count (const t_node *p_node) throw ()
static t_size	calc_depth (const t_nodeptr &ptr)
template<typename t_item1 , typename t_item2 >
static int	compare (const t_item1 &p_item1, const t_item2 &p_item2)
static t_nodeptr	extract_left_leaf (t_nodeptr &p_base)
static t_nodeptr	extract_right_leaf (t_nodeptr &p_base)
template<typename t_search >
static t_storage *	g_find_or_add (t_nodeptr &p_base, t_node *parent, t_search const &p_search, bool &p_new)
template<typename t_search >
static t_node *	g_find_or_add_node (t_nodeptr &p_base, t_node *parent, t_search const &p_search, bool &p_new)
static void	g_rebalance (t_nodeptr &p_node)
template<typename t_search >
static bool	g_remove (t_nodeptr &p_node, t_search const &p_search)
static void	g_rotate_left (t_nodeptr &oldroot)
static void	g_rotate_right (t_nodeptr &oldroot)
static bool	is_ptr_valid (t_nodeptr const &p)
static bool	is_ptr_valid (t_node const *p)
static void	recalc_depth (t_nodeptr const &ptr)
static void	remove_internal (t_nodeptr &p_node)
static void	selftest (t_nodeptr const &p_node)
static t_ssize	test_depth (t_nodeptr const &ptr)

Private Attributes
t_nodeptr	m_root

Detailed Description

template<typename t_storage, typename t_comparator = comparator_default>
class pfc::avltree_t< t_storage, t_comparator >

Definition at line 73 of file avltree.h.

Member Typedef Documentation

template<typename t_storage, typename t_comparator = comparator_default>

typedef pfc::const_iterator<t_storage> pfc::avltree_t< t_storage, t_comparator >::const_iterator

Definition at line 76 of file avltree.h.

template<typename t_storage, typename t_comparator = comparator_default>

typedef pfc::iterator<t_storage> pfc::avltree_t< t_storage, t_comparator >::iterator

Definition at line 77 of file avltree.h.

template<typename t_storage, typename t_comparator = comparator_default>

typedef t_storage pfc::avltree_t< t_storage, t_comparator >::t_item

Definition at line 78 of file avltree.h.

template<typename t_storage, typename t_comparator = comparator_default>

typedef _avltree_node<t_storage> pfc::avltree_t< t_storage, t_comparator >::t_node

private

Definition at line 80 of file avltree.h.

template<typename t_storage, typename t_comparator = comparator_default>

typedef refcounted_object_ptr_t<t_node> pfc::avltree_t< t_storage, t_comparator >::t_nodeptr

private

Definition at line 82 of file avltree.h.

template<typename t_storage, typename t_comparator = comparator_default>

typedef t_node::t_ptr pfc::avltree_t< t_storage, t_comparator >::t_nodeptr

private

Definition at line 85 of file avltree.h.

template<typename t_storage, typename t_comparator = comparator_default>

typedef t_node* pfc::avltree_t< t_storage, t_comparator >::t_noderawptr

private

Definition at line 83 of file avltree.h.

template<typename t_storage, typename t_comparator = comparator_default>

typedef t_node::t_rawptr pfc::avltree_t< t_storage, t_comparator >::t_noderawptr

private

Definition at line 86 of file avltree.h.

template<typename t_storage, typename t_comparator = comparator_default>

typedef avltree_t<t_storage,t_comparator> pfc::avltree_t< t_storage, t_comparator >::t_self

Definition at line 75 of file avltree.h.

Constructor & Destructor Documentation

template<typename t_storage, typename t_comparator = comparator_default>

pfc::avltree_t< t_storage, t_comparator >::avltree_t ( )

inline

Definition at line 362 of file avltree.h.

: m_root(NULL) {}

template<typename t_storage, typename t_comparator = comparator_default>

pfc::avltree_t< t_storage, t_comparator >::~avltree_t ( )

inline

Definition at line 363 of file avltree.h.

{reset();}

template<typename t_storage, typename t_comparator = comparator_default>

pfc::avltree_t< t_storage, t_comparator >::avltree_t ( const t_self &  p_other )

inline

Definition at line 365 of file avltree.h.

: m_root(NULL) {try{__copy(p_other);} catch(...) {remove_all(); throw;}}

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_other >

pfc::avltree_t< t_storage, t_comparator >::avltree_t ( const t_other &  p_other )

inline

Definition at line 368 of file avltree.h.

: m_root(NULL) {try{copy_list_enumerated(*this,p_other);}catch(...){remove_all(); throw;}}

Member Function Documentation

template<typename t_storage, typename t_comparator = comparator_default>

void pfc::avltree_t< t_storage, t_comparator >::__copy ( const t_self &  p_other )

inlineprivate

Definition at line 541 of file avltree.h.

                                            {
            reset();
            m_root = __copy_recur(p_other.m_root.get_ptr(),NULL);
            selftest(m_root);
        }

template<typename t_storage, typename t_comparator = comparator_default>

static t_nodeptr pfc::avltree_t< t_storage, t_comparator >::__copy_recur ( t_node *  p_source, t_node *  parent  )

inlinestaticprivate

Definition at line 528 of file avltree.h.

                                                                         {
            if (p_source == NULL) {
                return NULL;
            } else {
                t_nodeptr newnode = new t_node(p_source->m_content);
                newnode->m_depth = p_source->m_depth;
                newnode->m_left = __copy_recur(p_source->m_left.get_ptr(),newnode.get_ptr());
                newnode->m_right = __copy_recur(p_source->m_right.get_ptr(),newnode.get_ptr());
                newnode->m_parent = parent;
                return newnode;
            }
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_nodewalk , typename t_callback >

static void pfc::avltree_t< t_storage, t_comparator >::__enum_items_recur ( t_nodewalk *  p_node, t_callback &  p_callback  )

inlinestaticprivate

Definition at line 173 of file avltree.h.

                                                                                    {
            if (is_ptr_valid(p_node)) {
                __enum_items_recur<t_nodewalk>(p_node->m_left.get_ptr(),p_callback);
                p_callback (p_node->m_content);
                __enum_items_recur<t_nodewalk>(p_node->m_right.get_ptr(),p_callback);
            }
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<bool inclusive, bool above, typename t_search >

t_storage* pfc::avltree_t< t_storage, t_comparator >::__find_nearest ( const t_search &  p_search ) const

inlineprivate

Definition at line 340 of file avltree.h.

                                                                                                                          {
            t_node * ptr = m_root.get_ptr();
            t_storage * found = NULL;
            while(is_ptr_valid(ptr)) {
                int result = compare(ptr->m_content,p_search);
                if (above) result = -result;
                if (inclusive && result == 0) {
                    //direct hit
                    found = &ptr->m_content;
                    break;
                } else if (result < 0) {
                    //match
                    found = &ptr->m_content;
                    ptr = ptr->child(!above);
                } else {
                    //mismatch
                    ptr = ptr->child(above);
                }
            }
            return found;
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_callback >

void pfc::avltree_t< t_storage, t_comparator >::_enumerate_var ( t_callback &  p_callback )

inline

Allows callback to modify the tree content. Unsafe! Caller must not modify items in a way that changes sort order!

Definition at line 465 of file avltree.h.

{ __enum_items_recur<t_node>(m_root.get_ptr(),p_callback); }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

t_storage* pfc::avltree_t< t_storage, t_comparator >::_find_item_ptr ( t_param const &  p_item ) const

inlineprivate

Definition at line 317 of file avltree.h.

                                                                 {
            t_node* ptr = m_root.get_ptr();
            while(is_ptr_valid(ptr)) {
                int result = compare(ptr->m_content,p_item);
                if (result > 0) ptr=ptr->m_left.get_ptr();
                else if (result < 0) ptr=ptr->m_right.get_ptr();
                else return &ptr->m_content;
            }
            return NULL;
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

t_node* pfc::avltree_t< t_storage, t_comparator >::_find_node_ptr ( t_param const &  p_item ) const

inlineprivate

Definition at line 329 of file avltree.h.

                                                              {
            t_node* ptr = m_root.get_ptr();
            while(is_ptr_valid(ptr)) {
                int result = compare(ptr->m_content,p_item);
                if (result > 0) ptr=ptr->m_left.get_ptr();
                else if (result < 0) ptr=ptr->m_right.get_ptr();
                else return ptr;
            }
            return NULL;
        }

template<typename t_storage, typename t_comparator = comparator_default>

iterator pfc::avltree_t< t_storage, t_comparator >::_first_var ( )

inline

Unsafe! Caller must not modify items in a way that changes sort order!

Definition at line 488 of file avltree.h.

{ return _firstlast(false); }

template<typename t_storage, typename t_comparator = comparator_default>

t_node* pfc::avltree_t< t_storage, t_comparator >::_firstlast ( bool  which ) const throw ( )

inlineprivate

Definition at line 519 of file avltree.h.

                                                     {
            if (m_root.is_empty()) return NULL;
            for(t_node * walk = m_root.get_ptr(); ; ) {
                t_node * next = walk->child(which);
                if (next == NULL) return walk;
                PFC_ASSERT( next->m_parent == walk );
                walk = next;
            }
        }

template<typename t_storage, typename t_comparator = comparator_default>

iterator pfc::avltree_t< t_storage, t_comparator >::_last_var ( )

inline

Unsafe! Caller must not modify items in a way that changes sort order!

Definition at line 490 of file avltree.h.

{ return _firstlast(true); }

template<typename t_storage, typename t_comparator = comparator_default>

static void pfc::avltree_t< t_storage, t_comparator >::_unlink_recur ( t_nodeptr &  node )

inlinestaticprivate

Definition at line 512 of file avltree.h.

                                                    {
            if (node.is_valid()) {
                _unlink_recur(node->m_left);
                _unlink_recur(node->m_right);
                node->unlink();
            }
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

t_storage& pfc::avltree_t< t_storage, t_comparator >::add ( const t_param &  p_item )

inline

Definition at line 475 of file avltree.h.

{return add_item(p_item);}

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

t_storage& pfc::avltree_t< t_storage, t_comparator >::add_ex ( const t_param &  p_item, bool &  p_isnew  )

inline

Definition at line 476 of file avltree.h.

{return add_item_ex(p_item,p_isnew);}

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

t_storage& pfc::avltree_t< t_storage, t_comparator >::add_item ( t_param const &  p_item )

inline

Definition at line 380 of file avltree.h.

                                                     {
            bool dummy;
            return add_item_ex(p_item,dummy);
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

bool pfc::avltree_t< t_storage, t_comparator >::add_item_check ( t_param const &  item )

inline

Returns true when the list has been altered, false when the item was already present before.

Definition at line 393 of file avltree.h.

                                                  {
            bool isNew = false;
            g_find_or_add(m_root,NULL,item,isNew);
            selftest(m_root);
            return isNew;
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

t_storage& pfc::avltree_t< t_storage, t_comparator >::add_item_ex ( t_param const &  p_item, bool &  p_isnew  )

inline

Definition at line 400 of file avltree.h.

                                                                       {
            t_storage * ret = g_find_or_add(m_root,NULL,p_item,p_isnew);
            selftest(m_root);
            return *ret;
        }

template<typename t_storage, typename t_comparator = comparator_default>

static void pfc::avltree_t< t_storage, t_comparator >::assert_children ( t_nodeptr  ptr )

inlinestaticprivate

Definition at line 108 of file avltree.h.

                                                   {
            PFC_ASSERT(ptr->m_depth == pfc::max_t(calc_depth(ptr->m_left),calc_depth(ptr->m_right)) );
        }

template<typename t_storage, typename t_comparator = comparator_default>

static t_size pfc::avltree_t< t_storage, t_comparator >::calc_count ( const t_node *  p_node ) throw ( )

inlinestaticprivate

Definition at line 308 of file avltree.h.

                                                                {
            if (is_ptr_valid(p_node)) {
                return 1 + calc_count(p_node->m_left.get_ptr()) + calc_count(p_node->m_right.get_ptr());
            } else {
                return 0;
            }
        }

template<typename t_storage, typename t_comparator = comparator_default>

static t_size pfc::avltree_t< t_storage, t_comparator >::calc_depth ( const t_nodeptr &  ptr )

inlinestaticprivate

Definition at line 99 of file avltree.h.

        {
            return ptr.is_valid() ? 1+ptr->m_depth : 0;
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_item1 , typename t_item2 >

static int pfc::avltree_t< t_storage, t_comparator >::compare ( const t_item1 &  p_item1, const t_item2 &  p_item2  )

inlinestaticprivate

Definition at line 93 of file avltree.h.

                                                                                    {
            return t_comparator::compare(p_item1,p_item2);
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

bool pfc::avltree_t< t_storage, t_comparator >::contains ( const t_param &  p_item ) const

inline

Definition at line 427 of file avltree.h.

                                                    {
            return find_item_ptr(p_item) != NULL;
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_callback >

void pfc::avltree_t< t_storage, t_comparator >::enumerate ( t_callback &  p_callback ) const

inline

Definition at line 458 of file avltree.h.

                                                      {
            __enum_items_recur<const t_node>(m_root.get_ptr(),p_callback);
        }

template<typename t_storage, typename t_comparator = comparator_default>

static bool pfc::avltree_t< t_storage, t_comparator >::equals ( const t_self &  v1, const t_self &  v2  )

inlinestatic

Definition at line 505 of file avltree.h.

                                                                 {
            return listEquals(v1,v2);
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

bool pfc::avltree_t< t_storage, t_comparator >::exists ( t_param const &  p_item ) const

inline

Definition at line 479 of file avltree.h.

{return have_item(p_item);}

template<typename t_storage, typename t_comparator = comparator_default>

static t_nodeptr pfc::avltree_t< t_storage, t_comparator >::extract_left_leaf ( t_nodeptr &  p_base )

inlinestaticprivate

Definition at line 118 of file avltree.h.

                                                               {
            if (is_ptr_valid(p_base->m_left)) {
                t_nodeptr ret = extract_left_leaf(p_base->m_left);
                recalc_depth(p_base);
                g_rebalance(p_base);
                return ret;
            } else {
                t_nodeptr node = p_base;
                p_base = node->m_right;
                if (p_base.is_valid()) p_base->m_parent = node->m_parent;
                node->m_right.release();
                node->m_depth = 0;
                node->m_parent = NULL;
                return node;
            }
        }

template<typename t_storage, typename t_comparator = comparator_default>

static t_nodeptr pfc::avltree_t< t_storage, t_comparator >::extract_right_leaf ( t_nodeptr &  p_base )

inlinestaticprivate

Definition at line 135 of file avltree.h.

                                                                {
            if (is_ptr_valid(p_base->m_right)) {
                t_nodeptr ret = extract_right_leaf(p_base->m_right);
                recalc_depth(p_base);
                g_rebalance(p_base);
                return ret;
            } else {
                t_nodeptr node = p_base;
                p_base = node->m_left;
                if (p_base.is_valid()) p_base->m_parent = node->m_parent;
                node->m_left.release();
                node->m_depth = 0;
                node->m_parent = NULL;
                return node;
            }
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

const_iterator pfc::avltree_t< t_storage, t_comparator >::find ( t_param const &  item ) const

inline

Definition at line 420 of file avltree.h.

{ return _find_node_ptr(item);}

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

iterator pfc::avltree_t< t_storage, t_comparator >::find ( t_param const &  item )

inline

Unsafe! Caller must not modify items in a way that changes sort order!

Definition at line 423 of file avltree.h.

{ return _find_node_ptr(item);}

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

const t_storage* pfc::avltree_t< t_storage, t_comparator >::find_item_ptr ( t_param const &  p_item ) const

inline

Definition at line 414 of file avltree.h.

{return _find_item_ptr(p_item);}

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

t_storage* pfc::avltree_t< t_storage, t_comparator >::find_item_ptr ( t_param const &  p_item )

inline

Unsafe! Caller must not modify items in a way that changes sort order!

Definition at line 418 of file avltree.h.

{ return _find_item_ptr(p_item); }

template<typename t_storage, typename t_comparator = comparator_default>

template<bool inclusive, bool above, typename t_search >

const t_storage* pfc::avltree_t< t_storage, t_comparator >::find_nearest_item ( const t_search &  p_search ) const

inline

Definition at line 371 of file avltree.h.

                                                                                                                                   {
            return __find_nearest<inclusive,above>(p_search);
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<bool inclusive, bool above, typename t_search >

t_storage* pfc::avltree_t< t_storage, t_comparator >::find_nearest_item ( const t_search &  p_search )

inline

Definition at line 375 of file avltree.h.

                                                                                                                       {
            return __find_nearest<inclusive,above>(p_search);
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

const t_storage* pfc::avltree_t< t_storage, t_comparator >::find_ptr ( t_param const &  p_item ) const

inline

Definition at line 477 of file avltree.h.

{return find_item_ptr(p_item);}

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

t_storage* pfc::avltree_t< t_storage, t_comparator >::find_ptr ( t_param const &  p_item )

inline

Definition at line 478 of file avltree.h.

{return find_item_ptr(p_item);}

template<typename t_storage, typename t_comparator = comparator_default>

const_iterator pfc::avltree_t< t_storage, t_comparator >::first ( ) const throw ( )

inline

Definition at line 485 of file avltree.h.

{return _firstlast(false);}

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_search >

static t_storage* pfc::avltree_t< t_storage, t_comparator >::g_find_or_add ( t_nodeptr &  p_base, t_node *  parent, t_search const &  p_search, bool &  p_new  )

inlinestaticprivate

Definition at line 216 of file avltree.h.

                                                                                                                    {
            return &g_find_or_add_node(p_base,parent,p_search,p_new)->m_content;
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_search >

static t_node* pfc::avltree_t< t_storage, t_comparator >::g_find_or_add_node ( t_nodeptr &  p_base, t_node *  parent, t_search const &  p_search, bool &  p_new  )

inlinestaticprivate

Definition at line 181 of file avltree.h.

        {
            if (p_base.is_empty()) {
                p_base = new t_node(p_search);
                p_base->m_parent = parent;
                p_new = true;
                return p_base.get_ptr();
            }

            PFC_ASSERT( p_base->m_parent == parent );

            int result = compare(p_base->m_content,p_search);
            if (result > 0) {
                t_node * ret = g_find_or_add_node<t_search>(p_base->m_left,p_base.get_ptr(),p_search,p_new);
                if (p_new) {
                    recalc_depth(p_base);
                    g_rebalance(p_base);
                }
                return ret;
            } else if (result < 0) {
                t_node * ret = g_find_or_add_node<t_search>(p_base->m_right,p_base.get_ptr(),p_search,p_new);
                if (p_new) {
                    recalc_depth(p_base);
                    g_rebalance(p_base);
                }
                return ret;
            } else {
                p_new = false;
                return p_base.get_ptr();
            }
        }

template<typename t_storage, typename t_comparator = comparator_default>

static void pfc::avltree_t< t_storage, t_comparator >::g_rebalance ( t_nodeptr &  p_node )

inlinestaticprivate

Definition at line 243 of file avltree.h.

                                                    {
            t_ssize balance = test_depth(p_node);
            if (balance > 1) {
                //right becomes root
                if (test_depth(p_node->m_right) < 0) {
                    g_rotate_left(p_node->m_right);
                }
                g_rotate_right(p_node);
            } else if (balance < -1) {
                //left becomes root
                if (test_depth(p_node->m_left) > 0) {
                    g_rotate_right(p_node->m_left);
                }
                g_rotate_left(p_node);
            }
            selftest(p_node);
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_search >

static bool pfc::avltree_t< t_storage, t_comparator >::g_remove ( t_nodeptr &  p_node, t_search const &  p_search  )

inlinestaticprivate

Definition at line 262 of file avltree.h.

                                                                           {
            if (p_node.is_empty()) return false;

            int result = compare(p_node->m_content,p_search);
            if (result == 0) {
                remove_internal(p_node);
                if (is_ptr_valid(p_node)) {
                    recalc_depth(p_node);
                    g_rebalance(p_node);
                }
                return true;
            } else {
                if (g_remove<t_search>(result > 0 ? p_node->m_left : p_node->m_right,p_search)) {
                    recalc_depth(p_node);
                    g_rebalance(p_node);
                    return true;
                } else {
                    return false;
                }
            }
        }

template<typename t_storage, typename t_comparator = comparator_default>

static void pfc::avltree_t< t_storage, t_comparator >::g_rotate_left ( t_nodeptr &  oldroot )

inlinestaticprivate

Definition at line 232 of file avltree.h.

                                                       {
            t_nodeptr newroot ( oldroot->m_left );
            oldroot->link_child(false, newroot->m_right.get_ptr());
            newroot->m_right  = oldroot;
            newroot->m_parent = oldroot->m_parent;
            oldroot->m_parent = newroot.get_ptr();
            recalc_depth(oldroot);
            recalc_depth(newroot);
            oldroot = newroot;
        }

template<typename t_storage, typename t_comparator = comparator_default>

static void pfc::avltree_t< t_storage, t_comparator >::g_rotate_right ( t_nodeptr &  oldroot )

inlinestaticprivate

Definition at line 221 of file avltree.h.

                                                        {
            t_nodeptr newroot ( oldroot->m_right );
            oldroot->link_child(true, newroot->m_left.get_ptr());
            newroot->m_left   = oldroot;
            newroot->m_parent = oldroot->m_parent;
            oldroot->m_parent = newroot.get_ptr();
            recalc_depth(oldroot);
            recalc_depth(newroot);
            oldroot = newroot;
        }

template<typename t_storage, typename t_comparator = comparator_default>

t_size pfc::avltree_t< t_storage, t_comparator >::get_count ( ) const throw ( )

inline

Definition at line 453 of file avltree.h.

                                         {
            return calc_count(m_root.get_ptr());
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

bool pfc::avltree_t< t_storage, t_comparator >::get_first ( t_param &  p_item ) const throw ( )

inline

Definition at line 492 of file avltree.h.

                                                                                  {
            const_iterator iter = first();
            if (!iter.is_valid()) return false;
            p_item = *iter;
            return true;
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

bool pfc::avltree_t< t_storage, t_comparator >::get_last ( t_param &  p_item ) const throw ( )

inline

Definition at line 498 of file avltree.h.

                                                                                 {
            const_iterator iter = last();
            if (!iter.is_valid()) return false;
            p_item = *iter;
            return true;
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

bool pfc::avltree_t< t_storage, t_comparator >::have_item ( const t_param &  p_item ) const

inline

Same as contains().

Definition at line 433 of file avltree.h.

{return contains(p_item);}

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

iterator pfc::avltree_t< t_storage, t_comparator >::insert ( const t_param &  p_item )

inline

Definition at line 467 of file avltree.h.

                                                                           {
            bool isNew;
            t_node * ret = g_find_or_add_node(m_root,NULL,p_item,isNew);
            selftest(m_root);
            return ret;
        }

template<typename t_storage, typename t_comparator = comparator_default>

static bool pfc::avltree_t< t_storage, t_comparator >::is_ptr_valid ( t_nodeptr const &  p )

inlinestaticprivate

Definition at line 89 of file avltree.h.

{ return p.is_valid(); }

template<typename t_storage, typename t_comparator = comparator_default>

static bool pfc::avltree_t< t_storage, t_comparator >::is_ptr_valid ( t_node const *  p )

inlinestaticprivate

Definition at line 90 of file avltree.h.

{ return p != NULL; }

template<typename t_storage, typename t_comparator = comparator_default>

const_iterator pfc::avltree_t< t_storage, t_comparator >::last ( ) const throw ( )

inline

Definition at line 486 of file avltree.h.

{return _firstlast(true);}

template<typename t_storage, typename t_comparator = comparator_default>

bool pfc::avltree_t< t_storage, t_comparator >::operator!= ( const t_self &  other ) const

inline

Definition at line 509 of file avltree.h.

{return !equals(*this,other);}

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

t_self& pfc::avltree_t< t_storage, t_comparator >::operator+= ( const t_param &  p_item )

inline

Definition at line 386 of file avltree.h.

{add_item(p_item);return *this;}

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

t_self& pfc::avltree_t< t_storage, t_comparator >::operator-= ( const t_param &  p_item )

inline

Definition at line 389 of file avltree.h.

{remove_item(p_item);return *this;}

template<typename t_storage, typename t_comparator = comparator_default>

const t_self& pfc::avltree_t< t_storage, t_comparator >::operator= ( const t_self &  p_other )

inline

Definition at line 364 of file avltree.h.

{__copy(p_other);return *this;}

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_other >

const t_self& pfc::avltree_t< t_storage, t_comparator >::operator= ( const t_other &  p_other )

inline

Definition at line 367 of file avltree.h.

{copy_list_enumerated(*this,p_other);return *this;}

template<typename t_storage, typename t_comparator = comparator_default>

bool pfc::avltree_t< t_storage, t_comparator >::operator== ( const t_self &  other ) const

inline

Definition at line 508 of file avltree.h.

{return equals(*this,other);}

template<typename t_storage, typename t_comparator = comparator_default>

static void pfc::avltree_t< t_storage, t_comparator >::recalc_depth ( t_nodeptr const &  ptr )

inlinestaticprivate

Definition at line 104 of file avltree.h.

                                                       {
            ptr->m_depth = pfc::max_t(calc_depth(ptr->m_left), calc_depth(ptr->m_right));
        }

template<typename t_storage, typename t_comparator = comparator_default>

bool pfc::avltree_t< t_storage, t_comparator >::remove ( const_iterator const &  iter )

inline

Definition at line 440 of file avltree.h.

                                                {
            PFC_ASSERT(iter.is_valid());
            return remove_item(*iter);//OPTIMIZEME
            //should never return false unless there's a bug in calling code
        }

template<typename t_storage, typename t_comparator = comparator_default>

void pfc::avltree_t< t_storage, t_comparator >::remove_all ( ) throw ( )

inline

Definition at line 435 of file avltree.h.

                                  {
            _unlink_recur(m_root);
            m_root.release();
        }

template<typename t_storage, typename t_comparator = comparator_default>

static void pfc::avltree_t< t_storage, t_comparator >::remove_internal ( t_nodeptr &  p_node )

inlinestaticprivate

Definition at line 152 of file avltree.h.

                                                        {
            t_nodeptr oldval = p_node;
            if (p_node->m_left.is_empty()) {
                p_node = p_node->m_right;
                if (p_node.is_valid()) p_node->m_parent = oldval->m_parent;
            } else if (p_node->m_right.is_empty()) {
                p_node = p_node->m_left;
                if (p_node.is_valid()) p_node->m_parent = oldval->m_parent;
            } else {
                t_nodeptr swap = extract_left_leaf(p_node->m_right);

                swap->link_left(oldval->m_left.get_ptr());
                swap->link_right(oldval->m_right.get_ptr());
                swap->m_parent = oldval->m_parent;
                recalc_depth(swap);
                p_node = swap;
            }
            oldval->unlink();
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

bool pfc::avltree_t< t_storage, t_comparator >::remove_item ( t_param const &  p_item )

inline

Definition at line 447 of file avltree.h.

                                                 {
            bool ret = g_remove<t_param>(m_root,p_item);
            selftest(m_root);
            return ret;
        }

template<typename t_storage, typename t_comparator = comparator_default>

void pfc::avltree_t< t_storage, t_comparator >::reset ( )

inline

Definition at line 480 of file avltree.h.

{remove_all();}

template<typename t_storage, typename t_comparator = comparator_default>

static void pfc::avltree_t< t_storage, t_comparator >::selftest ( t_nodeptr const &  p_node )

inlinestaticprivate

Definition at line 284 of file avltree.h.

                                                      {
    #if 0 //def _DEBUG//SLOW!
            if (is_ptr_valid(p_node)) {
                selftest(p_node->m_left);
                selftest(p_node->m_right);
                assert_children(p_node);
                t_ssize delta = test_depth(p_node);
                PFC_ASSERT(delta >= -1 && delta <= 1);

                if (p_node->m_left.is_valid()) {
                    PFC_ASSERT( p_node.get_ptr() == p_node->m_left->m_parent );
                }
                if (p_node->m_right.is_valid()) {
                    PFC_ASSERT( p_node.get_ptr() == p_node->m_right->m_parent );
                }

                if (is_ptr_valid(p_node->m_parent)) {
                    PFC_ASSERT(p_node == p_node->m_parent->m_left || p_node == p_node->m_parent->m_right);
                }
            }
    #endif
        }

template<typename t_storage, typename t_comparator = comparator_default>

template<typename t_param >

void pfc::avltree_t< t_storage, t_comparator >::set_item ( const t_param &  p_item )

inline

Definition at line 407 of file avltree.h.

                                              {
            bool isnew;
            t_storage & found = add_item_ex(p_item,isnew);
            if (isnew) found = p_item;
        }

template<typename t_storage, typename t_comparator = comparator_default>

static t_ssize pfc::avltree_t< t_storage, t_comparator >::test_depth ( t_nodeptr const &  ptr )

inlinestaticprivate

Definition at line 112 of file avltree.h.

        {
            if (ptr==0) return 0;
            else return calc_depth(ptr->m_right) - calc_depth(ptr->m_left);
        }

Field Documentation

template<typename t_storage, typename t_comparator = comparator_default>

t_nodeptr pfc::avltree_t< t_storage, t_comparator >::m_root

private

Definition at line 97 of file avltree.h.

---

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

• pfc/avltree.h