include/root/TOrdCollection.h

0001 // @(#)root/cont:$Id$
0002 // Author: Fons Rademakers   13/09/95
0003
0004 /*************************************************************************
0005  * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers.               *
0006  * All rights reserved.                                                  *
0007  *                                                                       *
0008  * For the licensing terms see $ROOTSYS/LICENSE.                         *
0009  * For the list of contributors see $ROOTSYS/README/CREDITS.             *
0010  *************************************************************************/
0011
0012 #ifndef ROOT_TOrdCollection
0013 #define ROOT_TOrdCollection
0014
0015
0016 //////////////////////////////////////////////////////////////////////////
0017 //                                                                      //
0018 // TOrdCollection                                                       //
0019 //                                                                      //
0020 // Ordered collection.                                                  //
0021 //                                                                      //
0022 //////////////////////////////////////////////////////////////////////////
0023
0024 #include "TSeqCollection.h"
0025
0026 #include <iterator>
0027
0028
0029 class TOrdCollectionIter;
0030
0031
0032 class TOrdCollection : public TSeqCollection {
0033
0034 friend class  TOrdCollectionIter;
0035
0036 private:
0037    TObject  **fCont;
0038    Int_t      fCapacity;
0039    Int_t      fGapStart;
0040    Int_t      fGapSize;
0041
0042    Int_t      PhysIndex(Int_t idx) const;
0043    Int_t      LogIndex(Int_t idx) const;
0044    void       MoveGapTo(Int_t newGapStart);
0045    Bool_t     IllegalIndex(const char *method, Int_t idx) const;
0046    void       Init(Int_t capacity);
0047    Bool_t     LowWaterMark() const;
0048    void       SetCapacity(Int_t newCapacity);
0049
0050    TOrdCollection(const TOrdCollection&) = delete;
0051    TOrdCollection& operator=(const TOrdCollection&) = delete;
0052
0053 public:
0054    enum { kDefaultCapacity = 1, kMinExpand = 8, kShrinkFactor = 2 };
0055
0056    typedef TOrdCollectionIter Iterator_t;
0057
0058    TOrdCollection(Int_t capacity = kDefaultCapacity);
0059    ~TOrdCollection();
0060    void          Clear(Option_t *option="") override;
0061    void          Delete(Option_t *option="") override;
0062    TObject     **GetObjectRef(const TObject *obj) const override;
0063    Int_t         IndexOf(const TObject *obj) const override;
0064    TIterator    *MakeIterator(Bool_t dir = kIterForward) const override;
0065
0066    void          AddFirst(TObject *obj) override;
0067    void          AddLast(TObject *obj) override;
0068    void          AddAt(TObject *obj, Int_t idx) override;
0069    void          AddAfter(const TObject *after, TObject *obj) override;
0070    void          AddBefore(const TObject *before, TObject *obj) override;
0071    void          PutAt(TObject *obj, Int_t idx);
0072    TObject      *RemoveAt(Int_t idx) override;
0073    TObject      *Remove(TObject *obj) override;
0074
0075    TObject      *At(Int_t idx) const override;
0076    TObject      *Before(const TObject *obj) const override;
0077    TObject      *After(const TObject *obj) const override;
0078    TObject      *First() const override;
0079    TObject      *Last() const override;
0080
0081    void          Sort();
0082    Int_t         BinarySearch(TObject *obj);
0083
0084    ClassDefOverride(TOrdCollection,0)  //An ordered collection
0085 };
0086
0087
0088 //////////////////////////////////////////////////////////////////////////
0089 //                                                                      //
0090 // TOrdCollectionIter                                                   //
0091 //                                                                      //
0092 // Iterator of ordered collection.                                      //
0093 //                                                                      //
0094 //////////////////////////////////////////////////////////////////////////
0095
0096 class TOrdCollectionIter : public TIterator {
0097
0098 private:
0099    const TOrdCollection  *fCol;       //collection being iterated
0100    Int_t                  fCurCursor; //current position in collection
0101    Int_t                  fCursor;    //next position in collection
0102    Bool_t                 fDirection; //iteration direction
0103
0104    TOrdCollectionIter() : fCol(nullptr), fCurCursor(0), fCursor(0), fDirection(kIterForward) { }
0105
0106 public:
0107    using iterator_category = std::bidirectional_iterator_tag;
0108    using value_type = TObject *;
0109    using difference_type = std::ptrdiff_t;
0110    using pointer = TObject **;
0111    using const_pointer = const TObject **;
0112    using reference = const TObject *&;
0113
0114    TOrdCollectionIter(const TOrdCollection *col, Bool_t dir = kIterForward);
0115    TOrdCollectionIter(const TOrdCollectionIter &iter);
0116    ~TOrdCollectionIter() { }
0117    TIterator          &operator=(const TIterator &rhs) override;
0118    TOrdCollectionIter &operator=(const TOrdCollectionIter &rhs);
0119
0120    const TCollection *GetCollection() const override { return fCol; }
0121    TObject           *Next() override;
0122    void               Reset() override;
0123    Bool_t             operator!=(const TIterator &aIter) const override;
0124    Bool_t             operator!=(const TOrdCollectionIter &aIter) const;
0125    TObject           *operator*() const override;
0126
0127    ClassDefOverride(TOrdCollectionIter,0)  //Ordered collection iterator
0128 };
0129
0130 //---- inlines -----------------------------------------------------------------
0131
0132 inline Bool_t TOrdCollection::LowWaterMark() const
0133 {
0134    return (fSize < (fCapacity / 4) && fSize > TCollection::kInitCapacity);
0135 }
0136
0137 inline Int_t TOrdCollection::PhysIndex(Int_t idx) const
0138    { return (idx < fGapStart) ? idx : idx + fGapSize; }
0139
0140 inline Int_t TOrdCollection::LogIndex(Int_t idx) const
0141    { return (idx < fGapStart) ? idx : idx - fGapSize; }
0142
0143 #endif