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