home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 15 / CDACTUAL15.iso / cdactual / program / c / WLIB.ZIP / WBITS.H < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-07  |  10.0 KB  |  249 lines
  1. #ifndef WBitsIncluded
  2. #define WBitsIncluded
  3.  
  4. // copyright (c) 1992, 1993 by Paul Wheaton
  5. // 1916 Brooks #205, Missoula, MT  59801
  6. //
  7. // voice phone:  (406)543-7543
  8. // modem phone:  (406)543-1144 (2400N81)
  9. //  CompuServe:  72707,207
  10. //    Internet:  72707.207@CompuServe.com
  11.  
  12. #include <stdlib.h>
  13. #include <WStr.h>
  14. #include <WVec.h>
  15.  
  16. // for access by BitVector only
  17. class BitRef
  18.   {
  19.       Byte huge* P;  // pointer to byte containing bit
  20.       Byte M;   // mask for bit
  21.       BitRef(Byte huge* BP, long BitOffset); // non-inlined due to 16M stuff
  22.       friend BitVector;
  23.     public:
  24.       #ifdef BorlandFixedByteMath
  25.         operator Bool()         { return ((*P & M) != 0); }
  26.         Bool operator=(Bool b)
  27.           {
  28.             if (b) *P |= M;
  29.             else *P &= ~M;
  30.             return b;
  31.           }
  32.         void operator&=(Bool b) { if (!b) *P &= ~M; }
  33.         void operator|=(Bool b) { if (b) *P |= M; }
  34.         void operator^=(Bool b) { if (b) *P ^= M; }
  35.       #else
  36.         operator Bool()         { return ((int(*P) & int(M)) != 0); }
  37.         Bool operator=(Bool b);
  38.         void operator&=(Bool b);
  39.         void operator|=(Bool b);
  40.         void operator^=(Bool b);
  41.       #endif
  42.       #ifdef MAJORBBS
  43.         void* operator new(size_t size){return malloc(size);}
  44.         void  operator delete(void* p) {free(p);}
  45.       #endif
  46.   };
  47.  
  48. class BitVector : public ByteVector
  49.   {
  50.       long BitLen; // the number of bits used
  51.       void CtorsHelper(const long* LP,long Length);
  52.     public:
  53.       //  see the notes on the constructors at the end of this file
  54.       BitVector();
  55.       BitVector(long);
  56.       BitVector(long,long);
  57.       BitVector(long,long,long);
  58.       BitVector(long,long,long,long);
  59.       BitVector(long,long,long,long,long);
  60.       BitVector(long,long,long,long,long,long);
  61.       BitVector(long,long,long,long,long,long,long);
  62.       BitVector(long,long,long,long,long,long,long,long);
  63.       BitVector(long,long,long,long,long,long,long,long,long);
  64.       BitVector(const Byte* B, long Len); // direct copy
  65.       BitVector(const BitVector&);
  66.       BitRef Ref(long Index);
  67.       BitRef operator[](long Index);
  68.         /* used for setting or retrieving bit elements.  Accessing beyond the
  69.            last bit will make this vector longer. */
  70.       Bool operator()(long Index) const {return At(Index);}
  71.         /* used for reading bits only.  Accessing beyond the last bit will
  72.            return a 0 (False).  This is much faster than [] */
  73.       Bool At(long Index) const;
  74.       BitVector operator()(long Index,long Len) const {return At(Index,Len);}
  75.         // for a subset
  76.       BitVector At(long Index, long Len) const;
  77.       BitVector Before(long Index) const {return At(0,Index);}
  78.       BitVector Through(long Index) const {return At(0,Index+1);}
  79.       BitVector From(long Index) const;
  80.       BitVector After(long Index) const;
  81.       void Toggle(long Index){Ref(Index)=!At(Index);}
  82.       void operator=(const BitVector&);
  83.       BitVector operator!() const;
  84.       BitVector operator&(const BitVector&) const;
  85.       BitVector operator^(const BitVector&) const;
  86.       BitVector operator|(const BitVector&) const;
  87.       void operator&=(const BitVector&);
  88.       void operator^=(const BitVector&);
  89.       void operator|=(const BitVector&);
  90.       void ReAlloc(long NewCapacity);
  91.       long Size() const {return BitLen;}
  92.       long ByteSize() const {return Len;}
  93.       void ClearRange(long Index1,long Index2);
  94.       void SetRange(long Index1,long Index2,Bool X=On);
  95.       operator String() const;
  96.   };
  97.  
  98. inline long BytesNeeded(long NumBits) {return(((NumBits-1)/8)+1);}
  99.  
  100. /*
  101.  
  102. BitVector constructors:
  103.  
  104.   I wanted to use a variable argument constructor (see your favorite texts
  105.   on "elipsis", "...", "variable arguments" or "va_arg, va_end and
  106.   va_start") but there were limitations that I felt could lead to very hard
  107.   to find bugs, namely that the applications programmer must first pass a
  108.   value that reveals how many parameters there are.  Being off by one could
  109.   lead to a variety of problems.
  110.  
  111.   There are four ways to construct a BitVector:
  112.  
  113.     1) BitVector BV;
  114.  
  115.        This creates a vector that will have a length of 0 although some
  116.        memory will be allocated so that elements may be added later (which
  117.        is the most likely thing to happen).
  118.  
  119.     2) BitVector BV(1,2,55,8);
  120.  
  121.        This creates a bit vector of length 56 (7 bytes long minimum).  All
  122.        of the bits are 0 (False) except for bits 1, 2, 55 and 8 which are 1
  123.        (True).  You may pass 1 to 9 parameters using this type of
  124.        constructors.  You're limited to 9 because the Glock C++ name
  125.        mangling mixed with MSC 5.1 limits it this way (xxx).  An update of
  126.        either of these may solve this problem.
  127.  
  128.     3) static Byte BA[]={1,2,55,8};
  129.        BitVector BV(BA,4);
  130.  
  131.        This creates a vector of length 4, copying the elements from BA.
  132.        You don't have to copy from an array of bytes, you can use any kind
  133.        of array or even a pointer to anywhere in memory.
  134.  
  135.     4) BitVector BV2(BV);
  136.  
  137.        Create a BitVector from another BitVector.
  138.  
  139. */
  140. // for access by BitSets only
  141. class BitSetRef
  142.   {
  143.       Byte* P;  // pointer to byte containing bit
  144.       Byte M;   // mask for bit
  145.     public:
  146.       BitSetRef(Byte* BP, int BitOffset);
  147.       #ifdef BorlandFixedByteMath
  148.         operator Bool() { return ((*P & M) != 0); }
  149.         void operator&=(Bool b) { if (!b) *P &= ~M; }
  150.         void operator|=(Bool b) { if (b) *P |= M; }
  151.         void operator^=(Bool b) { if (b) *P ^= M; }
  152.       #else
  153.         operator Bool() { return ((int(*P) & int(M)) != 0); }
  154.         void operator&=(Bool b);
  155.         void operator|=(Bool b);
  156.         void operator^=(Bool b);
  157.       #endif
  158.       Bool operator=(Bool b);
  159.       #ifdef MAJORBBS
  160.         void* operator new(size_t size){return malloc(size);}
  161.         void  operator delete(void* p) {free(p);}
  162.       #endif
  163.   };
  164.  
  165. void ClearBitRange(void* P, long Index1,long Index2);
  166. void SetBitRange(void* P, long Index1,long Index2,Bool X=On);
  167. void QSB(Byte*P, int Index, Bool X=On); // Quick Set Bit for BitSet classes
  168.  
  169. #define CreateBitSetClass(ClassName,BitQuan)                                  \
  170. class ClassName                                                               \
  171.   {                                                                           \
  172.       Byte B[(BitQuan+7)/8];                                                  \
  173.     public:                                                                   \
  174.       ClassName(){memset(&B[0],0,(BitQuan+7)/8);}                             \
  175.       ClassName(const ClassName& BS){memcpy(&B[0],&(BS.B[0]),(BitQuan+7)/8);} \
  176.       ClassName(int I){memset(&B[0],0,(BitQuan+7)/8); Ref(I)=On;}             \
  177.       ClassName(int I1, int I2){memset(&B[0],0,(BitQuan+7)/8);                \
  178.         Ref(I1)=On; Ref(I2)=On;}                                              \
  179.       ClassName(int I1, int I2, int I3){memset(&B[0],0,(BitQuan+7)/8);        \
  180.         QSB(B,I1); QSB(B,I2); QSB(B,I3);}                                     \
  181.       ClassName(int I1, int I2, int I3, int I4){memset(&B[0],0,(BitQuan+7)/8);\
  182.         QSB(B,I1); QSB(B,I2); QSB(B,I3); QSB(B,I4);}                          \
  183.       ClassName(int I1,int I2,int I3,int I4,int I5)                           \
  184.         {memset(&B[0],0,(BitQuan+7)/8); QSB(B,I1); QSB(B,I2); QSB(B,I3);      \
  185.          QSB(B,I4); QSB(B,I5);}                                               \
  186.       ClassName(int I1,int I2,int I3,int I4,int I5,int I6)                    \
  187.         {memset(&B[0],0,(BitQuan+7)/8); QSB(B,I1); QSB(B,I2); QSB(B,I3);      \
  188.          QSB(B,I4); QSB(B,I5); QSB(B,I6);}                                    \
  189.       ClassName(int I1,int I2,int I3,int I4,int I5,int I6,int I7)             \
  190.         {memset(&B[0],0,(BitQuan+7)/8); QSB(B,I1); QSB(B,I2); QSB(B,I3);      \
  191.          QSB(B,I4); QSB(B,I5); QSB(B,I6); QSB(B,I7);}                         \
  192.       BitSetRef Ref(int Index) {return BitSetRef(&B[0],Index);}               \
  193.       BitSetRef operator[](int Index){return BitSetRef(&B[0],Index);}         \
  194.       Bool At(int Index){return ((B[Index/8] & (1<<(Index%8)) )!=0);}         \
  195.       Bool operator()(int Index)                                              \
  196.         {return ((B[Index/8] & (1<<(Index%8)) )!=0);}                         \
  197.       void Toggle(int Index){Ref(Index)=!At(Index);}                          \
  198.       void SetRange(int Index1, int Index2, Bool OnOrOff=On)                  \
  199.         {SetBitRange(&B[0],Index1,Index2,OnOrOff);}                           \
  200.       void ClearRange(int Index1, int Index2)                                 \
  201.         {ClearBitRange(&B[0],Index1,Index2);}                                 \
  202.       void SetAll(Bool OnOrOff=On) {SetBitRange(&B[0],0,BitQuan-1,OnOrOff);}  \
  203.       void ClearAll() {ClearBitRange(&B[0],0,BitQuan-1);}                     \
  204.       long& L(){return *((long*)&B[0]);}                                      \
  205.       int&  I(){return *((int*)&B[0]);}                                       \
  206.       char& C(){return *((char*)&B[0]);}                                      \
  207.       void* operator new(size_t size){return malloc(size);}                   \
  208.       void  operator delete(void* p) {free(p);}                               \
  209.   };
  210.  
  211. CreateBitSetClass(BitSet8,8);
  212. CreateBitSetClass(BitSet16,16);
  213. CreateBitSetClass(BitSet32,32);
  214.  
  215. #define Bit0 1
  216. #define Bit1 2
  217. #define Bit2 4
  218. #define Bit3 8
  219. #define Bit4 16
  220. #define Bit5 32
  221. #define Bit6 64
  222. #define Bit7 128
  223. #define Bit8 256
  224. #define Bit9 512
  225. #define Bit10 1024
  226. #define Bit11 2048
  227. #define Bit12 4096
  228. #define Bit13 8192
  229. #define Bit14 16384
  230. #define Bit15 32768
  231. #define Bit16 65536
  232. #define Bit17 131072
  233. #define Bit18 262144
  234. #define Bit19 524288
  235. #define Bit20 1048576
  236. #define Bit21 2097152
  237. #define Bit22 4194304
  238. #define Bit23 8388608
  239. #define Bit24 16777216
  240. #define Bit25 33554432
  241. #define Bit26 67108864
  242. #define Bit27 134217728
  243. #define Bit28 268435456
  244. #define Bit29 536870912
  245. #define Bit30 1073741824
  246. #define Bit31 2147483648
  247.  
  248. #endif
  249.