#ifndef ROOT_TBtree
#define ROOT_TBtree
#ifndef ROOT_TSeqCollection
#include "TSeqCollection.h"
#endif
#ifndef ROOT_TError
#include "TError.h"
#endif
class TBtNode;
class TBtInnerNode;
class TBtLeafNode;
class TBtree : public TSeqCollection {
friend class TBtNode;
friend class TBtInnerNode;
friend class TBtLeafNode;
private:
TBtNode *fRoot;
Int_t fOrder;
Int_t fOrder2;
Int_t fInnerLowWaterMark;
Int_t fLeafLowWaterMark;
Int_t fInnerMaxIndex;
Int_t fLeafMaxIndex;
void Init(Int_t i);
void RootIsFull();
void RootIsEmpty();
protected:
void IncrNofKeys() { fSize++; }
void DecrNofKeys() { fSize--; }
Int_t IdxAdd(const TObject &obj);
public:
TBtree(Int_t ordern = 3);
virtual ~TBtree();
void Clear(Option_t *option="");
void Delete(Option_t *option="");
TObject *FindObject(const char *name) const;
TObject *FindObject(const TObject *obj) const;
TObject **GetObjectRef(const TObject *) const { return 0; }
TIterator *MakeIterator(Bool_t dir = kIterForward) const;
void Add(TObject *obj);
void AddFirst(TObject *obj) { Add(obj); }
void AddLast(TObject *obj) { Add(obj); }
void AddAt(TObject *obj, Int_t) { Add(obj); }
void AddAfter(const TObject *, TObject *obj) { Add(obj); }
void AddBefore(const TObject *, TObject *obj) { Add(obj); }
TObject *Remove(TObject *obj);
TObject *At(Int_t idx) const;
TObject *Before(const TObject *obj) const;
TObject *After(const TObject *obj) const;
TObject *First() const;
TObject *Last() const;
Int_t Order() { return fOrder; }
TObject *operator[](Int_t i) const;
Int_t Rank(const TObject *obj) const;
ClassDef(TBtree,1)
};
class TBtNode {
friend class TBtree;
friend class TBtInnerNode;
friend class TBtLeafNode;
protected:
Int_t fLast;
TBtInnerNode *fParent;
TBtree *fTree;
Int_t fIsLeaf;
public:
TBtNode(Int_t isleaf, TBtInnerNode *p, TBtree *t = 0);
virtual ~TBtNode();
virtual void Add(const TObject *obj, Int_t index) = 0;
virtual TBtree *GetParentTree() const {return fTree;}
virtual void Remove(Int_t index) = 0;
virtual TObject *operator[](Int_t i) const = 0;
virtual TObject *Found(const TObject *obj, TBtNode **which, Int_t *where) = 0;
virtual Int_t FindRank(const TObject *obj) const = 0;
virtual Int_t NofKeys() const = 0;
virtual TBtLeafNode *FirstLeafNode() = 0;
virtual TBtLeafNode *LastLeafNode() = 0;
virtual void Split() = 0;
};
class TBtItem {
friend class TBtInnerNode;
private:
Int_t fNofKeysInTree;
TObject *fKey;
TBtNode *fTree;
public:
TBtItem();
TBtItem(TBtNode *n, TObject *o);
TBtItem(TObject *o, TBtNode *n);
~TBtItem();
};
class TBtInnerNode : public TBtNode {
private:
TBtItem *fItem;
public:
TBtInnerNode(TBtInnerNode *parent, TBtree *t = 0);
TBtInnerNode(TBtInnerNode *parent, TBtree *tree, TBtNode *oldroot);
~TBtInnerNode();
void Add(const TObject *obj, Int_t idx);
void Add(TBtItem &i, Int_t idx);
void Add(Int_t at, TObject *obj, TBtNode *n);
void AddElt(TBtItem &itm, Int_t at);
void AddElt(Int_t at, TObject *obj, TBtNode *n);
void Remove(Int_t idx);
void RemoveItem(Int_t idx);
TObject *operator[](Int_t i) const;
TObject *Found(const TObject *obj, TBtNode **which, Int_t *where);
Int_t NofKeys(Int_t idx) const;
Int_t NofKeys() const;
void SetTree(Int_t i, TBtNode *node) { fItem[i].fTree = node; node->fParent = this; }
void SetKey(Int_t i, TObject *obj) { fItem[i].fKey = obj; }
void SetItem(Int_t i, TBtItem &itm) { fItem[i] = itm; itm.fTree->fParent = this; }
void SetItem(Int_t i, TObject *obj, TBtNode *node) { SetTree(i, node); SetKey(i, obj); }
Int_t GetNofKeys(Int_t i) const;
void SetNofKeys(Int_t i, Int_t r);
Int_t IncNofKeys(Int_t i, Int_t n=1);
Int_t DecNofKeys(Int_t i, Int_t n=1);
Int_t FindRank(const TObject *obj) const;
Int_t FindRankUp(const TBtNode *n) const;
TBtNode *GetTree(Int_t i) const { return fItem[i].fTree; }
TObject *GetKey(Int_t i) const { return fItem[i].fKey; }
TBtItem &GetItem(Int_t i) const { return fItem[i]; }
Int_t IndexOf(const TBtNode *n) const;
void IncrNofKeys(TBtNode *np);
void DecrNofKeys(TBtNode *np);
TBtLeafNode *FirstLeafNode();
TBtLeafNode *LastLeafNode();
void InformParent();
void Split();
void SplitWith(TBtInnerNode *r, Int_t idx);
void MergeWithRight(TBtInnerNode *r, Int_t idx);
void BalanceWithLeft(TBtInnerNode *l, Int_t idx);
void BalanceWithRight(TBtInnerNode *r, Int_t idx);
void BalanceWith(TBtInnerNode *n, int idx);
void PushLeft(Int_t cnt, TBtInnerNode *leftsib, Int_t parentIdx);
void PushRight(Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx);
void AppendFrom(TBtInnerNode *src, Int_t start, Int_t stop);
void Append(TObject *obj, TBtNode *n);
void Append(TBtItem &itm);
void ShiftLeft(Int_t cnt);
Int_t Psize() const { return fLast; }
Int_t Vsize() const;
Int_t MaxIndex() const { return fTree->fInnerMaxIndex; }
Int_t MaxPsize() const { return fTree->fInnerMaxIndex; }
Int_t IsFull() const { return fLast == MaxIndex(); }
void IsFull(TBtNode *n);
Int_t IsAlmostFull() const { return fLast >= MaxIndex() - 1; }
Int_t IsLow() const { return fLast < fTree->fInnerLowWaterMark; }
void IsLow(TBtNode *n);
};
class TBtLeafNode : public TBtNode {
friend class TBtInnerNode;
private:
TObject **fItem;
public:
TBtLeafNode(TBtInnerNode *p, const TObject *obj = 0, TBtree *t = 0);
~TBtLeafNode();
void Add(const TObject *obj, Int_t idx);
void Remove(Int_t idx);
void RemoveItem(Int_t idx) { Remove(idx); }
TObject *operator[](Int_t i) const;
TObject *Found(const TObject *obj, TBtNode **which, Int_t *where);
Int_t NofKeys(Int_t i) const;
Int_t NofKeys() const;
Int_t FindRank(const TObject *obj) const;
TObject *GetKey(Int_t idx ) { return fItem[idx]; }
void SetKey(Int_t idx, TObject *obj) { fItem[idx] = obj; }
Int_t IndexOf(const TObject *obj) const;
TBtLeafNode *FirstLeafNode();
TBtLeafNode *LastLeafNode();
void Split();
void SplitWith(TBtLeafNode *r, Int_t idx);
void MergeWithRight(TBtLeafNode *r, Int_t idx);
void BalanceWithLeft(TBtLeafNode *l, Int_t idx);
void BalanceWithRight(TBtLeafNode *r, Int_t idx);
void BalanceWith(TBtLeafNode *n, Int_t idx);
void PushLeft(Int_t cnt, TBtLeafNode *l, Int_t parentIndex);
void PushRight(Int_t cnt, TBtLeafNode *r, Int_t parentIndex);
void AppendFrom(TBtLeafNode *src, Int_t start, Int_t stop);
void Append(TObject *obj);
void ShiftLeft(Int_t cnt);
Int_t Psize() const { return fLast + 1; }
Int_t Vsize() const;
Int_t MaxIndex() const { return fTree->fLeafMaxIndex; }
Int_t MaxPsize() const { return fTree->fLeafMaxIndex + 1; }
Int_t IsFull() const { return fLast == MaxIndex(); }
Int_t IsAlmostFull() const { return fLast >= MaxIndex() - 1; }
Int_t IsLow() const { return fLast < fTree->fLeafLowWaterMark; }
};
class TBtreeIter : public TIterator {
private:
const TBtree *fTree;
Int_t fCursor;
Bool_t fDirection;
TBtreeIter() : fTree(0), fCursor(0) { }
public:
TBtreeIter(const TBtree *t, Bool_t dir = kIterForward);
TBtreeIter(const TBtreeIter &iter);
~TBtreeIter() { }
TIterator &operator=(const TIterator &rhs);
TBtreeIter &operator=(const TBtreeIter &rhs);
const TCollection *GetCollection() const { return fTree; }
TObject *Next();
void Reset();
ClassDef(TBtreeIter,0)
};
inline TObject *TBtree::operator[](Int_t i) const
{
return (*fRoot)[i];
}
inline TObject *TBtree::At(Int_t i) const
{
return (*fRoot)[i];
}
inline TObject *TBtree::First() const
{
return (*fRoot)[0];
}
inline TObject *TBtree::Last() const
{
return (*fRoot)[fSize-1];
}
inline Int_t TBtInnerNode::GetNofKeys(Int_t i) const
{
R__ASSERT(i >= 0 && i <= fLast);
return fItem[i].fNofKeysInTree;
}
inline Int_t TBtInnerNode::NofKeys(Int_t idx) const
{
return GetNofKeys(idx);
}
inline void TBtInnerNode::SetNofKeys(Int_t i, Int_t r)
{
fItem[i].fNofKeysInTree = r;
}
inline Int_t TBtInnerNode::IncNofKeys(Int_t i, Int_t n)
{
return (fItem[i].fNofKeysInTree += n);
}
inline Int_t TBtInnerNode::DecNofKeys(Int_t i, Int_t n)
{
return (fItem[i].fNofKeysInTree -= n);
}
inline Int_t TBtInnerNode::Vsize() const
{
R__ASSERT(fParent != 0 && fParent->GetTree(0) != (TBtNode *)this);
return Psize()+1;
}
inline TObject *TBtLeafNode::operator[](Int_t i) const
{
R__ASSERT(i >= 0 && i <= fLast);
return fItem[i];
}
inline Int_t TBtLeafNode::Vsize() const
{
R__ASSERT(fParent != 0 && fParent->GetTree(0) != (TBtNode *)this);
return Psize()+1;
}
#endif
ROOT page - Class index - Class Hierarchy - Top of the page
This page has been automatically generated. If you have any comments or suggestions about the page layout send a mail to ROOT support, or contact the developers with any questions or problems regarding ROOT.