Logo ROOT   6.14/05
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
14 Ordered collection. An ordered collection has TList insertion
15 semantics but is implemented using an array of TObject*'s. It uses
16 less space than a TList (since there is no need for the prev and
17 next pointers), but it is more costly to insert objects (since it
18 has to create a gap by copying object pointers). TOrdCollection
19 is better than TList when objects are only added at the end of the
20 collection 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 
108 void TOrdCollection::AddBefore(const TObject *before, TObject *obj)
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 
129 void TOrdCollection::AddAfter(const TObject *after, TObject *obj)
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;
191  Init(fCapacity);
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;
208  Init(fCapacity);
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 
242 Bool_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
444 Iterator 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 
453 TOrdCollectionIter::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;
491  fDirection = rhs.fDirection;
492  fCursor = rhs.fCursor;
493  fCurCursor = rhs.fCurCursor;
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 {
520  if (fDirection == kIterForward)
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 }
static void Dealloc(void *ptr)
De-allocate block of memory, that was allocated via TStorage::Alloc().
Definition: TStorage.cxx:170
void Init(Int_t capacity)
Initialize ordered collection.
void Delete(Option_t *option="")
Remove all objects from the collection AND delete all heap based objects.
TObject * After(const TObject *obj) const
Return the object after object obj.
const char Option_t
Definition: RtypesCore.h:62
void AddLast(TObject *obj)
Add object at the end of the collection.
TObject * operator*() const
Return current object or nullptr.
TIterator * MakeIterator(Bool_t dir=kIterForward) const
Return an ordered collection iterator.
TObject * First() const
Return the first object in the collection.
#define R__ASSERT(e)
Definition: TError.h:96
int Int_t
Definition: RtypesCore.h:41
bool Bool_t
Definition: RtypesCore.h:59
void AddBefore(const TObject *before, TObject *obj)
Insert object before object before in the collection.
Int_t PhysIndex(Int_t idx) const
Iterator abstract base class.
Definition: TIterator.h:30
void Class()
Definition: Class.C:29
TObject ** GetObjectRef(const TObject *obj) const
return address of pointer obj
virtual void Changed()
TObject * Next()
Return next object in collection.
void PutAt(TObject *obj, Int_t idx)
Put object at index idx. Overwrites what was at idx before.
const Bool_t kIterForward
Definition: TCollection.h:40
Bool_t IsOwner() const
Definition: TCollection.h:188
void Reset()
Reset collection iterator.
TOrdCollection(const TOrdCollection &)
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
~TOrdCollection()
Delete the collection.
TObject * Before(const TObject *obj) const
Returns the object before object obj.
Int_t LogIndex(Int_t idx) const
TObject * Last() const
Return the last object in the collection.
void SetCapacity(Int_t newCapacity)
Set/change ordered collection capacity.
TObject ** fCont
virtual Int_t GrowBy(Int_t delta) const
Increase the collection&#39;s capacity by delta slots.
Bool_t operator!=(const TIterator &aIter) const
This operator compares two TIterator objects.
R__ALWAYS_INLINE Bool_t IsOnHeap() const
Definition: TObject.h:133
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition: TObject.cxx:880
Int_t IndexOf(const TObject *obj) const
Return index of object in collection.
TObject * RemoveAt(Int_t idx)
Remove object at index idx.
void AddFirst(TObject *obj)
Insert object at beginning of collection.
virtual Int_t Compare(const TObject *obj) const
Compare abstract method.
Definition: TObject.cxx:159
static void QSort(TObject **a, Int_t first, Int_t last)
Sort array of TObject pointers using a quicksort algorithm.
TIterator & operator=(const TIterator &rhs)
Overridden assignment operator.
TObject * Remove(TObject *obj)
Remove object from collection.
const Bool_t kFALSE
Definition: RtypesCore.h:88
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 GarbageCollect(TObject *obj)
Add to the list of things to be cleaned up.
void MoveGapTo(Int_t newGapStart)
Move gap to new position.
void Sort()
If objects in collection are sortable (i.e.
Bool_t LowWaterMark() const
#define ClassImp(name)
Definition: Rtypes.h:359
Int_t BinarySearch(TObject *obj)
Find object using a binary search.
Mother of all ROOT objects.
Definition: TObject.h:37
static void * ReAlloc(void *vp, size_t size)
Reallocate (i.e.
Definition: TStorage.cxx:183
const TOrdCollection * fCol
Short_t Max(Short_t a, Short_t b)
Definition: TMathBase.h:200
void Clear(Option_t *option="")
Remove all objects from the collection.
Iterator of ordered collection.
void AddAfter(const TObject *after, TObject *obj)
Insert object after object after in the collection.
void AddAt(TObject *obj, Int_t idx)
Insert object at position idx in the collection.
Bool_t IsSortable() const
Definition: TCollection.h:189
virtual Int_t GetSize() const
Return the capacity of the collection, i.e.
Definition: TCollection.h:182
Ordered collection.
TObject * At(Int_t idx) const
Returns the object at position idx. Returns 0 if idx is out of range.
const Bool_t kTRUE
Definition: RtypesCore.h:87
Bool_t IllegalIndex(const char *method, Int_t idx) const
Return true when index out of bounds and print error.
virtual void Warning(const char *method, const char *msgfmt,...) const
Issue warning message.
Definition: TObject.cxx:866
friend class TOrdCollectionIter