Logo ROOT  
Reference Guide
TEntryListBlock.cxx
Go to the documentation of this file.
1// @(#)root/tree:$Id$
2// Author: Anna Kreshuk 27/10/2006
3
4/*************************************************************************
5 * Copyright (C) 1995-2006, 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 TEntryListBlock
13\ingroup tree
14
15Used by TEntryList to store the entry numbers.
16
17There are 2 ways to represent entry numbers in a TEntryListBlock:
18
19 1. as bits, where passing entry numbers are assigned 1, not passing - 0
20 2. as a simple array of entry numbers
21 - storing the numbers of entries that pass
22 - storing the numbers of entries that don't pass
23
24In both cases, a UShort_t* is used. The second option is better in case
25less than 1/16 or more than 15/16 of entries pass the selection, and the representation can be
26changed by calling OptimizeStorage() function.
27When the block is being filled, it's always stored as bits, and the OptimizeStorage()
28function is called by TEntryList when it starts filling the next block. If
29Enter() or Remove() is called after OptimizeStorage(), representation is
30again changed to 1).
31
32Begin_Macro
33entrylistblock_figure1.C
34End_Macro
35
36## Operations on blocks (see also function comments)
37
38 - __Merge__() - adds all entries from one block to the other. If the first block
39 uses array representation, it's changed to bits representation only
40 if the total number of passing entries is still less than kBlockSize
41 - __GetEntry(n)__ - returns n-th non-zero entry.
42 - __Next__() - return next non-zero entry. In case of representation 1), Next()
43 is faster than GetEntry()
44*/
45
46#include "TEntryListBlock.h"
47#include "TString.h"
48
50
51////////////////////////////////////////////////////////////////////////////////
52/// Default c-tor
55{
56 fIndices = 0;
57 fN = kBlockSize;
58 fNPassed = 0;
59 fType = -1;
60 fPassing = 1;
61 fCurrent = 0;
64}
65
66////////////////////////////////////////////////////////////////////////////////
67/// Copy c-tor
70{
71 fN = eblock.fN;
72 if (eblock.fIndices){
73 fIndices = new UShort_t[fN];
74 for (Int_t i=0; i<fN; i++)
75 fIndices[i] = eblock.fIndices[i];
76 } else {
77 fIndices = 0;
78 }
79 fNPassed = eblock.fNPassed;
80 fType = eblock.fType;
81 fPassing = eblock.fPassing;
82 fCurrent = eblock.fCurrent;
85}
86
87////////////////////////////////////////////////////////////////////////////////
88/// Destructor
91{
92 if (fIndices)
93 delete [] fIndices;
94 fIndices = 0;
95}
96
97////////////////////////////////////////////////////////////////////////////////
100{
101 if (this != &eblock) {
102 if (fIndices)
103 delete [] fIndices;
104
105 fN = eblock.fN;
106 if (eblock.fIndices){
107 fIndices = new UShort_t[fN];
108 for (Int_t i=0; i<fN; i++)
109 fIndices[i] = eblock.fIndices[i];
110 } else {
111 fIndices = 0;
112 }
113 fNPassed = eblock.fNPassed;
114 fType = eblock.fType;
115 fPassing = eblock.fPassing;
116 fCurrent = eblock.fCurrent;
119 }
120 return *this;
121}
122
123////////////////////////////////////////////////////////////////////////////////
124/// If the block has already been optimized and the entries
125/// are stored as a list and not as bits, trying to enter a new entry
126/// will make the block switch to bits representation
129{
130 if (entry > kBlockSize*16) {
131 Error("Enter", "illegal entry value!");
132 return 0;
133 }
134 if (!fIndices){
136 for (Int_t i=0; i<kBlockSize; i++)
137 fIndices[i] = 0;
138 fType = 0; //start in bits
139 }
140 if (fType==0){
141 //bits
142 Int_t i = entry>>4;
143 Int_t j = entry & 15;
144 if ((fIndices[i] & (1<<j))==0){
145 fIndices[i] |= 1<<j;
146 fNPassed++;
147 return 1;
148 } else {
149 return 0;
150 }
151 }
152 //list
153 //change to bits
154 UShort_t *bits = new UShort_t[kBlockSize];
155 Transform(1, bits);
156 Enter(entry);
157 return 0;
158}
159
160////////////////////////////////////////////////////////////////////////////////
161/// Remove entry \#entry
162/// If the block has already been optimized and the entries
163/// are stored as a list and not as bits, trying to remove a new entry
164/// will make the block switch to bits representation
167{
168 if (entry > kBlockSize*16) {
169 Error("Remove", "Illegal entry value!\n");
170 return 0;
171 }
172 if (fType==0){
173 Int_t i = entry>>4;
174 Int_t j = entry & 15;
175 if ((fIndices[i] & (1<<j))!=0){
176 fIndices[i] &= (0xFFFF^(1<<j));
177 fNPassed--;
178 return 1;
179 } else {
180 return 0;
181 }
182 }
183 //list
184 //change to bits
185 UShort_t *bits = new UShort_t[kBlockSize];
186 Transform(1, bits);
187 return Remove(entry);
188 //return 0;
189}
190
191////////////////////////////////////////////////////////////////////////////////
192/// True if the block contains entry \#entry
195{
196 if (entry > kBlockSize*16) {
197 Error("Contains", "Illegal entry value!\n");
198 return 0;
199 }
200 if (!fIndices && fPassing)
201 return 0;
202 if (fType==0 && fIndices){
203 //bits
204 Int_t i = entry>>4;
205 Int_t j = entry & 15;
206 Bool_t result = (fIndices[i] & (1<<j))!=0;
207 return result;
208 }
209 //list
210 if (entry < fCurrent) fCurrent = 0;
211 if (fPassing && fIndices){
212 for (Int_t i = fCurrent; i<fNPassed; i++){
213 if (fIndices[i]==entry){
214 fCurrent = i;
215 return kTRUE;
216 }
217 }
218 } else {
219 if (!fIndices || fNPassed==0){
220 //all entries pass
221 return kTRUE;
222 }
223 if (entry > fIndices[fNPassed-1])
224 return kTRUE;
225 for (Int_t i= fCurrent; i<fNPassed; i++){
226 if (fIndices[i]==entry){
227 fCurrent = i;
228 return kFALSE;
229 }
230 if (fIndices[i]>entry){
231 fCurrent = i;
232 return kTRUE;
233 }
234 }
235 }
236 return 0;
237}
238
239////////////////////////////////////////////////////////////////////////////////
240/// Merge with the other block
241/// Returns the resulting number of entries in the block
244{
245 Int_t i, j;
246 if (block->GetNPassed() == 0) return GetNPassed();
247 if (GetNPassed() == 0){
248 //this block is empty
249 fN = block->fN;
250 fIndices = new UShort_t[fN];
251 for (i=0; i<fN; i++)
252 fIndices[i] = block->fIndices[i];
253 fNPassed = block->fNPassed;
254 fType = block->fType;
255 fPassing = block->fPassing;
256 fCurrent = block->fCurrent;
259 return fNPassed;
260 }
261 if (fType==0){
262 //stored as bits
263 if (block->fType == 0){
264 for (i=0; i<kBlockSize*16; i++){
265 if (block->Contains(i))
266 Enter(i);
267 }
268 } else {
269 if (block->fPassing){
270 //the other block stores entries that pass
271 for (i=0; i<block->fNPassed; i++){
272 Enter(block->fIndices[i]);
273 }
274 } else {
275 //the other block stores entries that don't pass
276 if (block->fNPassed==0){
277 for (i=0; i<kBlockSize*16; i++){
278 Enter(i);
279 }
280 }
281 for (j=0; j<block->fIndices[0]; j++)
282 Enter(j);
283 for (i=0; i<block->fNPassed-1; i++){
284 for (j=block->fIndices[i]+1; j<block->fIndices[i+1]; j++){
285 Enter(j);
286 }
287 }
288 for (j=block->fIndices[block->fNPassed-1]+1; j<kBlockSize*16; j++)
289 Enter(j);
290 }
291 }
292 } else {
293 //stored as a list
294 if (GetNPassed() + block->GetNPassed() > kBlockSize){
295 //change to bits
296 UShort_t *bits = new UShort_t[kBlockSize];
297 Transform(1, bits);
298 Merge(block);
299 } else {
300 //this is only possible if fPassing=1 in both blocks
301 if (block->fType==1){
302 //second block stored as a list
303 //make a bigger list
304 Int_t en = block->fNPassed;
305 Int_t newsize = fNPassed + en;
306 UShort_t *newlist = new UShort_t[newsize];
307 UShort_t *elst = block->fIndices;
308 Int_t newpos, elpos;
309 newpos = elpos = 0;
310 for (i=0; i<fNPassed; i++) {
311 while (elpos < en && fIndices[i] > elst[elpos]) {
312 newlist[newpos] = elst[elpos];
313 newpos++;
314 elpos++;
315 }
316 if (fIndices[i] == elst[elpos]) elpos++;
317 newlist[newpos] = fIndices[i];
318 newpos++;
319 }
320 while (elpos < en) {
321 newlist[newpos] = elst[elpos];
322 newpos++;
323 elpos++;
324 }
325 delete [] fIndices;
326 fIndices = newlist;
327 fNPassed = newpos;
328 fN = fNPassed;
329 } else {
330 //second block is stored as bits
331
332 Int_t en = block->fNPassed;
333 Int_t newsize = fNPassed + en;
334 UShort_t *newlist = new UShort_t[newsize];
335 Int_t newpos, current;
336 newpos = current = 0;
337 for (i=0; i<kBlockSize*16; i++){
338 if (!block->Contains(i)) continue;
339 while(current < fNPassed && fIndices[current]<i){
340 newlist[newpos] = fIndices[current];
341 current++;
342 newpos++;
343 }
344 if (fIndices[current]==i) current++;
345 newlist[newpos] = i;
346 newpos++;
347 }
348 while(current<fNPassed){
349 newlist[newpos] = fIndices[current];
350 newpos++;
351 current++;
352 }
353 delete [] fIndices;
354 fIndices = newlist;
355 fNPassed = newpos;
356 fN = fNPassed;
357 }
358 }
359 }
363 return GetNPassed();
364}
365
366////////////////////////////////////////////////////////////////////////////////
367/// Returns the number of entries, passing the selection.
368/// In case, when the block stores entries that pass (fPassing=1) returns fNPassed
371{
372 if (fPassing)
373 return fNPassed;
374 else
375 return kBlockSize*16-fNPassed;
376}
377
378////////////////////////////////////////////////////////////////////////////////
379/// Return entry \#entry.
380/// See also Next()
383{
384 if (entry > kBlockSize*16) return -1;
385 if (entry > GetNPassed()) return -1;
386 if (entry == fLastIndexQueried+1) return Next();
387 else {
388 Int_t i=0; Int_t j=0; Int_t entries_found=0;
389 if (fType==0){
390 if ((fIndices[i] & (1<<j))!=0)
391 entries_found++;
392 while (entries_found<entry+1){
393 if (j==15){i++; j=0;}
394 else j++;
395 if ((fIndices[i] & (1<<j))!=0)
396 entries_found++;
397 }
398 fLastIndexQueried = entry;
399 fLastIndexReturned = i*16+j;
400 return fLastIndexReturned;
401 }
402 if (fType==1){
403 if (fPassing){
404 fLastIndexQueried = entry;
406 return fIndices[entry];
407 } else {
408 fLastIndexQueried = entry;
409 if (!fIndices || fNPassed==0){
410 //all entries pass
411 fLastIndexReturned = entry;
412 return fLastIndexReturned;
413 }
414 for (i=0; i<fIndices[0]; i++){
415 entries_found++;
416 if (entries_found==entry+1){
418 return fLastIndexReturned;
419 }
420 }
421 for (i=0; i<fNPassed-1; i++){
422 for (j=fIndices[i]+1; j<fIndices[i+1]; j++){
423 entries_found++;
424 if (entries_found==entry+1){
426 return fLastIndexReturned;
427 }
428 }
429 }
430 for (j=fIndices[fNPassed-1]+1; j<kBlockSize*16; j++){
431 entries_found++;
432 if (entries_found==entry+1){
434 return fLastIndexReturned;
435 }
436 }
437 }
438 }
439 return -1;
440 }
441}
442
443////////////////////////////////////////////////////////////////////////////////
444/// Return the next non-zero entry
445/// Faster than GetEntry() function
448{
452 return -1;
453 }
454
455 if (fType==0) {
456 //bits
457 Int_t i=0;
458 Int_t j=0;
460 i = fLastIndexReturned>>4;
461 j = fLastIndexReturned & 15;
462 Bool_t result=(fIndices[i] & (1<<j))!=0;
463 while (result==0){
464 if (j==15) {j=0; i++;}
465 else j++;
466 result = (fIndices[i] & (1<<j))!=0;
467 }
468 fLastIndexReturned = i*16+j;
470 return fLastIndexReturned;
471
472 }
473 if (fType==1) {
475 if (fPassing){
478 } else {
482 }
483 return fLastIndexReturned;
484 }
485
486 }
487 return -1;
488}
489
490////////////////////////////////////////////////////////////////////////////////
491/// Print the entries in this block
493void TEntryListBlock::Print(const Option_t *option) const
494{
495 TString opt = option;
496 opt.ToUpper();
497 if (opt.Contains("A")) PrintWithShift(0);
498}
499
500////////////////////////////////////////////////////////////////////////////////
501/// Print the indices of this block + shift (used from TEntryList::Print()) to
502/// print the current values
505{
506 Int_t i;
507 if (fType==0){
508 Int_t ibit, ibite;
509 Bool_t result;
510 for (i=0; i<kBlockSize*16; i++){
511 ibite = i>>4;
512 ibit = i & 15;
513 result = (fIndices[ibite] & (1<<ibit))!=0;
514 if (result)
515 printf("%d\n", i+shift);
516 }
517 } else {
518 if (fPassing){
519 for (i=0; i<fNPassed; i++){
520 printf("%d\n", fIndices[i]+shift);
521 }
522 } else {
523 if (fNPassed==0){
524 for (i=0; i<kBlockSize*16; i++)
525 printf("%d\n", i+shift);
526 return;
527 }
528 for (i=0; i<fIndices[0]; i++){
529 printf("%d\n", i+shift);
530 }
531 for (i=0; i<fNPassed-1; i++){
532 for (Int_t j=fIndices[i]+1; j<fIndices[i+1]; j++){
533 printf("%d\n", j+shift);
534 }
535 }
536 for (Int_t j=fIndices[fNPassed-1]+1; j<kBlockSize*16; j++){
537 printf("%d\n", j+shift);
538 }
539 }
540 }
541}
542
543////////////////////////////////////////////////////////////////////////////////
544/// If there are < kBlockSize or >kBlockSize*15 entries, change to an array
545/// representation
548{
549 if (fType!=0) return;
550 if (fNPassed > kBlockSize*15)
551 fPassing = 0;
553 //less than 4000 entries passing, makes sense to change from bits to list
554 UShort_t *indexnew = new UShort_t[fNPassed];
555 Transform(0, indexnew);
556 }
557}
558
559////////////////////////////////////////////////////////////////////////////////
560/// Transform the existing fIndices
561/// - dir=0 - transform from bits to a list
562/// - dir=1 - tranform from a list to bits
564void TEntryListBlock::Transform(Bool_t dir, UShort_t *indexnew)
565{
566 Int_t i=0;
567 Int_t ilist = 0;
568 Int_t ibite, ibit;
569 if (!dir) {
570 for (i=0; i<kBlockSize*16; i++){
571 ibite = i >> 4;
572 ibit = i & 15;
573 Bool_t result = (fIndices[ibite] & (1<<ibit))!=0;
574 if (result && fPassing){
575 //fill with the entries that pass
576 indexnew[ilist] = i;
577 ilist++;
578 }
579 else if (!result && !fPassing){
580 //fill with the entries that don't pass
581 indexnew[ilist] = i;
582 ilist++;
583 }
584 }
585 if (fIndices)
586 delete [] fIndices;
587 fIndices = indexnew;
588 fType = 1;
589 if (!fPassing)
591 fN = fNPassed;
592 return;
593 }
594
595 if (fPassing){
596 for (i=0; i<kBlockSize; i++)
597 indexnew[i] = 0;
598 for (i=0; i<fNPassed; i++){
599 ibite = fIndices[i]>>4;
600 ibit = fIndices[i] & 15;
601 indexnew[ibite] |= 1<<ibit;
602 }
603 } else {
604 for (i=0; i<kBlockSize; i++)
605 indexnew[i] = 65535;
606 for (i=0; i<fNPassed; i++){
607 ibite = fIndices[i]>>4;
608 ibit = fIndices[i] & 15;
609 indexnew[ibite] ^= 1<<ibit;
610 }
612 }
613 if (fIndices)
614 delete [] fIndices;
615 fIndices = indexnew;
616 fType = 0;
617 fN = kBlockSize;
618 fPassing = 1;
619 return;
620}
unsigned short UShort_t
Definition: RtypesCore.h:36
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
Used by TEntryList to store the entry numbers.
Int_t fLastIndexQueried
! to optimize GetEntry() in a loop
void OptimizeStorage()
If there are < kBlockSize or >kBlockSize*15 entries, change to an array representation.
UShort_t * fIndices
[fN]
Int_t Next()
Return the next non-zero entry Faster than GetEntry() function.
TEntryListBlock & operator=(const TEntryListBlock &rhs)
void Transform(Bool_t dir, UShort_t *indexnew)
Transform the existing fIndices.
Int_t fType
0 - bits, 1 - list
Int_t fNPassed
number of entries in the entry list (if fPassing=0 - number of entries not in the entry list
~TEntryListBlock()
Destructor.
Int_t GetNPassed()
Returns the number of entries, passing the selection.
void PrintWithShift(Int_t shift) const
Print the indices of this block + shift (used from TEntryList::Print()) to print the current values.
Bool_t Enter(Int_t entry)
If the block has already been optimized and the entries are stored as a list and not as bits,...
Bool_t Remove(Int_t entry)
Remove entry #entry If the block has already been optimized and the entries are stored as a list and ...
Int_t fN
size of fIndices for I/O =fNPassed for list, fBlockSize for bits
Int_t fLastIndexReturned
! to optimize GetEntry() in a loop
Bool_t fPassing
1 - stores entries that belong to the list 0 - stores entries that don't belong to the list
UShort_t fCurrent
! to fasten Contains() in list mode
TEntryListBlock()
Default c-tor.
Int_t Contains(Int_t entry)
True if the block contains entry #entry.
virtual void Print(const Option_t *option="") const
Print the entries in this block.
Int_t GetEntry(Int_t entry)
Return entry #entry.
Int_t Merge(TEntryListBlock *block)
Merge with the other block Returns the resulting number of entries in the block.
Mother of all ROOT objects.
Definition: TObject.h:37
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition: TObject.cxx:880
Basic string class.
Definition: TString.h:131
void ToUpper()
Change string to upper case.
Definition: TString.cxx:1138
Bool_t Contains(const char *pat, ECaseCompare cmp=kExact) const
Definition: TString.h:619
constexpr size_t block
Definition: BatchHelpers.h:29