home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / libg++-2.7.1-bin.lha / lib / g++-include / BitSet.h < prev    next >
C/C++ Source or Header  |  1996-10-12  |  9KB  |  371 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17. */
  18.  
  19. #ifndef _BitSet_h
  20. #ifdef __GNUG__
  21. #pragma interface
  22. #endif
  23.  
  24. #define _BitSet_h 1
  25.  
  26. #include <iostream.h>
  27. #include <limits.h>
  28. #include <bitprims.h>
  29.  
  30. #undef OK
  31.  
  32. #define BITSETBITS  (sizeof(_BS_word) * CHAR_BIT)
  33.  
  34. struct BitSetRep
  35. {
  36.   unsigned short len;       // number of _BS_word in s
  37.   unsigned short sz;        // allocated slots
  38.   unsigned short virt;      // virtual 0 or 1
  39.   _BS_word  s[1];         // bits start here
  40. };
  41.  
  42. extern BitSetRep*   BitSetalloc(BitSetRep*, const _BS_word*, 
  43.                                 int, int, int);
  44. extern BitSetRep*   BitSetcopy(BitSetRep*, const BitSetRep*);
  45. extern BitSetRep*   BitSetresize(BitSetRep*, int);
  46. extern BitSetRep*   BitSetop(const BitSetRep*, const BitSetRep*, 
  47.                              BitSetRep*, char);
  48. extern BitSetRep*   BitSetcmpl(const BitSetRep*, BitSetRep*);
  49.  
  50.  
  51. extern BitSetRep    _nilBitSetRep;
  52.  
  53. class BitSet;
  54.  
  55. class BitSetBit
  56. {
  57. protected:
  58.   BitSet*            src;
  59.   unsigned long      pos;
  60.  
  61.  public:
  62.                      BitSetBit(BitSet* v, int p);
  63.                      BitSetBit(const BitSetBit& b);
  64.                     ~BitSetBit();
  65.                      operator int() const;
  66.   int                operator = (int b);
  67.   int                operator = (const BitSetBit& b);
  68. };
  69.  
  70. class BitSet
  71. {
  72. protected:
  73.   BitSetRep*          rep;
  74.  
  75.   
  76. public:
  77.  
  78. // constructors
  79.                      BitSet();
  80.                      BitSet(const BitSet&);
  81.  
  82.                     ~BitSet();
  83.  
  84.   BitSet&            operator =  (const BitSet& y);
  85.  
  86. // equality & subset tests
  87.  
  88.   friend int         operator == (const BitSet& x, const BitSet& y);
  89.   friend int         operator != (const BitSet& x, const BitSet& y);
  90.   friend int         operator <  (const BitSet& x, const BitSet& y);
  91.   friend int         operator <= (const BitSet& x, const BitSet& y);
  92.   friend int         operator >  (const BitSet& x, const BitSet& y);
  93.   friend int         operator >= (const BitSet& x, const BitSet& y);
  94.   friend int           lcompare(const BitSet& x, const BitSet& y);
  95.  
  96.  
  97. // operations on self
  98.  
  99.   BitSet&            operator |= (const BitSet& y);
  100.   BitSet&            operator &= (const BitSet& y);
  101.   BitSet&            operator -= (const BitSet& y);
  102.   BitSet&            operator ^= (const BitSet& y);
  103.  
  104.   void               complement();
  105.  
  106. // individual bit manipulation
  107.  
  108.   void               set(int pos);
  109.   void               set(int from, int to);
  110.   void               set(); // set all
  111.  
  112.   void               clear(int pos);
  113.   void               clear(int from, int to);
  114.   void               clear(); // clear all
  115.  
  116.   void               invert(int pos);
  117.   void               invert(int from, int to);
  118.  
  119.   int                test(int pos) const;
  120.   int                test(int from, int to) const;
  121.  
  122.   BitSetBit          operator [] (int i);
  123.   
  124. // iterators
  125.  
  126.   int                first(int b = 1) const;
  127.   int                last(int b = 1) const;
  128.  
  129.   int                next(int pos, int b = 1) const;
  130.   int                prev(int pos, int b = 1) const;
  131.   int                previous(int pos, int b = 1) const /* Obsolete synonym */
  132.     { return prev(pos, b); }
  133.  
  134. // status
  135.  
  136.   int                empty() const;
  137.   int                virtual_bit() const;
  138.   int                count(int b = 1) const;
  139.   
  140. // convertors & IO
  141.  
  142.   friend BitSet      atoBitSet(const char* s, 
  143.                                char f='0', char t='1', char star='*');
  144.   // BitSettoa is deprecated; do not use in new programs.
  145.   friend const char* BitSettoa(const BitSet& x, 
  146.                                char f='0', char t='1', char star='*');
  147.  
  148.   friend BitSet      shorttoBitSet(unsigned short w);
  149.   friend BitSet      longtoBitSet(unsigned long w);
  150.  
  151.   friend ostream&    operator << (ostream& s, const BitSet& x);
  152.   void             printon(ostream& s,
  153.                  char f='0', char t='1', char star='*') const;
  154.  
  155. // procedural versions of operators
  156.  
  157.   friend void        and(const BitSet& x, const BitSet& y, BitSet& r);
  158.   friend void        or(const BitSet& x, const BitSet& y, BitSet& r);
  159.   friend void        xor(const BitSet& x, const BitSet& y, BitSet& r);
  160.   friend void        diff(const BitSet& x, const BitSet& y, BitSet& r);
  161.   friend void        complement(const BitSet& x, BitSet& r);
  162.  
  163. // misc
  164.  
  165.   void      error(const char* msg) const;
  166.   int                OK() const;
  167. };
  168.  
  169.  
  170. typedef BitSet BitSetTmp;
  171.  
  172. // These are inlined regardless of optimization
  173.  
  174. inline int BitSet_index(int l)
  175. {
  176.   return (unsigned)(l) / BITSETBITS;
  177. }
  178.  
  179. inline int BitSet_pos(int l)
  180. {
  181.   return l & (BITSETBITS - 1);
  182. }
  183.  
  184.  
  185. inline BitSet::BitSet() : rep(&_nilBitSetRep) {}
  186.  
  187. inline BitSet::BitSet(const BitSet& x) :rep(BitSetcopy(0, x.rep)) {}
  188.  
  189. inline BitSet::~BitSet() { if (rep != &_nilBitSetRep) delete rep; }
  190.  
  191. inline BitSet& BitSet::operator =  (const BitSet& y)
  192. { 
  193.   rep = BitSetcopy(rep, y.rep);
  194.   return *this;
  195. }
  196.  
  197. inline int operator != (const BitSet& x, const BitSet& y) { return !(x == y); }
  198.  
  199. inline int operator >  (const BitSet& x, const BitSet& y) { return y < x; }
  200.  
  201. inline int operator >= (const BitSet& x, const BitSet& y) { return y <= x; }
  202.  
  203. inline void and(const BitSet& x, const BitSet& y, BitSet& r)
  204. {
  205.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '&');
  206. }
  207.  
  208. inline void or(const BitSet& x, const BitSet& y, BitSet& r)
  209. {
  210.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '|');
  211. }
  212.  
  213. inline void xor(const BitSet& x, const BitSet& y, BitSet& r)
  214. {
  215.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '^');
  216. }
  217.  
  218. inline void diff(const BitSet& x, const BitSet& y, BitSet& r)
  219. {
  220.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '-');
  221. }
  222.  
  223. inline void complement(const BitSet& x, BitSet& r)
  224. {
  225.   r.rep = BitSetcmpl(x.rep, r.rep);
  226. }
  227.  
  228. #if defined(__GNUG__) && !defined(_G_NO_NRV)
  229.  
  230. inline BitSet operator & (const BitSet& x, const BitSet& y) return r
  231. {
  232.   and(x, y, r);
  233. }
  234.  
  235. inline BitSet operator | (const BitSet& x, const BitSet& y) return r
  236. {
  237.   or(x, y, r);
  238. }
  239.  
  240. inline BitSet operator ^ (const BitSet& x, const BitSet& y) return r
  241. {
  242.   xor(x, y, r);
  243. }
  244.  
  245. inline BitSet operator - (const BitSet& x, const BitSet& y) return r
  246. {
  247.   diff(x, y, r);
  248. }
  249.  
  250. inline BitSet operator ~ (const BitSet& x) return r
  251. {
  252.   ::complement(x, r);
  253. }
  254.  
  255. #else /* NO_NRV */
  256.  
  257. inline BitSet operator & (const BitSet& x, const BitSet& y) 
  258. {
  259.   BitSet r; and(x, y, r); return r;
  260. }
  261.  
  262. inline BitSet operator | (const BitSet& x, const BitSet& y) 
  263. {
  264.   BitSet r; or(x, y, r); return r;
  265. }
  266.  
  267. inline BitSet operator ^ (const BitSet& x, const BitSet& y) 
  268. {
  269.   BitSet r; xor(x, y, r); return r;
  270. }
  271.  
  272. inline BitSet operator - (const BitSet& x, const BitSet& y) 
  273. {
  274.   BitSet r; diff(x, y, r); return r;
  275. }
  276.  
  277. inline BitSet operator ~ (const BitSet& x) 
  278. {
  279.   BitSet r; ::complement(x, r); return r;
  280. }
  281.  
  282. #endif
  283.  
  284. inline BitSet& BitSet::operator &= (const BitSet& y)
  285. {
  286.   and(*this, y, *this);
  287.   return *this;
  288. }
  289.  
  290. inline BitSet& BitSet::operator |= (const BitSet& y)
  291. {
  292.   or(*this, y, *this);
  293.   return *this;
  294. }
  295.  
  296. inline BitSet& BitSet::operator ^= (const BitSet& y)
  297. {
  298.   xor(*this, y, *this);
  299.   return *this;
  300. }
  301.  
  302. inline BitSet& BitSet::operator -= (const BitSet& y)
  303. {
  304.   diff(*this, y, *this);
  305.   return *this;
  306. }
  307.  
  308.  
  309. inline void BitSet::complement()
  310. {
  311.   ::complement(*this, *this);
  312. }
  313.  
  314. inline int BitSet::virtual_bit() const
  315. {
  316.   return rep->virt;
  317. }
  318.  
  319. inline int BitSet::first(int b) const
  320. {
  321.   return next(-1, b);
  322. }
  323.  
  324. inline int BitSet::test(int p) const
  325. {
  326.   if (p < 0) error("Illegal bit index");
  327.   int index = BitSet_index(p);
  328.   return (index >= rep->len)? rep->virt : 
  329.          ((rep->s[index] & (1 << BitSet_pos(p))) != 0);
  330. }
  331.  
  332.  
  333. inline void BitSet::set()
  334. {
  335.   rep = BitSetalloc(rep, 0, 0, 1, 0);
  336. }
  337.  
  338. inline BitSetBit::BitSetBit(const BitSetBit& b) :src(b.src), pos(b.pos) {}
  339.  
  340. inline BitSetBit::BitSetBit(BitSet* v, int p)
  341. {
  342.   src = v;  pos = p;
  343. }
  344.  
  345. inline BitSetBit::~BitSetBit() {}
  346.  
  347. inline BitSetBit::operator int() const
  348. {
  349.   return src->test(pos);
  350. }
  351.  
  352. inline int BitSetBit::operator = (int b)
  353. {
  354.   if (b) src->set(pos); else src->clear(pos); return b;
  355. }
  356.  
  357. inline int BitSetBit::operator = (const BitSetBit& b)
  358. {
  359.   int i = (int)b;
  360.   *this = i;
  361.   return i;
  362. }
  363.  
  364. inline BitSetBit BitSet::operator [] (int i)
  365. {
  366.   if (i < 0) error("illegal bit index");
  367.   return BitSetBit(this, i);
  368. }
  369.  
  370. #endif
  371.