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
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 }
TOrdCollection::Last
TObject * Last() const
Return the last object in the collection.
Definition: TOrdCollection.cxx:234
TOrdCollection::PhysIndex
Int_t PhysIndex(Int_t idx) const
Definition: TOrdCollection.h:134
TOrdCollection::IllegalIndex
Bool_t IllegalIndex(const char *method, Int_t idx) const
Return true when index out of bounds and print error.
Definition: TOrdCollection.cxx:242
kTRUE
const Bool_t kTRUE
Definition: RtypesCore.h:91
TCollection::IsSortable
Bool_t IsSortable() const
Definition: TCollection.h:189
TMath::Max
Short_t Max(Short_t a, Short_t b)
Definition: TMathBase.h:212
TObject::Compare
virtual Int_t Compare(const TObject *obj) const
Compare abstract method.
Definition: TObject.cxx:161
TSeqCollection::QSort
static void QSort(TObject **a, Int_t first, Int_t last)
Sort array of TObject pointers using a quicksort algorithm.
Definition: TSeqCollection.cxx:70
TOrdCollectionIter::operator*
TObject * operator*() const
Return current object or nullptr.
Definition: TOrdCollection.cxx:551
TOrdCollection::Delete
void Delete(Option_t *option="")
Remove all objects from the collection AND delete all heap based objects.
Definition: TOrdCollection.cxx:199
ClassImp
#define ClassImp(name)
Definition: Rtypes.h:364
TOrdCollection::GetObjectRef
TObject ** GetObjectRef(const TObject *obj) const
return address of pointer obj
Definition: TOrdCollection.cxx:224
TOrdCollection::fGapStart
Int_t fGapStart
Definition: TOrdCollection.h:39
TObject::Error
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition: TObject.cxx:890
TOrdCollection::kMinExpand
@ kMinExpand
Definition: TOrdCollection.h:54
TOrdCollection
Definition: TOrdCollection.h:32
TOrdCollection::kDefaultCapacity
@ kDefaultCapacity
Definition: TOrdCollection.h:54
TOrdCollection::RemoveAt
TObject * RemoveAt(Int_t idx)
Remove object at index idx.
Definition: TOrdCollection.cxx:328
TOrdCollectionIter::fCursor
Int_t fCursor
Definition: TOrdCollection.h:104
TOrdCollection::SetCapacity
void SetCapacity(Int_t newCapacity)
Set/change ordered collection capacity.
Definition: TOrdCollection.cxx:378
TOrdCollection::AddBefore
void AddBefore(const TObject *before, TObject *obj)
Insert object before object before in the collection.
Definition: TOrdCollection.cxx:108
TOrdCollection::kShrinkFactor
@ kShrinkFactor
Definition: TOrdCollection.h:54
TOrdCollection::~TOrdCollection
~TOrdCollection()
Delete the collection.
Definition: TOrdCollection.cxx:46
TStorage::Dealloc
static void Dealloc(void *ptr)
De-allocate block of memory, that was allocated via TStorage::Alloc().
Definition: TStorage.cxx:170
bool
TIterator
Definition: TIterator.h:30
TOrdCollection::AddAt
void AddAt(TObject *obj, Int_t idx)
Insert object at position idx in the collection.
Definition: TOrdCollection.cxx:59
kIterForward
const Bool_t kIterForward
Definition: TCollection.h:40
TOrdCollection::MakeIterator
TIterator * MakeIterator(Bool_t dir=kIterForward) const
Return an ordered collection iterator.
Definition: TOrdCollection.cxx:280
TOrdCollection::Before
TObject * Before(const TObject *obj) const
Returns the object before object obj.
Definition: TOrdCollection.cxx:170
TSeqCollection::fSorted
Bool_t fSorted
Definition: TSeqCollection.h:37
TOrdCollection::TOrdCollection
TOrdCollection(const TOrdCollection &)
TOrdCollectionIter::fDirection
Bool_t fDirection
Definition: TOrdCollection.h:105
TOrdCollection::At
TObject * At(Int_t idx) const
Returns the object at position idx. Returns 0 if idx is out of range.
Definition: TOrdCollection.cxx:160
TOrdCollectionIter::fCurCursor
Int_t fCurCursor
Definition: TOrdCollection.h:103
TSeqCollection::Changed
virtual void Changed()
Definition: TSeqCollection.h:40
Option_t
const typedef char Option_t
Definition: RtypesCore.h:66
TOrdCollection::IndexOf
Int_t IndexOf(const TObject *obj) const
Return index of object in collection.
Definition: TOrdCollection.cxx:255
TOrdCollection.h
TOrdCollectionIter::operator!=
Bool_t operator!=(const TIterator &aIter) const
This operator compares two TIterator objects.
Definition: TOrdCollection.cxx:531
TOrdCollectionIter::TOrdCollectionIter
TOrdCollectionIter()
Definition: TOrdCollection.h:107
TCollection::GarbageCollect
static void GarbageCollect(TObject *obj)
Add to the list of things to be cleaned up.
Definition: TCollection.cxx:725
kFALSE
const Bool_t kFALSE
Definition: RtypesCore.h:92
TCollection::fSize
Int_t fSize
Definition: TCollection.h:148
TOrdCollection::LowWaterMark
Bool_t LowWaterMark() const
Definition: TOrdCollection.h:129
TOrdCollectionIter::operator=
TIterator & operator=(const TIterator &rhs)
Overridden assignment operator.
Definition: TOrdCollection.cxx:472
TCollection::IsOwner
Bool_t IsOwner() const
Definition: TCollection.h:188
TCollection::GrowBy
virtual Int_t GrowBy(Int_t delta) const
Increase the collection's capacity by delta slots.
Definition: TCollection.cxx:360
TObject::IsEqual
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:485
TOrdCollection::After
TObject * After(const TObject *obj) const
Return the object after object obj.
Definition: TOrdCollection.cxx:147
TOrdCollection::PutAt
void PutAt(TObject *obj, Int_t idx)
Put object at index idx. Overwrites what was at idx before.
Definition: TOrdCollection.cxx:315
TOrdCollection::AddAfter
void AddAfter(const TObject *after, TObject *obj)
Insert object after object after in the collection.
Definition: TOrdCollection.cxx:129
TObject::Warning
virtual void Warning(const char *method, const char *msgfmt,...) const
Issue warning message.
Definition: TObject.cxx:876
TOrdCollectionIter
Definition: TOrdCollection.h:96
TOrdCollection::MoveGapTo
void MoveGapTo(Int_t newGapStart)
Move gap to new position.
Definition: TOrdCollection.cxx:289
TOrdCollection::Sort
void Sort()
If objects in collection are sortable (i.e.
Definition: TOrdCollection.cxx:397
TOrdCollectionIter::Next
TObject * Next()
Return next object in collection.
Definition: TOrdCollection.cxx:502
TOrdCollection::Remove
TObject * Remove(TObject *obj)
Remove object from collection.
Definition: TOrdCollection.cxx:365
R__ASSERT
#define R__ASSERT(e)
Definition: TError.h:120
TOrdCollection::BinarySearch
Int_t BinarySearch(TObject *obj)
Find object using a binary search.
Definition: TOrdCollection.cxx:415
TCollection::GetSize
virtual Int_t GetSize() const
Return the capacity of the collection, i.e.
Definition: TCollection.h:182
TOrdCollection::Init
void Init(Int_t capacity)
Initialize ordered collection.
Definition: TOrdCollection.cxx:267
TOrdCollectionIter::Reset
void Reset()
Reset collection iterator.
Definition: TOrdCollection.cxx:518
TStorage::Alloc
static void * Alloc(size_t size)
Allocate a block of memory, that later can be resized using TStorage::ReAlloc().
Definition: TStorage.cxx:152
TOrdCollection::fCapacity
Int_t fCapacity
Definition: TOrdCollection.h:38
TObject
Definition: TObject.h:37
TObject::IsOnHeap
R__ALWAYS_INLINE Bool_t IsOnHeap() const
Definition: TObject.h:133
TStorage::ReAlloc
static void * ReAlloc(void *vp, size_t size)
Reallocate (i.e.
Definition: TStorage.cxx:183
Class
void Class()
Definition: Class.C:29
TOrdCollection::AddFirst
void AddFirst(TObject *obj)
Insert object at beginning of collection.
Definition: TOrdCollection.cxx:92
TOrdCollection::Clear
void Clear(Option_t *option="")
Remove all objects from the collection.
Definition: TOrdCollection.cxx:184
TOrdCollection::fCont
TObject ** fCont
Definition: TOrdCollection.h:37
TOrdCollection::First
TObject * First() const
Return the first object in the collection.
Definition: TOrdCollection.cxx:216
TOrdCollection::TOrdCollectionIter
friend class TOrdCollectionIter
Definition: TOrdCollection.h:34
int
TOrdCollection::fGapSize
Int_t fGapSize
Definition: TOrdCollection.h:40
TOrdCollection::AddLast
void AddLast(TObject *obj)
Add object at the end of the collection.
Definition: TOrdCollection.cxx:100
TError.h
TOrdCollectionIter::fCol
const TOrdCollection * fCol
Definition: TOrdCollection.h:102
TOrdCollection::LogIndex
Int_t LogIndex(Int_t idx) const
Definition: TOrdCollection.h:137