mi32/bitset.h

Go to the documentation of this file.

/**
 * \file mi32/bitset.h
 * \brief Definitions for BITSET classes.
 *
 * This class is designed so that an access violation beyond 
 * the array size results in a bit setting of 'false'.
 *
 * \if NODOC
 * $Id: bitset.h_v 1.60 2006/03/08 20:43:10 dwilliss Exp $
 *
 * $Log: bitset.h_v $
 * Revision 1.60  2006/03/08 20:43:10  dwilliss
 * missed a ctor
 *
 * Revision 1.59  2006/03/08 17:55:43  dwilliss
 * Make ctors non-inline to see if that will solve a problem I'm having.
 * Unfortunately, have to recompile everything to know for sure.
 *
 * Revision 1.58  2005/11/14 20:29:45  mju
 * Put most of implementations in misystem dll as many inlines were too large.
 *
 * Revision 1.57  2005/03/01 14:15:43  mju
 * Use 'value' in hasMultiple.
 *
 * Revision 1.56  2005/02/28 21:47:27  mju
 * Add HasValue, HasMultiple, CountValues.
 *
 * Revision 1.55  2004/02/24 18:50:44  mju
 * In unowned assign, check for null array.
 *
 * Revision 1.54  2004/02/04 15:02:16  scowan
 * Handle ctor with legacy bit array of null.
 *
 * Revision 1.53  2003/12/24 21:22:15  scowan
 * Fixed vc7 warning.
 *
 * Revision 1.52  2003/11/17 17:30:22  dwilliss
 * Gave the iterator a default constructor so you could declare it outside
 * a loop and assign it inside a loop.
 *
 * Revision 1.51  2003/10/01 22:10:50  dwilliss
 * *** empty log message ***
 *
 * Revision 1.50  2003/09/25 21:29:07  dwilliss
 * Don't capitalize enum any more. Genitor needed it, doxygen doesn't like it.
 *
 * Revision 1.49  2003/09/15 13:49:56  fileserver!dwilliss
 * Doxygen
 *
 * Revision 1.48  2003/06/24 15:59:05  mju
 * Add SET_OPERATION enum.
 *
 * Revision 1.47  2003/01/23 21:23:56  scowan
 * Fixed unsigned / signed comparison warnings.
 *
 * Revision 1.46  2003/01/23 18:23:10  scowan
 * Added private array methods to disallow array access to the bitset.
 *
 * Revision 1.45  2002/11/20 23:52:31  dwilliss
 * Fixed problem in SetRange/ClearRange if the whole range fell within a single
 * byte
 *
 * Revision 1.43  2002/09/12 21:27:59  mju
 * Alloc copy/assign of bitset_unowned.
 *
 * Revision 1.42  2002/08/19 15:01:10  scowan
 * Fixed g++3.1 warnings.
 *
 * Revision 1.41  2002/02/27 16:26:49  scowan
 * Fixed issues with get range.
 *
 * Revision 1.40  2002/02/26 15:03:01  scowan
 * Fixed stupid warning.
 *
 * Revision 1.39  2002/01/30 23:20:12  scowan
 * Fixed problems with GetRange.
 *
 * Revision 1.38  2002/01/29 21:37:32  scowan
 * Fixed infinite loop.
 *
 * Revision 1.37  2002/01/28 21:34:59  scowan
 * Added a Get Range method.
 *
 * Revision 1.36  2002/01/25 23:34:02  scowan
 * Added bitset shared class.
 *
 * Revision 1.35  2001/09/17 14:11:04  mju
 * Fix Set/ClearRange, was writing 1 byte too far.
 *
 * Revision 1.34  2001/08/13 15:05:45  scowan
 * Fixed ABR in operator++().
 *
 * Revision 1.33  2000/11/28 21:15:00  scowan
 * Attach() and Detach() methods added.
 *
 * Revision 1.32  2000/10/05 16:57:23  mju
 * make bitset_unowned::begin/end const.
 *
 * Revision 1.31  2000/09/20 21:48:14  mju
 * In op++ check index past end before access.
 *
 * Revision 1.30  2000/07/20 20:33:49  mju
 * Fix SetRange() where end of range was < 8 would cause ABW.
 *
 * Revision 1.29  2000/07/10 19:34:20  mju
 * Fix Set/ClearRange().
 *
 * Revision 1.28  2000/07/10 14:42:29  mju
 * Add Set/ClearRange methods.
 *
 * Revision 1.27  2000/06/20 14:15:35  mju
 * Fix bitwise operators comparison for same size.
 *
 * Revision 1.26  2000/06/19 17:32:31  scowan
 * *** empty log message ***
 *
 * Revision 1.25  2000/06/09 14:27:19  mju
 * Add BITSET copy ctor too so compiler doesn't generate an incorrect one.
 *
 * Revision 1.24  2000/06/09 14:25:23  mju
 * Add bitset assignment from BITSET as Unix compilers complain otherwise.
 *
 * Revision 1.23  2000/06/08 20:45:24  mju
 * Implement BITSET_UNOWNED so can use old-style bitarrays without copy.
 * Change to use UINT8* so can safely cast to old-style bit arrays.
 * Change iterator to allow iteration through 'false' entries too.
 * Rename Clear as ClearAll.
 * Rename FlipBit as Invert.
 * Add Set(entry), Clear(entry), and InvertAll.
 * Add bitwise operators between bit sets.
 *
 * Revision 1.21  2000/06/07 16:03:45  scowan
 * Fixed Begin().
 *
 * Revision 1.20  2000/06/05 13:23:08  mju
 * Must define loop vars outside of loop if reference after end of loop.
 *
 * Revision 1.19  2000/06/02 22:53:34  scowan
 * Added new SETITERATOR nested class to iterate through set items.
 *
 * Revision 1.18  2000/05/31 22:10:45  mju
 * Don't include stdincls, include only those headers needed.
 * Use inclusion guards.
 *
 * \endif
***/

#ifndef INC_MI32_BITSET_H
#define INC_MI32_BITSET_H

#ifndef  INC_MI32_STDDEFNS_H
#include <mi32/stddefns.h>
#endif

#ifndef  INC_MEMORY_H
#include <memory.h>     // Includes defn for memset()
#define  INC_MEMORY_H
#endif


#ifdef MISYSTEMDLL
   #define CLASSLIBEXPORT MI_DLLCLASSEXPORT
#else
   #define CLASSLIBEXPORT MI_DLLCLASSIMPORT
#endif


#ifndef GENERATING_DOXYGEN_OUTPUT
class BITSET_SHARED;
#endif // GENERATING_DOXYGEN_OUTPUT


enum SET_OPERATION {
   SET_OPERATION_Null =          0,
   SET_OPERATION_Clear =         1,
   SET_OPERATION_Set =           2,
   SET_OPERATION_Negate =        3,
   SET_OPERATION_Copy =          4,
   SET_OPERATION_Union =         5,
   SET_OPERATION_Add =           SET_OPERATION_Union,
   SET_OPERATION_Subtract =      6,
   SET_OPERATION_ExUnion =       7,
   SET_OPERATION_Intersection =  8,
   };


//=====================================================================================================================
//! Base bit set class for case where actual array is "owned" by
//! something other than the class.
class CLASSLIBEXPORT BITSET_UNOWNED {

   protected:                          //! Placed here so that ITERATOR class can have access to them
      UINT8 *m_Array;                     //!< Memory containing the bit array
      UINT32 m_NumEntries;                //!< Actual number of bits used
      UINT32 m_ArraySize;                 //!< Array size in bytes
      
   public:

      class ITERATOR;
      friend class ITERATOR;

      //! Iterator to step forward through all selected items in a BITSET.
      class CLASSLIBEXPORT ITERATOR {
         public:

            //! Default constructor (leaves the bitset unattache).
            ITERATOR ();

            //! Dereference operator, returns item number set.
            UINT32 operator* (
               ) const {
               return (m_SetItemIndex);
               }

            //! Cast operator to UINT32.
            operator UINT32 (
               ) const {
               return (m_SetItemIndex);
               }

            //! Pre-increment operator.
            ITERATOR& operator++ (
               );

            //! Equality operator.
            bool operator== (
               const ITERATOR& rhs
               ) const {
               return (m_BitSet == rhs.m_BitSet && (m_SetItemIndex == rhs.m_SetItemIndex || (m_SetItemIndex >= m_BitSet->m_NumEntries && rhs.m_SetItemIndex >= m_BitSet->m_NumEntries)));
               }

            //! Inequality operator.
            bool operator!= (
               const ITERATOR& rhs
               ) const {
               return (!(*this == rhs));
               }

         protected:
            #ifndef GENERATING_DOXYGEN_OUTPUT
            const BITSET_UNOWNED* GetBitSet () const { return m_BitSet; }
            #endif

         private:
            #ifndef GENERATING_DOXYGEN_OUTPUT
            const BITSET_UNOWNED* m_BitSet;
            UINT32 m_SetItemIndex;
            UINT8 m_TestBit;
            UINT8 m_SkipByte;

            // Construct for "begin".
            ITERATOR (
               const BITSET_UNOWNED* BitSet,
               bool testvalue
               );

            // Construct for "end".
            ITERATOR (
               const BITSET_UNOWNED* BitSet
               ) : 
               m_BitSet(BitSet),
               m_SetItemIndex(BitSet->GetNumEntries()),
               m_TestBit(0),
               m_SkipByte(0)
               {
               }

            friend class BITSET_UNOWNED;
         #endif // GENERATING_DOXYGEN_OUTPUT
         };
      

      //! Default constructor.
      BITSET_UNOWNED (                    
         );

      //! Constructor to convert old bit-array's into BITSET_UNOWNEDs.
      BITSET_UNOWNED (
         UINT8 *set,                      //!< Old bit array set
         UINT32 NumEntries                //!< Number of items in old bit array, not size in bytes
         );

      //! Destructor.
      virtual ~BITSET_UNOWNED (
         );

      //! Conversion to old bit-array style for legacy code.      
      operator UINT8* (
         ) {
         return (m_Array);
         }

      //! Conversion to old bit-array style for legacy code.      
      operator const UINT8* (
         ) const {
         return (m_Array);
         }

      //! Bitwise AND.
      //! If the bit sets are not the same size the set will be unaltered.
      BITSET_UNOWNED& operator&= (
         const BITSET_UNOWNED& rhs
         );

      //! Bitwise OR.
      //! If the bit sets are not the same size the set will be unaltered.
      BITSET_UNOWNED& operator|= (
         const BITSET_UNOWNED& rhs
         );

      //! Bitwise XOR.
      //! If the bit sets are not the same size the set will be unaltered.
      BITSET_UNOWNED& operator^= (
         const BITSET_UNOWNED& rhs
         );

      //! Assign from old type bit arrays.
      virtual ERRVALUE Assign (
         UINT8 *set,                      //!< Pointer to old bit-array
         UINT32 NumEntries                //!< Number of items in old bit array
         );
         
      //! Initialize iterator with first set or unset item in the bit set.
      //! Returns iterator to first set entry, otherwise the last+1 item if no matching item.
      ITERATOR Begin (
         bool value = true                //!< Value to iterate through
         ) const {
         return (ITERATOR(this, value));
         }

      //! Clear value at specified position.
      void Clear (
         UINT32 posn
         ) {
         if (posn < m_NumEntries) {
            m_Array[posn/8] &= ~(1 << (posn & 7));
            }
         return;
         }

      //! Clear bit array with false.
      //! Makes all the entries in the bit set 'false'.
      void ClearAll (
         ) {
         if (m_ArraySize > 0) memset(m_Array, 0, m_ArraySize);
         return;
         }

      //! Set range of entries to "false".
      void ClearRange (
         UINT32 min,
         UINT32 max
         );

      //! Transfer value from source to dest entry.
      //! Replaces putbit(set, DestPosn, getbit(set, SourcePosn)).
      void CopyBit (
         UINT32 DestPosn,                 //!< where setting goes to
         UINT32 SourcePosn                //!< where setting comes from
         );

      //! Count the values in the set.
      //! Iterates through the set, so should not be used in time-critical code.
      INT32 CountValues (
         bool value = true
         ) const;
         
      //! Initialize iterator with last+1 item in the bit set.
      //! Returns iterator to last+1 item
      ITERATOR End (
         ) const {
         return (ITERATOR(this));
         }

      //! Retrieve value at the requested position, true or false.
      //! Returns 'false' if the position given is outside the range of the BITSET
      bool GetBit (
         UINT32 posn                      //!< position where value is retrieved from
         ) const {
         if (posn >= m_NumEntries) return (false);
         return ((m_Array[posn/8] & (1 << (posn & 7))) != 0);
         }

      //! Return the number of valid entries.
      UINT32 GetNumEntries (           
         ) const {
         return (m_NumEntries);
         }

      //! Get a range of entries that are set continuously in the bitset
      //! @return 'True' if a true range, 'false' if a false range
      bool GetRange (
         UINT32 StartPosn,       //!< Staring position
         UINT32 MaxEnd,          //!< Maximum ending position
         UINT32& EndPosn         //!< Ending position (inclusive) RETURNED
         ) const;

      //! Does bit set have any entries?
      bool HasEntries (
         ) const {
         return (m_NumEntries > 0);
         }

      //! Determine if has multiple entries with specified value.
      bool HasMultiple (
         bool value
         ) const;

      //! Determine if has at least one entry with specified value;
      bool HasValue (
         bool value
         ) const { return (Begin(value) != End()); }

      //! Invert value at specified position.
      void Invert (
         UINT32 posn                      //!< Position to be inverted
         ) {
         if (posn >= m_NumEntries) return;
         m_Array[posn/8] ^= 1 << (posn & 7);
         return;
         }
         
      //! Invert all entries in bit set.
      void InvertAll (
         );
         
      //! Set range of entries to inverse
      void InvertRange (
         UINT32 min,
         UINT32 max
         );

      //! Set a value at the requested position to "true".
      //! Does nothing if the position given is outside range.
      void Set (              
         UINT32 posn                      //!< Position to set
         ) {
         if (posn < m_NumEntries) {
            m_Array[posn/8] |= 1 << (posn & 7);
            }
         return;
         }

      //! Set all entries to true, opposite of ClearAll().
      //! Turn all bit positions to true.
      void SetAll (              
         );

      //! Set a value at the requested position, true or false.
      //! Does nothing if the position given is outside range.
      void SetBit (              
         UINT32 posn,                     //!< Position where value is set
         bool value                       //!< Value to be set at position
         ) {
         if (posn >= m_NumEntries) return;
         if (value) {
            m_Array[posn/8] |= 1 << (posn & 7);
            }
         else {
            m_Array[posn/8] &= ~(1 << (posn & 7));
            }
         return;
         }

      //! Set range of entries to "true".
      void SetRange (
         UINT32 min,
         UINT32 max
         );
         
   private:
      #ifndef GENERATING_DOXYGEN_OUTPUT
      // Disallowed operations.
      const UINT8& operator[](int) const;
      UINT8& operator[](int);
      #endif // GENERATING_DOXYGEN_OUTPUT

   };

//=====================================================================================================================
//! Bit set.
class CLASSLIBEXPORT BITSET : public BITSET_UNOWNED {

   public:

      //! Default constructor.
      BITSET (
         );

      //! Copy constructor.
      BITSET (
         const BITSET& rhs
         );

      //! Construct from BITSET_UNOWNED.
      BITSET (
         const BITSET_UNOWNED& rhs
         );

      //! Constructor to convert old bit-array's into BITSETs.
      BITSET (
         UINT8 *set,                      //!< Old bit array set
         UINT32 NumEntries                //!< Number of items in old bit array, not size in bytes
         );

      //! Destructor.
      virtual ~BITSET (
         );

      //! Assignment from BITSET.
      BITSET& operator= (
         const BITSET& rhs
         );

      //! Assignment from BITSET_UNOWNED.
      BITSET& operator= (
         const BITSET_UNOWNED& rhs
         );

      //! Assign from old type bit arrays.
      virtual ERRVALUE Assign (
         UINT8 *set,                      //!< Pointer to old bit-array
         UINT32 NumEntries                //!< Number of items in old bit array
         );
         
      //! Attach a old bit array to the BITSET
      //!
      //! After passing a buffer to Attach(), the BITSET \b "owns" the
      //! buffer and will free it in its destructor.  
      //! 
      //! @param items Reference to a pointer to the other bit array.
      //! The reason it's a reference is that after recording the pointer,
      //! Attach() will set <i>your</i> pointer to 0.  This will prevent you
      //! from accidently freeing a pointer you no longer own.  If you want
      //! it back, call the Detach() method
      //! 
      void Attach (
         UINT8*& items,                
         int numitems               //!< Number of items in array
         );
         
      //! Detach the buffer from the BITSET
      //! This turns ownership of the buffer over to the caller, who is then
      //! responsibile for seeing that it gets disposed of.
      //! After calling Detach(), the BITSET will behave as if it had
      //! just been constructed.  In other words, it will be a NULL pointer
      //! pointing to 0 items.
      //! This means that if you want to know how many items are in the
      //! array returned, you'd better find out @{before} you call Detach()!
      UINT8* Detach (
         );

      //! Erase BITSET internals, same as calling destructor.
      void Free (
         );

      //! Resize BITSET to a new number of entries.
      ERRVALUE Resize (
         UINT32 NumEntries                //!< Number of elements to resize to
         );
         
      private:
         #ifndef GENERATING_DOXYGEN_OUTPUT
         friend class BITSET_SHARED;
         #endif // GENERATING_DOXYGEN_OUTPUT
   };


//=====================================================================================================================
//! Shared Bit set.
class CLASSLIBEXPORT BITSET_SHARED : public BITSET_UNOWNED {

   private:
      #ifndef GENERATING_DOXYGEN_OUTPUT
      struct BITSET_COUNT {
         mutable UINT32 m_RefCount;
         BITSET m_Bitset;
         BITSET_COUNT () : m_RefCount(1) {}
         BITSET_COUNT (const BITSET_UNOWNED& rhs) : m_RefCount(1), m_Bitset(rhs) {}
         BITSET_COUNT (UINT8 *set, UINT32 NumEntries) : m_RefCount(1), m_Bitset(set, NumEntries) {}
         ERRVALUE Resize (UINT32 NumEntries) {return (m_Bitset.Resize(NumEntries));}
         };

      BITSET_COUNT* m_SharedBitset;
      #endif // GENERATING_DOXYGEN_OUTPUT
      
   public:

      //! Default constructor.
      BITSET_SHARED (
         );

      //! Copy constructor.
      BITSET_SHARED (
         const BITSET_SHARED& rhs
         );

      //! Construct from BITSET_UNOWNED.
      BITSET_SHARED (
         const BITSET_UNOWNED& rhs
         );

      //! Constructor to convert old bit-array's into BITSETs.
      BITSET_SHARED (
         UINT8 *set,                      //!< Old bit array set
         UINT32 NumEntries                //!< Number of items in old bit array, not size in bytes
         );

      //! Destructor.
      virtual ~BITSET_SHARED (
         );

      //! Assignment from BITSET_SHARED.
      BITSET_SHARED& operator= (
         const BITSET_SHARED& rhs
         );

      //! Assignment from BITSET_UNOWNED.
      BITSET_SHARED& operator= (
         const BITSET_UNOWNED& rhs
         );

      //! Assign from old type bit arrays.
      virtual ERRVALUE Assign (
         UINT8 *set,                      //!< Pointer to old bit-array
         UINT32 NumEntries                //!< Number of items in old bit array
         );
         
      //! Attach a old bit array to the BITSET
      //!
      //! After passing a buffer to Attach(), the BITSET @b "owns" the
      //! buffer and will free it in its destructor.  
      //! 
      //! @param items Reference to a pointer to the other bit array.
      //! The reason it's a reference is that after recording the pointer,
      //! Attach() will set <i>your</i> pointer to 0.  This will prevent you
      //! from accidently freeing a pointer you no longer own.  If you want
      //! it back, call the Detach() method
      //! 
      void Attach (
         UINT8*& items,                
         int numitems               //!< Number of items in array
         );
         
      // Detach() method cannot work here!!

      //! Erase BITSET internals, same as calling destructor.
      void Free (
         );

      //! Resize BITSET_SHARED to a new number of entries.
      ERRVALUE Resize (
         UINT32 NumEntries                //!< Number of elements to resize to
         );
         
   private:
      #ifndef GENERATING_DOXYGEN_OUTPUT
      void AttachPointers ();
      void DecrementCount ();
      #endif // GENERATING_DOXYGEN_OUTPUT
         
   };

//=====================================================================================================================

#undef   CLASSLIBEXPORT

#endif      // INC_MI32_BITSET_H

---