// @(#)root/cont:$Id$
// Author: Fons Rademakers   10/08/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_TList
#define ROOT_TList


//////////////////////////////////////////////////////////////////////////
//                                                                      //
// TList                                                                //
//                                                                      //
// A doubly linked list. All classes inheriting from TObject can be     //
// inserted in a TList.                                                 //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

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

#include <iterator>

#if (__GNUC__ >= 3) && !defined(__INTEL_COMPILER)
// Prevent -Weffc++ from complaining about the inheritance
// TListIter from std::iterator.
#pragma GCC system_header
#endif

const Bool_t kSortAscending  = kTRUE;
const Bool_t kSortDescending = !kSortAscending;

class TObjLink;
class TListIter;


class TList : public TSeqCollection {

friend  class TListIter;

protected:
   TObjLink  *fFirst;     //! pointer to first entry in linked list
   TObjLink  *fLast;      //! pointer to last entry in linked list
   TObjLink  *fCache;     //! cache to speedup sequential calling of Before() and After() functions
   Bool_t     fAscending; //! sorting order (when calling Sort() or for TSortedList)

   TObjLink          *LinkAt(Int_t idx) const;
   TObjLink          *FindLink(const TObject *obj, Int_t &idx) const;
   TObjLink         **DoSort(TObjLink **head, Int_t n);
   Bool_t             LnkCompare(TObjLink *l1, TObjLink *l2);
   virtual TObjLink  *NewLink(TObject *obj, TObjLink *prev = NULL);
   virtual TObjLink  *NewOptLink(TObject *obj, Option_t *opt, TObjLink *prev = NULL);
   virtual void       DeleteLink(TObjLink *lnk);

private:
   TList(const TList&);             // not implemented
   TList& operator=(const TList&);  // not implemented

public:
   typedef TListIter Iterator_t;

   TList() : fFirst(0), fLast(0), fCache(0), fAscending(kTRUE) { }
   TList(TObject *) : fFirst(0), fLast(0), fCache(0), fAscending(kTRUE) { } // for backward compatibility, don't use
   virtual           ~TList();
   virtual void      Clear(Option_t *option="");
   virtual void      Delete(Option_t *option="");
   virtual TObject  *FindObject(const char *name) const;
   virtual TObject  *FindObject(const TObject *obj) const;
   virtual TIterator *MakeIterator(Bool_t dir = kIterForward) const;

   virtual void      Add(TObject *obj) { AddLast(obj); }
   virtual void      Add(TObject *obj, Option_t *opt) { AddLast(obj, opt); }
   virtual void      AddFirst(TObject *obj);
   virtual void      AddFirst(TObject *obj, Option_t *opt);
   virtual void      AddLast(TObject *obj);
   virtual void      AddLast(TObject *obj, Option_t *opt);
   virtual void      AddAt(TObject *obj, Int_t idx);
   virtual void      AddAfter(const TObject *after, TObject *obj);
   virtual void      AddAfter(TObjLink *after, TObject *obj);
   virtual void      AddBefore(const TObject *before, TObject *obj);
   virtual void      AddBefore(TObjLink *before, TObject *obj);
   virtual TObject  *Remove(TObject *obj);
   virtual TObject  *Remove(TObjLink *lnk);
   virtual void      RemoveLast();
   virtual void      RecursiveRemove(TObject *obj);

   virtual TObject  *At(Int_t idx) const;
   virtual TObject  *After(const TObject *obj) const;
   virtual TObject  *Before(const TObject *obj) const;
   virtual TObject  *First() const;
   virtual TObjLink *FirstLink() const { return fFirst; }
   virtual TObject **GetObjectRef(const TObject *obj) const;
   virtual TObject  *Last() const;
   virtual TObjLink *LastLink() const { return fLast; }

   virtual void      Sort(Bool_t order = kSortAscending);
   Bool_t            IsAscending() { return fAscending; }

   ClassDef(TList,5)  //Doubly linked list
};


//////////////////////////////////////////////////////////////////////////
//                                                                      //
// TObjLink                                                             //
//                                                                      //
// Wrapper around a TObject so it can be stored in a TList.             //
//                                                                      //
//////////////////////////////////////////////////////////////////////////
class TObjLink {

friend  class TList;

private:
   TObjLink   *fNext;
   TObjLink   *fPrev;
   TObject    *fObject;

   TObjLink(const TObjLink&);            // not implemented
   TObjLink& operator=(const TObjLink&); // not implemented

protected:
   TObjLink() : fNext(NULL), fPrev(NULL), fObject(NULL) { fNext = fPrev = this; }

public:
   TObjLink(TObject *obj) : fNext(NULL), fPrev(NULL), fObject(obj) { }
   TObjLink(TObject *obj, TObjLink *lnk);
   virtual ~TObjLink() { }

   TObject                *GetObject() const { return fObject; }
   TObject               **GetObjectRef() { return &fObject; }
   void                    SetObject(TObject *obj) { fObject = obj; }
   virtual Option_t       *GetAddOption() const { return ""; }
   virtual Option_t       *GetOption() const { return fObject->GetOption(); }
   virtual void            SetOption(Option_t *) { }
   TObjLink               *Next() { return fNext; }
   TObjLink               *Prev() { return fPrev; }
};


//////////////////////////////////////////////////////////////////////////
//                                                                      //
// TObjOptLink                                                          //
//                                                                      //
// Wrapper around a TObject so it can be stored in a TList including    //
// an option string.                                                    //
//                                                                      //
//////////////////////////////////////////////////////////////////////////
class TObjOptLink : public TObjLink {

private:
   TString   fOption;

public:
   TObjOptLink(TObject *obj, Option_t *opt) : TObjLink(obj), fOption(opt) { }
   TObjOptLink(TObject *obj, TObjLink *lnk, Option_t *opt) : TObjLink(obj, lnk), fOption(opt) { }
   ~TObjOptLink() { }
   Option_t        *GetAddOption() const { return fOption.Data(); }
   Option_t        *GetOption() const { return fOption.Data(); }
   void             SetOption(Option_t *option) { fOption = option; }
};


// Preventing warnings with -Weffc++ in GCC since it is a false positive for the TListIter destructor.
#if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) >= 40600
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Weffc++"
#endif

//////////////////////////////////////////////////////////////////////////
//                                                                      //
// TListIter                                                            //
//                                                                      //
// Iterator of linked list.                                             //
//                                                                      //
//////////////////////////////////////////////////////////////////////////
class TListIter : public TIterator,
                  public std::iterator<std::bidirectional_iterator_tag,
                                       TObject*, std::ptrdiff_t,
                                       const TObject**, const TObject*&> {

protected:
   const TList       *fList;         //list being iterated
   TObjLink          *fCurCursor;    //current position in list
   TObjLink          *fCursor;       //next position in list
   Bool_t             fDirection;    //iteration direction
   Bool_t             fStarted;      //iteration started

   TListIter() : fList(0), fCurCursor(0), fCursor(0), fDirection(kIterForward),
                 fStarted(kFALSE) { }

public:
   TListIter(const TList *l, Bool_t dir = kIterForward);
   TListIter(const TListIter &iter);
   ~TListIter() { }
   TIterator &operator=(const TIterator &rhs);
   TListIter &operator=(const TListIter &rhs);

   const TCollection *GetCollection() const { return fList; }
   Option_t          *GetOption() const;
   void               SetOption(Option_t *option);
   TObject           *Next();
   void               Reset();
   Bool_t             operator!=(const TIterator &aIter) const;
   Bool_t             operator!=(const TListIter &aIter) const;
   TObject           *operator*() const { return (fCurCursor ? fCurCursor->GetObject() : nullptr); }

   ClassDef(TListIter,0)  //Linked list iterator
};

#if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) >= 40600
#pragma GCC diagnostic pop
#endif

#endif
 TList.h:1
 TList.h:2
 TList.h:3
 TList.h:4
 TList.h:5
 TList.h:6
 TList.h:7
 TList.h:8
 TList.h:9
 TList.h:10
 TList.h:11
 TList.h:12
 TList.h:13
 TList.h:14
 TList.h:15
 TList.h:16
 TList.h:17
 TList.h:18
 TList.h:19
 TList.h:20
 TList.h:21
 TList.h:22
 TList.h:23
 TList.h:24
 TList.h:25
 TList.h:26
 TList.h:27
 TList.h:28
 TList.h:29
 TList.h:30
 TList.h:31
 TList.h:32
 TList.h:33
 TList.h:34
 TList.h:35
 TList.h:36
 TList.h:37
 TList.h:38
 TList.h:39
 TList.h:40
 TList.h:41
 TList.h:42
 TList.h:43
 TList.h:44
 TList.h:45
 TList.h:46
 TList.h:47
 TList.h:48
 TList.h:49
 TList.h:50
 TList.h:51
 TList.h:52
 TList.h:53
 TList.h:54
 TList.h:55
 TList.h:56
 TList.h:57
 TList.h:58
 TList.h:59
 TList.h:60
 TList.h:61
 TList.h:62
 TList.h:63
 TList.h:64
 TList.h:65
 TList.h:66
 TList.h:67
 TList.h:68
 TList.h:69
 TList.h:70
 TList.h:71
 TList.h:72
 TList.h:73
 TList.h:74
 TList.h:75
 TList.h:76
 TList.h:77
 TList.h:78
 TList.h:79
 TList.h:80
 TList.h:81
 TList.h:82
 TList.h:83
 TList.h:84
 TList.h:85
 TList.h:86
 TList.h:87
 TList.h:88
 TList.h:89
 TList.h:90
 TList.h:91
 TList.h:92
 TList.h:93
 TList.h:94
 TList.h:95
 TList.h:96
 TList.h:97
 TList.h:98
 TList.h:99
 TList.h:100
 TList.h:101
 TList.h:102
 TList.h:103
 TList.h:104
 TList.h:105
 TList.h:106
 TList.h:107
 TList.h:108
 TList.h:109
 TList.h:110
 TList.h:111
 TList.h:112
 TList.h:113
 TList.h:114
 TList.h:115
 TList.h:116
 TList.h:117
 TList.h:118
 TList.h:119
 TList.h:120
 TList.h:121
 TList.h:122
 TList.h:123
 TList.h:124
 TList.h:125
 TList.h:126
 TList.h:127
 TList.h:128
 TList.h:129
 TList.h:130
 TList.h:131
 TList.h:132
 TList.h:133
 TList.h:134
 TList.h:135
 TList.h:136
 TList.h:137
 TList.h:138
 TList.h:139
 TList.h:140
 TList.h:141
 TList.h:142
 TList.h:143
 TList.h:144
 TList.h:145
 TList.h:146
 TList.h:147
 TList.h:148
 TList.h:149
 TList.h:150
 TList.h:151
 TList.h:152
 TList.h:153
 TList.h:154
 TList.h:155
 TList.h:156
 TList.h:157
 TList.h:158
 TList.h:159
 TList.h:160
 TList.h:161
 TList.h:162
 TList.h:163
 TList.h:164
 TList.h:165
 TList.h:166
 TList.h:167
 TList.h:168
 TList.h:169
 TList.h:170
 TList.h:171
 TList.h:172
 TList.h:173
 TList.h:174
 TList.h:175
 TList.h:176
 TList.h:177
 TList.h:178
 TList.h:179
 TList.h:180
 TList.h:181
 TList.h:182
 TList.h:183
 TList.h:184
 TList.h:185
 TList.h:186
 TList.h:187
 TList.h:188
 TList.h:189
 TList.h:190
 TList.h:191
 TList.h:192
 TList.h:193
 TList.h:194
 TList.h:195
 TList.h:196
 TList.h:197
 TList.h:198
 TList.h:199
 TList.h:200
 TList.h:201
 TList.h:202
 TList.h:203
 TList.h:204
 TList.h:205
 TList.h:206
 TList.h:207
 TList.h:208
 TList.h:209
 TList.h:210
 TList.h:211
 TList.h:212
 TList.h:213
 TList.h:214
 TList.h:215
 TList.h:216
 TList.h:217
 TList.h:218
 TList.h:219
 TList.h:220
 TList.h:221
 TList.h:222
 TList.h:223
 TList.h:224
 TList.h:225