Logo ROOT  
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
40class TObjLink;
41class TListIter;
42
43
44class TList : public TSeqCollection {
45
46friend class TListIter;
47
48protected:
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
71private:
72 TList(const TList&); // not implemented
73 TList& operator=(const TList&); // not implemented
74
75public:
77
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//////////////////////////////////////////////////////////////////////////
127class TObjLink : public std::enable_shared_from_this<TObjLink> {
128
129friend class TList;
130
131private:
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
144public:
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(); }
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//////////////////////////////////////////////////////////////////////////
170class TObjOptLink : public TObjLink {
171
172private:
174
175public:
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//////////////////////////////////////////////////////////////////////////
197class TListIter : public TIterator,
198 public std::iterator<std::bidirectional_iterator_tag,
199 TObject*, std::ptrdiff_t,
200 const TObject**, const TObject*&> {
201
202protected:
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
212 fStarted(kFALSE) { }
213
214public:
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
233inline bool operator==(TObjOptLink *l, const std::shared_ptr<TObjLink> &r) {
234 return l == r.get();
235}
236
237inline 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
ROOT::R::TRInterface & r
Definition: Object.C:4
int Int_t
Definition: RtypesCore.h:41
const Bool_t kFALSE
Definition: RtypesCore.h:88
bool Bool_t
Definition: RtypesCore.h:59
const Bool_t kTRUE
Definition: RtypesCore.h:87
const char Option_t
Definition: RtypesCore.h:62
#define ClassDef(name, id)
Definition: Rtypes.h:326
const Bool_t kIterForward
Definition: TCollection.h:40
char name[80]
Definition: TGX11.cxx:109
bool operator==(TObjOptLink *l, const std::shared_ptr< TObjLink > &r)
Definition: TList.h:233
const Bool_t kSortAscending
Definition: TList.h:37
const Bool_t kSortDescending
Definition: TList.h:38
Collection abstract base class.
Definition: TCollection.h:63
Iterator abstract base class.
Definition: TIterator.h:30
Iterator of linked list.
Definition: TList.h:200
TObject * Next()
Return next object in the list. Returns 0 when no more objects in list.
Definition: TList.cxx:1110
const TList * fList
Definition: TList.h:205
TObjLinkPtr_t fCursor
Definition: TList.h:207
TObjLinkPtr_t fCurCursor
Definition: TList.h:206
std::shared_ptr< TObjLink > TObjLinkPtr_t
Definition: TList.h:203
void Reset()
Reset list iterator.
Definition: TList.cxx:1158
TListIter()
Definition: TList.h:211
void SetOption(Option_t *option)
Sets the object option stored in the list.
Definition: TList.cxx:1150
Bool_t fStarted
Definition: TList.h:209
~TListIter()
Definition: TList.h:217
const TCollection * GetCollection() const
Definition: TList.h:221
Bool_t operator!=(const TIterator &aIter) const
This operator compares two TIterator objects.
Definition: TList.cxx:1167
TObject * operator*() const
Return current object or nullptr.
Definition: TList.h:228
TIterator & operator=(const TIterator &rhs)
Overridden assignment operator.
Definition: TList.cxx:1074
Option_t * GetOption() const
Returns the object option stored in the list.
Definition: TList.cxx:1141
Bool_t fDirection
Definition: TList.h:208
A doubly linked list.
Definition: TList.h:44
Bool_t LnkCompare(const TObjLinkPtr_t &l1, const TObjLinkPtr_t &l2)
Compares the objects stored in the TObjLink objects.
Definition: TList.cxx:969
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:745
virtual void Add(TObject *obj)
Definition: TList.h:87
virtual TObject * After(const TObject *obj) const
Returns the object after object obj.
Definition: TList.cxx:327
virtual TObjLink * LastLink() const
Definition: TList.h:111
virtual ~TList()
Delete the list.
Definition: TList.cxx:89
std::weak_ptr< TObjLink > TObjLinkWeakPtr_t
Definition: TList.h:50
Bool_t fAscending
cache to speedup sequential calling of Before() and After() functions
Definition: TList.h:55
virtual TObject * Remove(TObject *obj)
Remove object from the list.
Definition: TList.cxx:819
virtual TObject ** GetObjectRef(const TObject *obj) const
Return address of pointer to obj.
Definition: TList.cxx:668
virtual void AddAt(TObject *obj, Int_t idx)
Insert object at position idx in the list.
Definition: TList.cxx:303
TList(TObject *)
Definition: TList.h:79
TObjLink * FindLink(const TObject *obj, Int_t &idx) const
Returns the TObjLink object that contains object obj.
Definition: TList.cxx:625
Bool_t IsAscending()
Definition: TList.h:114
std::shared_ptr< TObjLink > TObjLinkPtr_t
Definition: TList.h:49
TObject * Remove(const TObjLinkPtr_t &lnk)
Definition: TList.h:100
virtual void AddFirst(TObject *obj)
Add object at the beginning of the list.
Definition: TList.cxx:97
TObjLinkPtr_t fLast
pointer to first entry in linked list
Definition: TList.h:53
void InsertAfter(const TObjLinkPtr_t &newlink, const TObjLinkPtr_t &prev)
Insert a new link in the chain.
Definition: TList.cxx:1032
virtual void RemoveLast()
Remove the last object of the list.
Definition: TList.cxx:906
virtual TObject * FindObject(const char *name) const
Find an object in this list using its name.
Definition: TList.cxx:575
TObjLink * LinkAt(Int_t idx) const
sorting order (when calling Sort() or for TSortedList)
Definition: TList.cxx:702
virtual TObjLink * FirstLink() const
Definition: TList.h:108
TListIter Iterator_t
Definition: TList.h:76
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
TObjLinkPtr_t NewLink(TObject *obj, const TObjLinkPtr_t &prev=nullptr)
Return a new TObjLink.
Definition: TList.cxx:730
virtual TObject * Last() const
Return the last object in the list. Returns 0 when list is empty.
Definition: TList.cxx:690
virtual void AddAfter(const TObject *after, TObject *obj)
Insert object after object after in the list.
Definition: TList.cxx:247
TObjLinkPtr_t fFirst
Definition: TList.h:52
virtual void RecursiveRemove(TObject *obj)
Remove object from this collection and recursively remove the object from all other objects (and coll...
Definition: TList.cxx:761
virtual void Add(TObject *obj, Option_t *opt)
Definition: TList.h:88
virtual void AddBefore(const TObject *before, TObject *obj)
Insert object before object before in the list.
Definition: TList.cxx:193
TList & operator=(const TList &)
virtual TIterator * MakeIterator(Bool_t dir=kIterForward) const
Return a list iterator.
Definition: TList.cxx:719
TList(const TList &)
TObjLinkWeakPtr_t fCache
pointer to last entry in linked list
Definition: TList.h:54
virtual TObject * Before(const TObject *obj) const
Returns the object before object obj.
Definition: TList.cxx:368
virtual void Delete(Option_t *option="")
Remove all objects from the list AND delete all heap based objects.
Definition: TList.cxx:467
virtual TObject * First() const
Return the first object in the list. Returns 0 when list is empty.
Definition: TList.cxx:656
virtual void AddLast(TObject *obj)
Add object at the end of the list.
Definition: TList.cxx:149
TList()
Definition: TList.h:78
TObjLinkPtr_t * DoSort(TObjLinkPtr_t *head, Int_t n)
Sort linked list.
Definition: TList.cxx:981
virtual void Clear(Option_t *option="")
Remove all objects from the list.
Definition: TList.cxx:399
virtual void Sort(Bool_t order=kSortAscending)
Sort linked list.
Definition: TList.cxx:934
Mother of all ROOT objects.
Definition: TObject.h:37
virtual Option_t * GetOption() const
Definition: TObject.h:120
Sequenceable collection abstract base class.
Basic string class.
Definition: TString.h:131
const char * Data() const
Definition: TString.h:364
const Int_t n
Definition: legend1.C:16
auto * l
Definition: textangle.C:4