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          AddFirst(TObject *obj, Option_t *) override { AddFirst(obj); }
0068    void          AddLast(TObject *obj) override;
0069    void          AddLast(TObject *obj, Option_t *) override { AddLast(obj); }
0070    void          AddAt(TObject *obj, Int_t idx) override;
0071    void          AddAt(TObject *obj, Int_t idx, Option_t *) override { AddAt(obj, idx); }
0072    void          AddAfter(const TObject *after, TObject *obj) override;
0073    void          AddAfter(const TObject *after, TObject *obj, Option_t *) override { AddAfter(after, obj); }
0074    void          AddBefore(const TObject *before, TObject *obj) override;
0075    void          AddBefore(const TObject *before, TObject *obj, Option_t *) override { AddBefore(before, obj); }
0076    void          PutAt(TObject *obj, Int_t idx);
0077    TObject      *RemoveAt(Int_t idx) override;
0078    TObject      *Remove(TObject *obj) override;
0079
0080    TObject      *At(Int_t idx) const override;
0081    TObject      *Before(const TObject *obj) const override;
0082    TObject      *After(const TObject *obj) const override;
0083    TObject      *First() const override;
0084    TObject      *Last() const override;
0085
0086    void          Sort();
0087    Int_t         BinarySearch(TObject *obj);
0088
0089    ClassDefOverride(TOrdCollection,0)  //An ordered collection
0090 };
0091
0092
0093 //////////////////////////////////////////////////////////////////////////
0094 //                                                                      //
0095 // TOrdCollectionIter                                                   //
0096 //                                                                      //
0097 // Iterator of ordered collection.                                      //
0098 //                                                                      //
0099 //////////////////////////////////////////////////////////////////////////
0100
0101 class TOrdCollectionIter : public TIterator {
0102
0103 private:
0104    const TOrdCollection  *fCol;       //collection being iterated
0105    Int_t                  fCurCursor; //current position in collection
0106    Int_t                  fCursor;    //next position in collection
0107    Bool_t                 fDirection; //iteration direction
0108
0109    TOrdCollectionIter() : fCol(nullptr), fCurCursor(0), fCursor(0), fDirection(kIterForward) { }
0110
0111 public:
0112    using iterator_category = std::bidirectional_iterator_tag;
0113    using value_type = TObject *;
0114    using difference_type = std::ptrdiff_t;
0115    using pointer = TObject **;
0116    using const_pointer = const TObject **;
0117    using reference = const TObject *&;
0118
0119    TOrdCollectionIter(const TOrdCollection *col, Bool_t dir = kIterForward);
0120    TOrdCollectionIter(const TOrdCollectionIter &iter);
0121    ~TOrdCollectionIter() { }
0122    TIterator          &operator=(const TIterator &rhs) override;
0123    TOrdCollectionIter &operator=(const TOrdCollectionIter &rhs);
0124
0125    const TCollection *GetCollection() const override { return fCol; }
0126    TObject           *Next() override;
0127    void               Reset() override;
0128    Bool_t             operator!=(const TIterator &aIter) const override;
0129    Bool_t             operator!=(const TOrdCollectionIter &aIter) const;
0130    TObject           *operator*() const override;
0131
0132    ClassDefOverride(TOrdCollectionIter,0)  //Ordered collection iterator
0133 };
0134
0135 //---- inlines -----------------------------------------------------------------
0136
0137 inline Bool_t TOrdCollection::LowWaterMark() const
0138 {
0139    return (fSize < (fCapacity / 4) && fSize > TCollection::kInitCapacity);
0140 }
0141
0142 inline Int_t TOrdCollection::PhysIndex(Int_t idx) const
0143    { return (idx < fGapStart) ? idx : idx + fGapSize; }
0144
0145 inline Int_t TOrdCollection::LogIndex(Int_t idx) const
0146    { return (idx < fGapStart) ? idx : idx - fGapSize; }
0147
0148 #endif