internal_poltrig::SplayTree< T, KeyType > Class Template Reference

Collaboration diagram for internal_poltrig::SplayTree< T, KeyType >:

Public Member Functions
	SplayTree ()
	SplayTree (const SplayTree &rhs)
	~SplayTree ()
void	MakeEmpty ()
bool	IsEmpty () const
long int	Size ()
BTreeNode< T, KeyType > *	Root ()
void	Find (const KeyType &keys, BTreeNode< T, KeyType > *&res)
void	FindMin (BTreeNode< T, KeyType > *&min)
void	FindMax (BTreeNode< T, KeyType > *&max)
void	FindMaxSmallerThan (const KeyType &keys, BTreeNode< T, KeyType > *&res)
void	Insert (const T &x)
void	Delete (const KeyType &keys)
void	Delete (const KeyType &keys, BTreeNode< T, KeyType > *&res)
void	DeleteMin (BTreeNode< T, KeyType > *&min)
void	DeleteMax (BTreeNode< T, KeyType > *&max)
const SplayTree &	operator= (const SplayTree &rhs)
void	PreOrder (void(*Visit)(BTreeNode< T, KeyType > *u))
void	InOrder (void(*Visit)(BTreeNode< T, KeyType > *u))
void	InOrder (void(*Visit)(BTreeNode< T, KeyType > *u, double y), double y)
void	PostOrder (void(*Visit)(BTreeNode< T, KeyType > *u))
int	Height () const
int	Height (BTreeNode< T, KeyType > *t) const
BTreeNode< T, KeyType > *	Left (BTreeNode< T, KeyType > *node)
BTreeNode< T, KeyType > *	Right (BTreeNode< T, KeyType > *node)

Private Member Functions
void	reclaimMemory (BTreeNode< T, KeyType > *t) const
BTreeNode< T, KeyType > *	clone (BTreeNode< T, KeyType > *t) const
void	PreOrder (void(*Visit)(BTreeNode< T, KeyType > *u), BTreeNode< T, KeyType > *t)
void	InOrder (void(*Visit)(BTreeNode< T, KeyType > *u), BTreeNode< T, KeyType > *t)
void	PostOrder (void(*Visit)(BTreeNode< T, KeyType > *u), BTreeNode< T, KeyType > *t)
void	InOrder (void(*Visit)(BTreeNode< T, KeyType > *, double y), BTreeNode< T, KeyType > *t, double y)
void	rotateWithLeftChild (BTreeNode< T, KeyType > *&k2) const
void	rotateWithRightChild (BTreeNode< T, KeyType > *&k1) const
void	splay (const KeyType &keys, BTreeNode< T, KeyType > *&t) const

Private Attributes
BTreeNode< T, KeyType > *	m_root {}
long int	m_size {}

Detailed Description

template<class T, class KeyType>
class internal_poltrig::SplayTree< T, KeyType >

Definition at line 663 of file PolygonTriangulator.cxx.

Constructor & Destructor Documentation

SplayTree() [1/2]

template<class T, class KeyType>

internal_poltrig::SplayTree< T, KeyType >::SplayTree ( )

inlineexplicit

Definition at line 666 of file PolygonTriangulator.cxx.

:m_root(NULL),m_size(0) { }

SplayTree() [2/2]

template<class T, class KeyType>

internal_poltrig::SplayTree< T, KeyType >::SplayTree

(

const SplayTree< T, KeyType > &

rhs

)

Definition at line 732 of file PolygonTriangulator.cxx.

  {
    *this = rhs;
  }

~SplayTree()

template<class T, class KeyType>

internal_poltrig::SplayTree< T, KeyType >::~SplayTree

(

)

Definition at line 741 of file PolygonTriangulator.cxx.

  {
    MakeEmpty( );
  }

Member Function Documentation

clone()

template<class T, class KeyType>

BTreeNode< T, KeyType > * internal_poltrig::SplayTree< T, KeyType >::clone ( BTreeNode< T, KeyType > * t ) const

private

Definition at line 1102 of file PolygonTriangulator.cxx.

  {
    if( t == t->m_left )  // Cannot test against NULLNode!!!
      return NULL;
    else
      return new BTreeNode<T, KeyType>( t->_data, clone( t->m_left ), clone( t->m_right ) );
  }

Delete() [1/2]

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::Delete

(

const KeyType &

keys

)

Definition at line 827 of file PolygonTriangulator.cxx.

  {
    BTreeNode<T, KeyType> *newTree;
 
    splay( keys, m_root );
    KeyType rootk=m_root->keyValue();
    if( rootk != keys ) { return; } // Item not found; do nothing
 
    if( m_root->m_left == NULL ) newTree = m_root->m_right;
    else
      {
    // Find the maximum in the _left subtree
    // Splay it to the root; and then attach _right child
    newTree = m_root->m_left;
    splay( keys, newTree );
    newTree->m_right = m_root->m_right;
      }
 
    delete m_root;
    m_root = newTree;
    m_size--;
  }

Delete() [2/2]

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::Delete	(	const KeyType &	keys,
		BTreeNode< T, KeyType > *&	res )

Definition at line 799 of file PolygonTriangulator.cxx.

  {
    BTreeNode<T, KeyType> *newTree;
 
    splay( keys, m_root );
    if( m_root->keyValue() != keys ) { res=NULL; return; } // Item not found; do nothing
 
    res = m_root;
 
    if( m_root->m_left == NULL )
      newTree = m_root->m_right;
    else
      {
    // Find the maximum in the m_left subtree
    // Splay it to the root; and then attach m_right child
    newTree = m_root->m_left;
    splay( keys, newTree );
    newTree->m_right = m_root->m_right;
      }
 
    m_root = newTree;
    m_size--;
  }

DeleteMax()

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::DeleteMax

(

BTreeNode< T, KeyType > *&

max

)

Definition at line 883 of file PolygonTriangulator.cxx.

  {
    if( IsEmpty( ) )  { max=NULL; return; }
 
    double keys=1.0e30;
    splay( keys, m_root );
 
    max = m_root;
 
    BTreeNode<T, KeyType> *newTree;
    if( m_root->m_left == NULL ) newTree = m_root->m_right;
    else
      {
    newTree = m_root->m_left;
    splay( keys, newTree );
    newTree->m_right = m_root->m_right;
      }
    m_size--;
    m_root = newTree;
  }

DeleteMin()

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::DeleteMin

(

BTreeNode< T, KeyType > *&

min

)

Definition at line 856 of file PolygonTriangulator.cxx.

  {
    if( IsEmpty( ) )  { min=NULL; return; }
 
    double keys=-1.0e30;
    splay( keys, m_root );
 
    min = m_root;
 
    BTreeNode<T, KeyType> *newTree;
    if( m_root->m_left == NULL ) newTree = m_root->m_right;
    else
      {
    newTree = m_root->m_left;
    splay( keys, newTree );
    newTree->m_right = m_root->m_right;
      }
 
    m_size--;
    m_root = newTree;
 
  }

Find()

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::Find	(	const KeyType &	keys,
		BTreeNode< T, KeyType > *&	res )

Definition at line 938 of file PolygonTriangulator.cxx.

  {
    if( IsEmpty( ) ) { res=NULL; return; }
    splay( keys, m_root );
    if( m_root->keyValue() != keys ) { res=NULL; return; }
    else res = m_root;
  }

FindMax()

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::FindMax

(

BTreeNode< T, KeyType > *&

max

)

Definition at line 923 of file PolygonTriangulator.cxx.

  {
    if( IsEmpty( ) )   { max=NULL; return; }
 
    BTreeNode<T, KeyType> *ptr = m_root;
    while( ptr->m_right != NULL ) ptr = ptr->m_right;
    splay( ptr->keyValue(), m_root );
    max =  ptr;
  }

FindMaxSmallerThan()

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::FindMaxSmallerThan	(	const KeyType &	keys,
		BTreeNode< T, KeyType > *&	res )

Definition at line 952 of file PolygonTriangulator.cxx.

  {
    if( IsEmpty( ) ) { res=NULL; return; }
    splay( keys, m_root );
 
    if( m_root->data()->keyValue() < keys) res=m_root;
    else if(m_root->m_left)
      {
    res=m_root->m_left;
    while(res->m_right) res=res->m_right;
      }
    else
      {
    assert(false);
      }
  }

FindMin()

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::FindMin

(

BTreeNode< T, KeyType > *&

min

)

Definition at line 909 of file PolygonTriangulator.cxx.

  {
    if( IsEmpty( ) )  { min=NULL; return; }
    BTreeNode<T, KeyType> *ptr = m_root;
 
    while( ptr->m_left != NULL ) ptr = ptr->m_left;
    splay( ptr->keyValue(), m_root );
    min = ptr;
  }

Height() [1/2]

template<class T, class KeyType>

int internal_poltrig::SplayTree< T, KeyType >::Height ( ) const

inline

Definition at line 700 of file PolygonTriangulator.cxx.

{ return Height(m_root); }  //height of root

Height() [2/2]

template<class T, class KeyType>

int internal_poltrig::SplayTree< T, KeyType >::Height

(

BTreeNode< T, KeyType > *

t

)

const

Definition at line 1175 of file PolygonTriangulator.cxx.

  {
    if(subtree==NULL) return 0;
    int lh=Height(subtree->m_left);
    int rh=Height(subtree->m_right);
 
    return (lh>rh)?(++lh):(++rh);
  }

InOrder() [1/4]

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::InOrder ( void(* Visit )(BTreeNode< T, KeyType > *, double y), BTreeNode< T, KeyType > * t, double y )

private

Definition at line 1144 of file PolygonTriangulator.cxx.

  {
    if(t!=NULL)
      {
        InOrder(Visit,t->m_left, y);
        Visit(t, y);
        InOrder(Visit,t->m_right, y);
      }
  }

InOrder() [2/4]

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::InOrder ( void(* Visit )(BTreeNode< T, KeyType > *u) )

inline

Definition at line 691 of file PolygonTriangulator.cxx.

    { InOrder(Visit, m_root); }

InOrder() [3/4]

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::InOrder ( void(* Visit )(BTreeNode< T, KeyType > *u), BTreeNode< T, KeyType > * t )

private

Definition at line 1129 of file PolygonTriangulator.cxx.

  {
    if(t!=NULL)
      {
        InOrder(Visit,t->m_left);
        Visit(t);
        InOrder(Visit,t->m_right);
      }
  }

InOrder() [4/4]

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::InOrder ( void(* Visit )(BTreeNode< T, KeyType > *u, double y), double y )

inline

Definition at line 694 of file PolygonTriangulator.cxx.

    { InOrder(Visit, m_root, y); }

Insert()

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::Insert

(

const T &

x

)

Definition at line 750 of file PolygonTriangulator.cxx.

  {
 
    BTreeNode<T, KeyType> *newNode= new BTreeNode<T, KeyType>;
    newNode->m_data=x;
 
    if( m_root == NULL )
      {
    newNode->m_left = newNode->m_right = NULL;
    m_root = newNode; ++m_size;
      }
    else
      {
    KeyType keys=x->keyValue();
    splay( keys, m_root );
    KeyType rootk=m_root->keyValue();
    if( keys < rootk )
      {
        newNode->m_left = m_root->m_left;
        newNode->m_right = m_root;
        m_root->m_left = NULL;
        m_root = newNode;
        ++m_size;
      }
        else if( keys > rootk )
      {
 
        newNode->m_right = m_root->m_right;
        newNode->m_left = m_root;
        m_root->m_right = NULL;
        m_root = newNode;
        ++m_size;
      }
        else
      {
        delete newNode;//TK: don't leak
 
        //slight incresed the keyvalue to avoid duplicated keys
        x->increaseKeyValue(1.0e-10);
        Insert(x);
 
      }
      }
  }

IsEmpty()

template<class T, class KeyType>

bool internal_poltrig::SplayTree< T, KeyType >::IsEmpty

(

)

const

Definition at line 987 of file PolygonTriangulator.cxx.

  {
    return m_root == NULL;
  }

Left()

template<class T, class KeyType>

BTreeNode< T, KeyType > * internal_poltrig::SplayTree< T, KeyType >::Left ( BTreeNode< T, KeyType > * node )

inline

Definition at line 702 of file PolygonTriangulator.cxx.

{ return node->m_left; }

MakeEmpty()

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::MakeEmpty

(

)

Definition at line 973 of file PolygonTriangulator.cxx.

  {
    BTreeNode<T, KeyType>* ptr;
    while( !IsEmpty( ) )
      {
    DeleteMax(ptr);
    delete ptr;
      }
  }

operator=()

template<class T, class KeyType>

const SplayTree< T, KeyType > & internal_poltrig::SplayTree< T, KeyType >::operator=

(

const SplayTree< T, KeyType > &

rhs

)

Definition at line 996 of file PolygonTriangulator.cxx.

  {
    if( this != &rhs )
      {
    MakeEmpty( );
    m_root = clone( rhs.m_root );
    m_size = rhs.m_size;
      }
 
    return *this;
  }

PostOrder() [1/2]

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::PostOrder ( void(* Visit )(BTreeNode< T, KeyType > *u) )

inline

Definition at line 697 of file PolygonTriangulator.cxx.

    { PostOrder(Visit, m_root); }

PostOrder() [2/2]

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::PostOrder ( void(* Visit )(BTreeNode< T, KeyType > *u), BTreeNode< T, KeyType > * t )

private

Definition at line 1161 of file PolygonTriangulator.cxx.

  {
    if(t!=NULL)
      {
        PostOrder(Visit,t->m_left);
        PostOrder(Visit,t->m_right);
        Visit(t);
      }
  }

PreOrder() [1/2]

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::PreOrder ( void(* Visit )(BTreeNode< T, KeyType > *u) )

inline

Definition at line 689 of file PolygonTriangulator.cxx.

    { PreOrder(Visit, m_root); }

PreOrder() [2/2]

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::PreOrder ( void(* Visit )(BTreeNode< T, KeyType > *u), BTreeNode< T, KeyType > * t )

private

Definition at line 1114 of file PolygonTriangulator.cxx.

  {
    if(t!=NULL)
      {
    Visit(t);
    PreOrder(Visit,t->m_left);
    PreOrder(Visit,t->m_right);
      }
 
  }

reclaimMemory()

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::reclaimMemory ( BTreeNode< T, KeyType > * t ) const

private

Definition at line 1087 of file PolygonTriangulator.cxx.

  {
    if( t != t->m_left )
      {
    reclaimMemory( t->m_left );
    reclaimMemory( t->m_right );
    delete t;
      }
  }

Right()

template<class T, class KeyType>

BTreeNode< T, KeyType > * internal_poltrig::SplayTree< T, KeyType >::Right ( BTreeNode< T, KeyType > * node )

inline

Definition at line 703 of file PolygonTriangulator.cxx.

{ return node->m_right; }

Root()

template<class T, class KeyType>

BTreeNode< T, KeyType > * internal_poltrig::SplayTree< T, KeyType >::Root ( )

inline

Definition at line 673 of file PolygonTriangulator.cxx.

{ return m_root; }

rotateWithLeftChild()

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::rotateWithLeftChild ( BTreeNode< T, KeyType > *& k2 ) const

private

Definition at line 1062 of file PolygonTriangulator.cxx.

  {
    BTreeNode<T, KeyType> *k1 = k2->m_left;
    k2->m_left = k1->m_right;
    k1->m_right = k2;
    k2 = k1;
  }

rotateWithRightChild()

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::rotateWithRightChild ( BTreeNode< T, KeyType > *& k1 ) const

private

Definition at line 1074 of file PolygonTriangulator.cxx.

  {
    BTreeNode<T, KeyType> *k2 = k1->m_right;
    k1->m_right = k2->m_left;
    k2->m_left = k1;
    k1 = k2;
  }

Size()

template<class T, class KeyType>

long int internal_poltrig::SplayTree< T, KeyType >::Size ( )

inline

Definition at line 672 of file PolygonTriangulator.cxx.

{ return m_size; }

splay()

template<class T, class KeyType>

void internal_poltrig::SplayTree< T, KeyType >::splay ( const KeyType & keys, BTreeNode< T, KeyType > *& t ) const

private

Definition at line 1014 of file PolygonTriangulator.cxx.

  {
    BTreeNode<T, KeyType> *leftTreeMax, *rightTreeMin;
    //    static BTreeNode<T, KeyType> header;
    BTreeNode<T, KeyType> header;//TK: Removed static keyword. Rather a bit slower than thread problems...
 
    header.m_left = header.m_right = NULL;
    leftTreeMax = rightTreeMin = &header;
 
    for( ; ; )
      {
    KeyType rkey=t->keyValue();
    if( keys < rkey )
      {
        if(t->m_left == NULL) break;
        if( keys < t->m_left->keyValue() ) rotateWithLeftChild( t );
        if( t->m_left == NULL ) break;
 
        // Link Right
        rightTreeMin->m_left = t;
        rightTreeMin = t;
        t = t->m_left;
      }
    else if( keys > rkey )
      {
        if( t->m_right == NULL ) break;
        if( keys > t->m_right->keyValue() ) rotateWithRightChild( t );
        if( t->m_right == NULL ) break;
 
        // Link Left
        leftTreeMax->m_right = t;
        leftTreeMax = t;
        t = t->m_right;
      }
    else  break;
      }
 
    leftTreeMax->m_right = t->m_left;
    rightTreeMin->m_left = t->m_right;
    t->m_left = header.m_right;
    t->m_right = header.m_left;
 
  }

Member Data Documentation

m_root

template<class T, class KeyType>

BTreeNode<T, KeyType>* internal_poltrig::SplayTree< T, KeyType >::m_root {}

private

Definition at line 706 of file PolygonTriangulator.cxx.

{};

m_size

template<class T, class KeyType>

long int internal_poltrig::SplayTree< T, KeyType >::m_size {}

private

Definition at line 707 of file PolygonTriangulator.cxx.

{};

---

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

• PolygonTriangulator.cxx