Logo ROOT   6.30.04
Reference Guide
 All Namespaces Files Pages
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 
37 const Bool_t kSortAscending = kTRUE;
38 const Bool_t kSortDescending = !kSortAscending;
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 
60  TObjLinkPtr_t *DoSort(TObjLinkPtr_t *head, Int_t n);
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);
65  TObjLinkPtr_t NewLink(TObject *obj, TObjLink *prev);
66  TObjLinkPtr_t NewOptLink(TObject *obj, Option_t *opt, TObjLink *prev);
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:
76  typedef TListIter Iterator_t;
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);
114  Bool_t IsAscending() { return fAscending; }
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 
135  TObjLinkPtr_t fNext;
136  TObjLinkWeakPtr_t fPrev;
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:
173  TString fOption;
174 
175 public:
176  TObjOptLink(TObject *obj, Option_t *opt) : TObjLink(obj), fOption(opt) { }
177  ~TObjOptLink() { }
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);
217  ~TListIter() { }
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 
241 inline TList::TObjLinkPtr_t TList::NewLink(TObject *obj, TObjLink *prev) {
242  return NewLink(obj, prev ? prev->shared_from_this() : nullptr);
243 }
244 inline TList::TObjLinkPtr_t TList::NewOptLink(TObject *obj, Option_t *opt, TObjLink *prev) {
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