#ifndef ROOT_TBtree #define ROOT_TBtree //+SEQ,CopyRight,T=NOINCLUDE. ////////////////////////////////////////////////////////////////////////// // // // TBtree // // // // Btree class. TBtree inherits from the TSeqCollection ABC. // // // // For a more extensive algorithmic description see the TBtree source. // // // ////////////////////////////////////////////////////////////////////////// #ifndef ROOT_TSeqCollection //*KEEP,TSeqCollection. #include "TSeqCollection.h" //*KEND. #endif #ifndef ROOT_TError //*KEEP,TError. #include "TError.h" //*KEND. #endif #if defined(R__MAC) && defined(SetItem) # undef SetItem # undef GetItem #endif class TBtNode; class TBtInnerNode; class TBtLeafNode; class TBtree : public TSeqCollection { friend class TBtNode; friend class TBtInnerNode; friend class TBtLeafNode; private: TBtNode *fRoot; //root node of btree Int_t fOrder; //the order of the tree (should be > 2) Int_t fOrder2; //order*2+1 (assumes a memory access is //cheaper than a multiply and increment by one Int_t fInnerLowWaterMark; //inner node low water mark Int_t fLeafLowWaterMark; //leaf low water mark Int_t fInnerMaxIndex; //maximum inner node index Int_t fLeafMaxIndex; //maximum leaf index void Init(Int_t i); //initialize btree void RootIsFull(); //called when the root node is full void RootIsEmpty(); //called when root is empty protected: void IncrNofKeys() { fSize++; } void DecrNofKeys() { fSize--; } // add the object to the tree; return the index in the tree at which // the object was inserted. NOTE: other insertions and deletions may // change this object's index. Int_t IdxAdd(const TObject &obj); public: TBtree(Int_t ordern = 3); //create a TBtree of order n ~TBtree(); void Clear(Option_t *option=""); void Delete(Option_t *option=""); TObject *FindObject(const Text_t *name) const; TObject *FindObject(TObject *obj) const; 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(TObject *, TObject *obj) { Add(obj); } void AddBefore(TObject *, TObject *obj) { Add(obj); } TObject *Remove(TObject *obj); TObject *At(Int_t idx) const; TObject *Before(TObject *obj) const; TObject *After(TObject *obj) const; TObject *First() const; TObject *Last() const; //void PrintOn(ostream &os) const; Int_t Order() { return fOrder; } TObject *operator[](Int_t i) const; Int_t Rank(const TObject *obj) const; ClassDef(TBtree,1) //A B-tree }; ////////////////////////////////////////////////////////////////////////// // // // TBtNode // // // // Abstract base class (ABC) of a TBtree node. // // // ////////////////////////////////////////////////////////////////////////// class TBtNode { friend class TBtree; friend class TBtInnerNode; friend class TBtLeafNode; protected: Int_t fLast; // for inner node 1 <= fLast <= fInnerMaxIndex // for leaf node 1 <= fLast <= fLeafMaxIndex // (fLast==0 only temporarily while the tree is being // updated) TBtInnerNode *fParent; // a parent is always an inner node (or 0 for the root) TBtree *fTree; // the tree of which this node is a part Int_t fIsLeaf; // run-time type flag 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; // # keys in or below this node virtual TBtLeafNode *FirstLeafNode() = 0; virtual TBtLeafNode *LastLeafNode() = 0; virtual void Split() = 0; // virtual void PrintOn(ostream &os) const = 0; // friend ostream &operator<<(ostream &os, const TBtNode &node); }; ////////////////////////////////////////////////////////////////////////// // // // TBtItem // // // // Item stored in inner nodes of a TBtree. // // // ////////////////////////////////////////////////////////////////////////// class TBtItem { friend class TBtInnerNode; private: Int_t fNofKeysInTree; // number of keys in TBtree TObject *fKey; // key TBtNode *fTree; // sub-tree public: TBtItem(); TBtItem(TBtNode *n, TObject *o); TBtItem(TObject *o, TBtNode *n); ~TBtItem(); }; ////////////////////////////////////////////////////////////////////////// // // // TBtInnerNode // // // // Inner node of a TBtree. // // // ////////////////////////////////////////////////////////////////////////// class TBtInnerNode : public TBtNode { private: TBtItem *fItem; // actually fItem[MaxIndex()+1] is desired 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; } // void PrintOn(ostream &os) const; 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); }; ////////////////////////////////////////////////////////////////////////// // // // TBtLeafNode // // // // Leaf node of a TBtree. // // // ////////////////////////////////////////////////////////////////////////// class TBtLeafNode : public TBtNode { friend class TBtInnerNode; private: TObject **fItem; // actually TObject *fItem[MaxIndex()+1] is desired 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; } // void PrintOn(ostream &os) const; Int_t IsFull() const { return fLast == MaxIndex(); } Int_t IsAlmostFull() const { return fLast >= MaxIndex() - 1; } Int_t IsLow() const { return fLast < fTree->fLeafLowWaterMark; } }; ////////////////////////////////////////////////////////////////////////// // // // TBtreeIter // // // // Iterator of btree. // // // ////////////////////////////////////////////////////////////////////////// class TBtreeIter : public TIterator { private: const TBtree *fTree; //btree being iterated Int_t fCursor; //current position in btree Bool_t fDirection; //iteration direction 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) //B-tree iterator }; //----- TBtree inlines --------------------------------------------------------- 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]; } //----- TBtInnerNode inlines --------------------------------------------------- inline Int_t TBtInnerNode::GetNofKeys(Int_t i) const { 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 { Assert(fParent != 0 && fParent->GetTree(0) != (TBtNode *)this); return Psize()+1; } //----- TBtLeafNode inlines ---------------------------------------------------- inline TObject *TBtLeafNode::operator[](Int_t i) const { Assert(i >= 0 && i <= fLast); return fItem[i]; } inline Int_t TBtLeafNode::Vsize() const { Assert(fParent != 0 && fParent->GetTree(0) != (TBtNode *)this); return Psize()+1; } //inline ostream &operator<<(ostream& outputStream, const TBtNode &aNode) //{ // aNode.PrintOn(outputStream); // return outputStream; //} #endif