    // @(#)root/base:$Name:  $:$Id: TBits.cxx,v 1.16 2004/01/26 11:52:40 brun Exp $
    // Author: Philippe Canal 05/02/2001
    //    Feb  5 2001: Creation
    //    Feb  6 2001: Changed all int to unsigned int.
    //______________________________________________________________________________

    //////////////////////////////////////////////////////////////////////////
    //                                                                      //
    // TBits                                                                //
    //                                                                      //
    // Container of bits                                                    //
    //                                                                      //
    // This class provides a simple container of bits.                      //
    // Each bit can be set and tested via the functions SetBitNumber and    //
    // TestBitNumber.                                             .         //
    // The default value of all bits is kFALSE.                             //
    // The size of the container is automatically extended when a bit       //
    // number is either set or tested.  To reduce the memory size of the    //
    // container use the Compact function, this will discard the memory     //
    // occupied by the upper bits that are 0.                               //
    //                                                                      //
    //////////////////////////////////////////////////////////////////////////

    #include "TBits.h"
    #include "string.h"

    ClassImp(TBits)

    //______________________________________________________________________________
     TBits::TBits(UInt_t nbits) : fNbits(nbits)
    {
       // TBits constructor.  All bits set to 0

       if (nbits <= 0) nbits = 8;
       fNbytes  = ((nbits-1)/8) + 1;
       fAllBits = new UChar_t[fNbytes];
       // this is redundant only with libNew
       memset(fAllBits,0,fNbytes);
    }

    //______________________________________________________________________________
     TBits::TBits(const TBits &original) : TObject(original), fNbits(original.fNbits),
       fNbytes(original.fNbytes)
    {
       // TBits copy constructor

       fAllBits = new UChar_t[fNbytes];
       memcpy(fAllBits,original.fAllBits,fNbytes);

    }

    //______________________________________________________________________________
    TBits& TBits::operator=(const TBits& rhs)
    {
       // TBits assignment operator

       if (this != &rhs) {
          TObject::operator=(rhs);
          fNbits   = rhs.fNbits;
          fNbytes  = rhs.fNbytes;
          delete [] fAllBits;
          if (fNbytes != 0) {
             fAllBits = new UChar_t[fNbytes];
             memcpy(fAllBits,rhs.fAllBits,fNbytes);
          } else {
             fAllBits = 0;
          }
       }
       return *this;
    }

    //______________________________________________________________________________
     TBits::~TBits()
    {
       // TBits destructor

       delete [] fAllBits;
    }

    //______________________________________________________________________________
     void TBits::Clear(Option_t * /*option*/)
    {
       delete [] fAllBits;
       fAllBits = 0;
       fNbits   = 0;
       fNbytes  = 0;
    }

    //______________________________________________________________________________
     void TBits::Compact()
    {
       // Reduce the storage used by the object to a minimun

       if (!fNbits || !fAllBits) return;
       UInt_t needed;
       for(needed=fNbytes-1;
           needed > 0 && fAllBits[needed]==0; ) { needed--; };
       needed++;

       if (needed!=fNbytes) {
          UChar_t *old_location = fAllBits;
          fAllBits = new UChar_t[needed];

          memcpy(fAllBits,old_location,needed);
          delete [] old_location;

          fNbytes = needed;
          fNbits = 8*fNbytes;
       }
    }

    //______________________________________________________________________________
     UInt_t TBits::CountBits(UInt_t startBit) const
    {
       // Return number of bits set to 1 starting at bit startBit

       const Int_t nbits[256] = {
                 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
                 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
                 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
                 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
                 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
                 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
                 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
                 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
                 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
                 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
                 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
                 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
                 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
                 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
                 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
                 4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};

       UInt_t i,count = 0;
       if (startBit == 0) {
          for(i=0; i<fNbytes; i++) {
             count += nbits[fAllBits[i]];
          }
          return count;
       }
       if (startBit >= fNbits) return count;
       UInt_t startByte = startBit/8;
       UInt_t ibit = startBit%8;
       if (ibit) {
          for (i=ibit;i<8;i++) {
             if (fAllBits[startByte] & (1<<ibit)) count++;
          }
          startByte++;
       }
       for(i=startByte; i<fNbytes; i++) {
          count += nbits[fAllBits[i]];
       }
       return count;
    }

    //______________________________________________________________________________
     UInt_t TBits::FirstNullBit(UInt_t startBit) const
    {
       // Return position of first null bit

       const Int_t fbits[256] = {
                 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,
                 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
                 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,
                 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,
                 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,
                 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
                 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,
                 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,7,
                 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,
                 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
                 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,
                 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,
                 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,
                 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
                 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,
                 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,8};

       UInt_t i;
       if (startBit == 0) {
          for(UInt_t i=0; i<fNbytes; i++) {
             if (fAllBits[i] != 255) return 8*i + fbits[fAllBits[i]];
          }
          return fNbits;
       }
       if (startBit >= fNbits) return fNbits;
       UInt_t startByte = startBit/8;
       UInt_t ibit = startBit%8;
       if (ibit) {
          for (i=ibit;i<8;i++) {
             if ((fAllBits[startByte] & (1<<i)) == 0) return 8*startByte+i;
          }
          startByte++;
       }
       for(i=startByte; i<fNbytes; i++) {
          if (fAllBits[i] != 255) return 8*i + fbits[fAllBits[i]];
       }
       return fNbits;
    }

    //______________________________________________________________________________
     UInt_t TBits::FirstSetBit(UInt_t startBit) const
    {
       // Return position of first non null bit

       const Int_t fbits[256] = {
                 8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
                 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
                 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
                 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
                 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
                 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
                 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
                 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
                 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
                 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
                 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
                 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
                 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
                 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
                 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
                 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0};

       UInt_t i;
       if (startBit == 0) {
          for(UInt_t i=0; i<fNbytes; i++) {
             if (fAllBits[i] != 0) return 8*i + fbits[fAllBits[i]];
          }
          return fNbits;
       }
       if (startBit >= fNbits) return fNbits;
       UInt_t startByte = startBit/8;
       UInt_t ibit = startBit%8;
       if (ibit) {
          for (i=ibit;i<8;i++) {
             if ((fAllBits[startByte] & (1<<i)) != 0) return 8*startByte+i;
          }
          startByte++;
       }
       for(i=startByte; i<fNbytes; i++) {
          if (fAllBits[i] != 0) return 8*i + fbits[fAllBits[i]];
       }
       return fNbits;
    }

    //______________________________________________________________________________
     void TBits::Paint(Option_t *)
    {
       // Once implemented, it will draw the bit field as an histogram.
       // use the TVirtualPainter as the usual trick

    }

    //______________________________________________________________________________
     void TBits::Print(Option_t *) const
    {
       // Print the list of active bits

       Int_t count = 0;
       for(UInt_t i=0; i<fNbytes; i++) {
          UChar_t val = fAllBits[i];
          for (UInt_t j=0; j<8; j++) {
             if (val & 1) printf(" bit:%4d = 1n",count);
             count++;
             val = val >> 1;
          }
       }
    }

    //______________________________________________________________________________
     void TBits::ResetAllBits(Bool_t)
    {
       // Reset all bits to 0 (false).

       if (fAllBits) memset(fAllBits,0,fNbytes);
    }

     //______________________________________________________________________________
      void TBits::ReserveBytes(UInt_t nbytes)
     {
         if (nbytes > fNbytes) {
             // do it in this order to remain exception-safe.
             UChar_t *newBits=new UChar_t[nbytes];
             delete[] fAllBits;
             fNbytes=nbytes;
             fAllBits=newBits;
         }
     }

     //______________________________________________________________________________
      void TBits::Set(UInt_t nbits, const Char_t *array)
     {
         UInt_t nbytes=(nbits+7)>>3;

         ReserveBytes(nbytes);

         fNbits=nbits;
         memcpy(fAllBits, array, nbytes);
     }

     //______________________________________________________________________________
      void TBits::Get(Char_t *array) const
     {
         memcpy(array, fAllBits, (fNbits+7)>>3);
     }

     #ifdef R__BYTESWAP  /* means we are on little endian */

     /*
     If we are on a little endian machine, a bitvector represented using
     any integer type is identical to a bitvector represented using bytes.
     -- FP.
     */

      void TBits::Set(UInt_t nbits, const Short_t *array)
      {
         Set(nbits, (const Char_t*)array);
     }

      void TBits::Set(UInt_t nbits, const Int_t *array)
     {
         Set(nbits, (const Char_t*)array);
     }

      void TBits::Set(UInt_t nbits, const Long64_t *array)
     {
         Set(nbits, (const Char_t*)array);
     }

      void TBits::Get(Short_t *array) const
     {
         Get((Char_t*)array);
     }

      void TBits::Get(Int_t *array) const
     {
         Get((Char_t*)array);
     }

      void TBits::Get(Long64_t *array) const
     {
         Get((Char_t*)array);
     }

     #else

     /*
     If we are on a big endian machine, some swapping around is required.
     */

      void TBits::Set(UInt_t nbits, const Short_t *array)
     {
         // make nbytes even so that the loop below is neat.
         UInt_t nbytes = ((nbits+15)>>3)&~1;

         ReserveBytes(nbytes);

         fNbits=nbits;

         const UChar_t *cArray = (const UChar_t*)array;
         for (UInt_t i=0; i<nbytes; i+=2) {
             fAllBits[i] = cArray[i+1];
             fAllBits[i+1] = cArray[i];
         }
     }

      void TBits::Set(UInt_t nbits, const Int_t *array)
     {
         // make nbytes a multiple of 4 so that the loop below is neat.
         UInt_t nbytes = ((nbits+31)>>3)&~3;

         ReserveBytes(nbytes);

         fNbits=nbits;

         const UChar_t *cArray = (const UChar_t*)array;
         for (UInt_t i=0; i<nbytes; i+=4) {
             fAllBits[i] = cArray[i+3];
             fAllBits[i+1] = cArray[i+2];
             fAllBits[i+2] = cArray[i+1];
             fAllBits[i+3] = cArray[i];
         }
     }

      void TBits::Set(UInt_t nbits, const Long64_t *array)
     {
        // make nbytes a multiple of 8 so that the loop below is neat.
        UInt_t nbytes = ((nbits+63)>>3)&~7;

        ReserveBytes(nbytes);

        fNbits=nbits;

        const UChar_t *cArray = (const UChar_t*)array;
        for (UInt_t i=0; i<nbytes; i+=8) {
            fAllBits[i] = cArray[i+7];
            fAllBits[i+1] = cArray[i+6];
            fAllBits[i+2] = cArray[i+5];
            fAllBits[i+3] = cArray[i+4];
            fAllBits[i+4] = cArray[i+3];
            fAllBits[i+5] = cArray[i+2];
            fAllBits[i+6] = cArray[i+1];
            fAllBits[i+7] = cArray[i];
        }
     }

      void TBits::Get(Short_t *array) const
     {
         UInt_t nBytes = (fNbits+7)>>3;
         UInt_t nSafeBytes = nBytes&~1;

         UChar_t *cArray=(UChar_t*)array;
         for (UInt_t i=0; i<nSafeBytes; i+=2) {
             cArray[i] = fAllBits[i+1];
             cArray[i+1] = fAllBits[i];
         }

         if (nBytes>nSafeBytes) {
             cArray[nSafeBytes+1] = fAllBits[nSafeBytes];
         }
     }

      void TBits::Get(Int_t *array) const
     {
         UInt_t nBytes = (fNbits+7)>>3;
         UInt_t nSafeBytes = nBytes&~3;

         UChar_t *cArray=(UChar_t*)array;
         UInt_t i;
         for (i=0; i<nSafeBytes; i+=4) {
             cArray[i] = fAllBits[i+3];
             cArray[i+1] = fAllBits[i+2];
             cArray[i+2] = fAllBits[i+1];
             cArray[i+3] = fAllBits[i];
         }

         for (i=0; i<nBytes-nSafeBytes; ++i) {
             cArray[nSafeBytes + (3 - i)] = fAllBits[nSafeBytes + i];
         }
     }

      void TBits::Get(Long64_t *array) const
     {
        UInt_t nBytes = (fNbits+7)>>3;
        UInt_t nSafeBytes = nBytes&~7;

        UChar_t *cArray=(UChar_t*)array;
        UInt_t i;
        for (i=0; i<nSafeBytes; i+=8) {
            cArray[i] = fAllBits[i+7];
            cArray[i+1] = fAllBits[i+6];
            cArray[i+2] = fAllBits[i+5];
            cArray[i+3] = fAllBits[i+4];
            cArray[i+4] = fAllBits[i+3];
            cArray[i+5] = fAllBits[i+2];
            cArray[i+6] = fAllBits[i+1];
            cArray[i+7] = fAllBits[i];
        }

        for (i=0; i<nBytes-nSafeBytes; ++i) {
            cArray[nSafeBytes + (7 - i)] = fAllBits[nSafeBytes + i];
        }
     }

     #endif

     Bool_t TBits::operator==(const TBits &other) const
     {
         if (fNbits != other.fNbits) {
             return kFALSE;
         }

         return !memcmp(fAllBits, other.fAllBits, (fNbits+7)>>3);
     }