home *** CD-ROM | disk | FTP | other *** search
/ Big Green CD 8 / BGCD_8_Dev.iso / OPENSTEP / UNIX / GNU / gcc-2.7.2.3.1-I / lib / g++-include / BitSet.h < prev    next >
Encoding:
C/C++ Source or Header  |  1997-09-12  |  9.2 KB  |  361 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. extern BitSetRep    _nilBitSetRep;
  50.  
  51. class BitSet;
  52.  
  53. class BitSetBit
  54. {
  55. protected:
  56.   BitSet*            src;
  57.   unsigned long      pos;
  58.  
  59.  public:
  60.                      BitSetBit(BitSet* v, int p);
  61.                      BitSetBit(const BitSetBit& b);
  62.                     ~BitSetBit();
  63.                      operator int() const;
  64.   int                operator = (int b);
  65.   int                operator = (const BitSetBit& b);
  66. };
  67.  
  68. class BitSet
  69. {
  70. protected:
  71.   BitSetRep*          rep;
  72.  
  73.   enum BS_op {
  74.     BS_and = (int) '&',
  75.     BS_or = (int) '|',
  76.     BS_xor = (int) '^',
  77.     BS_diff = (int) '-',
  78.     BS_inv = (int) '~'
  79.   };
  80.   BitSet(const BitSet& x, const BitSet& y, enum BS_op op)
  81.     { rep = BitSetop (x.rep, y.rep, NULL, (char) op);  }
  82.   BitSet(const BitSet& x, enum BS_op /* op */)
  83.     { rep = BitSetcmpl (x.rep, NULL); }
  84.  
  85. public:
  86.  
  87. // constructors
  88.                      BitSet();
  89.                      BitSet(const BitSet&);
  90.  
  91.                     ~BitSet();
  92.  
  93.   BitSet&            operator =  (const BitSet& y);
  94.  
  95. // equality & subset tests
  96.  
  97.   friend int         operator == (const BitSet& x, const BitSet& y);
  98.   friend int         operator != (const BitSet& x, const BitSet& y);
  99.   friend int         operator <  (const BitSet& x, const BitSet& y);
  100.   friend int         operator <= (const BitSet& x, const BitSet& y);
  101.   friend int         operator >  (const BitSet& x, const BitSet& y);
  102.   friend int         operator >= (const BitSet& x, const BitSet& y);
  103.   friend int           lcompare(const BitSet& x, const BitSet& y);
  104.  
  105. // operations on self
  106.  
  107.   BitSet&            operator |= (const BitSet& y);
  108.   BitSet&            operator &= (const BitSet& y);
  109.   BitSet&            operator -= (const BitSet& y);
  110.   BitSet&            operator ^= (const BitSet& y);
  111.  
  112.   void               complement();
  113.  
  114. // functional operators
  115.  
  116.   friend BitSet operator & (const BitSet& x, const BitSet& y);
  117.   friend BitSet operator | (const BitSet& x, const BitSet& y);
  118.   friend BitSet operator ^ (const BitSet& x, const BitSet& y);
  119.   friend BitSet operator - (const BitSet& x, const BitSet& y);
  120.   friend BitSet operator ~ (const BitSet& x);
  121.  
  122. // individual bit manipulation
  123.  
  124.   void               set(int pos);
  125.   void               set(int from, int to);
  126.   void               set(); // set all
  127.  
  128.   void               clear(int pos);
  129.   void               clear(int from, int to);
  130.   void               clear(); // clear all
  131.  
  132.   void               invert(int pos);
  133.   void               invert(int from, int to);
  134.  
  135.   int                test(int pos) const;
  136.   int                test(int from, int to) const;
  137.  
  138.   BitSetBit          operator [] (int i);
  139.   
  140. // iterators
  141.  
  142.   int                first(int b = 1) const;
  143.   int                last(int b = 1) const;
  144.  
  145.   int                next(int pos, int b = 1) const;
  146.   int                prev(int pos, int b = 1) const;
  147.   int                previous(int pos, int b = 1) const /* Obsolete synonym */
  148.     { return prev(pos, b); }
  149.  
  150. // status
  151.  
  152.   int                empty() const;
  153.   int                virtual_bit() const;
  154.   int                count(int b = 1) const;
  155.   
  156. // convertors & IO
  157.  
  158.   friend BitSet      atoBitSet(const char* s, 
  159.                                char f='0', char t='1', char star='*');
  160.   // BitSettoa is deprecated; do not use in new programs.
  161.   friend const char* BitSettoa(const BitSet& x, 
  162.                                char f='0', char t='1', char star='*');
  163.  
  164.   friend BitSet      shorttoBitSet(unsigned short w);
  165.   friend BitSet      longtoBitSet(unsigned long w);
  166.  
  167.   friend ostream&    operator << (ostream& s, const BitSet& x);
  168.   void             printon(ostream& s,
  169.                  char f='0', char t='1', char star='*') const;
  170.  
  171. #ifndef __STRICT_ANSI__
  172.   // procedural versions of operators
  173.  
  174.   // The first three of these are incompatible with ANSI C++ digraphs.
  175.   // In any case, it's not a great interface.
  176.   friend void        and(const BitSet& x, const BitSet& y, BitSet& r);
  177.   friend void        or(const BitSet& x, const BitSet& y, BitSet& r);
  178.   friend void        xor(const BitSet& x, const BitSet& y, BitSet& r);
  179.   friend void        diff(const BitSet& x, const BitSet& y, BitSet& r);
  180.   friend void        complement(const BitSet& x, BitSet& r);
  181. #endif
  182.  
  183. // misc
  184.  
  185.   void      error(const char* msg) const;
  186.   int                OK() const;
  187. };
  188.  
  189.  
  190. typedef BitSet BitSetTmp;
  191.  
  192. // These are inlined regardless of optimization
  193.  
  194. inline int BitSet_index(int l)
  195. {
  196.   return (unsigned)(l) / BITSETBITS;
  197. }
  198.  
  199. inline int BitSet_pos(int l)
  200. {
  201.   return l & (BITSETBITS - 1);
  202. }
  203.  
  204. inline BitSet::BitSet() : rep(&_nilBitSetRep) {}
  205.  
  206. inline BitSet::BitSet(const BitSet& x) :rep(BitSetcopy(0, x.rep)) {}
  207.  
  208. inline BitSet::~BitSet() { if (rep != &_nilBitSetRep) delete rep; }
  209.  
  210. inline BitSet& BitSet::operator =  (const BitSet& y)
  211. { 
  212.   rep = BitSetcopy(rep, y.rep);
  213.   return *this;
  214. }
  215.  
  216. inline int operator != (const BitSet& x, const BitSet& y) { return !(x == y); }
  217.  
  218. inline int operator >  (const BitSet& x, const BitSet& y) { return y < x; }
  219.  
  220. inline int operator >= (const BitSet& x, const BitSet& y) { return y <= x; }
  221.  
  222. #ifndef __STRICT_ANSI__
  223. inline void and(const BitSet& x, const BitSet& y, BitSet& r)
  224. {
  225.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '&');
  226. }
  227.  
  228. inline void or(const BitSet& x, const BitSet& y, BitSet& r)
  229. {
  230.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '|');
  231. }
  232.  
  233. inline void xor(const BitSet& x, const BitSet& y, BitSet& r)
  234. {
  235.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '^');
  236. }
  237.  
  238. inline void diff(const BitSet& x, const BitSet& y, BitSet& r)
  239. {
  240.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '-');
  241. }
  242.  
  243. inline void complement(const BitSet& x, BitSet& r)
  244. {
  245.   r.rep = BitSetcmpl(x.rep, r.rep);
  246. }
  247. #endif
  248.  
  249. inline BitSet operator & (const BitSet& x, const BitSet& y) 
  250. {
  251.   return BitSet::BitSet(x, y, BitSet::BS_and);
  252. }
  253.  
  254. inline BitSet operator | (const BitSet& x, const BitSet& y) 
  255. {
  256.   return BitSet::BitSet(x, y, BitSet::BS_or);
  257. }
  258.  
  259. inline BitSet operator ^ (const BitSet& x, const BitSet& y) 
  260. {
  261.   return BitSet::BitSet(x, y, BitSet::BS_xor);
  262. }
  263.  
  264. inline BitSet operator - (const BitSet& x, const BitSet& y) 
  265. {
  266.   return BitSet::BitSet(x, y, BitSet::BS_diff);
  267. }
  268.  
  269. inline BitSet operator ~ (const BitSet& x) 
  270. {
  271.   return BitSet::BitSet(x, BitSet::BS_inv);
  272. }
  273.  
  274. inline BitSet& BitSet::operator &= (const BitSet& y)
  275. {
  276.   rep =  BitSetop(rep, y.rep, rep, '&');
  277.   return *this;
  278. }
  279.  
  280. inline BitSet& BitSet::operator |= (const BitSet& y)
  281. {
  282.   rep =  BitSetop(rep, y.rep, rep, '|');
  283.   return *this;
  284. }
  285.  
  286. inline BitSet& BitSet::operator ^= (const BitSet& y)
  287. {
  288.   rep =  BitSetop(rep, y.rep, rep, '^');
  289.   return *this;
  290. }
  291.  
  292. inline BitSet& BitSet::operator -= (const BitSet& y)
  293. {
  294.   rep =  BitSetop(rep, y.rep, rep, '-');
  295.   return *this;
  296. }
  297.  
  298.  
  299. inline void BitSet::complement()
  300. {
  301.   rep = BitSetcmpl(rep, rep);
  302. }
  303.  
  304. inline int BitSet::virtual_bit() const
  305. {
  306.   return rep->virt;
  307. }
  308.  
  309. inline int BitSet::first(int b) const
  310. {
  311.   return next(-1, b);
  312. }
  313.  
  314. inline int BitSet::test(int p) const
  315. {
  316.   if (p < 0) error("Illegal bit index");
  317.   int index = BitSet_index(p);
  318.   return (index >= rep->len)? rep->virt : 
  319.          ((rep->s[index] & ((_BS_word)1 << BitSet_pos(p))) != 0);
  320. }
  321.  
  322.  
  323. inline void BitSet::set()
  324. {
  325.   rep = BitSetalloc(rep, 0, 0, 1, 0);
  326. }
  327.  
  328. inline BitSetBit::BitSetBit(const BitSetBit& b) :src(b.src), pos(b.pos) {}
  329.  
  330. inline BitSetBit::BitSetBit(BitSet* v, int p)
  331. {
  332.   src = v;  pos = p;
  333. }
  334.  
  335. inline BitSetBit::~BitSetBit() {}
  336.  
  337. inline BitSetBit::operator int() const
  338. {
  339.   return src->test(pos);
  340. }
  341.  
  342. inline int BitSetBit::operator = (int b)
  343. {
  344.   if (b) src->set(pos); else src->clear(pos); return b;
  345. }
  346.  
  347. inline int BitSetBit::operator = (const BitSetBit& b)
  348. {
  349.   int i = (int)b;
  350.   *this = i;
  351.   return i;
  352. }
  353.  
  354. inline BitSetBit BitSet::operator [] (int i)
  355. {
  356.   if (i < 0) error("illegal bit index");
  357.   return BitSetBit(this, i);
  358. }
  359.  
  360. #endif
  361.