T2RedBlackTree< T > Class Template Reference

#include <T2RedBlackTree.h>

Inheritance diagram for T2RedBlackTree< T >:

Classes
class	CIterator
class	Iterator

Public Types
using	Node = T2RedBlackTreeNode<T>

Public Member Functions
	T2RedBlackTree (T2Allocator *pAllocator=GetGlobalAllocator())
TBOOL	IsRoot (Node *pNode)
Iterator	Begin ()
Iterator	End ()
const CIterator	Begin () const
const CIterator	End () const
void	DeleteAll ()
void	Delete (Node *a_pNode)
void	Erase (Node *a_pFrom, Node *a_pTo)
Iterator	Insert (const T &value)
Iterator	Insert (T &&value)
Iterator	Find (const T &value) const
Iterator	FindNext (const Node *a_pNextAfter, const T &value) const
TSIZE	Size () const
T2Allocator *	GetAllocator () const

Additional Inherited Members
Protected Member Functions inherited from T2GenericRedBlackTree
	T2GenericRedBlackTree (T2Allocator *pAllocator)
	~T2GenericRedBlackTree ()
T2Allocator *	GetAllocator () const
size_t	GetNumElements () const
T2GenericRedBlackTreeNode *	GetFirstNode () const
T2GenericRedBlackTreeNode *	Insert (T2GenericRedBlackTreeNode *pNode)
void	DeleteFixUp (T2GenericRedBlackTreeNode *pNode)
T2GenericRedBlackTreeNode *	DeleteNode (T2GenericRedBlackTreeNode *pNode)
void	LeftRotate (T2GenericRedBlackTreeNode *pNode)
void	RightRotate (T2GenericRedBlackTreeNode *pNode)
Static Protected Member Functions inherited from T2GenericRedBlackTree
static T2GenericRedBlackTreeNode *	GetSuccessorOf (const T2GenericRedBlackTreeNode *pNode)
static T2GenericRedBlackTreeNode *	GetPredecessorOf (const T2GenericRedBlackTreeNode *pNode)
Protected Attributes inherited from T2GenericRedBlackTree
T2Allocator *	m_pAllocator
T2GenericRedBlackTreeNode	m_oRoot
size_t	m_iNumElements
Static Protected Attributes inherited from T2GenericRedBlackTree
static constinit T2GenericRedBlackTreeNode	ms_oNil

Detailed Description

template<class T>
class T2RedBlackTree< T >

Definition at line 178 of file T2RedBlackTree.h.

Member Typedef Documentation

Node

template<class T>

using T2RedBlackTree< T >::Node = T2RedBlackTreeNode<T>

Definition at line 181 of file T2RedBlackTree.h.

Constructor & Destructor Documentation

T2RedBlackTree()

template<class T>

T2RedBlackTree< T >::T2RedBlackTree ( T2Allocator * pAllocator = GetGlobalAllocator() )

inline

Definition at line 348 of file T2RedBlackTree.h.

        : T2GenericRedBlackTree( pAllocator )
    {
    }

Member Function Documentation

Begin() [1/2]

template<class T>

Iterator T2RedBlackTree< T >::Begin ( )

inline

Definition at line 358 of file T2RedBlackTree.h.

    {
        return Iterator( TREINTERPRETCAST( Node*, GetFirstNode() ) );
    }

Begin() [2/2]

template<class T>

const CIterator T2RedBlackTree< T >::Begin ( ) const

inline

Definition at line 368 of file T2RedBlackTree.h.

    {
        return CIterator( TREINTERPRETCAST( const Node*, GetFirstNode() ) );
    }

Delete()

template<class T>

void T2RedBlackTree< T >::Delete ( Node * a_pNode )

inline

Definition at line 386 of file T2RedBlackTree.h.

    {
        m_pAllocator->Delete( DeleteNode( a_pNode ) );
    }

DeleteAll()

template<class T>

void T2RedBlackTree< T >::DeleteAll ( )

inline

Definition at line 378 of file T2RedBlackTree.h.

    {
        while ( GetNumElements() > 0 )
        {
            Delete( TSTATICCAST( Node, GetFirstNode() ) );
        }
    }

End() [1/2]

template<class T>

Iterator T2RedBlackTree< T >::End ( )

inline

Definition at line 363 of file T2RedBlackTree.h.

    {
        return Iterator( TREINTERPRETCAST( Node*, &m_oRoot ) );
    }

End() [2/2]

template<class T>

const CIterator T2RedBlackTree< T >::End ( ) const

inline

Definition at line 373 of file T2RedBlackTree.h.

    {
        return CIterator( TREINTERPRETCAST( const Node*, &m_oRoot ) );
    }

Erase()

template<class T>

void T2RedBlackTree< T >::Erase ( Node * a_pFrom, Node * a_pTo )

inline

Definition at line 391 of file T2RedBlackTree.h.

    {
        Node* pNode = a_pFrom;
 
        while ( pNode != a_pTo )
        {
            auto pNext = GetSuccessorOf( pNode );
            Delete( pNode );
            pNode = pNext;
        }
    }

Find()

template<class T>

Iterator T2RedBlackTree< T >::Find ( const T & value ) const

inline

Definition at line 421 of file T2RedBlackTree.h.

    {
        Node* pCurrentNode = TSTATICCAST( Node, m_oRoot.m_pLeft );
 
        while ( pCurrentNode != &ms_oNil )
        {
            if ( pCurrentNode->operator==( value ) )
            {
                return pCurrentNode;
            }
 
            if ( pCurrentNode->IsLeftNodeNext( value ) )
            {
                pCurrentNode = TSTATICCAST( Node, pCurrentNode->m_pLeft );
            }
            else
            {
                pCurrentNode = TSTATICCAST( Node, pCurrentNode->m_pRight );
            }
        }
 
        return TSTATICCAST( Node, &m_oRoot );
    }

FindNext()

template<class T>

Iterator T2RedBlackTree< T >::FindNext ( const Node * a_pNextAfter, const T & value ) const

inline

Definition at line 445 of file T2RedBlackTree.h.

    {
        Node* pNode = TSTATICCAST( Node, GetSuccessorOf( a_pNextAfter ) );
 
        if ( pNode->operator==( value ) )
        {
            return pNode;
        }
 
        return TSTATICCAST( Node, &m_oRoot );
    }

GetAllocator()

template<class T>

T2Allocator * T2RedBlackTree< T >::GetAllocator ( ) const

inline

Definition at line 462 of file T2RedBlackTree.h.

    {
        return m_pAllocator;
    }

Insert() [1/2]

template<class T>

Iterator T2RedBlackTree< T >::Insert ( const T & value )

inline

Definition at line 403 of file T2RedBlackTree.h.

    {
        Node* pNode     = m_pAllocator->New<Node>( value );
        pNode->m_pLeft  = &ms_oNil;
        pNode->m_pRight = &ms_oNil;
 
        return InsertImpl( pNode );
    }

Insert() [2/2]

template<class T>

Iterator T2RedBlackTree< T >::Insert ( T && value )

inline

Definition at line 412 of file T2RedBlackTree.h.

    {
        Node* pNode     = m_pAllocator->New<Node>( value );
        pNode->m_pLeft  = &ms_oNil;
        pNode->m_pRight = &ms_oNil;
 
        return InsertImpl( pNode );
    }

IsRoot()

template<class T>

TBOOL T2RedBlackTree< T >::IsRoot ( Node * pNode )

inline

Definition at line 353 of file T2RedBlackTree.h.

    {
        return pNode == &m_oRoot;
    }

Size()

template<class T>

TSIZE T2RedBlackTree< T >::Size ( ) const

inline

Definition at line 457 of file T2RedBlackTree.h.

    {
        return GetNumElements();
    }

---

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

• D:/_dev/OpenBarnyard/Source/Toshi/Source/Toshi/T2RedBlackTree.h