Logo ROOT   6.30.04
Reference Guide
 All Namespaces Files Pages
TBits.h
Go to the documentation of this file.
1 // @(#)root/cont:$Id$
2 // Author: Philippe Canal 05/02/01
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 #ifndef ROOT_TBits
13 #define ROOT_TBits
14 
15 //////////////////////////////////////////////////////////////////////////
16 // //
17 // TBits //
18 // //
19 // Container of bits. //
20 // //
21 //////////////////////////////////////////////////////////////////////////
22 
23 #include "Rtypes.h"
24 #include "TObject.h"
25 #include <string.h>
26 
27 class TBits : public TObject {
28 
29 protected:
30 
31  UInt_t fNbits; // Highest bit set + 1
32  UInt_t fNbytes; // Number of UChars in fAllBits
33  UChar_t *fAllBits; //[fNbytes] array of UChars
34 
35  void ReserveBytes(UInt_t nbytes);
36  void DoAndEqual(const TBits& rhs);
37  void DoOrEqual (const TBits& rhs);
38  void DoXorEqual(const TBits& rhs);
39  void DoLeftShift(UInt_t shift);
40  void DoRightShift(UInt_t shift);
41  void DoFlip();
42  void Resize(UInt_t newlen);
43 
44 public:
45  TBits(UInt_t nbits = 8);
46  TBits(const TBits&);
47  TBits& operator=(const TBits&);
48  virtual ~TBits();
49 
50  class TReference {
51  friend class TBits;
52 
53  TBits &fBits; //!
54  UInt_t fPos; //!
55 
56  TReference(); // left undefined
57 
58 public:
59  TReference(TBits& bit, UInt_t pos) : fBits(bit),fPos(pos) { }
60  ~TReference() { }
61 
62  // For b[i] = val;
63  TReference& operator=(Bool_t val);
64 
65  // For b[i] = b[__j];
66  TReference& operator=(const TReference& rhs);
67 
68  // Flips the bit
69  Bool_t operator~() const;
70 
71  // For val = b[i];
72  operator Bool_t() const;
73  };
74 
75  //----- bit manipulation
76  //----- (note the difference with TObject's bit manipulations)
77  void ResetAllBits(Bool_t value=kFALSE); // if value=1 set all bits to 1
78  void ResetBitNumber(UInt_t bitnumber);
79  void SetBitNumber(UInt_t bitnumber, Bool_t value = kTRUE);
80  Bool_t TestBitNumber(UInt_t bitnumber) const;
81 
82  //----- Accessors and operator
83  TBits::TReference operator[](UInt_t bitnumber) { return TReference(*this,bitnumber); }
84  Bool_t operator[](UInt_t bitnumber) const;
85 
86  TBits& operator&=(const TBits& rhs) { DoAndEqual(rhs); return *this; }
87  TBits& operator|=(const TBits& rhs) { DoOrEqual(rhs); return *this; }
88  TBits& operator^=(const TBits& rhs) { DoXorEqual(rhs); return *this; }
89  TBits& operator<<=(UInt_t rhs) { DoLeftShift(rhs); return *this; }
90  TBits& operator>>=(UInt_t rhs) { DoRightShift(rhs); return *this; }
91  TBits operator<<(UInt_t rhs) { return TBits(*this)<<= rhs; }
92  TBits operator>>(UInt_t rhs) { return TBits(*this)>>= rhs; }
93  TBits operator~() const { TBits res(*this); res.DoFlip(); return res; }
94 
95  //----- Optimized setters
96  // Each of these will replace the contents of the receiver with the bitvector
97  // in the parameter array. The number of bits is changed to nbits. If nbits
98  // is smaller than fNbits, the receiver will NOT be compacted.
99  void Set(UInt_t nbits, const Char_t *array);
100  void Set(UInt_t nbits, const UChar_t *array) { Set(nbits, (const Char_t*)array); }
101  void Set(UInt_t nbits, const Short_t *array);
102  void Set(UInt_t nbits, const UShort_t *array) { Set(nbits, (const Short_t*)array); }
103  void Set(UInt_t nbits, const Int_t *array);
104  void Set(UInt_t nbits, const UInt_t *array) { Set(nbits, (const Int_t*)array); }
105  void Set(UInt_t nbits, const Long64_t *array);
106  void Set(UInt_t nbits, const ULong64_t *array) { Set(nbits, (const Long64_t*)array); }
107 
108  //----- Optimized getters
109  // Each of these will replace the contents of the parameter array with the
110  // bits in the receiver. The parameter array must be large enough to hold
111  // all of the bits in the receiver.
112  // Note on semantics: any bits in the parameter array that go beyond the
113  // number of the bits in the receiver will have an unspecified value. For
114  // example, if you call Get(Int*) with an array of one integer and the TBits
115  // object has less than 32 bits, then the remaining bits in the integer will
116  // have an unspecified value.
117  void Get(Char_t *array) const;
118  void Get(UChar_t *array) const { Get((Char_t*)array); }
119  void Get(Short_t *array) const;
120  void Get(UShort_t *array) const { Get((Short_t*)array); }
121  void Get(Int_t *array) const;
122  void Get(UInt_t *array) const { Get((Int_t*)array); }
123  void Get(Long64_t *array) const;
124  void Get(ULong64_t *array) const { Get((Long64_t*)array); }
125 
126  //----- Utilities
127  void Clear(Option_t *option="");
128  void Compact(); // Reduce the space used.
129  UInt_t CountBits(UInt_t startBit=0) const ; // return number of bits set to 1
130  UInt_t FirstNullBit(UInt_t startBit=0) const;
131  UInt_t FirstSetBit(UInt_t startBit=0) const;
132  UInt_t LastNullBit(UInt_t startBit=999999999) const;
133  UInt_t LastSetBit(UInt_t startBit=999999999) const;
134  UInt_t GetNbits() const { return fNbits; }
135  UInt_t GetNbytes() const { return fNbytes; }
136 
137  Bool_t operator==(const TBits &other) const;
138  Bool_t operator!=(const TBits &other) const { return !(*this==other); }
139 
140  void Paint(Option_t *option=""); // to visualize the bits array as an histogram, etc
141  void Print(Option_t *option="") const; // to show the list of active bits
142  void Output(std::ostream &) const;
143 
144  ClassDef(TBits,1) // Bit container
145 };
146 
147 
148 inline Bool_t operator&(const TBits::TReference& lhs, const TBits::TReference& rhs)
149 {
150  return (Bool_t)lhs & rhs;
151 }
152 
153 inline Bool_t operator|(const TBits::TReference& lhs, const TBits::TReference& rhs)
154 {
155  return (Bool_t)lhs | rhs;
156 }
157 
158 inline Bool_t operator^(const TBits::TReference& lhs, const TBits::TReference& rhs)
159 {
160  return (Bool_t)lhs ^ rhs;
161 }
162 
163 inline TBits operator&(const TBits& lhs, const TBits& rhs)
164 {
165  TBits result(lhs);
166  result &= rhs;
167  return result;
168 }
169 
170 inline TBits operator|(const TBits& lhs, const TBits& rhs)
171 {
172  TBits result(lhs);
173  result |= rhs;
174  return result;
175 }
176 
177 inline TBits operator^(const TBits& lhs, const TBits& rhs)
178 {
179  TBits result(lhs);
180  result ^= rhs;
181  return result;
182 }
183 
184 inline std::ostream &operator<<(std::ostream& os, const TBits& rhs)
185 {
186  rhs.Output(os); return os;
187 }
188 
189 // inline functions...
190 
191 inline void TBits::Resize(UInt_t newbitnumber)
192 {
193  // Update the allocated size.
194  UInt_t new_size = (newbitnumber / 8) + 1;
195  if (new_size > fNbytes) {
196  new_size *= 2;
197  UChar_t *old_location = fAllBits;
198  fAllBits = new UChar_t[new_size];
199  memcpy(fAllBits, old_location, fNbytes);
200  memset(fAllBits + fNbytes, 0, new_size - fNbytes);
201  fNbytes = new_size;
202  delete[] old_location;
203  }
204 }
205 
206 inline void TBits::SetBitNumber(UInt_t bitnumber, Bool_t value)
207 {
208  // Set bit number 'bitnumber' to be value
209 
210  if (bitnumber >= fNbits) {
211  Resize(bitnumber);
212  fNbits = bitnumber+1;
213  }
214  UInt_t loc = bitnumber/8;
215  UChar_t bit = bitnumber%8;
216  if (value)
217  fAllBits[loc] |= (1<<bit);
218  else
219  fAllBits[loc] &= (0xFF ^ (1<<bit));
220 }
221 
222 inline Bool_t TBits::TestBitNumber(UInt_t bitnumber) const
223 {
224  // Return the current value of the bit
225 
226  if (bitnumber >= fNbits) return kFALSE;
227  UInt_t loc = bitnumber/8;
228  UChar_t value = fAllBits[loc];
229  UChar_t bit = bitnumber%8;
230  Bool_t result = (value & (1<<bit)) != 0;
231  return result;
232  // short: return 0 != (fAllBits[bitnumber/8] & (1<< (bitnumber%8)));
233 }
234 
235 inline void TBits::ResetBitNumber(UInt_t bitnumber)
236 {
237  SetBitNumber(bitnumber,kFALSE);
238 }
239 
240 inline Bool_t TBits::operator[](UInt_t bitnumber) const
241 {
242  return TestBitNumber(bitnumber);
243 }
244 
245 inline TBits::TReference& TBits::TReference::operator=(Bool_t val)
246 {
247  // For b[i] = val.
248 
249  fBits.SetBitNumber(fPos,val); return *this;
250 }
251 
252 inline TBits::TReference& TBits::TReference::operator=(const TReference& rhs)
253 {
254  // For b[i] = b[__j].
255 
256  fBits.SetBitNumber(fPos,rhs.fBits.TestBitNumber(rhs.fPos)); return *this;
257 }
258 
259 inline Bool_t TBits::TReference::operator~() const
260 {
261  // Flips the bit.
262 
263  return !fBits.TestBitNumber(fPos);
264 }
265 
266 inline TBits::TReference::operator Bool_t() const
267 {
268  // For val = b[i].
269 
270  return fBits.TestBitNumber(fPos);
271 }
272 
273 #endif
274 
275