home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_12_01 / allison / bits.h < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-07  |  9.5 KB  |  463 lines
  1. // bits.h
  2.  
  3. #include <iostream.h>
  4. #include <stddef.h>
  5. #include <limits.h>
  6. #include <assert.h>
  7. #include "string.hpp"
  8.  
  9. template<size_t N>
  10. class bits
  11. {
  12.     // Global I/O funtions
  13.     friend ostream& operator<<(ostream& os, const bits<N>& rhs)
  14.       {os << rhs.to_string(); return os;}
  15.     friend istream& operator>>(istream& is, bits<N>& rhs)
  16.       {rhs.read(is); return is;}
  17.  
  18.     // Global bitwise operators
  19.     friend bits<N> operator&(const bits<N>& b1,const bits<N>& 
  20. b2)
  21.       {bits<N> r(b1); return r &= b2;}
  22.     friend bits<N> operator|(const bits<N>& b1,const bits<N>& 
  23. b2)
  24.       {bits<N> r(b1); return r |= b2;}
  25.     friend bits<N> operator^(const bits<N>& b1,const bits<N>& 
  26. b2)
  27.       {bits<N> r(b1); return r ^= b2;}
  28.  
  29. public:
  30.     // Constructors
  31.     bits();
  32.     bits(unsigned long n);
  33.     bits(const bits<N>& b);
  34.     bits(const string& s);
  35.  
  36.     // Conversions
  37.     unsigned short to_ushort() const;
  38.     unsigned long to_ulong() const;
  39.     string to_string() const;
  40.  
  41.     // Assignment
  42.     bits<N>& operator=(const bits<N>& rhs);
  43.  
  44.     // Equality
  45.     int operator==(const bits<N>& rhs) const;
  46.     int operator!=(const bits<N>& rhs) const;
  47.  
  48.     // Basic bit operations
  49.     bits<N>& set(size_t pos, int val = 1);
  50.     bits<N>& set();
  51.     bits<N>& reset(size_t pos);
  52.     bits<N>& reset();
  53.     bits<N>& toggle(size_t pos);
  54.     bits<N>& toggle();
  55.     bits<N> operator~() const;
  56.     int test(size_t n) const;
  57.     int any() const;
  58.     int none() const;
  59.  
  60.     // Bit-wise operators
  61.  
  62.     bits<N>& operator&=(const bits<N>& rhs);
  63.     bits<N>& operator|=(const bits<N>& rhs);
  64.     bits<N>& operator^=(const bits<N>& rhs);
  65.  
  66.     // Shift operators
  67.     bits<N>& operator<<=(size_t n);
  68.     bits<N>& operator>>=(size_t n);
  69.     bits<N> operator<<(size_t n) const;
  70.     bits<N> operator>>(size_t n) const;
  71.  
  72.     size_t count() const;
  73.     size_t length() const;
  74.  
  75. private:
  76.     typedef unsigned int Block;
  77.     enum {BLKSIZ = CHAR_BIT * sizeof (Block)};
  78.     enum {nblks_ = (N+BLKSIZ-1) / BLKSIZ};
  79.  
  80.     Block bits_[nblks_];
  81.  
  82.     static size_t word(size_t pos)
  83.       {return nblks_ - 1 - pos/BLKSIZ;}
  84.     static size_t offset(size_t pos)
  85.       {return pos % BLKSIZ;}
  86.     static Block mask1(size_t pos)
  87.       {return Block(1) << offset(pos);}
  88.     static Block mask0(size_t pos)
  89.       {return ~(Block(1) << offset(pos));}
  90.  
  91.     void cleanup();
  92.     void set_(size_t pos);
  93.     int set_(size_t pos, int val);
  94.     void reset_(size_t pos);
  95.     int test_(size_t pos) const;
  96.     void from_string(const string& s);
  97.     void read(istream& is);
  98.     int any(size_t start_pos) const;
  99.     unsigned long to(size_t) const;
  100. };
  101.  
  102. template<size_t N>
  103. inline bits<N>::bits()
  104. {
  105.     reset();
  106. }
  107.  
  108. template<size_t N>
  109. bits<N>::bits(const string& s)
  110. {
  111.     // Validate that s has only 0's and 1's
  112.     for (int i = 0; i < s.length(); ++i)
  113.     {
  114.         char c = s.get_at(i);
  115.         if (c != '0' &&  c != '1')
  116.             break;
  117.     }
  118.     assert(i == s.length());
  119.  
  120.     from_string(s);
  121. }
  122.  
  123. template<size_t N>
  124. inline bits<N>::bits(const bits<N>& b)
  125. {
  126.     memcpy(bits_,b.bits_,nblks_*sizeof(bits_[0]));
  127. }
  128.  
  129. template<size_t N>
  130. bits<N>::bits(unsigned long n)
  131. {
  132.     // Don't drop any bits
  133.     if (N < CHAR_BIT * sizeof(unsigned long))
  134.         assert((n >> N) == 0);
  135.     reset();
  136.  
  137.     size_t nblks = sizeof (unsigned long) / sizeof (Block);
  138.     if (nblks > 1)
  139.         for (int i = 0; i < nblks; ++i)
  140.         {
  141.             bits_[nblks_ - 1 - i] = Block(n);
  142.             n >>= BLKSIZ;
  143.         }
  144.     else
  145.         bits_[nblks_ - 1] = Block(n);
  146. }
  147.  
  148. template<size_t N>
  149. unsigned short bits<N>::to_ushort() const
  150. {
  151.     size_t limit = sizeof(unsigned short) * CHAR_BIT;
  152.     assert(!(length() > limit && any(limit)));
  153.     size_t nblks = sizeof(unsigned short) / sizeof(Block);
  154.     return (unsigned short) to(nblks);
  155. }
  156. template<size_t N>
  157. unsigned long bits<N>::to_ulong() const
  158. {
  159.     size_t limit = sizeof(unsigned long) * CHAR_BIT;
  160.     assert(!(length() > limit && any(limit)));
  161.     size_t nblks = sizeof(unsigned long) / sizeof(Block);
  162.     return to(nblks);
  163. }
  164.  
  165. template<size_t N>
  166. string bits<N>::to_string() const
  167. {
  168.     char *s = new char[N+1];
  169.     for (int i = 0; i < N; ++i)
  170.         s[i] = '0' + test_(N-1-i);
  171.     s[N] = '\0';
  172.     string s2(s);
  173.     delete [] s;
  174.     return s2;
  175. }
  176.  
  177. template<size_t N>
  178. bits<N>& bits<N>::operator=(const bits<N>& b)
  179. {
  180.     if (this != &b)
  181.         memcpy(bits_,b.bits_, nblks_ * sizeof(bits_[0]));
  182.     return *this;
  183. }
  184.  
  185. template<size_t N>
  186. inline int bits<N>::operator==(const bits<N>& b) const
  187. {
  188.     return !memcmp(bits_,b.bits_,nblks_ * sizeof(bits_[0]));
  189. }
  190.  
  191. template<size_t N>
  192. inline int bits<N>::operator!=(const bits<N>& b) const
  193. {
  194.     return !operator==(b);
  195. }
  196.  
  197. template<size_t N>
  198. inline bits<N>& bits<N>::set(size_t pos, int val)
  199. {
  200.     assert(pos < N);
  201.     (void) set_(pos,val);
  202.     return *this;
  203. }
  204.  
  205. template<size_t N>
  206. inline bits<N>& bits<N>::set()
  207. {
  208.     memset(bits_,~0u,nblks_ * sizeof bits_[0]);
  209.     cleanup();
  210.     return *this;
  211. }
  212.  
  213. template<size_t N>
  214. inline bits<N>& bits<N>::reset(size_t pos)
  215. {
  216.     assert(pos < N);
  217.     reset_(pos);
  218.     return *this;
  219. }
  220.  
  221. template<size_t N>
  222. inline bits<N>& bits<N>::reset()
  223. {
  224.     memset(bits_,0,nblks_ * sizeof bits_[0]);
  225.     return *this;
  226. }
  227.  
  228. template<size_t N>
  229. inline bits<N>& bits<N>::toggle(size_t pos)
  230. {
  231.     assert(pos < N);
  232.     bits_[word(pos)] ^= mask1(pos);
  233.     return *this;
  234. }
  235.  
  236. template<size_t N>
  237. bits<N>& bits<N>::toggle()
  238. {
  239.     size_t nw = nblks_;
  240.     while (nw--)
  241.  
  242.         bits_[nw] = ~bits_[nw];
  243.     cleanup();
  244.     return *this;
  245. }
  246.  
  247. template<size_t N>
  248. inline bits<N> bits<N>::operator~() const
  249. {
  250.     bits<N> b(*this);
  251.     b.toggle();
  252.     return b;
  253. }
  254.  
  255. template<size_t N>
  256. inline int bits<N>::test(size_t pos) const
  257. {
  258.     assert(pos < N);
  259.     return test_(pos);
  260. }
  261.  
  262. template<size_t N>
  263. int bits<N>::any() const
  264. {
  265.     for (int i = 0; i < nblks_; ++i)
  266.         if (bits_[i])
  267.             return 1;
  268.     return 0;
  269. }
  270.  
  271. template<size_t N>
  272. inline int bits<N>::none() const
  273. {
  274.     return !any();
  275. }
  276.  
  277. template<size_t N>
  278. bits<N>& bits<N>::operator&=(const bits<N>& rhs)
  279. {
  280.     for (int i = 0; i < nblks_; ++i)
  281.         bits_[i] &= rhs.bits_[i];
  282.     return *this;
  283. }
  284.  
  285. template<size_t N>
  286. bits<N>& bits<N>::operator|=(const bits<N>& rhs)
  287. {
  288.     for (int i = 0; i < nblks_; ++i)
  289.         bits_[i] |= rhs.bits_[i];
  290.     return *this;
  291. }
  292.  
  293. template<size_t N>
  294. bits<N>& bits<N>::operator^=(const bits<N>& rhs)
  295. {
  296.     for (int i = 0; i < nblks_; ++i)
  297.         bits_[i] ^= rhs.bits_[i];
  298.     return *this;
  299. }
  300.  
  301. template<size_t N>
  302.  
  303. bits<N>& bits<N>::operator>>=(size_t n)
  304. {
  305.     if (n > N)
  306.         n = N;
  307.     for (int i = 0; i < N-n; ++i)
  308.         (void) set_(i,test_(i+n));
  309.     for (i = N-n; i < N; ++i)
  310.         reset_(i);
  311.     return *this;
  312. }
  313.  
  314. template<size_t N>
  315. bits<N>& bits<N>::operator<<=(size_t n)
  316. {
  317.     if (n > N)
  318.         n = N;
  319.     for (int i = N-1; i >= n; --i)
  320.         (void) set_(i,test(i-n));
  321.     for (i = 0; i < n; ++i)
  322.         reset_(i);
  323.     return *this;
  324. }
  325.  
  326. template<size_t N>
  327. inline bits<N> bits<N>::operator>>(size_t n) const
  328. {
  329.     bits r(*this);
  330.     return r >>= n;
  331. }
  332.  
  333. template<size_t N>
  334. inline bits<N> bits<N>::operator<<(size_t n) const
  335. {
  336.     bits r(*this);
  337.     return r <<= n;
  338. }
  339.  
  340. template<size_t N>
  341. size_t bits<N>::count() const
  342. {
  343.     size_t sum = 0;
  344.     for (int i = 0; i < N; ++i)
  345.         if (test_(i))
  346.             ++sum;
  347.     return sum;
  348. }
  349.  
  350. template<size_t N>
  351. inline size_t bits<N>::length() const
  352. {
  353.     return N;
  354. }
  355.  
  356. // Private functions
  357. template<size_t N>
  358. inline void bits<N>::set_(size_t pos)
  359. {
  360.     bits_[word(pos)] |= mask1(pos);
  361. }
  362.  
  363.  
  364. template<size_t N>
  365. int bits<N>::set_(size_t pos, int val)
  366. {
  367.     if (val)
  368.         set_(pos);
  369.     else
  370.         reset_(pos);
  371.     return !!val;
  372. }
  373.  
  374. template<size_t N>
  375. inline void bits<N>::reset_(size_t pos)
  376. {
  377.     bits_[word(pos)] &= mask0(pos);
  378. }
  379.  
  380. template<size_t N>
  381. inline int bits<N>::test_(size_t pos) const
  382. {
  383.     return !!(bits_[word(pos)] & mask1(pos));
  384. }
  385.  
  386. template<size_t N>
  387. inline void bits<N>::cleanup()
  388. {
  389.     // Make sure unused bits don't get set
  390.     bits_[0] &= (~Block(0) >> (nblks_ * BLKSIZ - N));
  391. }
  392.  
  393. template<size_t N>
  394. void bits<N>::from_string(const string& s)
  395. {
  396.     // Assumes s contains only 0's and 1's
  397.     size_t slen = s.length();
  398.     reset();
  399.     for (int i = slen-1; i >= 0; --i)
  400.         if (s.get_at(i) == '1')set_(slen-i-1);
  401. }
  402.  
  403. template<size_t N>
  404. void bits<N>::read(istream& is)
  405. {
  406.     char *buf = new char[N];
  407.     char c;
  408.  
  409.     is >> ws;
  410.     for (int i = 0; i < N; ++i)
  411.     {
  412.         is.get(c);
  413.         if (c == '0' || c == '1')
  414.             buf[i] = c;
  415.         else
  416.         {
  417.             is.putback(c);
  418.             buf[i] = '\0';
  419.             break;
  420.         }
  421.     }
  422.  
  423.  
  424.     if (i == 0)
  425.         is.clear(ios::failbit);
  426.     else
  427.         from_string(string(buf));
  428.  
  429.     delete buf;
  430. }
  431.  
  432. template<size_t N>
  433. int bits<N>::any(size_t start) const
  434. {
  435.     // See if any bit past start (inclusive) is set
  436.     for (int i = start; i < N; ++i)
  437.         if (test_(i))
  438.             return 1;
  439.     return 0;
  440. }
  441.  
  442. template<size_t N>
  443. unsigned long bits<N>::to(size_t nblks) const
  444. {
  445.     if (nblks > 1)
  446.     {
  447.         int i;
  448.         unsigned long n = bits_[nblks_ - nblks];
  449.  
  450.         /* Collect low-order sub-blocks into an unsigned */
  451.         if (nblks > nblks_)
  452.             nblks = nblks_;
  453.         while (--nblks)
  454.             n = (n << BLKSIZ) | bits_[nblks_ - nblks];
  455.         return n;
  456.     }
  457.     else
  458.         return (unsigned long) bits_[nblks_ - 1];
  459. }
  460.  
  461. /* End of File */ 
  462.  
  463.