#include "SplayTree.h"
#include "Except.h"
template <class Comparable>
SplayTree<Comparable>::
SplayTree( )
{
nullNode = new BinaryNode<Comparable>;
nullNode->left = nullNode->right = nullNode;
root = nullNode;
}
template <class Comparable>
SplayTree<Comparable>::
SplayTree( const SplayTree<Comparable> & rhs )
{
nullNode = new BinaryNode<Comparable>;
nullNode->left = nullNode->right = nullNode;
root = nullNode;
*this = rhs;
}
template <class Comparable>
SplayTree<Comparable>::
~SplayTree( )
{
makeEmpty( );
delete nullNode;
}
template <class Comparable>
void SplayTree<Comparable>::
insert( const Comparable & x )
{
static BinaryNode<Comparable> *newNode = NULL;
if( newNode == NULL )
newNode = new BinaryNode<Comparable>;
newNode->element = x;
if( root == nullNode )
{
newNode->left = newNode->right = nullNode;
root = newNode;
}
else
{
splay( x, root );
if( x < root->element )
{
newNode->left = root->left;
newNode->right = root;
root->left = nullNode;
root = newNode;
}
else
if( root->element < x )
{
newNode->right = root->right;
newNode->left = root;
root->right = nullNode;
root = newNode;
}
else
throw DuplicateItemException( );
}
newNode = NULL; }
template <class Comparable>
void SplayTree<Comparable>::
remove( const Comparable & x )
{
BinaryNode<Comparable> *newTree;
splay( x, root );
if( root->element != x )
throw ItemNotFoundException( );
if( root->left == nullNode )
newTree = root->right;
else
{
newTree = root->left;
splay( x, newTree );
newTree->right = root->right;
}
delete root;
root = newTree;
}
template <class Comparable>
Cref<Comparable> SplayTree<Comparable>::
elementAt( BinaryNode<Comparable> *t ) const
{
return t == NULL ? Cref<Comparable>( ) : Cref<Comparable>( t->element );
}
template <class Comparable>
Cref<Comparable> SplayTree<Comparable>::
findMin( )
{
if( isEmpty( ) )
return elementAt( NULL );
BinaryNode<Comparable> *ptr = root;
while( ptr->left != nullNode )
ptr = ptr->left;
splay( ptr->element, root );
return elementAt( root );
}
template <class Comparable>
Cref<Comparable> SplayTree<Comparable>::
findMax( )
{
if( isEmpty( ) )
return elementAt( NULL );
BinaryNode<Comparable> *ptr = root;
while( ptr->right != nullNode )
ptr = ptr->right;
splay( ptr->element, root );
return elementAt( root );
}
template <class Comparable>
Cref<Comparable> SplayTree<Comparable>::
find( const Comparable & x )
{
splay( x, root );
if( isEmpty( ) || root->element != x )
return elementAt( NULL );
return elementAt( root );
}
template <class Comparable>
void SplayTree<Comparable>::
makeEmpty( )
{
findMax( ); while( !isEmpty( ) )
remove( root->element );
}
template <class Comparable>
bool SplayTree<Comparable>::
isEmpty( ) const
{
return root == nullNode;
}
template <class Comparable>
const SplayTree<Comparable> &
SplayTree<Comparable>::
operator=( const SplayTree<Comparable> & rhs )
{
if( this != &rhs )
{
makeEmpty( );
root = clone( rhs.root );
}
return *this;
}
template <class Comparable>
void SplayTree<Comparable>::
splay( const Comparable & x,
BinaryNode<Comparable> * & t ) const
{
BinaryNode<Comparable> *leftTreeMax, *rightTreeMin;
static BinaryNode<Comparable> header;
header.left = header.right = nullNode;
leftTreeMax = rightTreeMin = &header;
nullNode->element = x;
for( ; ; )
if( x < t->element )
{
if( x < t->left->element )
rotateWithLeftChild( t );
if( t->left == nullNode )
break;
rightTreeMin->left = t;
rightTreeMin = t;
t = t->left;
}
else if( t->element < x )
{
if( t->right->element < x )
rotateWithRightChild( t );
if( t->right == nullNode )
break;
leftTreeMax->right = t;
leftTreeMax = t;
t = t->right;
}
else
break;
leftTreeMax->right = t->left;
rightTreeMin->left = t->right;
t->left = header.right;
t->right = header.left;
}
template <class Comparable>
void SplayTree<Comparable>::
rotateWithLeftChild( BinaryNode<Comparable> * & k2 ) const
{
BinaryNode<Comparable> *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2 = k1;
}
template <class Comparable>
void SplayTree<Comparable>::
rotateWithRightChild( BinaryNode<Comparable> * & k1 ) const
{
BinaryNode<Comparable> *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1 = k2;
}
template <class Comparable>
void SplayTree<Comparable>::
reclaimMemory( BinaryNode<Comparable> * t ) const
{
if( t != t->left )
{
reclaimMemory( t->left );
reclaimMemory( t->right );
delete t;
}
}
template <class Comparable>
BinaryNode<Comparable> *
SplayTree<Comparable>::
clone( BinaryNode<Comparable> * t ) const
{
if( t == t->left ) return nullNode;
else
return new BinaryNode<Comparable>( t->element, clone( t->left ), clone( t->right ) );
}