Logo ROOT   6.08/07
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 
15 Used by TEntryList to store the entry numbers.
16 
17 There 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 
24 In both cases, a UShort_t* is used. The second option is better in case
25 less than 1/16 or more than 15/16 of entries pass the selection, and the representation can be
26 changed by calling OptimizeStorage() function.
27 When the block is being filled, it's always stored as bits, and the OptimizeStorage()
28 function is called by TEntryList when it starts filling the next block. If
29 Enter() or Remove() is called after OptimizeStorage(), representation is
30 again changed to 1).
31 
32 Begin_Macro(source)
33 entrylistblock_figure1.C
34 End_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
53 
55 {
56  fIndices = 0;
57  fN = kBlockSize;
58  fNPassed = 0;
59  fType = -1;
60  fPassing = 1;
61  fCurrent = 0;
62  fLastIndexReturned = -1;
63  fLastIndexQueried = -1;
64 }
65 
66 ////////////////////////////////////////////////////////////////////////////////
67 /// Copy c-tor
68 
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;
83  fLastIndexReturned = -1;
84  fLastIndexQueried = -1;
85 }
86 
87 ////////////////////////////////////////////////////////////////////////////////
88 /// Destructor
89 
91 {
92  if (fIndices)
93  delete [] fIndices;
94  fIndices = 0;
95 }
96 
97 ////////////////////////////////////////////////////////////////////////////////
98 
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;
117  fLastIndexReturned = -1;
118  fLastIndexQueried = -1;
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
127 
129 {
130  if (entry > kBlockSize*16) {
131  Error("Enter", "illegal entry value!");
132  return 0;
133  }
134  if (!fIndices){
135  fIndices = new UShort_t[kBlockSize] ;
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
165 
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
193 
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
242 
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;
257  fLastIndexReturned = -1;
258  fLastIndexQueried = -1;
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  }
360  fLastIndexQueried = -1;
361  fLastIndexReturned = -1;
362  OptimizeStorage();
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
369 
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()
381 
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;
405  fLastIndexReturned = fIndices[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){
417  fLastIndexReturned = i;
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){
425  fLastIndexReturned = j;
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){
433  fLastIndexReturned = j;
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
446 
448 {
449  if (fLastIndexQueried==GetNPassed()-1){
451  fLastIndexReturned = -1;
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){
477  return fIndices[fLastIndexQueried];
478  } else {
480  while (!Contains(fLastIndexReturned)){
482  }
483  return fLastIndexReturned;
484  }
485 
486  }
487  return -1;
488 }
489 
490 ////////////////////////////////////////////////////////////////////////////////
491 /// Print the entries in this block
492 
493 void 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 corrent values
503 
504 void TEntryListBlock::PrintWithShift(Int_t shift) const
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
546 
548 {
549  if (fType!=0) return;
550  if (fNPassed > kBlockSize*15)
551  fPassing = 0;
552  if (fNPassed<kBlockSize || !fPassing){
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
563 
564 void 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)
590  fNPassed = kBlockSize*16-fNPassed;
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  }
611  fNPassed = kBlockSize*16-fNPassed;
612  }
613  if (fIndices)
614  delete [] fIndices;
615  fIndices = indexnew;
616  fType = 0;
617  fN = kBlockSize;
618  fPassing = 1;
619  return;
620 }
Int_t fLastIndexQueried
! to optimize GetEntry() in a loop
const char Option_t
Definition: RtypesCore.h:62
void OptimizeStorage()
If there are < kBlockSize or >kBlockSize*15 entries, change to an array representation.
unsigned short UShort_t
Definition: RtypesCore.h:36
void ToUpper()
Change string to upper case.
Definition: TString.cxx:1102
Int_t fLastIndexReturned
! to optimize GetEntry() in a loop
Int_t Merge(TEntryListBlock *block)
Merge with the other block Returns the resulting number of entries in the block.
Basic string class.
Definition: TString.h:137
int Int_t
Definition: RtypesCore.h:41
bool Bool_t
Definition: RtypesCore.h:59
const Bool_t kFALSE
Definition: Rtypes.h:92
Int_t fType
0 - bits, 1 - list
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...
Int_t GetEntry(Int_t entry)
Return entry #entry.
void PrintWithShift(Int_t shift) const
Print the indices of this block + shift (used from TEntryList::Print()) to print the corrent values...
UShort_t * fIndices
[fN]
TObject()
TObject constructor.
Definition: TObject.cxx:65
TEntryListBlock()
Default c-tor.
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition: TObject.cxx:925
Bool_t fPassing
1 - stores entries that belong to the list 0 - stores entries that don&#39;t belong to the list ...
~TEntryListBlock()
Destructor.
Int_t Contains(Int_t entry)
True if the block contains entry #entry.
Int_t GetNPassed()
Returns the number of entries, passing the selection.
Int_t Next()
Return the next non-zero entry Faster than GetEntry() function.
#define ClassImp(name)
Definition: Rtypes.h:279
Int_t fNPassed
number of entries in the entry list (if fPassing=0 - number of entries not in the entry list ...
virtual void Print(const Option_t *option="") const
Print the entries in this block.
Bool_t Contains(const char *pat, ECaseCompare cmp=kExact) const
Definition: TString.h:567
UShort_t fCurrent
! to fasten Contains() in list mode
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 ...
void Transform(Bool_t dir, UShort_t *indexnew)
Transform the existing fIndices.
double result[121]
Used by TEntryList to store the entry numbers.
Int_t fN
size of fIndices for I/O =fNPassed for list, fBlockSize for bits
const Bool_t kTRUE
Definition: Rtypes.h:91
TEntryListBlock & operator=(const TEntryListBlock &rhs)