ATLAS Offline Software
Public Member Functions | Private Member Functions | Private Attributes | List of all members
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 117 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 663 of file PolygonTriangulator.cxx.

663 :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 729 of file PolygonTriangulator.cxx.

730  {
731  *this = rhs;
732  }

◆ ~SplayTree()

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

Definition at line 738 of file PolygonTriangulator.cxx.

739  {
740  MakeEmpty( );
741  }

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 1099 of file PolygonTriangulator.cxx.

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

◆ Delete() [1/2]

template<class T , class KeyType >
void internal_poltrig::SplayTree< T, KeyType >::Delete ( const KeyType &  keys)

Definition at line 824 of file PolygonTriangulator.cxx.

825  {
826  BTreeNode<T, KeyType> *newTree;
827 
828  splay( keys, m_root );
829  KeyType rootk=m_root->keyValue();
830  if( rootk != keys ) { return; } // Item not found; do nothing
831 
832  if( m_root->m_left == NULL ) newTree = m_root->m_right;
833  else
834  {
835  // Find the maximum in the _left subtree
836  // Splay it to the root; and then attach _right child
837  newTree = m_root->m_left;
838  splay( keys, newTree );
839  newTree->m_right = m_root->m_right;
840  }
841 
842  delete m_root;
843  m_root = newTree;
844  m_size--;
845  }

◆ 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 796 of file PolygonTriangulator.cxx.

797  {
798  BTreeNode<T, KeyType> *newTree;
799 
800  splay( keys, m_root );
801  if( m_root->keyValue() != keys ) { res=NULL; return; } // Item not found; do nothing
802 
803  res = m_root;
804 
805  if( m_root->m_left == NULL )
806  newTree = m_root->m_right;
807  else
808  {
809  // Find the maximum in the m_left subtree
810  // Splay it to the root; and then attach m_right child
811  newTree = m_root->m_left;
812  splay( keys, newTree );
813  newTree->m_right = m_root->m_right;
814  }
815 
816  m_root = newTree;
817  m_size--;
818  }

◆ DeleteMax()

template<class T , class KeyType >
void internal_poltrig::SplayTree< T, KeyType >::DeleteMax ( BTreeNode< T, KeyType > *&  max)

Definition at line 880 of file PolygonTriangulator.cxx.

881  {
882  if( IsEmpty( ) ) { max=NULL; return; }
883 
884  double keys=1.0e30;
885  splay( keys, m_root );
886 
887  max = m_root;
888 
889  BTreeNode<T, KeyType> *newTree;
890  if( m_root->m_left == NULL ) newTree = m_root->m_right;
891  else
892  {
893  newTree = m_root->m_left;
894  splay( keys, newTree );
895  newTree->m_right = m_root->m_right;
896  }
897  m_size--;
898  m_root = newTree;
899  }

◆ DeleteMin()

template<class T , class KeyType >
void internal_poltrig::SplayTree< T, KeyType >::DeleteMin ( BTreeNode< T, KeyType > *&  min)

Definition at line 853 of file PolygonTriangulator.cxx.

854  {
855  if( IsEmpty( ) ) { min=NULL; return; }
856 
857  double keys=-1.0e30;
858  splay( keys, m_root );
859 
860  min = m_root;
861 
862  BTreeNode<T, KeyType> *newTree;
863  if( m_root->m_left == NULL ) newTree = m_root->m_right;
864  else
865  {
866  newTree = m_root->m_left;
867  splay( keys, newTree );
868  newTree->m_right = m_root->m_right;
869  }
870 
871  m_size--;
872  m_root = newTree;
873 
874  }

◆ Find()

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

Definition at line 935 of file PolygonTriangulator.cxx.

936  {
937  if( IsEmpty( ) ) { res=NULL; return; }
938  splay( keys, m_root );
939  if( m_root->keyValue() != keys ) { res=NULL; return; }
940  else res = m_root;
941  }

◆ FindMax()

template<class T , class KeyType >
void internal_poltrig::SplayTree< T, KeyType >::FindMax ( BTreeNode< T, KeyType > *&  max)

Definition at line 920 of file PolygonTriangulator.cxx.

921  {
922  if( IsEmpty( ) ) { max=NULL; return; }
923 
924  BTreeNode<T, KeyType> *ptr = m_root;
925  while( ptr->m_right != NULL ) ptr = ptr->m_right;
926  splay( ptr->keyValue(), m_root );
927  max = ptr;
928  }

◆ FindMaxSmallerThan()

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

Definition at line 949 of file PolygonTriangulator.cxx.

950  {
951  if( IsEmpty( ) ) { res=NULL; return; }
952  splay( keys, m_root );
953 
954  if( m_root->data()->keyValue() < keys) res=m_root;
955  else if(m_root->m_left)
956  {
957  res=m_root->m_left;
958  while(res->m_right) res=res->m_right;
959  }
960  else
961  {
962  assert(false);
963  }
964  }

◆ FindMin()

template<class T , class KeyType >
void internal_poltrig::SplayTree< T, KeyType >::FindMin ( BTreeNode< T, KeyType > *&  min)

Definition at line 906 of file PolygonTriangulator.cxx.

907  {
908  if( IsEmpty( ) ) { min=NULL; return; }
909  BTreeNode<T, KeyType> *ptr = m_root;
910 
911  while( ptr->m_left != NULL ) ptr = ptr->m_left;
912  splay( ptr->keyValue(), m_root );
913  min = ptr;
914  }

◆ Height() [1/2]

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

Definition at line 697 of file PolygonTriangulator.cxx.

697 { 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 1172 of file PolygonTriangulator.cxx.

1173  {
1174  if(subtree==NULL) return 0;
1175  int lh=Height(subtree->m_left);
1176  int rh=Height(subtree->m_right);
1177 
1178  return (lh>rh)?(++lh):(++rh);
1179  }

◆ InOrder() [1/4]

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

◆ InOrder() [2/4]

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

Definition at line 688 of file PolygonTriangulator.cxx.

689  { InOrder(Visit, m_root); }

◆ InOrder() [3/4]

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

Definition at line 1126 of file PolygonTriangulator.cxx.

1127  {
1128  if(t!=NULL)
1129  {
1130  InOrder(Visit,t->m_left);
1131  Visit(t);
1132  InOrder(Visit,t->m_right);
1133  }
1134  }

◆ InOrder() [4/4]

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

Definition at line 691 of file PolygonTriangulator.cxx.

692  { InOrder(Visit, m_root, y); }

◆ Insert()

template<class T , class KeyType >
void internal_poltrig::SplayTree< T, KeyType >::Insert ( const T &  x)

Definition at line 747 of file PolygonTriangulator.cxx.

748  {
749 
750  BTreeNode<T, KeyType> *newNode= new BTreeNode<T, KeyType>;
751  newNode->m_data=x;
752 
753  if( m_root == NULL )
754  {
755  newNode->m_left = newNode->m_right = NULL;
756  m_root = newNode; ++m_size;
757  }
758  else
759  {
760  KeyType keys=x->keyValue();
761  splay( keys, m_root );
762  KeyType rootk=m_root->keyValue();
763  if( keys < rootk )
764  {
765  newNode->m_left = m_root->m_left;
766  newNode->m_right = m_root;
767  m_root->m_left = NULL;
768  m_root = newNode;
769  ++m_size;
770  }
771  else if( keys > rootk )
772  {
773 
774  newNode->m_right = m_root->m_right;
775  newNode->m_left = m_root;
776  m_root->m_right = NULL;
777  m_root = newNode;
778  ++m_size;
779  }
780  else
781  {
782  delete newNode;//TK: don't leak
783 
784  //slight incresed the keyvalue to avoid duplicated keys
785  x->increaseKeyValue(1.0e-10);
786  Insert(x);
787 
788  }
789  }
790  }

◆ IsEmpty()

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

Definition at line 984 of file PolygonTriangulator.cxx.

985  {
986  return m_root == NULL;
987  }

◆ Left()

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

Definition at line 699 of file PolygonTriangulator.cxx.

699 { return node->m_left; }

◆ MakeEmpty()

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

Definition at line 970 of file PolygonTriangulator.cxx.

971  {
972  BTreeNode<T, KeyType>* ptr;
973  while( !IsEmpty( ) )
974  {
975  DeleteMax(ptr);
976  delete ptr;
977  }
978  }

◆ operator=()

template<class T , class KeyType >
const SplayTree< T, KeyType > & internal_poltrig::SplayTree< T, KeyType >::operator= ( const SplayTree< T, KeyType > &  rhs)

Definition at line 993 of file PolygonTriangulator.cxx.

994  {
995  if( this != &rhs )
996  {
997  MakeEmpty( );
998  m_root = clone( rhs.m_root );
999  m_size = rhs.m_size;
1000  }
1001 
1002  return *this;
1003  }

◆ PostOrder() [1/2]

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

Definition at line 694 of file PolygonTriangulator.cxx.

695  { PostOrder(Visit, m_root); }

◆ PostOrder() [2/2]

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

Definition at line 1158 of file PolygonTriangulator.cxx.

1159  {
1160  if(t!=NULL)
1161  {
1162  PostOrder(Visit,t->m_left);
1163  PostOrder(Visit,t->m_right);
1164  Visit(t);
1165  }
1166  }

◆ PreOrder() [1/2]

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

Definition at line 686 of file PolygonTriangulator.cxx.

687  { PreOrder(Visit, m_root); }

◆ PreOrder() [2/2]

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

Definition at line 1111 of file PolygonTriangulator.cxx.

1112  {
1113  if(t!=NULL)
1114  {
1115  Visit(t);
1116  PreOrder(Visit,t->m_left);
1117  PreOrder(Visit,t->m_right);
1118  }
1119 
1120  }

◆ reclaimMemory()

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

Definition at line 1084 of file PolygonTriangulator.cxx.

1085  {
1086  if( t != t->m_left )
1087  {
1088  reclaimMemory( t->m_left );
1089  reclaimMemory( t->m_right );
1090  delete t;
1091  }
1092  }

◆ Right()

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

Definition at line 700 of file PolygonTriangulator.cxx.

700 { return node->m_right; }

◆ Root()

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

Definition at line 670 of file PolygonTriangulator.cxx.

670 { 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 1059 of file PolygonTriangulator.cxx.

1060  {
1061  BTreeNode<T, KeyType> *k1 = k2->m_left;
1062  k2->m_left = k1->m_right;
1063  k1->m_right = k2;
1064  k2 = k1;
1065  }

◆ rotateWithRightChild()

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

Definition at line 1071 of file PolygonTriangulator.cxx.

1072  {
1073  BTreeNode<T, KeyType> *k2 = k1->m_right;
1074  k1->m_right = k2->m_left;
1075  k2->m_left = k1;
1076  k1 = k2;
1077  }

◆ Size()

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

Definition at line 669 of file PolygonTriangulator.cxx.

669 { 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 1011 of file PolygonTriangulator.cxx.

1012  {
1013  BTreeNode<T, KeyType> *leftTreeMax, *rightTreeMin;
1014  // static BTreeNode<T, KeyType> header;
1015  BTreeNode<T, KeyType> header;//TK: Removed static keyword. Rather a bit slower than thread problems...
1016 
1017  header.m_left = header.m_right = NULL;
1018  leftTreeMax = rightTreeMin = &header;
1019 
1020  for( ; ; )
1021  {
1022  KeyType rkey=t->keyValue();
1023  if( keys < rkey )
1024  {
1025  if(t->m_left == NULL) break;
1026  if( keys < t->m_left->keyValue() ) rotateWithLeftChild( t );
1027  if( t->m_left == NULL ) break;
1028 
1029  // Link Right
1030  rightTreeMin->m_left = t;
1031  rightTreeMin = t;
1032  t = t->m_left;
1033  }
1034  else if( keys > rkey )
1035  {
1036  if( t->m_right == NULL ) break;
1037  if( keys > t->m_right->keyValue() ) rotateWithRightChild( t );
1038  if( t->m_right == NULL ) break;
1039 
1040  // Link Left
1041  leftTreeMax->m_right = t;
1042  leftTreeMax = t;
1043  t = t->m_right;
1044  }
1045  else break;
1046  }
1047 
1048  leftTreeMax->m_right = t->m_left;
1049  rightTreeMin->m_left = t->m_right;
1050  t->m_left = header.m_right;
1051  t->m_right = header.m_left;
1052 
1053  }

Member Data Documentation

◆ m_root

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

Definition at line 703 of file PolygonTriangulator.cxx.

◆ m_size

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

Definition at line 704 of file PolygonTriangulator.cxx.

The documentation for this class was generated from the following file:
internal_poltrig::SplayTree::PostOrder
void PostOrder(void(*Visit)(BTreeNode< T, KeyType > *u))
Definition: PolygonTriangulator.cxx:694
DiTauMassTools::TauTypes::lh
@ lh
Definition: PhysicsAnalysis/TauID/DiTauMassTools/DiTauMassTools/HelperFunctions.h:49
internal_poltrig::SplayTree::clone
BTreeNode< T, KeyType > * clone(BTreeNode< T, KeyType > *t) const
Definition: PolygonTriangulator.cxx:1099
header
Definition: hcg.cxx:526
max
#define max(a, b)
Definition: cfImp.cxx:41
internal_poltrig::SplayTree::IsEmpty
bool IsEmpty() const
Definition: PolygonTriangulator.cxx:984
read_hist_ntuple.t
t
Definition: read_hist_ntuple.py:5
x
#define x
internal_poltrig::SplayTree::PreOrder
void PreOrder(void(*Visit)(BTreeNode< T, KeyType > *u))
Definition: PolygonTriangulator.cxx:686
internal_poltrig::SplayTree::InOrder
void InOrder(void(*Visit)(BTreeNode< T, KeyType > *u))
Definition: PolygonTriangulator.cxx:688
internal_poltrig::SplayTree::Insert
void Insert(const T &x)
Definition: PolygonTriangulator.cxx:747
res
std::pair< std::vector< unsigned int >, bool > res
Definition: JetGroupProductTest.cxx:14
internal_poltrig::SplayTree::Height
int Height() const
Definition: PolygonTriangulator.cxx:697
internal_poltrig::SplayTree::m_root
BTreeNode< T, KeyType > * m_root
Definition: PolygonTriangulator.cxx:703
internal_poltrig::SplayTree::rotateWithRightChild
void rotateWithRightChild(BTreeNode< T, KeyType > *&k1) const
Definition: PolygonTriangulator.cxx:1071
min
#define min(a, b)
Definition: cfImp.cxx:40
internal_poltrig::SplayTree::m_size
long int m_size
Definition: PolygonTriangulator.cxx:704
DiTauMassTools::MaxHistStrategyV2::e
e
Definition: PhysicsAnalysis/TauID/DiTauMassTools/DiTauMassTools/HelperFunctions.h:26
y
#define y
TMVAToMVAUtils::newTree
void newTree(MVAUtils::ForestTMVA *forest, const TMVA::DecisionTreeNode *node, float weight, bool isRegression, bool useYesNoLeaf)
Definition: TMVAToMVAUtils.h:15
internal_poltrig::SplayTree::DeleteMax
void DeleteMax(BTreeNode< T, KeyType > *&max)
Definition: PolygonTriangulator.cxx:880
python.Bindings.keys
keys
Definition: Control/AthenaPython/python/Bindings.py:790
internal_poltrig::SplayTree::MakeEmpty
void MakeEmpty()
Definition: PolygonTriangulator.cxx:970
makeTOC.header
header
Definition: makeTOC.py:28
internal_poltrig::SplayTree::rotateWithLeftChild
void rotateWithLeftChild(BTreeNode< T, KeyType > *&k2) const
Definition: PolygonTriangulator.cxx:1059
internal_poltrig::SplayTree::reclaimMemory
void reclaimMemory(BTreeNode< T, KeyType > *t) const
Definition: PolygonTriangulator.cxx:1084
node
Definition: memory_hooks-stdcmalloc.h:74
internal_poltrig::SplayTree::splay
void splay(const KeyType &keys, BTreeNode< T, KeyType > *&t) const
Definition: PolygonTriangulator.cxx:1011
Generated on Sun Jun 30 2024 22:17:57 for ATLAS Offline Software by   doxygen 1.8.18