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 120 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.

666 :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.

733  {
734  *this = rhs;
735  }

◆ ~SplayTree()

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

Definition at line 741 of file PolygonTriangulator.cxx.

742  {
743  MakeEmpty( );
744  }

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.

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

◆ 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.

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

◆ 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.

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

◆ 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.

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

◆ 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.

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

◆ 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.

939  {
940  if( IsEmpty( ) ) { res=NULL; return; }
941  splay( keys, m_root );
942  if( m_root->keyValue() != keys ) { res=NULL; return; }
943  else res = m_root;
944  }

◆ 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.

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

◆ 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.

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

◆ 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.

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

◆ 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.

700 { 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.

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

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

692  { 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 1129 of file PolygonTriangulator.cxx.

1130  {
1131  if(t!=NULL)
1132  {
1133  InOrder(Visit,t->m_left);
1134  Visit(t);
1135  InOrder(Visit,t->m_right);
1136  }
1137  }

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

695  { 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.

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

◆ IsEmpty()

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

Definition at line 987 of file PolygonTriangulator.cxx.

988  {
989  return m_root == NULL;
990  }

◆ 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.

702 { 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.

974  {
975  BTreeNode<T, KeyType>* ptr;
976  while( !IsEmpty( ) )
977  {
978  DeleteMax(ptr);
979  delete ptr;
980  }
981  }

◆ 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.

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

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

698  { 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 1161 of file PolygonTriangulator.cxx.

1162  {
1163  if(t!=NULL)
1164  {
1165  PostOrder(Visit,t->m_left);
1166  PostOrder(Visit,t->m_right);
1167  Visit(t);
1168  }
1169  }

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

690  { 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 1114 of file PolygonTriangulator.cxx.

1115  {
1116  if(t!=NULL)
1117  {
1118  Visit(t);
1119  PreOrder(Visit,t->m_left);
1120  PreOrder(Visit,t->m_right);
1121  }
1122 
1123  }

◆ 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.

1088  {
1089  if( t != t->m_left )
1090  {
1091  reclaimMemory( t->m_left );
1092  reclaimMemory( t->m_right );
1093  delete t;
1094  }
1095  }

◆ 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.

703 { 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.

673 { 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.

1063  {
1064  BTreeNode<T, KeyType> *k1 = k2->m_left;
1065  k2->m_left = k1->m_right;
1066  k1->m_right = k2;
1067  k2 = k1;
1068  }

◆ 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.

1075  {
1076  BTreeNode<T, KeyType> *k2 = k1->m_right;
1077  k1->m_right = k2->m_left;
1078  k2->m_left = k1;
1079  k1 = k2;
1080  }

◆ Size()

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

Definition at line 672 of file PolygonTriangulator.cxx.

672 { 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.

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

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:
AllowedVariables::e
e
Definition: AsgElectronSelectorTool.cxx:37
internal_poltrig::SplayTree::PostOrder
void PostOrder(void(*Visit)(BTreeNode< T, KeyType > *u))
Definition: PolygonTriangulator.cxx:697
DiTauMassTools::TauTypes::lh
@ lh
Definition: PhysicsAnalysis/TauID/DiTauMassTools/DiTauMassTools/HelperFunctions.h:53
internal_poltrig::SplayTree::clone
BTreeNode< T, KeyType > * clone(BTreeNode< T, KeyType > *t) const
Definition: PolygonTriangulator.cxx:1102
header
Definition: hcg.cxx:527
max
constexpr double max()
Definition: ap_fixedTest.cxx:33
min
constexpr double min()
Definition: ap_fixedTest.cxx:26
internal_poltrig::SplayTree::IsEmpty
bool IsEmpty() const
Definition: PolygonTriangulator.cxx:987
read_hist_ntuple.t
t
Definition: read_hist_ntuple.py:5
dbg::ptr
void * ptr(T *p)
Definition: SGImplSvc.cxx:74
x
#define x
internal_poltrig::SplayTree::PreOrder
void PreOrder(void(*Visit)(BTreeNode< T, KeyType > *u))
Definition: PolygonTriangulator.cxx:689
internal_poltrig::SplayTree::InOrder
void InOrder(void(*Visit)(BTreeNode< T, KeyType > *u))
Definition: PolygonTriangulator.cxx:691
internal_poltrig::SplayTree::Insert
void Insert(const T &x)
Definition: PolygonTriangulator.cxx:750
res
std::pair< std::vector< unsigned int >, bool > res
Definition: JetGroupProductTest.cxx:11
internal_poltrig::SplayTree::Height
int Height() const
Definition: PolygonTriangulator.cxx:700
internal_poltrig::SplayTree::m_root
BTreeNode< T, KeyType > * m_root
Definition: PolygonTriangulator.cxx:706
internal_poltrig::SplayTree::rotateWithRightChild
void rotateWithRightChild(BTreeNode< T, KeyType > *&k1) const
Definition: PolygonTriangulator.cxx:1074
internal_poltrig::SplayTree::m_size
long int m_size
Definition: PolygonTriangulator.cxx:707
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:883
python.Bindings.keys
keys
Definition: Control/AthenaPython/python/Bindings.py:801
internal_poltrig::SplayTree::MakeEmpty
void MakeEmpty()
Definition: PolygonTriangulator.cxx:973
makeTOC.header
header
Definition: makeTOC.py:28
internal_poltrig::SplayTree::rotateWithLeftChild
void rotateWithLeftChild(BTreeNode< T, KeyType > *&k2) const
Definition: PolygonTriangulator.cxx:1062
internal_poltrig::SplayTree::reclaimMemory
void reclaimMemory(BTreeNode< T, KeyType > *t) const
Definition: PolygonTriangulator.cxx:1087
node
Definition: node.h:24
internal_poltrig::SplayTree::splay
void splay(const KeyType &keys, BTreeNode< T, KeyType > *&t) const
Definition: PolygonTriangulator.cxx:1014
Generated on Sun Nov 23 2025 21:55:45 for ATLAS Offline Software by   doxygen 1.8.18