// @(#)root/cont:$Id$
// Author: Fons Rademakers   13/09/95

/*************************************************************************
 * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers.               *
 * All rights reserved.                                                  *
 *                                                                       *
 * For the licensing terms see $ROOTSYS/LICENSE.                         *
 * For the list of contributors see $ROOTSYS/README/CREDITS.             *
 *************************************************************************/

#ifndef ROOT_TOrdCollection
#define ROOT_TOrdCollection


//////////////////////////////////////////////////////////////////////////
//                                                                      //
// TOrdCollection                                                       //
//                                                                      //
// Ordered collection.                                                  //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

#ifndef ROOT_TSeqCollection
#include "TSeqCollection.h"
#endif

#include <iterator>


class TOrdCollectionIter;


class TOrdCollection : public TSeqCollection {

friend class  TOrdCollectionIter;

private:
   TObject  **fCont;
   Int_t      fCapacity;
   Int_t      fGapStart;
   Int_t      fGapSize;

   Int_t      PhysIndex(Int_t idx) const;
   Int_t      LogIndex(Int_t idx) const;
   void       MoveGapTo(Int_t newGapStart);
   Bool_t     IllegalIndex(const char *method, Int_t idx) const;
   void       Init(Int_t capacity);
   Bool_t     LowWaterMark() const;
   void       SetCapacity(Int_t newCapacity);

   TOrdCollection(const TOrdCollection&); // Not implemented
   TOrdCollection& operator=(const TOrdCollection&); // Not implemented

public:
   enum { kDefaultCapacity = 1, kMinExpand = 8, kShrinkFactor = 2 };

   typedef TOrdCollectionIter Iterator_t;

   TOrdCollection(Int_t capacity = kDefaultCapacity);
   ~TOrdCollection();
   void          Clear(Option_t *option="");
   void          Delete(Option_t *option="");
   TObject     **GetObjectRef(const TObject *obj) const;
   Int_t         IndexOf(const TObject *obj) const;
   TIterator    *MakeIterator(Bool_t dir = kIterForward) const;

   void          AddFirst(TObject *obj);
   void          AddLast(TObject *obj);
   void          AddAt(TObject *obj, Int_t idx);
   void          AddAfter(const TObject *after, TObject *obj);
   void          AddBefore(const TObject *before, TObject *obj);
   void          PutAt(TObject *obj, Int_t idx);
   TObject      *RemoveAt(Int_t idx);
   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;

   void          Sort();
   Int_t         BinarySearch(TObject *obj);

   ClassDef(TOrdCollection,0)  //An ordered collection
};


//////////////////////////////////////////////////////////////////////////
//                                                                      //
// TOrdCollectionIter                                                   //
//                                                                      //
// Iterator of ordered collection.                                      //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

class TOrdCollectionIter : public TIterator,
                           public std::iterator<std::bidirectional_iterator_tag,
                                                TObject*, std::ptrdiff_t,
                                                const TObject**, const TObject*&> {

private:
   const TOrdCollection  *fCol;       //collection being iterated
   Int_t                  fCurCursor; //current position in collection
   Int_t                  fCursor;    //next position in collection
   Bool_t                 fDirection; //iteration direction

   TOrdCollectionIter() : fCol(0), fCurCursor(0), fCursor(0), fDirection(kIterForward) { }

public:
   TOrdCollectionIter(const TOrdCollection *col, Bool_t dir = kIterForward);
   TOrdCollectionIter(const TOrdCollectionIter &iter);
   ~TOrdCollectionIter() { }
   TIterator          &operator=(const TIterator &rhs);
   TOrdCollectionIter &operator=(const TOrdCollectionIter &rhs);

   const TCollection *GetCollection() const { return fCol; }
   TObject           *Next();
   void               Reset();
   Bool_t             operator!=(const TIterator &aIter) const;
   Bool_t             operator!=(const TOrdCollectionIter &aIter) const;
   TObject           *operator*() const;

   ClassDef(TOrdCollectionIter,0)  //Ordered collection iterator
};


//---- inlines -----------------------------------------------------------------

inline Bool_t TOrdCollection::LowWaterMark() const
{
   return (fSize < (fCapacity / 4) && fSize > TCollection::kInitCapacity);
}

inline Int_t TOrdCollection::PhysIndex(Int_t idx) const
   { return (idx < fGapStart) ? idx : idx + fGapSize; }

inline Int_t TOrdCollection::LogIndex(Int_t idx) const
   { return (idx < fGapStart) ? idx : idx - fGapSize; }

#endif
 TOrdCollection.h:1
 TOrdCollection.h:2
 TOrdCollection.h:3
 TOrdCollection.h:4
 TOrdCollection.h:5
 TOrdCollection.h:6
 TOrdCollection.h:7
 TOrdCollection.h:8
 TOrdCollection.h:9
 TOrdCollection.h:10
 TOrdCollection.h:11
 TOrdCollection.h:12
 TOrdCollection.h:13
 TOrdCollection.h:14
 TOrdCollection.h:15
 TOrdCollection.h:16
 TOrdCollection.h:17
 TOrdCollection.h:18
 TOrdCollection.h:19
 TOrdCollection.h:20
 TOrdCollection.h:21
 TOrdCollection.h:22
 TOrdCollection.h:23
 TOrdCollection.h:24
 TOrdCollection.h:25
 TOrdCollection.h:26
 TOrdCollection.h:27
 TOrdCollection.h:28
 TOrdCollection.h:29
 TOrdCollection.h:30
 TOrdCollection.h:31
 TOrdCollection.h:32
 TOrdCollection.h:33
 TOrdCollection.h:34
 TOrdCollection.h:35
 TOrdCollection.h:36
 TOrdCollection.h:37
 TOrdCollection.h:38
 TOrdCollection.h:39
 TOrdCollection.h:40
 TOrdCollection.h:41
 TOrdCollection.h:42
 TOrdCollection.h:43
 TOrdCollection.h:44
 TOrdCollection.h:45
 TOrdCollection.h:46
 TOrdCollection.h:47
 TOrdCollection.h:48
 TOrdCollection.h:49
 TOrdCollection.h:50
 TOrdCollection.h:51
 TOrdCollection.h:52
 TOrdCollection.h:53
 TOrdCollection.h:54
 TOrdCollection.h:55
 TOrdCollection.h:56
 TOrdCollection.h:57
 TOrdCollection.h:58
 TOrdCollection.h:59
 TOrdCollection.h:60
 TOrdCollection.h:61
 TOrdCollection.h:62
 TOrdCollection.h:63
 TOrdCollection.h:64
 TOrdCollection.h:65
 TOrdCollection.h:66
 TOrdCollection.h:67
 TOrdCollection.h:68
 TOrdCollection.h:69
 TOrdCollection.h:70
 TOrdCollection.h:71
 TOrdCollection.h:72
 TOrdCollection.h:73
 TOrdCollection.h:74
 TOrdCollection.h:75
 TOrdCollection.h:76
 TOrdCollection.h:77
 TOrdCollection.h:78
 TOrdCollection.h:79
 TOrdCollection.h:80
 TOrdCollection.h:81
 TOrdCollection.h:82
 TOrdCollection.h:83
 TOrdCollection.h:84
 TOrdCollection.h:85
 TOrdCollection.h:86
 TOrdCollection.h:87
 TOrdCollection.h:88
 TOrdCollection.h:89
 TOrdCollection.h:90
 TOrdCollection.h:91
 TOrdCollection.h:92
 TOrdCollection.h:93
 TOrdCollection.h:94
 TOrdCollection.h:95
 TOrdCollection.h:96
 TOrdCollection.h:97
 TOrdCollection.h:98
 TOrdCollection.h:99
 TOrdCollection.h:100
 TOrdCollection.h:101
 TOrdCollection.h:102
 TOrdCollection.h:103
 TOrdCollection.h:104
 TOrdCollection.h:105
 TOrdCollection.h:106
 TOrdCollection.h:107
 TOrdCollection.h:108
 TOrdCollection.h:109
 TOrdCollection.h:110
 TOrdCollection.h:111
 TOrdCollection.h:112
 TOrdCollection.h:113
 TOrdCollection.h:114
 TOrdCollection.h:115
 TOrdCollection.h:116
 TOrdCollection.h:117
 TOrdCollection.h:118
 TOrdCollection.h:119
 TOrdCollection.h:120
 TOrdCollection.h:121
 TOrdCollection.h:122
 TOrdCollection.h:123
 TOrdCollection.h:124
 TOrdCollection.h:125
 TOrdCollection.h:126
 TOrdCollection.h:127
 TOrdCollection.h:128
 TOrdCollection.h:129
 TOrdCollection.h:130
 TOrdCollection.h:131
 TOrdCollection.h:132
 TOrdCollection.h:133
 TOrdCollection.h:134
 TOrdCollection.h:135
 TOrdCollection.h:136
 TOrdCollection.h:137
 TOrdCollection.h:138
 TOrdCollection.h:139
 TOrdCollection.h:140
 TOrdCollection.h:141
 TOrdCollection.h:142