Logo ROOT  
Reference Guide
 
Loading...
Searching...
No Matches
TOrdCollection.cxx
Go to the documentation of this file.
1// @(#)root/cont:$Id$
2// Author: Fons Rademakers 13/09/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/** \class TOrdCollection
13\ingroup Containers
14Ordered collection. An ordered collection has TList insertion
15semantics but is implemented using an array of TObject*'s. It uses
16less space than a TList (since there is no need for the prev and
17next pointers), but it is more costly to insert objects (since it
18has to create a gap by copying object pointers). TOrdCollection
19is better than TList when objects are only added at the end of the
20collection since no copying needs to be done.
21*/
22
23#include "TOrdCollection.h"
24#include "TError.h"
25
26
27
28////////////////////////////////////////////////////////////////////////////////
29/// Create an ordered collection.
30
32{
33 if (capacity < 0) {
34 Warning("TOrdCollection", "capacity (%d) < 0", capacity);
35 capacity = kDefaultCapacity;
36 } else if (capacity == 0)
37 capacity = kDefaultCapacity;
38 Init(capacity);
39}
40
41////////////////////////////////////////////////////////////////////////////////
42/// Delete the collection. Objects are not deleted unless the TOrdCollection
43/// is the owner (set via SetOwner()).
44
46{
47 if (IsOwner())
48 Delete();
49
51 fCont = nullptr;
52 fSize = 0;
53}
54
55////////////////////////////////////////////////////////////////////////////////
56/// Insert object at position idx in the collection.
57
59{
61
62 if (idx > fSize) idx = fSize;
63
64 if (fGapSize <= 0)
65 SetCapacity(GrowBy(std::max(fCapacity, (int)kMinExpand)));
66
67 if (idx == fGapStart) {
69 fGapStart++;
70 } else {
71 physIdx = PhysIndex(idx);
72 if (physIdx < fGapStart) {
75 fGapStart++;
76 } else {
79 }
80 }
82 fCont[physIdx] = obj;
83 fGapSize--;
84 fSize++;
85 Changed();
86}
87
88////////////////////////////////////////////////////////////////////////////////
89/// Insert object at beginning of collection.
90
92{
93 AddAt(obj, 0);
94}
95
96////////////////////////////////////////////////////////////////////////////////
97/// Add object at the end of the collection.
98
100{
101 AddAt(obj, fSize);
102}
103
104////////////////////////////////////////////////////////////////////////////////
105/// Insert object before object before in the collection.
106
108{
109 if (!before)
110 AddFirst(obj);
111 else {
112 Int_t idx = IndexOf(before);
113 if (idx == -1) {
114 Error("AddBefore", "before not found, object not added");
115 return;
116 }
117 if (idx == 0) {
118 AddFirst(obj);
119 return;
120 }
121 AddAt(obj, idx);
122 }
123}
124
125////////////////////////////////////////////////////////////////////////////////
126/// Insert object after object after in the collection.
127
129{
130 if (!after)
131 AddLast(obj);
132 else {
133 Int_t idx = IndexOf(after);
134 if (idx == -1) {
135 Error("AddAfter", "after not found, object not added");
136 return;
137 }
138 AddAt(obj, idx+1);
139 }
140}
141
142////////////////////////////////////////////////////////////////////////////////
143/// Return the object after object obj. Returns 0 if obj is last
144/// in collection.
145
147{
148 if (!obj) return nullptr;
149
150 Int_t idx = IndexOf(obj);
151 if (idx == -1 || idx == fSize-1) return nullptr;
152
153 return At(idx+1);
154}
155
156////////////////////////////////////////////////////////////////////////////////
157/// Returns the object at position idx. Returns 0 if idx is out of range.
158
160{
161 if (IllegalIndex("At", idx)) return nullptr;
162 return fCont[PhysIndex(idx)];
163}
164
165////////////////////////////////////////////////////////////////////////////////
166/// Returns the object before object obj. Returns 0 if obj is first
167/// in collection.
168
170{
171 if (!obj) return nullptr;
172
173 Int_t idx = IndexOf(obj);
174 if (idx == -1 || idx == 0) return nullptr;
175
176 return At(idx-1);
177}
178
179////////////////////////////////////////////////////////////////////////////////
180/// Remove all objects from the collection. Does not delete the objects
181/// unless the TOrdCollection is the owner (set via SetOwner()).
182
184{
185 if (IsOwner())
186 Delete();
187 else {
189 fCont = nullptr;
191 fSize = 0;
192 }
193}
194
195////////////////////////////////////////////////////////////////////////////////
196/// Remove all objects from the collection AND delete all heap based objects.
197
199{
200 for (Int_t i = 0; i < fSize; i++) {
201 TObject *obj = At(i);
202 if (obj && obj->IsOnHeap())
204 }
206 fCont = nullptr;
208 fSize = 0;
209}
210
211////////////////////////////////////////////////////////////////////////////////
212/// Return the first object in the collection. Returns 0 when collection
213/// is empty.
214
216{
217 return At(0);
218}
219
220////////////////////////////////////////////////////////////////////////////////
221/// return address of pointer obj
222
224{
225 Int_t index = IndexOf(obj);
226 return &fCont[index];
227}
228
229////////////////////////////////////////////////////////////////////////////////
230/// Return the last object in the collection. Returns 0 when collection
231/// is empty.
232
234{
235 return At(fSize-1);
236}
237
238////////////////////////////////////////////////////////////////////////////////
239/// Return true when index out of bounds and print error.
240
242{
243 if (idx < 0 || idx >= fSize) {
244 Error(method, "index error (= %d) < 0 or > Size() (= %d)", idx, fSize);
245 return kTRUE;
246 }
247 return kFALSE;
248}
249
250////////////////////////////////////////////////////////////////////////////////
251/// Return index of object in collection. Returns -1 when object not found.
252/// Uses member IsEqual() to find object.
253
255{
256 for (Int_t i = 0; i < GetSize(); i++)
257 if (fCont[PhysIndex(i)]->IsEqual(obj))
258 return i;
259
260 return -1;
261}
262
263////////////////////////////////////////////////////////////////////////////////
264/// Initialize ordered collection.
265
267{
268 fCapacity = capacity;
269 fCont = (TObject**) TStorage::Alloc(fCapacity*sizeof(TObject*)); //new TObject* [fCapacity];
270 memset(fCont, 0, fCapacity*sizeof(TObject*));
271 fGapStart = 0;
272 fGapSize = capacity;
273 Changed();
274}
275
276////////////////////////////////////////////////////////////////////////////////
277/// Return an ordered collection iterator.
278
280{
281 return new TOrdCollectionIter(this, dir);
282}
283
284////////////////////////////////////////////////////////////////////////////////
285/// Move gap to new position. Gap needs to be moved when objects are
286/// inserted not at the end.
287
289{
290 Int_t i;
291
292 R__ASSERT(start + fGapSize - 1 < fCapacity);
293
294 if (fGapSize <= 0) {
295 fGapStart = start;
296 return;
297 }
298 if (start < fGapStart) {
299 for (i = fGapStart - 1; i >= start; i--)
300 fCont[i + fGapSize] = fCont[i];
301 } else if (start > fGapStart) {
302 Int_t stop = start + fGapSize;
303 for (i = fGapStart + fGapSize; i < stop; i++)
304 fCont[i - fGapSize] = fCont[i];
305 }
306 fGapStart = start;
307 for (i = fGapStart; i < fGapStart + fGapSize; i++)
308 fCont[i] = nullptr;
309}
310
311////////////////////////////////////////////////////////////////////////////////
312/// Put object at index idx. Overwrites what was at idx before.
313
315{
316 if (IllegalIndex("PutAt", idx)) return;
317
318 Int_t phx = PhysIndex(idx);
319 R__ASSERT(phx >= 0 && phx < fCapacity);
320 fCont[phx] = obj;
321 Changed();
322}
323
324////////////////////////////////////////////////////////////////////////////////
325/// Remove object at index idx.
326
328{
330
331 if (idx == fGapStart - 1 || idx == fGapStart) {
332 if (idx == fGapStart)
333 physIdx = fGapStart + fGapSize; // at right boundary
334 else
335 physIdx = --fGapStart; // at left boundary
336 } else {
337 physIdx = PhysIndex(idx);
338 if (physIdx < fGapStart) {
339 MoveGapTo(physIdx + 1);
340 physIdx = --fGapStart;
341 } else {
344 }
345 }
347 TObject *obj = fCont[physIdx];
348 fCont[physIdx] = nullptr;
349 fGapSize++;
350 fSize--;
351 Changed();
352
353 if (LowWaterMark()) {
354 Int_t newCapacity = std::max(int(fCapacity / kShrinkFactor), 1);
357 }
358 return obj;
359}
360
361////////////////////////////////////////////////////////////////////////////////
362/// Remove object from collection.
363
365{
366 if (!obj) return nullptr;
367
368 Int_t idx = IndexOf(obj);
369 if (idx == -1) return nullptr;
370
371 return RemoveAt(idx);
372}
373
374////////////////////////////////////////////////////////////////////////////////
375/// Set/change ordered collection capacity.
376
391
392////////////////////////////////////////////////////////////////////////////////
393/// If objects in collection are sortable (i.e. IsSortable() returns true
394/// for all objects) then sort collection.
395
397{
398 if (fSize <= 0 || fSorted) return;
399 if (!At(0)->IsSortable()) {
400 Error("Sort", "objects in collection are not sortable");
401 return;
402 }
403
405 QSort(fCont, 0, fSize);
406
407 fSorted = kTRUE;
408}
409
410////////////////////////////////////////////////////////////////////////////////
411/// Find object using a binary search. Collection must first have been
412/// sorted.
413
415{
417
418 if (!obj) return -1;
419
420 if (!fSorted) {
421 Error("BinarySearch", "collection must first be sorted");
422 return -1;
423 }
424
426
427 Int_t base = 0;
428 Int_t last = base + GetSize() - 1;
429 while (last >= base) {
430 Int_t position = (base + last) / 2;
431 TObject *obj2 = fCont[position];
432 if (!obj2 || (result = obj->Compare(obj2)) == 0)
433 return LogIndex(position);
434 if (result < 0)
435 last = position - 1;
436 else
437 base = position + 1;
438 }
439 return -1;
440}
441
442/** \class TOrdCollectionIter
443Iterator of ordered collection.
444*/
445
446
447////////////////////////////////////////////////////////////////////////////////
448/// Create collection iterator. By default the iteration direction
449/// is kIterForward. To go backward use kIterBackward.
450
451TOrdCollectionIter::TOrdCollectionIter(const TOrdCollection *col, Bool_t dir): fCol(col), fDirection(dir)
452{
453 Reset();
454}
455
456////////////////////////////////////////////////////////////////////////////////
457/// Copy ctor.
458
460{
461 fCol = iter.fCol;
462 fDirection = iter.fDirection;
463 fCursor = iter.fCursor;
464 fCurCursor = iter.fCurCursor;
465}
466
467////////////////////////////////////////////////////////////////////////////////
468/// Overridden assignment operator.
469
471{
472 if (this != &rhs && rhs.IsA() == TOrdCollectionIter::Class()) {
474 fCol = rhs1.fCol;
475 fDirection = rhs1.fDirection;
476 fCursor = rhs1.fCursor;
477 fCurCursor = rhs1.fCurCursor;
478 }
479 return *this;
480}
481
482////////////////////////////////////////////////////////////////////////////////
483/// Overloaded assignment operator.
484
486{
487 if (this != &rhs) {
488 fCol = rhs.fCol;
489 fDirection = rhs.fDirection;
490 fCursor = rhs.fCursor;
491 fCurCursor = rhs.fCurCursor;
492 }
493 return *this;
494}
495
496////////////////////////////////////////////////////////////////////////////////
497/// Return next object in collection. Returns 0 when no more objects in
498/// collection.
499
501{
503 if (fDirection == kIterForward) {
504 if (fCursor < fCol->GetSize())
505 return fCol->At(fCursor++);
506 } else {
507 if (fCursor >= 0)
508 return fCol->At(fCursor--);
509 }
510 return nullptr;
511}
512
513////////////////////////////////////////////////////////////////////////////////
514/// Reset collection iterator.
515
517{
519 fCursor = 0;
520 else
521 fCursor = fCol->GetSize() - 1;
522
524}
525
526////////////////////////////////////////////////////////////////////////////////
527/// This operator compares two TIterator objects.
528
530{
531 if (aIter.IsA() == TOrdCollectionIter::Class()) {
532 const TOrdCollectionIter &iter(dynamic_cast<const TOrdCollectionIter &>(aIter));
533 return (fCurCursor != iter.fCurCursor);
534 }
535 return false; // for base class we don't implement a comparison
536}
537
538////////////////////////////////////////////////////////////////////////////////
539/// This operator compares two TOrdCollectionIter objects.
540
542{
543 return (fCurCursor != aIter.fCurCursor);
544}
545
546////////////////////////////////////////////////////////////////////////////////
547/// Return current object or nullptr.
548
550{
551 return (((fCurCursor >= 0) && (fCurCursor < fCol->GetSize())) ?
552 fCol->At(fCurCursor) : nullptr);
553}
constexpr Bool_t kFALSE
Definition RtypesCore.h:108
constexpr Bool_t kTRUE
Definition RtypesCore.h:107
const char Option_t
Option string (const char)
Definition RtypesCore.h:80
const Bool_t kIterForward
Definition TCollection.h:42
ROOT::Detail::TRangeCast< T, true > TRangeDynCast
TRangeDynCast is an adapter class that allows the typed iteration through a TCollection.
#define R__ASSERT(e)
Checks condition e and reports a fatal error if it's false.
Definition TError.h:125
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t Float_t Float_t Int_t Int_t UInt_t UInt_t Rectangle_t result
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t index
virtual Int_t GrowBy(Int_t delta) const
Increase the collection's capacity by delta slots.
Bool_t IsOwner() const
static void GarbageCollect(TObject *obj)
Add to the list of things to be cleaned up.
Bool_t IsSortable() const override
virtual Int_t GetSize() const
Return the capacity of the collection, i.e.
Iterator abstract base class.
Definition TIterator.h:30
Mother of all ROOT objects.
Definition TObject.h:41
virtual Bool_t IsEqual(const TObject *obj) const
Default equal comparison (objects are equal if they have the same address in memory).
Definition TObject.cxx:583
R__ALWAYS_INLINE Bool_t IsOnHeap() const
Definition TObject.h:158
virtual void Warning(const char *method, const char *msgfmt,...) const
Issue warning message.
Definition TObject.cxx:1057
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition TObject.cxx:1071
virtual Int_t Compare(const TObject *obj) const
Compare abstract method.
Definition TObject.cxx:257
Iterator of ordered collection.
TIterator & operator=(const TIterator &rhs) override
Overridden assignment operator.
TObject * operator*() const override
Return current object or nullptr.
void Reset() override
Reset collection iterator.
static TClass * Class()
const TOrdCollection * fCol
TObject * Next() override
Return next object in collection.
Bool_t operator!=(const TIterator &aIter) const override
This operator compares two TIterator objects.
Ordered collection.
void AddFirst(TObject *obj) override
Insert object at beginning of collection.
TObject * After(const TObject *obj) const override
Return the object after object obj.
TObject * First() const override
Return the first object in the collection.
Bool_t LowWaterMark() const
TOrdCollection(const TOrdCollection &)=delete
void PutAt(TObject *obj, Int_t idx)
Put object at index idx. Overwrites what was at idx before.
TObject ** fCont
void AddBefore(const TObject *before, TObject *obj) override
Insert object before object before in the collection.
void AddLast(TObject *obj) override
Add object at the end of the collection.
void Clear(Option_t *option="") override
Remove all objects from the collection.
void AddAfter(const TObject *after, TObject *obj) override
Insert object after object after in the collection.
~TOrdCollection()
Delete the collection.
Int_t PhysIndex(Int_t idx) const
void Sort()
If objects in collection are sortable (i.e.
Int_t IndexOf(const TObject *obj) const override
Return index of object in collection.
TObject * Last() const override
Return the last object in the collection.
Int_t LogIndex(Int_t idx) const
TObject * Remove(TObject *obj) override
Remove object from collection.
friend class TOrdCollectionIter
TObject * Before(const TObject *obj) const override
Returns the object before object obj.
void AddAt(TObject *obj, Int_t idx) override
Insert object at position idx in the collection.
TObject * RemoveAt(Int_t idx) override
Remove object at index idx.
void Init(Int_t capacity)
Initialize ordered collection.
void Delete(Option_t *option="") override
Remove all objects from the collection AND delete all heap based objects.
Bool_t IllegalIndex(const char *method, Int_t idx) const
Return true when index out of bounds and print error.
TObject * At(Int_t idx) const override
Returns the object at position idx. Returns 0 if idx is out of range.
TObject ** GetObjectRef(const TObject *obj) const override
return address of pointer obj
void MoveGapTo(Int_t newGapStart)
Move gap to new position.
TIterator * MakeIterator(Bool_t dir=kIterForward) const override
Return an ordered collection iterator.
Int_t BinarySearch(TObject *obj)
Find object using a binary search.
void SetCapacity(Int_t newCapacity)
Set/change ordered collection capacity.
virtual void Changed()
static void QSort(TObject **a, Int_t first, Int_t last)
Sort array of TObject pointers using a quicksort algorithm.
static void * Alloc(size_t size)
Allocate a block of memory, that later can be resized using TStorage::ReAlloc().
Definition TStorage.cxx:151
static void Dealloc(void *ptr)
De-allocate block of memory, that was allocated via TStorage::Alloc().
Definition TStorage.cxx:169
static void * ReAlloc(void *vp, size_t size, size_t oldsize)
Reallocate (i.e.
Definition TStorage.cxx:182