Logo ROOT  
Reference Guide
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
28
29////////////////////////////////////////////////////////////////////////////////
30/// Create an ordered collection.
31
33{
34 if (capacity < 0) {
35 Warning("TOrdCollection", "capacity (%d) < 0", capacity);
36 capacity = kDefaultCapacity;
37 } else if (capacity == 0)
38 capacity = kDefaultCapacity;
39 Init(capacity);
40}
41
42////////////////////////////////////////////////////////////////////////////////
43/// Delete the collection. Objects are not deleted unless the TOrdCollection
44/// is the owner (set via SetOwner()).
45
47{
48 if (IsOwner())
49 Delete();
50
52 fCont = 0;
53 fSize = 0;
54}
55
56////////////////////////////////////////////////////////////////////////////////
57/// Insert object at position idx in the collection.
58
60{
61 Int_t physIdx;
62
63 if (idx > fSize) idx = fSize;
64
65 if (fGapSize <= 0)
67
68 if (idx == fGapStart) {
69 physIdx = fGapStart;
70 fGapStart++;
71 } else {
72 physIdx = PhysIndex(idx);
73 if (physIdx < fGapStart) {
74 MoveGapTo(physIdx);
75 physIdx = fGapStart;
76 fGapStart++;
77 } else {
78 MoveGapTo(physIdx - fGapSize);
79 physIdx = fGapStart + fGapSize - 1;
80 }
81 }
82 R__ASSERT(physIdx >= 0 && physIdx < fCapacity);
83 fCont[physIdx] = obj;
84 fGapSize--;
85 fSize++;
86 Changed();
87}
88
89////////////////////////////////////////////////////////////////////////////////
90/// Insert object at beginning of collection.
91
93{
94 AddAt(obj, 0);
95}
96
97////////////////////////////////////////////////////////////////////////////////
98/// Add object at the end of the collection.
99
101{
102 AddAt(obj, fSize);
103}
104
105////////////////////////////////////////////////////////////////////////////////
106/// Insert object before object before in the collection.
107
109{
110 if (!before)
111 AddFirst(obj);
112 else {
113 Int_t idx = IndexOf(before);
114 if (idx == -1) {
115 Error("AddBefore", "before not found, object not added");
116 return;
117 }
118 if (idx == 0) {
119 AddFirst(obj);
120 return;
121 }
122 AddAt(obj, idx);
123 }
124}
125
126////////////////////////////////////////////////////////////////////////////////
127/// Insert object after object after in the collection.
128
130{
131 if (!after)
132 AddLast(obj);
133 else {
134 Int_t idx = IndexOf(after);
135 if (idx == -1) {
136 Error("AddAfter", "after not found, object not added");
137 return;
138 }
139 AddAt(obj, idx+1);
140 }
141}
142
143////////////////////////////////////////////////////////////////////////////////
144/// Return the object after object obj. Returns 0 if obj is last
145/// in collection.
146
148{
149 if (!obj) return 0;
150
151 Int_t idx = IndexOf(obj);
152 if (idx == -1 || idx == fSize-1) return 0;
153
154 return At(idx+1);
155}
156
157////////////////////////////////////////////////////////////////////////////////
158/// Returns the object at position idx. Returns 0 if idx is out of range.
159
161{
162 if (IllegalIndex("At", idx)) return 0;
163 return fCont[PhysIndex(idx)];
164}
165
166////////////////////////////////////////////////////////////////////////////////
167/// Returns the object before object obj. Returns 0 if obj is first
168/// in collection.
169
171{
172 if (!obj) return 0;
173
174 Int_t idx = IndexOf(obj);
175 if (idx == -1 || idx == 0) return 0;
176
177 return At(idx-1);
178}
179
180////////////////////////////////////////////////////////////////////////////////
181/// Remove all objects from the collection. Does not delete the objects
182/// unless the TOrdCollection is the owner (set via SetOwner()).
183
185{
186 if (IsOwner())
187 Delete();
188 else {
190 fCont = 0;
192 fSize = 0;
193 }
194}
195
196////////////////////////////////////////////////////////////////////////////////
197/// Remove all objects from the collection AND delete all heap based objects.
198
200{
201 for (Int_t i = 0; i < fSize; i++) {
202 TObject *obj = At(i);
203 if (obj && obj->IsOnHeap())
205 }
207 fCont = 0;
209 fSize = 0;
210}
211
212////////////////////////////////////////////////////////////////////////////////
213/// Return the first object in the collection. Returns 0 when collection
214/// is empty.
215
217{
218 return At(0);
219}
220
221////////////////////////////////////////////////////////////////////////////////
222/// return address of pointer obj
223
225{
226 Int_t index = IndexOf(obj);
227 return &fCont[index];
228}
229
230////////////////////////////////////////////////////////////////////////////////
231/// Return the last object in the collection. Returns 0 when collection
232/// is empty.
233
235{
236 return At(fSize-1);
237}
238
239////////////////////////////////////////////////////////////////////////////////
240/// Return true when index out of bounds and print error.
241
242Bool_t TOrdCollection::IllegalIndex(const char *method, Int_t idx) const
243{
244 if (idx < 0 || idx >= fSize) {
245 Error(method, "index error (= %d) < 0 or > Size() (= %d)", idx, fSize);
246 return kTRUE;
247 }
248 return kFALSE;
249}
250
251////////////////////////////////////////////////////////////////////////////////
252/// Return index of object in collection. Returns -1 when object not found.
253/// Uses member IsEqual() to find object.
254
256{
257 for (Int_t i = 0; i < GetSize(); i++)
258 if (fCont[PhysIndex(i)]->IsEqual(obj))
259 return i;
260
261 return -1;
262}
263
264////////////////////////////////////////////////////////////////////////////////
265/// Initialize ordered collection.
266
268{
269 fCapacity = capacity;
270 fCont = (TObject**) TStorage::Alloc(fCapacity*sizeof(TObject*)); //new TObject* [fCapacity];
271 memset(fCont, 0, fCapacity*sizeof(TObject*));
272 fGapStart = 0;
273 fGapSize = capacity;
274 Changed();
275}
276
277////////////////////////////////////////////////////////////////////////////////
278/// Return an ordered collection iterator.
279
281{
282 return new TOrdCollectionIter(this, dir);
283}
284
285////////////////////////////////////////////////////////////////////////////////
286/// Move gap to new position. Gap needs to be moved when objects are
287/// inserted not at the end.
288
290{
291 Int_t i;
292
293 R__ASSERT(start + fGapSize - 1 < fCapacity);
294
295 if (fGapSize <= 0) {
296 fGapStart = start;
297 return;
298 }
299 if (start < fGapStart) {
300 for (i = fGapStart - 1; i >= start; i--)
301 fCont[i + fGapSize] = fCont[i];
302 } else if (start > fGapStart) {
303 Int_t stop = start + fGapSize;
304 for (i = fGapStart + fGapSize; i < stop; i++)
305 fCont[i - fGapSize] = fCont[i];
306 }
307 fGapStart = start;
308 for (i = fGapStart; i < fGapStart + fGapSize; i++)
309 fCont[i] = 0;
310}
311
312////////////////////////////////////////////////////////////////////////////////
313/// Put object at index idx. Overwrites what was at idx before.
314
316{
317 if (IllegalIndex("PutAt", idx)) return;
318
319 Int_t phx = PhysIndex(idx);
320 R__ASSERT(phx >= 0 && phx < fCapacity);
321 fCont[phx] = obj;
322 Changed();
323}
324
325////////////////////////////////////////////////////////////////////////////////
326/// Remove object at index idx.
327
329{
330 Int_t physIdx;
331
332 if (idx == fGapStart - 1 || idx == fGapStart) {
333 if (idx == fGapStart)
334 physIdx = fGapStart + fGapSize; // at right boundary
335 else
336 physIdx = --fGapStart; // at left boundary
337 } else {
338 physIdx = PhysIndex(idx);
339 if (physIdx < fGapStart) {
340 MoveGapTo(physIdx + 1);
341 physIdx = --fGapStart;
342 } else {
343 MoveGapTo(physIdx - fGapSize);
344 physIdx = fGapStart + fGapSize;
345 }
346 }
347 R__ASSERT(physIdx >= 0 && physIdx < fCapacity);
348 TObject *obj = fCont[physIdx];
349 fCont[physIdx] = 0;
350 fGapSize++;
351 fSize--;
352 Changed();
353
354 if (LowWaterMark()) {
355 Int_t newCapacity = TMath::Max(int(fCapacity / kShrinkFactor), 1);
356 if (fCapacity > newCapacity)
357 SetCapacity(newCapacity);
358 }
359 return obj;
360}
361
362////////////////////////////////////////////////////////////////////////////////
363/// Remove object from collection.
364
366{
367 if (!obj) return 0;
368
369 Int_t idx = IndexOf(obj);
370 if (idx == -1) return 0;
371
372 return RemoveAt(idx);
373}
374
375////////////////////////////////////////////////////////////////////////////////
376/// Set/change ordered collection capacity.
377
379{
380 R__ASSERT(newCapacity > 0);
381 R__ASSERT(fSize <= newCapacity);
382
383 if (fCapacity == newCapacity) return;
384
385 Int_t newGapSize = newCapacity - fSize;
387 fCont = (TObject**) TStorage::ReAlloc(fCont, newCapacity*sizeof(TObject*),
388 fCapacity*sizeof(TObject*));
389 fGapSize = newGapSize;
390 fCapacity = newCapacity;
391}
392
393////////////////////////////////////////////////////////////////////////////////
394/// If objects in collection are sortable (i.e. IsSortable() returns true
395/// for all objects) then sort collection.
396
398{
399 if (fSize <= 0 || fSorted) return;
400 if (!At(0)->IsSortable()) {
401 Error("Sort", "objects in collection are not sortable");
402 return;
403 }
404
406 QSort(fCont, 0, fSize);
407
408 fSorted = kTRUE;
409}
410
411////////////////////////////////////////////////////////////////////////////////
412/// Find object using a binary search. Collection must first have been
413/// sorted.
414
416{
417 Int_t result;
418
419 if (!obj) return -1;
420
421 if (!fSorted) {
422 Error("BinarySearch", "collection must first be sorted");
423 return -1;
424 }
425
427
428 Int_t base = 0;
429 Int_t last = base + GetSize() - 1;
430 while (last >= base) {
431 Int_t position = (base + last) / 2;
432 TObject *obj2 = fCont[position];
433 if ((obj2 == 0) || (result = obj->Compare(obj2)) == 0)
434 return LogIndex(position);
435 if (result < 0)
436 last = position - 1;
437 else
438 base = position + 1;
439 }
440 return -1;
441}
442
443/** \class TOrdCollectionIter
444Iterator of ordered collection.
445*/
446
448
449////////////////////////////////////////////////////////////////////////////////
450/// Create collection iterator. By default the iteration direction
451/// is kIterForward. To go backward use kIterBackward.
452
453TOrdCollectionIter::TOrdCollectionIter(const TOrdCollection *col, Bool_t dir): fCol(col), fDirection(dir)
454{
455 Reset();
456}
457
458////////////////////////////////////////////////////////////////////////////////
459/// Copy ctor.
460
462{
463 fCol = iter.fCol;
464 fDirection = iter.fDirection;
465 fCursor = iter.fCursor;
466 fCurCursor = iter.fCurCursor;
467}
468
469////////////////////////////////////////////////////////////////////////////////
470/// Overridden assignment operator.
471
473{
474 if (this != &rhs && rhs.IsA() == TOrdCollectionIter::Class()) {
475 const TOrdCollectionIter &rhs1 = (const TOrdCollectionIter &)rhs;
476 fCol = rhs1.fCol;
477 fDirection = rhs1.fDirection;
478 fCursor = rhs1.fCursor;
479 fCurCursor = rhs1.fCurCursor;
480 }
481 return *this;
482}
483
484////////////////////////////////////////////////////////////////////////////////
485/// Overloaded assignment operator.
486
488{
489 if (this != &rhs) {
490 fCol = rhs.fCol;
492 fCursor = rhs.fCursor;
494 }
495 return *this;
496}
497
498////////////////////////////////////////////////////////////////////////////////
499/// Return next object in collection. Returns 0 when no more objects in
500/// collection.
501
503{
505 if (fDirection == kIterForward) {
506 if (fCursor < fCol->GetSize())
507 return fCol->At(fCursor++);
508 } else {
509 if (fCursor >= 0)
510 return fCol->At(fCursor--);
511 }
512 return 0;
513}
514
515////////////////////////////////////////////////////////////////////////////////
516/// Reset collection iterator.
517
519{
521 fCursor = 0;
522 else
523 fCursor = fCol->GetSize() - 1;
524
526}
527
528////////////////////////////////////////////////////////////////////////////////
529/// This operator compares two TIterator objects.
530
532{
533 if (aIter.IsA() == TOrdCollectionIter::Class()) {
534 const TOrdCollectionIter &iter(dynamic_cast<const TOrdCollectionIter &>(aIter));
535 return (fCurCursor != iter.fCurCursor);
536 }
537 return false; // for base class we don't implement a comparison
538}
539
540////////////////////////////////////////////////////////////////////////////////
541/// This operator compares two TOrdCollectionIter objects.
542
544{
545 return (fCurCursor != aIter.fCurCursor);
546}
547
548////////////////////////////////////////////////////////////////////////////////
549/// Return current object or nullptr.
550
552{
553 return (((fCurCursor >= 0) && (fCurCursor < fCol->GetSize())) ?
554 fCol->At(fCurCursor) : nullptr);
555}
void Class()
Definition: Class.C:29
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 ClassImp(name)
Definition: Rtypes.h:365
const Bool_t kIterForward
Definition: TCollection.h:40
#define R__ASSERT(e)
Definition: TError.h:96
Bool_t IsSortable() const
Definition: TCollection.h:189
virtual Int_t GrowBy(Int_t delta) const
Increase the collection's capacity by delta slots.
Bool_t IsOwner() const
Definition: TCollection.h:188
static void GarbageCollect(TObject *obj)
Add to the list of things to be cleaned up.
virtual Int_t GetSize() const
Return the capacity of the collection, i.e.
Definition: TCollection.h:182
Iterator abstract base class.
Definition: TIterator.h:30
Mother of all ROOT objects.
Definition: TObject.h:37
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:483
R__ALWAYS_INLINE Bool_t IsOnHeap() const
Definition: TObject.h:133
virtual void Warning(const char *method, const char *msgfmt,...) const
Issue warning message.
Definition: TObject.cxx:866
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition: TObject.cxx:880
virtual Int_t Compare(const TObject *obj) const
Compare abstract method.
Definition: TObject.cxx:159
Iterator of ordered collection.
void Reset()
Reset collection iterator.
Bool_t operator!=(const TIterator &aIter) const
This operator compares two TIterator objects.
const TOrdCollection * fCol
TObject * Next()
Return next object in collection.
TIterator & operator=(const TIterator &rhs)
Overridden assignment operator.
TObject * operator*() const
Return current object or nullptr.
Ordered collection.
TObject * Remove(TObject *obj)
Remove object from collection.
Bool_t LowWaterMark() const
Int_t IndexOf(const TObject *obj) const
Return index of object in collection.
void Clear(Option_t *option="")
Remove all objects from the collection.
TObject * After(const TObject *obj) const
Return the object after object obj.
void AddBefore(const TObject *before, TObject *obj)
Insert object before object before in the collection.
void PutAt(TObject *obj, Int_t idx)
Put object at index idx. Overwrites what was at idx before.
TObject ** fCont
TOrdCollection(const TOrdCollection &)
void AddLast(TObject *obj)
Add object at the end of the collection.
~TOrdCollection()
Delete the collection.
Int_t PhysIndex(Int_t idx) const
void Sort()
If objects in collection are sortable (i.e.
TObject ** GetObjectRef(const TObject *obj) const
return address of pointer obj
void AddAt(TObject *obj, Int_t idx)
Insert object at position idx in the collection.
TObject * At(Int_t idx) const
Returns the object at position idx. Returns 0 if idx is out of range.
Int_t LogIndex(Int_t idx) const
friend class TOrdCollectionIter
void AddFirst(TObject *obj)
Insert object at beginning of collection.
void AddAfter(const TObject *after, TObject *obj)
Insert object after object after in the collection.
void Init(Int_t capacity)
Initialize ordered collection.
Bool_t IllegalIndex(const char *method, Int_t idx) const
Return true when index out of bounds and print error.
TObject * RemoveAt(Int_t idx)
Remove object at index idx.
TObject * First() const
Return the first object in the collection.
TIterator * MakeIterator(Bool_t dir=kIterForward) const
Return an ordered collection iterator.
TObject * Before(const TObject *obj) const
Returns the object before object obj.
void MoveGapTo(Int_t newGapStart)
Move gap to new position.
Int_t BinarySearch(TObject *obj)
Find object using a binary search.
void Delete(Option_t *option="")
Remove all objects from the collection AND delete all heap based objects.
TObject * Last() const
Return the last object in the collection.
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:152
static void * ReAlloc(void *vp, size_t size)
Reallocate (i.e.
Definition: TStorage.cxx:183
static void Dealloc(void *ptr)
De-allocate block of memory, that was allocated via TStorage::Alloc().
Definition: TStorage.cxx:170
Short_t Max(Short_t a, Short_t b)
Definition: TMathBase.h:212