home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Programmierung / SOURCE.mdf / programm / msdos / c / djgpp / include / bitset.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-03-03  |  8.9 KB  |  386 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 GNU CC.
  7.  
  8. GNU CC is distributed in the hope that it will be useful,
  9. but WITHOUT ANY WARRANTY.  No author or distributor
  10. accepts responsibility to anyone for the consequences of using it
  11. or for whether it serves any particular purpose or works at all,
  12. unless he says so in writing.  Refer to the GNU CC General Public
  13. License for full details.
  14.  
  15. Everyone is granted permission to copy, modify and redistribute
  16. GNU CC, but only under the conditions described in the
  17. GNU CC General Public License.   A copy of this license is
  18. supposed to have been given to you along with GNU CC so you
  19. can know your rights and responsibilities.  It should be in a
  20. file named COPYING.  Among other things, the copyright notice
  21. and this notice must be preserved on all copies.  
  22. */
  23.  
  24. #ifndef _BitSet_h
  25. #ifdef __GNUG__
  26. #pragma once
  27. #pragma interface
  28. #endif
  29.  
  30. #define _BitSet_h 1
  31.  
  32. #include <stream.h>
  33. #include <values.h>
  34.  
  35. #define BITSETBITS  BITS(short)
  36.  
  37. struct BitSetRep
  38. {
  39.   unsigned short  len;          // number of shorts in s
  40.   unsigned short  sz;           // allocated slots
  41.   unsigned short  virt;         // virtual 0 or 1
  42.   unsigned short  s[1];         // bits start here
  43. };
  44.  
  45. extern BitSetRep*   BitSetalloc(BitSetRep*, const unsigned short*, 
  46.                                 int, int, int);
  47. extern BitSetRep*   BitSetcopy(BitSetRep*, const BitSetRep*);
  48. extern BitSetRep*   BitSetresize(BitSetRep*, int);
  49. extern BitSetRep*   BitSetop(const BitSetRep*, const BitSetRep*, 
  50.                              BitSetRep*, char);
  51. extern BitSetRep*   BitSetcmpl(const BitSetRep*, BitSetRep*);
  52.  
  53.  
  54. extern BitSetRep    _nilBitSetRep;
  55.  
  56. class BitSet;
  57.  
  58. class BitSetBit
  59. {
  60. protected:
  61.   BitSet*            src;
  62.   unsigned long      pos;
  63.  
  64.  public:
  65.                      BitSetBit(BitSet* v, int p);
  66.                      BitSetBit(const BitSetBit& b);
  67.                     ~BitSetBit();
  68.                      operator int();
  69.   int                operator = (int b);
  70.   int                operator == (int b);
  71.   int                operator != (int b);
  72. };
  73.  
  74. class BitSet
  75. {
  76. protected:
  77.   BitSetRep*          rep;
  78.  
  79.   
  80. public:
  81.  
  82. // constructors
  83.                      BitSet();
  84.                      BitSet(const BitSet&);
  85.  
  86.                     ~BitSet();
  87.  
  88.   void               operator =  (const BitSet& y);
  89.  
  90. // equality & subset tests
  91.  
  92.   friend int         operator == (const BitSet& x, const BitSet& y);
  93.   friend int         operator != (const BitSet& x, const BitSet& y);
  94.   friend int         operator <  (const BitSet& x, const BitSet& y);
  95.   friend int         operator <= (const BitSet& x, const BitSet& y);
  96.   friend int         operator >  (const BitSet& x, const BitSet& y);
  97.   friend int         operator >= (const BitSet& x, const BitSet& y);
  98.  
  99.  
  100. // operations on self
  101.  
  102.   void               operator |= (const BitSet& y);
  103.   void               operator &= (const BitSet& y);
  104.   void               operator -= (const BitSet& y);
  105.   void               operator ^= (const BitSet& y);
  106.  
  107.   void               complement();
  108.  
  109. // individual bit manipulation
  110.  
  111.   void               set(int pos);
  112.   void               set(int from, int to);
  113.   void               set(); // set all
  114.  
  115.   void               clear(int pos);
  116.   void               clear(int from, int to);
  117.   void               clear(); // clear all
  118.  
  119.   void               invert(int pos);
  120.   void               invert(int from, int to);
  121.  
  122.   int                test(int pos) const;
  123.   int                test(int from, int to) const;
  124.  
  125.   BitSetBit          operator [] (int i);
  126.   
  127. // iterators
  128.  
  129.   int                first(int b = 1) const;
  130.   int                last(int b = 1) const;
  131.  
  132.   int                next(int pos, int b = 1) const;
  133.   int                previous(int pos, int b = 1) const;
  134.  
  135. // status
  136.  
  137.   int                empty() const;
  138.   int                virtual_bit() const;
  139.   int                count(int b = 1) const;
  140.   
  141. // convertors & IO
  142.  
  143.   friend BitSet      atoBitSet(const char* s, 
  144.                                char f='0', char t='1', char star='*');
  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.  
  153. // procedural versions of operators
  154.  
  155.   friend void        and(const BitSet& x, const BitSet& y, BitSet& r);
  156.   friend void        or(const BitSet& x, const BitSet& y, BitSet& r);
  157.   friend void        xor(const BitSet& x, const BitSet& y, BitSet& r);
  158.   friend void        diff(const BitSet& x, const BitSet& y, BitSet& r);
  159.   friend void        complement(const BitSet& x, BitSet& r);
  160.  
  161. // misc
  162.  
  163.   volatile void      error(const char* msg) const;
  164.   int                OK() const;
  165. };
  166.  
  167.  
  168. typedef BitSet BitSetTmp;
  169.  
  170.  
  171.   BitSet      operator |  (const BitSet& x, const BitSet& y);
  172.   BitSet      operator &  (const BitSet& x, const BitSet& y);
  173.   BitSet      operator -  (const BitSet& x, const BitSet& y);
  174.   BitSet      operator ^  (const BitSet& x, const BitSet& y);
  175.  
  176.   BitSet      operator ~  (const BitSet& x);
  177.  
  178. // These are inlined regardless of optimization
  179.  
  180. inline int BitSet_index(int l)
  181. {
  182.   return (unsigned)(l) / BITSETBITS;
  183. }
  184.  
  185. inline int BitSet_pos(int l)
  186. {
  187.   return l & (BITSETBITS - 1);
  188. }
  189.  
  190. #if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
  191.  
  192.  
  193. inline BitSet::BitSet() : rep(&_nilBitSetRep) {}
  194.  
  195. inline BitSet::BitSet(const BitSet& x) :rep(BitSetcopy(0, x.rep)) {}
  196.  
  197. inline BitSet::~BitSet() { if (rep != &_nilBitSetRep) delete rep; }
  198.  
  199. inline void BitSet::operator =  (const BitSet& y)
  200. { 
  201.   rep = BitSetcopy(rep, y.rep);
  202. }
  203.  
  204. inline int operator != (const BitSet& x, const BitSet& y) { return !(x == y); }
  205.  
  206. inline int operator >  (const BitSet& x, const BitSet& y) { return y < x; }
  207.  
  208. inline int operator >= (const BitSet& x, const BitSet& y) { return y <= x; }
  209.  
  210. inline void and(const BitSet& x, const BitSet& y, BitSet& r)
  211. {
  212.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '&');
  213. }
  214.  
  215. inline void or(const BitSet& x, const BitSet& y, BitSet& r)
  216. {
  217.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '|');
  218. }
  219.  
  220. inline void xor(const BitSet& x, const BitSet& y, BitSet& r)
  221. {
  222.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '^');
  223. }
  224.  
  225. inline void diff(const BitSet& x, const BitSet& y, BitSet& r)
  226. {
  227.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '-');
  228. }
  229.  
  230. inline void complement(const BitSet& x, BitSet& r)
  231. {
  232.   r.rep = BitSetcmpl(x.rep, r.rep);
  233. }
  234.  
  235. #if defined(__GNUG__) && !defined(NO_NRV)
  236.  
  237. inline BitSet operator & (const BitSet& x, const BitSet& y) return r
  238. {
  239.   and(x, y, r);
  240. }
  241.  
  242. inline BitSet operator | (const BitSet& x, const BitSet& y) return r
  243. {
  244.   or(x, y, r);
  245. }
  246.  
  247. inline BitSet operator ^ (const BitSet& x, const BitSet& y) return r
  248. {
  249.   xor(x, y, r);
  250. }
  251.  
  252. inline BitSet operator - (const BitSet& x, const BitSet& y) return r
  253. {
  254.   diff(x, y, r);
  255. }
  256.  
  257. inline BitSet operator ~ (const BitSet& x) return r
  258. {
  259.   ::complement(x, r);
  260. }
  261.  
  262. #else /* NO_NRV */
  263.  
  264. inline BitSet operator & (const BitSet& x, const BitSet& y) 
  265. {
  266.   BitSet r; and(x, y, r); return r;
  267. }
  268.  
  269. inline BitSet operator | (const BitSet& x, const BitSet& y) 
  270. {
  271.   BitSet r; or(x, y, r); return r;
  272. }
  273.  
  274. inline BitSet operator ^ (const BitSet& x, const BitSet& y) 
  275. {
  276.   BitSet r; xor(x, y, r); return r;
  277. }
  278.  
  279. inline BitSet operator - (const BitSet& x, const BitSet& y) 
  280. {
  281.   BitSet r; diff(x, y, r); return r;
  282. }
  283.  
  284. inline BitSet operator ~ (const BitSet& x) 
  285. {
  286.   BitSet r; ::complement(x, r); return r;
  287. }
  288.  
  289. #endif
  290.  
  291. inline void BitSet::operator &= (const BitSet& y)
  292. {
  293.   and(*this, y, *this);
  294. }
  295.  
  296. inline void BitSet::operator |= (const BitSet& y)
  297. {
  298.   or(*this, y, *this);
  299. }
  300.  
  301. inline void BitSet::operator ^= (const BitSet& y)
  302. {
  303.   xor(*this, y, *this);
  304. }
  305.  
  306. inline void BitSet::operator -= (const BitSet& y)
  307. {
  308.   diff(*this, y, *this);
  309. }
  310.  
  311.  
  312. inline void BitSet::complement()
  313. {
  314.   ::complement(*this, *this);
  315. }
  316.  
  317. inline int BitSet::virtual_bit() const
  318. {
  319.   return rep->virt;
  320. }
  321.  
  322. inline int BitSet::first(int b) const
  323. {
  324.   return next(-1, b);
  325. }
  326.  
  327. inline int BitSet::test(int p) const
  328. {
  329.   if (p < 0) error("Illegal bit index");
  330.   int index = BitSet_index(p);
  331.   return (index >= rep->len)? rep->virt : 
  332.          ((rep->s[index] & (1 << BitSet_pos(p))) != 0);
  333. }
  334.  
  335.  
  336. inline void BitSet::clear()
  337. {
  338.   if (rep->len > 0) bzero(rep->s, rep->sz * sizeof(short));
  339.   rep->len = rep->virt = 0;
  340. }
  341.  
  342. inline void BitSet::set()
  343. {
  344.   rep = BitSetalloc(rep, 0, 0, 1, 0);
  345. }
  346.  
  347. inline BitSetBit::BitSetBit(const BitSetBit& b) :src(b.src), pos(b.pos) {}
  348.  
  349. inline BitSetBit::BitSetBit(BitSet* v, int p)
  350. {
  351.   src = v;  pos = p;
  352. }
  353.  
  354. inline BitSetBit::~BitSetBit() {}
  355.  
  356. inline BitSetBit::operator int()
  357. {
  358.   return src->test(pos);
  359. }
  360.  
  361. inline int BitSetBit::operator = (int b)
  362. {
  363.   if (b) src->set(pos); else src->clear(pos); return b;
  364. }
  365.  
  366. inline int BitSetBit::operator == (int b)
  367. {
  368.   return src->test(pos) == b;
  369. }
  370.  
  371. inline int BitSetBit::operator != (int b)
  372. {
  373.   return src->test(pos) != b;
  374. }
  375.  
  376. inline BitSetBit BitSet::operator [] (int i)
  377. {
  378.   if (i < 0) error("illegal bit index");
  379.   return BitSetBit(this, i);
  380. }
  381.  
  382.  
  383.  
  384. #endif
  385. #endif
  386.