home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / gnu / g__inc / xbitset.h < prev    next >
Encoding:
C/C++ Source or Header  |  1993-07-23  |  8.8 KB  |  381 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, 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18.  
  19. #ifndef _BitSet_h
  20. #ifdef __GNUG__
  21. #pragma once
  22. #pragma interface
  23. #endif
  24.  
  25. #define _BitSet_h 1
  26.  
  27. #include <stream.h>
  28. #include <values.h>
  29.  
  30. #define BITSETBITS  BITS(short)
  31.  
  32. struct BitSetRep
  33. {
  34.   unsigned short  len;          // number of shorts in s
  35.   unsigned short  sz;           // allocated slots
  36.   unsigned short  virt;         // virtual 0 or 1
  37.   unsigned short  s[1];         // bits start here
  38. };
  39.  
  40. extern BitSetRep*   BitSetalloc(BitSetRep*, const unsigned short*, 
  41.                                 int, int, int);
  42. extern BitSetRep*   BitSetcopy(BitSetRep*, const BitSetRep*);
  43. extern BitSetRep*   BitSetresize(BitSetRep*, int);
  44. extern BitSetRep*   BitSetop(const BitSetRep*, const BitSetRep*, 
  45.                              BitSetRep*, char);
  46. extern BitSetRep*   BitSetcmpl(const BitSetRep*, BitSetRep*);
  47.  
  48.  
  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();
  64.   int                operator = (int b);
  65.   int                operator == (int b);
  66.   int                operator != (int b);
  67. };
  68.  
  69. class BitSet
  70. {
  71. protected:
  72.   BitSetRep*          rep;
  73.  
  74.   
  75. public:
  76.  
  77. // constructors
  78.                      BitSet();
  79.                      BitSet(const BitSet&);
  80.  
  81.                     ~BitSet();
  82.  
  83.   void               operator =  (const BitSet& y);
  84.  
  85. // equality & subset tests
  86.  
  87.   friend int         operator == (const BitSet& x, const BitSet& y);
  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.  
  94.  
  95. // operations on self
  96.  
  97.   void               operator |= (const BitSet& y);
  98.   void               operator &= (const BitSet& y);
  99.   void               operator -= (const BitSet& y);
  100.   void               operator ^= (const BitSet& y);
  101.  
  102.   void               complement();
  103.  
  104. // individual bit manipulation
  105.  
  106.   void               set(int pos);
  107.   void               set(int from, int to);
  108.   void               set(); // set all
  109.  
  110.   void               clear(int pos);
  111.   void               clear(int from, int to);
  112.   void               clear(); // clear all
  113.  
  114.   void               invert(int pos);
  115.   void               invert(int from, int to);
  116.  
  117.   int                test(int pos) const;
  118.   int                test(int from, int to) const;
  119.  
  120.   BitSetBit          operator [] (int i);
  121.   
  122. // iterators
  123.  
  124.   int                first(int b = 1) const;
  125.   int                last(int b = 1) const;
  126.  
  127.   int                next(int pos, int b = 1) const;
  128.   int                previous(int pos, int b = 1) const;
  129.  
  130. // status
  131.  
  132.   int                empty() const;
  133.   int                virtual_bit() const;
  134.   int                count(int b = 1) const;
  135.   
  136. // convertors & IO
  137.  
  138.   friend BitSet      atoBitSet(const char* s, 
  139.                                char f='0', char t='1', char star='*');
  140.   friend const char* BitSettoa(const BitSet& x, 
  141.                                char f='0', char t='1', char star='*');
  142.  
  143.   friend BitSet      shorttoBitSet(unsigned short w);
  144.   friend BitSet      longtoBitSet(unsigned long w);
  145.  
  146.   friend ostream&    operator << (ostream& s, const BitSet& x);
  147.  
  148. // procedural versions of operators
  149.  
  150.   friend void        and(const BitSet& x, const BitSet& y, BitSet& r);
  151.   friend void        or(const BitSet& x, const BitSet& y, BitSet& r);
  152.   friend void        xor(const BitSet& x, const BitSet& y, BitSet& r);
  153.   friend void        diff(const BitSet& x, const BitSet& y, BitSet& r);
  154.   friend void        complement(const BitSet& x, BitSet& r);
  155.  
  156. // misc
  157.  
  158.   volatile void      error(const char* msg) const;
  159.   int                OK() const;
  160. };
  161.  
  162.  
  163. typedef BitSet BitSetTmp;
  164.  
  165.  
  166.   BitSet      operator |  (const BitSet& x, const BitSet& y);
  167.   BitSet      operator &  (const BitSet& x, const BitSet& y);
  168.   BitSet      operator -  (const BitSet& x, const BitSet& y);
  169.   BitSet      operator ^  (const BitSet& x, const BitSet& y);
  170.  
  171.   BitSet      operator ~  (const BitSet& x);
  172.  
  173. // These are inlined regardless of optimization
  174.  
  175. inline int BitSet_index(int l)
  176. {
  177.   return (unsigned)(l) / BITSETBITS;
  178. }
  179.  
  180. inline int BitSet_pos(int l)
  181. {
  182.   return l & (BITSETBITS - 1);
  183. }
  184.  
  185. #if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
  186.  
  187.  
  188. inline BitSet::BitSet() : rep(&_nilBitSetRep) {}
  189.  
  190. inline BitSet::BitSet(const BitSet& x) :rep(BitSetcopy(0, x.rep)) {}
  191.  
  192. inline BitSet::~BitSet() { if (rep != &_nilBitSetRep) delete rep; }
  193.  
  194. inline void BitSet::operator =  (const BitSet& y)
  195. { 
  196.   rep = BitSetcopy(rep, y.rep);
  197. }
  198.  
  199. inline int operator != (const BitSet& x, const BitSet& y) { return !(x == y); }
  200.  
  201. inline int operator >  (const BitSet& x, const BitSet& y) { return y < x; }
  202.  
  203. inline int operator >= (const BitSet& x, const BitSet& y) { return y <= x; }
  204.  
  205. inline void and(const BitSet& x, const BitSet& y, BitSet& r)
  206. {
  207.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '&');
  208. }
  209.  
  210. inline void or(const BitSet& x, const BitSet& y, BitSet& r)
  211. {
  212.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '|');
  213. }
  214.  
  215. inline void xor(const BitSet& x, const BitSet& y, BitSet& r)
  216. {
  217.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '^');
  218. }
  219.  
  220. inline void diff(const BitSet& x, const BitSet& y, BitSet& r)
  221. {
  222.   r.rep =  BitSetop(x.rep, y.rep, r.rep, '-');
  223. }
  224.  
  225. inline void complement(const BitSet& x, BitSet& r)
  226. {
  227.   r.rep = BitSetcmpl(x.rep, r.rep);
  228. }
  229.  
  230. #if defined(__GNUG__) && !defined(NO_NRV)
  231.  
  232. inline BitSet operator & (const BitSet& x, const BitSet& y) return r
  233. {
  234.   and(x, y, r);
  235. }
  236.  
  237. inline BitSet operator | (const BitSet& x, const BitSet& y) return r
  238. {
  239.   or(x, y, r);
  240. }
  241.  
  242. inline BitSet operator ^ (const BitSet& x, const BitSet& y) return r
  243. {
  244.   xor(x, y, r);
  245. }
  246.  
  247. inline BitSet operator - (const BitSet& x, const BitSet& y) return r
  248. {
  249.   diff(x, y, r);
  250. }
  251.  
  252. inline BitSet operator ~ (const BitSet& x) return r
  253. {
  254.   ::complement(x, r);
  255. }
  256.  
  257. #else /* NO_NRV */
  258.  
  259. inline BitSet operator & (const BitSet& x, const BitSet& y) 
  260. {
  261.   BitSet r; and(x, y, r); return r;
  262. }
  263.  
  264. inline BitSet operator | (const BitSet& x, const BitSet& y) 
  265. {
  266.   BitSet r; or(x, y, r); return r;
  267. }
  268.  
  269. inline BitSet operator ^ (const BitSet& x, const BitSet& y) 
  270. {
  271.   BitSet r; xor(x, y, r); return r;
  272. }
  273.  
  274. inline BitSet operator - (const BitSet& x, const BitSet& y) 
  275. {
  276.   BitSet r; diff(x, y, r); return r;
  277. }
  278.  
  279. inline BitSet operator ~ (const BitSet& x) 
  280. {
  281.   BitSet r; ::complement(x, r); return r;
  282. }
  283.  
  284. #endif
  285.  
  286. inline void BitSet::operator &= (const BitSet& y)
  287. {
  288.   and(*this, y, *this);
  289. }
  290.  
  291. inline void BitSet::operator |= (const BitSet& y)
  292. {
  293.   or(*this, y, *this);
  294. }
  295.  
  296. inline void BitSet::operator ^= (const BitSet& y)
  297. {
  298.   xor(*this, y, *this);
  299. }
  300.  
  301. inline void BitSet::operator -= (const BitSet& y)
  302. {
  303.   diff(*this, y, *this);
  304. }
  305.  
  306.  
  307. inline void BitSet::complement()
  308. {
  309.   ::complement(*this, *this);
  310. }
  311.  
  312. inline int BitSet::virtual_bit() const
  313. {
  314.   return rep->virt;
  315. }
  316.  
  317. inline int BitSet::first(int b) const
  318. {
  319.   return next(-1, b);
  320. }
  321.  
  322. inline int BitSet::test(int p) const
  323. {
  324.   if (p < 0) error("Illegal bit index");
  325.   int index = BitSet_index(p);
  326.   return (index >= rep->len)? rep->virt : 
  327.          ((rep->s[index] & (1 << BitSet_pos(p))) != 0);
  328. }
  329.  
  330.  
  331. inline void BitSet::clear()
  332. {
  333.   if (rep->len > 0) bzero(rep->s, rep->sz * sizeof(short));
  334.   rep->len = rep->virt = 0;
  335. }
  336.  
  337. inline void BitSet::set()
  338. {
  339.   rep = BitSetalloc(rep, 0, 0, 1, 0);
  340. }
  341.  
  342. inline BitSetBit::BitSetBit(const BitSetBit& b) :src(b.src), pos(b.pos) {}
  343.  
  344. inline BitSetBit::BitSetBit(BitSet* v, int p)
  345. {
  346.   src = v;  pos = p;
  347. }
  348.  
  349. inline BitSetBit::~BitSetBit() {}
  350.  
  351. inline BitSetBit::operator int()
  352. {
  353.   return src->test(pos);
  354. }
  355.  
  356. inline int BitSetBit::operator = (int b)
  357. {
  358.   if (b) src->set(pos); else src->clear(pos); return b;
  359. }
  360.  
  361. inline int BitSetBit::operator == (int b)
  362. {
  363.   return src->test(pos) == b;
  364. }
  365.  
  366. inline int BitSetBit::operator != (int b)
  367. {
  368.   return src->test(pos) != b;
  369. }
  370.  
  371. inline BitSetBit BitSet::operator [] (int i)
  372. {
  373.   if (i < 0) error("illegal bit index");
  374.   return BitSetBit(this, i);
  375. }
  376.  
  377.  
  378.  
  379. #endif
  380. #endif
  381.