Logo ROOT   6.12/07
Reference Guide
TList.h
Go to the documentation of this file.
1 // @(#)root/cont:$Id$
2 // Author: Fons Rademakers 10/08/95
3 
4 /*************************************************************************
5  * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers. *
6  * All rights reserved. *
7  * *
8  * For the licensing terms see $ROOTSYS/LICENSE. *
9  * For the list of contributors see $ROOTSYS/README/CREDITS. *
10  *************************************************************************/
11 
12 #ifndef ROOT_TList
13 #define ROOT_TList
14 
15 
16 //////////////////////////////////////////////////////////////////////////
17 // //
18 // TList //
19 // //
20 // A doubly linked list. All classes inheriting from TObject can be //
21 // inserted in a TList. //
22 // //
23 //////////////////////////////////////////////////////////////////////////
24 
25 #include "TSeqCollection.h"
26 #include "TString.h"
27 
28 #include <iterator>
29 #include <memory>
30 
31 #if (__GNUC__ >= 3) && !defined(__INTEL_COMPILER)
32 // Prevent -Weffc++ from complaining about the inheritance
33 // TListIter from std::iterator.
34 #pragma GCC system_header
35 #endif
36 
39 
40 class TObjLink;
41 class TListIter;
42 
43 
44 class TList : public TSeqCollection {
45 
46 friend class TListIter;
47 
48 protected:
49  using TObjLinkPtr_t = std::shared_ptr<TObjLink>;
50  using TObjLinkWeakPtr_t = std::weak_ptr<TObjLink>;
51 
52  TObjLinkPtr_t fFirst; //! pointer to first entry in linked list
53  TObjLinkPtr_t fLast; //! pointer to last entry in linked list
54  TObjLinkWeakPtr_t fCache; //! cache to speedup sequential calling of Before() and After() functions
55  Bool_t fAscending; //! sorting order (when calling Sort() or for TSortedList)
56 
57  TObjLink *LinkAt(Int_t idx) const;
58  TObjLink *FindLink(const TObject *obj, Int_t &idx) const;
59 
61 
62  Bool_t LnkCompare(const TObjLinkPtr_t &l1, const TObjLinkPtr_t &l2);
63  TObjLinkPtr_t NewLink(TObject *obj, const TObjLinkPtr_t &prev = nullptr);
64  TObjLinkPtr_t NewOptLink(TObject *obj, Option_t *opt, const TObjLinkPtr_t &prev = nullptr);
67  // virtual void DeleteLink(TObjLink *lnk);
68 
69  void InsertAfter(const TObjLinkPtr_t &newlink, const TObjLinkPtr_t &prev);
70 
71 private:
72  TList(const TList&); // not implemented
73  TList& operator=(const TList&); // not implemented
74 
75 public:
77 
78  TList() : fAscending(kTRUE) { }
79  TList(TObject *) : fAscending(kTRUE) { } // for backward compatibility, don't use
80  virtual ~TList();
81  virtual void Clear(Option_t *option="");
82  virtual void Delete(Option_t *option="");
83  virtual TObject *FindObject(const char *name) const;
84  virtual TObject *FindObject(const TObject *obj) const;
85  virtual TIterator *MakeIterator(Bool_t dir = kIterForward) const;
86 
87  virtual void Add(TObject *obj) { AddLast(obj); }
88  virtual void Add(TObject *obj, Option_t *opt) { AddLast(obj, opt); }
89  virtual void AddFirst(TObject *obj);
90  virtual void AddFirst(TObject *obj, Option_t *opt);
91  virtual void AddLast(TObject *obj);
92  virtual void AddLast(TObject *obj, Option_t *opt);
93  virtual void AddAt(TObject *obj, Int_t idx);
94  virtual void AddAfter(const TObject *after, TObject *obj);
95  virtual void AddAfter(TObjLink *after, TObject *obj);
96  virtual void AddBefore(const TObject *before, TObject *obj);
97  virtual void AddBefore(TObjLink *before, TObject *obj);
98  virtual TObject *Remove(TObject *obj);
99  virtual TObject *Remove(TObjLink *lnk);
100  TObject *Remove(const TObjLinkPtr_t &lnk) { return Remove(lnk.get()); }
101  virtual void RemoveLast();
102  virtual void RecursiveRemove(TObject *obj);
103 
104  virtual TObject *At(Int_t idx) const;
105  virtual TObject *After(const TObject *obj) const;
106  virtual TObject *Before(const TObject *obj) const;
107  virtual TObject *First() const;
108  virtual TObjLink *FirstLink() const { return fFirst.get(); }
109  virtual TObject **GetObjectRef(const TObject *obj) const;
110  virtual TObject *Last() const;
111  virtual TObjLink *LastLink() const { return fLast.get(); }
112 
113  virtual void Sort(Bool_t order = kSortAscending);
115 
116  ClassDef(TList,5) //Doubly linked list
117 };
118 
119 
120 //////////////////////////////////////////////////////////////////////////
121 // //
122 // TObjLink //
123 // //
124 // Wrapper around a TObject so it can be stored in a TList. //
125 // //
126 //////////////////////////////////////////////////////////////////////////
127 class TObjLink : public std::enable_shared_from_this<TObjLink> {
128 
129 friend class TList;
130 
131 private:
132  using TObjLinkPtr_t = std::shared_ptr<TObjLink>;
133  using TObjLinkWeakPtr_t = std::weak_ptr<TObjLink>;
134 
137 
138  TObject *fObject; // should be atomic ...
139 
140  TObjLink(const TObjLink&) = delete;
141  TObjLink& operator=(const TObjLink&) = delete;
142  TObjLink() = delete;
143 
144 public:
145 
146  TObjLink(TObject *obj) : fObject(obj) { }
147  virtual ~TObjLink() { }
148 
149  TObject *GetObject() const { return fObject; }
150  TObject **GetObjectRef() { return &fObject; }
151  void SetObject(TObject *obj) { fObject = obj; }
152  virtual Option_t *GetAddOption() const { return ""; }
153  virtual Option_t *GetOption() const { return fObject->GetOption(); }
154  virtual void SetOption(Option_t *) { }
155  TObjLink *Next() { return fNext.get(); }
156  TObjLink *Prev() { return fPrev.lock().get(); }
157  TObjLinkPtr_t NextSP() { return fNext; }
158  TObjLinkPtr_t PrevSP() { return fPrev.lock(); }
159 };
160 
161 
162 //////////////////////////////////////////////////////////////////////////
163 // //
164 // TObjOptLink //
165 // //
166 // Wrapper around a TObject so it can be stored in a TList including //
167 // an option string. //
168 // //
169 //////////////////////////////////////////////////////////////////////////
170 class TObjOptLink : public TObjLink {
171 
172 private:
174 
175 public:
176  TObjOptLink(TObject *obj, Option_t *opt) : TObjLink(obj), fOption(opt) { }
178  Option_t *GetAddOption() const { return fOption.Data(); }
179  Option_t *GetOption() const { return fOption.Data(); }
180  void SetOption(Option_t *option) { fOption = option; }
181 };
182 
183 
184 // Preventing warnings with -Weffc++ in GCC since it is a false positive for the TListIter destructor.
185 #if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) >= 40600
186 #pragma GCC diagnostic push
187 #pragma GCC diagnostic ignored "-Weffc++"
188 #endif
189 
190 //////////////////////////////////////////////////////////////////////////
191 // //
192 // TListIter //
193 // //
194 // Iterator of linked list. //
195 // //
196 //////////////////////////////////////////////////////////////////////////
197 class TListIter : public TIterator,
198  public std::iterator<std::bidirectional_iterator_tag,
199  TObject*, std::ptrdiff_t,
200  const TObject**, const TObject*&> {
201 
202 protected:
203  using TObjLinkPtr_t = std::shared_ptr<TObjLink>;
204 
205  const TList *fList; //list being iterated
206  TObjLinkPtr_t fCurCursor; //current position in list
207  TObjLinkPtr_t fCursor; //next position in list
208  Bool_t fDirection; //iteration direction
209  Bool_t fStarted; //iteration started
210 
211  TListIter() : fList(0), fCurCursor(0), fCursor(0), fDirection(kIterForward),
212  fStarted(kFALSE) { }
213 
214 public:
215  TListIter(const TList *l, Bool_t dir = kIterForward);
216  TListIter(const TListIter &iter);
218  TIterator &operator=(const TIterator &rhs);
219  TListIter &operator=(const TListIter &rhs);
220 
221  const TCollection *GetCollection() const { return fList; }
222  Option_t *GetOption() const;
223  void SetOption(Option_t *option);
224  TObject *Next();
225  void Reset();
226  Bool_t operator!=(const TIterator &aIter) const;
227  Bool_t operator!=(const TListIter &aIter) const;
228  TObject *operator*() const { return (fCurCursor ? fCurCursor->GetObject() : nullptr); }
229 
230  ClassDef(TListIter,0) //Linked list iterator
231 };
232 
233 inline bool operator==(TObjOptLink *l, const std::shared_ptr<TObjLink> &r) {
234  return l == r.get();
235 }
236 
237 inline bool operator==(const std::shared_ptr<TObjLink> &l, TObjOptLink *r) {
238  return r == l;
239 }
240 
242  return NewLink(obj, prev ? prev->shared_from_this() : nullptr);
243 }
245  return NewOptLink(obj, opt, prev ? prev->shared_from_this() : nullptr);
246 }
247 
248 
249 #if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) >= 40600
250 #pragma GCC diagnostic pop
251 #endif
252 
253 #endif
virtual void AddAt(TObject *obj, Int_t idx)
Insert object at position idx in the list.
Definition: TList.cxx:303
virtual void Delete(Option_t *option="")
Remove all objects from the list AND delete all heap based objects.
Definition: TList.cxx:467
Bool_t fStarted
Definition: TList.h:209
TListIter Iterator_t
Definition: TList.h:76
const char Option_t
Definition: RtypesCore.h:62
void InsertAfter(const TObjLinkPtr_t &newlink, const TObjLinkPtr_t &prev)
Insert a new link in the chain.
Definition: TList.cxx:1031
virtual void RemoveLast()
Remove the last object of the list.
Definition: TList.cxx:905
TObjLink * LinkAt(Int_t idx) const
sorting order (when calling Sort() or for TSortedList)
Definition: TList.cxx:701
friend class TListIter
Definition: TList.h:46
TObjLinkPtr_t fFirst
Definition: TList.h:52
virtual TObject * Last() const
Return the last object in the list. Returns 0 when list is empty.
Definition: TList.cxx:689
virtual void AddFirst(TObject *obj)
Add object at the beginning of the list.
Definition: TList.cxx:97
const TList * fList
Definition: TList.h:205
Basic string class.
Definition: TString.h:125
int Int_t
Definition: RtypesCore.h:41
bool Bool_t
Definition: RtypesCore.h:59
TObject * Remove(const TObjLinkPtr_t &lnk)
Definition: TList.h:100
Iterator abstract base class.
Definition: TIterator.h:30
Iterator of linked list.
Definition: TList.h:197
virtual void AddLast(TObject *obj)
Add object at the end of the list.
Definition: TList.cxx:149
TObjLinkWeakPtr_t fCache
pointer to last entry in linked list
Definition: TList.h:54
virtual TObject * FindObject(const char *name) const
Delete a TObjLink object.
Definition: TList.cxx:574
TList & operator=(const TList &)
TObjLinkPtr_t fCurCursor
Definition: TList.h:206
virtual void Sort(Bool_t order=kSortAscending)
Sort linked list.
Definition: TList.cxx:933
Bool_t LnkCompare(const TObjLinkPtr_t &l1, const TObjLinkPtr_t &l2)
Compares the objects stored in the TObjLink objects.
Definition: TList.cxx:968
Sequenceable collection abstract base class.
#define ClassDef(name, id)
Definition: Rtypes.h:320
virtual void Add(TObject *obj, Option_t *opt)
Definition: TList.h:88
Bool_t fDirection
Definition: TList.h:208
const Bool_t kIterForward
Definition: TCollection.h:40
std::shared_ptr< TObjLink > TObjLinkPtr_t
Definition: TList.h:49
Bool_t operator!=(const TDatime &d1, const TDatime &d2)
Definition: TDatime.h:104
const Bool_t kSortDescending
Definition: TList.h:38
TObjLinkPtr_t NewOptLink(TObject *obj, Option_t *opt, const TObjLinkPtr_t &prev=nullptr)
Return a new TObjOptLink (a TObjLink that also stores the option).
Definition: TList.cxx:744
virtual TIterator * MakeIterator(Bool_t dir=kIterForward) const
Return a list iterator.
Definition: TList.cxx:718
TList(TObject *)
Definition: TList.h:79
A doubly linked list.
Definition: TList.h:44
virtual ~TList()
Delete the list.
Definition: TList.cxx:89
std::shared_ptr< TObjLink > TObjLinkPtr_t
Definition: TList.h:203
std::weak_ptr< TObjLink > TObjLinkWeakPtr_t
Definition: TList.h:50
const TCollection * GetCollection() const
Definition: TList.h:221
virtual TObject * First() const
Return the first object in the list. Returns 0 when list is empty.
Definition: TList.cxx:655
ROOT::R::TRInterface & r
Definition: Object.C:4
TListIter()
Definition: TList.h:211
virtual TObject * Remove(TObject *obj)
Remove object from the list.
Definition: TList.cxx:818
Collection abstract base class.
Definition: TCollection.h:63
virtual TObject * Before(const TObject *obj) const
Returns the object before object obj.
Definition: TList.cxx:368
TObjLinkPtr_t fCursor
Definition: TList.h:207
virtual TObject * After(const TObject *obj) const
Returns the object after object obj.
Definition: TList.cxx:327
bool operator==(TObjOptLink *l, const std::shared_ptr< TObjLink > &r)
Definition: TList.h:233
virtual TObject * At(Int_t idx) const
Returns the object at position idx. Returns 0 if idx is out of range.
Definition: TList.cxx:354
void Reset(Detail::TBranchProxy *x)
virtual void AddBefore(const TObject *before, TObject *obj)
Insert object before object before in the list.
Definition: TList.cxx:193
virtual TObjLink * FirstLink() const
Definition: TList.h:108
const Bool_t kFALSE
Definition: RtypesCore.h:88
TObjLinkPtr_t * DoSort(TObjLinkPtr_t *head, Int_t n)
Sort linked list.
Definition: TList.cxx:980
Bool_t fAscending
cache to speedup sequential calling of Before() and After() functions
Definition: TList.h:55
TObject * operator*() const
Return current object or nullptr.
Definition: TList.h:228
const Bool_t kSortAscending
Definition: TList.h:37
virtual Option_t * GetOption() const
Definition: TObject.h:120
virtual void Clear(Option_t *option="")
Remove all objects from the list.
Definition: TList.cxx:399
virtual void AddAfter(const TObject *after, TObject *obj)
Insert object after object after in the list.
Definition: TList.cxx:247
Mother of all ROOT objects.
Definition: TObject.h:37
TList()
Definition: TList.h:78
virtual void Add(TObject *obj)
Definition: TList.h:87
auto * l
Definition: textangle.C:4
virtual void RecursiveRemove(TObject *obj)
Remove object from this collection and recursively remove the object from all other objects (and coll...
Definition: TList.cxx:760
Bool_t IsAscending()
Definition: TList.h:114
virtual TObjLink * LastLink() const
Definition: TList.h:111
const Bool_t kTRUE
Definition: RtypesCore.h:87
~TListIter()
Definition: TList.h:217
virtual TObject ** GetObjectRef(const TObject *obj) const
Return address of pointer to obj.
Definition: TList.cxx:667
const Int_t n
Definition: legend1.C:16
char name[80]
Definition: TGX11.cxx:109
TObjLinkPtr_t fLast
pointer to first entry in linked list
Definition: TList.h:53
TObjLink * FindLink(const TObject *obj, Int_t &idx) const
Returns the TObjLink object that contains object obj.
Definition: TList.cxx:624
TObjLinkPtr_t NewLink(TObject *obj, const TObjLinkPtr_t &prev=nullptr)
Return a new TObjLink.
Definition: TList.cxx:729
const char * Data() const
Definition: TString.h:345