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 #ifndef ROOT_TSeqCollection
26 #include "TSeqCollection.h"
27 #endif
28 #ifndef ROOT_TString
29 #include "TString.h"
30 #endif
31
32 #include <iterator>
33
34 #if (__GNUC__ >= 3) && !defined(__INTEL_COMPILER)
35 // Prevent -Weffc++ from complaining about the inheritance
36 // TListIter from std::iterator.
37 #pragma GCC system_header
38 #endif
39
40 const Bool_t kSortAscending = kTRUE;
41 const Bool_t kSortDescending = !kSortAscending;
42
43 class TObjLink;
44 class TListIter;
45
46
47 class TList : public TSeqCollection {
48
49 friend class TListIter;
50
51 protected:
52 TObjLink *fFirst; //! pointer to first entry in linked list
53 TObjLink *fLast; //! pointer to last entry in linked list
54 TObjLink *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 TObjLink **DoSort(TObjLink **head, Int_t n);
60 Bool_t LnkCompare(TObjLink *l1, TObjLink *l2);
61 virtual TObjLink *NewLink(TObject *obj, TObjLink *prev = NULL);
62 virtual TObjLink *NewOptLink(TObject *obj, Option_t *opt, TObjLink *prev = NULL);
63 virtual void DeleteLink(TObjLink *lnk);
64
65 private:
66 TList(const TList&); // not implemented
67 TList& operator=(const TList&); // not implemented
68
69 public:
70 typedef TListIter Iterator_t;
71
72 TList() : fFirst(0), fLast(0), fCache(0), fAscending(kTRUE) { }
73 TList(TObject *) : fFirst(0), fLast(0), fCache(0), fAscending(kTRUE) { } // for backward compatibility, don't use
74 virtual ~TList();
75 virtual void Clear(Option_t *option="");
76 virtual void Delete(Option_t *option="");
77 virtual TObject *FindObject(const char *name) const;
78 virtual TObject *FindObject(const TObject *obj) const;
79 virtual TIterator *MakeIterator(Bool_t dir = kIterForward) const;
80
81 virtual void Add(TObject *obj) { AddLast(obj); }
82 virtual void Add(TObject *obj, Option_t *opt) { AddLast(obj, opt); }
83 virtual void AddFirst(TObject *obj);
84 virtual void AddFirst(TObject *obj, Option_t *opt);
85 virtual void AddLast(TObject *obj);
86 virtual void AddLast(TObject *obj, Option_t *opt);
87 virtual void AddAt(TObject *obj, Int_t idx);
88 virtual void AddAfter(const TObject *after, TObject *obj);
89 virtual void AddAfter(TObjLink *after, TObject *obj);
90 virtual void AddBefore(const TObject *before, TObject *obj);
91 virtual void AddBefore(TObjLink *before, TObject *obj);
92 virtual TObject *Remove(TObject *obj);
93 virtual TObject *Remove(TObjLink *lnk);
94 virtual void RemoveLast();
95 virtual void RecursiveRemove(TObject *obj);
96
97 virtual TObject *At(Int_t idx) const;
98 virtual TObject *After(const TObject *obj) const;
99 virtual TObject *Before(const TObject *obj) const;
100 virtual TObject *First() const;
101 virtual TObjLink *FirstLink() const { return fFirst; }
102 virtual TObject **GetObjectRef(const TObject *obj) const;
103 virtual TObject *Last() const;
104 virtual TObjLink *LastLink() const { return fLast; }
105
106 virtual void Sort(Bool_t order = kSortAscending);
107 Bool_t IsAscending() { return fAscending; }
108
109 ClassDef(TList,5) //Doubly linked list
110 };
111
112
113 //////////////////////////////////////////////////////////////////////////
114 // //
115 // TObjLink //
116 // //
117 // Wrapper around a TObject so it can be stored in a TList. //
118 // //
119 //////////////////////////////////////////////////////////////////////////
120 class TObjLink {
121
122 friend class TList;
123
124 private:
125 TObjLink *fNext;
126 TObjLink *fPrev;
127 TObject *fObject;
128
129 TObjLink(const TObjLink&); // not implemented
130 TObjLink& operator=(const TObjLink&); // not implemented
131
132 protected:
133 TObjLink() : fNext(NULL), fPrev(NULL), fObject(NULL) { fNext = fPrev = this; }
134
135 public:
136 TObjLink(TObject *obj) : fNext(NULL), fPrev(NULL), fObject(obj) { }
137 TObjLink(TObject *obj, TObjLink *lnk);
138 virtual ~TObjLink() { }
139
140 TObject *GetObject() const { return fObject; }
141 TObject **GetObjectRef() { return &fObject; }
142 void SetObject(TObject *obj) { fObject = obj; }
143 virtual Option_t *GetAddOption() const { return ""; }
144 virtual Option_t *GetOption() const { return fObject->GetOption(); }
145 virtual void SetOption(Option_t *) { }
146 TObjLink *Next() { return fNext; }
147 TObjLink *Prev() { return fPrev; }
148 };
149
150
151 //////////////////////////////////////////////////////////////////////////
152 // //
153 // TObjOptLink //
154 // //
155 // Wrapper around a TObject so it can be stored in a TList including //
156 // an option string. //
157 // //
158 //////////////////////////////////////////////////////////////////////////
159 class TObjOptLink : public TObjLink {
160
161 private:
162 TString fOption;
163
164 public:
165 TObjOptLink(TObject *obj, Option_t *opt) : TObjLink(obj), fOption(opt) { }
166 TObjOptLink(TObject *obj, TObjLink *lnk, Option_t *opt) : TObjLink(obj, lnk), fOption(opt) { }
167 ~TObjOptLink() { }
168 Option_t *GetAddOption() const { return fOption.Data(); }
169 Option_t *GetOption() const { return fOption.Data(); }
170 void SetOption(Option_t *option) { fOption = option; }
171 };
172
173
174 // Preventing warnings with -Weffc++ in GCC since it is a false positive for the TListIter destructor.
175 #if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) >= 40600
176 #pragma GCC diagnostic push
177 #pragma GCC diagnostic ignored "-Weffc++"
178 #endif
179
180 //////////////////////////////////////////////////////////////////////////
181 // //
182 // TListIter //
183 // //
184 // Iterator of linked list. //
185 // //
186 //////////////////////////////////////////////////////////////////////////
187 class TListIter : public TIterator,
188 public std::iterator<std::bidirectional_iterator_tag,
189 TObject*, std::ptrdiff_t,
190 const TObject**, const TObject*&> {
191
192 protected:
193 const TList *fList; //list being iterated
194 TObjLink *fCurCursor; //current position in list
195 TObjLink *fCursor; //next position in list
196 Bool_t fDirection; //iteration direction
197 Bool_t fStarted; //iteration started
198
199 TListIter() : fList(0), fCurCursor(0), fCursor(0), fDirection(kIterForward),
200 fStarted(kFALSE) { }
201
202 public:
203 TListIter(const TList *l, Bool_t dir = kIterForward);
204 TListIter(const TListIter &iter);
205 ~TListIter() { }
206 TIterator &operator=(const TIterator &rhs);
207 TListIter &operator=(const TListIter &rhs);
208
209 const TCollection *GetCollection() const { return fList; }
210 Option_t *GetOption() const;
211 void SetOption(Option_t *option);
212 TObject *Next();
213 void Reset();
214 Bool_t operator!=(const TIterator &aIter) const;
215 Bool_t operator!=(const TListIter &aIter) const;
216 TObject *operator*() const { return (fCurCursor ? fCurCursor->GetObject() : nullptr); }
217
218 ClassDef(TListIter,0) //Linked list iterator
219 };
220
221 #if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) >= 40600
222 #pragma GCC diagnostic pop
223 #endif
224
225 #endif
226