home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c017 / 7.ddi / GPPLIB.ZIP / BITSTR.H < prev    next >
Encoding:
C/C++ Source or Header  |  1988-08-17  |  13.7 KB  |  529 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 _BitString_h
  25.  
  26. #define _BitString_h 1
  27.  
  28. #include <stream.h>
  29.  
  30. struct _BitStringrep
  31. {
  32.   unsigned long   len;          // length in bits
  33.   unsigned short  sz;           // allocated slots
  34.   short           ref;          // reference count
  35.   unsigned long   s[1];         // bits start here
  36. };
  37.  
  38. extern _BitStringrep    _nil_BitStringrep;
  39.  
  40. class BitString;
  41. class BitPattern;
  42.  
  43. class BitSubString
  44. {
  45.   friend class      BitString;
  46.   friend class      BitPattern;
  47.  
  48.   BitString*        S;
  49.   long              pos;
  50.   long              len;
  51.  
  52.                     BitSubString(BitString* x, int p, int l);
  53.                     BitSubString(BitSubString& x);
  54. public:
  55.                     ~BitSubString();
  56.  
  57.   void              operator =  (BitString&  y);
  58.   void              operator =  (BitSubString&  y);
  59.   int               length();
  60.   int               empty();
  61. };
  62.  
  63. class BitString
  64. {
  65.   friend class       BitSubString;
  66.   friend class       BitPattern;
  67.  
  68.   _BitStringrep*     rep;
  69.  
  70.   void              copy(unsigned long*, int, int);
  71.   int               search(int, int, unsigned long*, int, int);
  72.   int               match(int, int, int, unsigned long*, int, int);
  73.  
  74. public:
  75.  
  76. // constructors
  77.                      BitString();
  78.                      BitString(BitString&);
  79.                      BitString(BitSubString& y);
  80.  
  81.                      ~BitString();
  82.  
  83.   BitString&         operator =  (BitString& y);
  84.   BitString&         operator =  (BitSubString& y);
  85.   BitString&         nullify();
  86.  
  87. // equality & subset tests
  88.  
  89.   friend int         operator == (BitString& x, BitString& y);
  90.   friend int         operator != (BitString& x, BitString& y);
  91.   friend int         operator <  (BitString& x, BitString& y);
  92.   friend int         operator <= (BitString& x, BitString& y);
  93.   friend int         operator >  (BitString& x, BitString& y);
  94.   friend int         operator >= (BitString& x, BitString& y);
  95.  
  96.   friend int         lcompare(BitString& x, BitString& y); // lexigraphic comp
  97.  
  98. // set operators
  99.  
  100.   friend BitString   operator |  (BitString& x, BitString& y);
  101.   friend BitString   operator &  (BitString& x, BitString& y);
  102.   friend BitString   operator -  (BitString& x, BitString& y);
  103.   friend BitString   operator ^  (BitString& x, BitString& y);
  104.   friend BitString   operator << (BitString& x, int s);
  105.   friend BitString   operator >> (BitString& x, int s);
  106.  
  107.   BitString          operator ~ ();
  108.   BitString&         complement();
  109.  
  110.   BitString&         operator |= (BitString& y);
  111.   BitString&         operator &= (BitString& y);
  112.   BitString&         operator -= (BitString& y);
  113.   BitString&         operator ^= (BitString& y);
  114.   BitString&         operator <<=(int s);
  115.   BitString&         operator >>=(int s);
  116.  
  117. // concatenation
  118.  
  119.   friend BitString   operator +  (BitString& x, BitString& y);
  120.   BitString&         operator += (BitString& y);
  121.  
  122. // individual bit manipulation
  123.  
  124.   void               set(int pos);
  125.   void               set(int from, int to);
  126.  
  127.   void               clear(int pos);
  128.   void               clear(int from, int to);
  129.  
  130.   void               invert(int pos);
  131.   void               invert(int from, int to);
  132.  
  133.   int                test(int pos);
  134.   int                test(int from, int to);
  135.  
  136. // iterators
  137.  
  138.   int                first(int b = 1);
  139.   int                last(int b = 1);
  140.  
  141.   int                next(int pos, int b = 1);
  142.   int                previous(int pos, int b = 1);
  143.  
  144. // searching & matching
  145.  
  146.   int                index(int          bit, int startpos = 0);      
  147.   int                index(BitString&     y, int startpos = 0);      
  148.   int                index(BitSubString&  y, int startpos = 0);      
  149.   int                index(BitPattern&    r, int startpos = 0);       
  150.  
  151.   int                contains(BitString&     y);
  152.   int                contains(BitSubString&  y);
  153.   int                contains(BitPattern&    r);
  154.  
  155.   int                contains(BitString&     y, int pos);
  156.   int                contains(BitSubString&  y, int pos);
  157.   int                contains(BitPattern&    r, int pos);
  158.  
  159.   int                matches(BitString&     y, int pos = 0);
  160.   int                matches(BitSubString&  y, int pos = 0);
  161.   int                matches(BitPattern& r, int pos = 0);
  162.  
  163. // BitSubString extraction
  164.  
  165.   BitSubString       at(int               pos, int len);
  166.   BitSubString       at(BitString&        x, int startpos = 0); 
  167.   BitSubString       at(BitSubString&     x, int startpos = 0); 
  168.   BitSubString       at(BitPattern&       r, int startpos = 0); 
  169.  
  170.   BitSubString       before(int           pos);
  171.   BitSubString       before(BitString&    x, int startpos = 0);
  172.   BitSubString       before(BitSubString& x, int startpos = 0);
  173.   BitSubString       before(BitPattern&   r, int startpos = 0);
  174.  
  175.   BitSubString       after(int            pos);
  176.   BitSubString       after(BitString&     x, int startpos = 0);
  177.   BitSubString       after(BitSubString&  x, int startpos = 0);
  178.   BitSubString       after(BitPattern&    r, int startpos = 0);
  179.  
  180. // other friends & utilities
  181.  
  182.   friend BitString   common_prefix(BitString& x, BitString& y, int pos = 0);
  183.   friend BitString   common_suffix(BitString& x, BitString& y, int pos = -1);
  184.   friend BitString   reverse(BitString& x);
  185.  
  186.   void               right_trim(int bit);
  187.   void               left_trim(int bit);
  188.  
  189. // status
  190.  
  191.   int                empty();
  192.   int                count(int bit = 1);
  193.   int                length();
  194.   int                operator ! ();
  195.  
  196. // convertors & IO
  197.  
  198.   friend BitString   atoBitString(const char* s, char f='0', char t='1');
  199.   friend const char* BitStringtoa(BitString& x, char f='0', char t='1');
  200.  
  201.   friend ostream&    operator << (ostream& s, BitString& x);
  202.  
  203. // misc
  204.  
  205.   void               setlength(int len, int clear = 0);
  206.   void               make_unique();
  207.   void               error(char* msg);
  208.  
  209.  
  210. // non-operator versions
  211.  
  212.   friend void        and(BitString& x, BitString& y, BitString& r);
  213.   friend void        or(BitString& x, BitString& y, BitString& r);
  214.   friend void        xor(BitString& x, BitString& y, BitString& r);
  215.   friend void        difference(BitString& x, BitString& y, BitString& r);
  216.   friend void        concat(BitString& x, BitString& y, BitString& r);
  217.   friend void        rshift(BitString& x, int s, BitString& y);
  218.   void               copy(BitString& y);
  219.  
  220. // indirect friends
  221.  
  222.   friend const char* BitPatterntoa(BitPattern& p, 
  223.                                   char f='0',char t='1',char x='X');
  224.   friend BitPattern atoBitPattern(const char* s,
  225.                                   char f='0',char t='1',char x='X');
  226. };
  227.  
  228. class BitPattern
  229. {
  230. public:
  231.   BitString          pattern;
  232.   BitString          mask;
  233.  
  234.                      BitPattern();
  235.                      BitPattern(BitString& p, BitString& m);
  236.                      ~BitPattern();
  237.  
  238.   friend const char* BitPatterntoa(BitPattern& p, 
  239.                                   char f='0',char t='1',char x='X');
  240.   friend BitPattern atoBitPattern(const char* s,
  241.                                   char f='0',char t='1',char x='X');
  242.   friend ostream&   operator << (ostream& s, BitPattern& x);
  243.  
  244.   int               search(unsigned long*, int, int);
  245.   int               match(unsigned long* xs, int, int, int);
  246. };
  247.  
  248. // error handlers
  249.  
  250. extern void default_BitString_error_handler(char*);
  251. extern one_arg_error_handler_t BitString_error_handler;
  252.  
  253. extern one_arg_error_handler_t 
  254.         set_BitString_error_handler(one_arg_error_handler_t f);
  255.  
  256. //#ifdef __OPTIMIZE__
  257.  
  258. inline BitString::BitString()
  259.   rep = &_nil_BitStringrep;
  260. }
  261.  
  262. inline BitString::BitString(BitString& x)
  263.   rep = x.rep; if (rep->ref > 0) rep->ref++;
  264. }
  265.  
  266. inline BitString::BitString(BitSubString& y)
  267. {
  268.   rep = &_nil_BitStringrep; copy(y.S->rep->s, y.pos, y.pos+y.len);
  269. }
  270.  
  271. inline BitString::~BitString()
  272.   if (rep->ref > 0 && --rep->ref == 0) delete rep;
  273. }
  274.  
  275. inline BitString& BitString::operator =  (BitString& y)
  276.   y.rep->ref++;
  277.   if (rep->ref > 0 && --rep->ref == 0) delete rep;
  278.   rep = y.rep;
  279.   return *this; 
  280. }
  281.  
  282. inline BitString& BitString::nullify()
  283.   if (rep->ref > 0 && --rep->ref == 0) delete rep;
  284.   rep = &_nil_BitStringrep;
  285.   return *this; 
  286. }
  287.  
  288. inline BitString& BitString::operator=(BitSubString&  y)
  289. {
  290.   copy(y.S->rep->s, y.pos, y.pos+y.len); return *this;
  291. }
  292.  
  293. inline void BitString::copy(BitString& y)
  294. {
  295.   copy(y.rep->s, 0, y.rep->len);
  296. }
  297.  
  298. inline BitSubString::BitSubString(BitSubString& x)
  299.   S = x.S; pos = x.pos;   len = x.len; 
  300. }
  301.  
  302. inline BitSubString::~BitSubString() {}
  303.  
  304. inline BitPattern::BitPattern(BitString& p, BitString& m)
  305.   pattern = p; mask = m;
  306. }
  307.  
  308. inline BitPattern::BitPattern() {}
  309. inline BitPattern::~BitPattern() {}
  310.  
  311. inline BitString& BitString::operator+=(BitString& y)
  312. {
  313.   concat(*this, y, *this); return *this;
  314. }
  315.  
  316. inline BitString operator + (BitString& x, BitString& y)
  317. {
  318.   BitString r; concat(x, y, r); return r;
  319. }
  320.   
  321. inline int BitString::length()
  322.   return rep->len;
  323. }
  324.  
  325. inline int BitString::empty()
  326.   return rep->len == 0;
  327. }
  328.  
  329. inline int BitString::index(BitString& y, int startpos = 0)
  330. {   
  331.   return search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  332. }
  333.  
  334. inline int BitString::index(BitSubString& y, int startpos = 0)
  335. {   
  336.   return search(startpos, rep->len, y.S->rep->s, y.pos, y.pos+y.len);
  337. }
  338.  
  339. inline int BitString::contains(BitString& y)
  340. {   
  341.   return search(0, rep->len, y.rep->s, 0, y.rep->len) >= 0;
  342. }
  343.  
  344. inline int BitString::contains(BitSubString& y)
  345. {   
  346.   return search(0, rep->len, y.S->rep->s, y.pos, y.pos+y.len) >= 0;
  347. }
  348.  
  349. inline int BitString::contains(BitString& y, int p)
  350. {
  351.   return match(p, rep->len, 0, y.rep->s, 0, y.rep->len);
  352. }
  353.  
  354. inline int BitString::matches(BitString& y, int p = 0)
  355. {
  356.   return match(p, rep->len, 1, y.rep->s, 0, y.rep->len);
  357. }
  358.  
  359. inline int BitString::contains(BitSubString& y, int p)
  360. {
  361.   return match(p, rep->len, 0, y.S->rep->s, y.pos, y.pos+y.len);
  362. }
  363.  
  364. inline int BitString::matches(BitSubString& y, int p = 0)
  365. {
  366.   return match(p, rep->len, 1, y.S->rep->s, y.pos, y.pos+y.len);
  367. }
  368.  
  369. inline int BitString::contains(BitPattern& r)
  370. {
  371.   return r.search(rep->s, 0, rep->len) >= 0;
  372. }
  373.  
  374. inline int BitString::contains(BitPattern& r, int p)
  375. {
  376.   return r.match(rep->s, p, rep->len, 0);
  377. }
  378.  
  379. inline int BitString::matches(BitPattern& r, int p = 0)
  380. {
  381.   return r.match(rep->s, p, rep->len, 1);
  382. }
  383.  
  384. inline int BitString::index(BitPattern& r, int startpos = 0)
  385. {
  386.   return r.search(rep->s, startpos, rep->len);
  387. }
  388.  
  389. inline  int BitSubString::length()
  390.   return len;
  391. }
  392.  
  393. inline  int BitSubString::empty()
  394.   return len == 0;
  395. }
  396.  
  397. inline int operator != (BitString& x, BitString& y)
  398. {
  399.   return !(x == y);
  400. }
  401.  
  402. inline int operator>(BitString& x, BitString& y)
  403. {
  404.   return y < x;
  405. }
  406.  
  407. inline int operator>=(BitString& x, BitString& y)
  408. {
  409.   return y <= x;
  410. }
  411.  
  412. inline void BitString::make_unique()
  413. {
  414.   if (rep->ref != 1) setlength(rep->len);
  415. }
  416.  
  417. inline BitString operator & (BitString& x, BitString& y)
  418. {
  419.   BitString r; and(x, y, r); return r;
  420. }
  421.  
  422. inline BitString operator | (BitString& x, BitString& y)
  423. {
  424.   BitString r; or(x, y, r); return r;
  425. }
  426.  
  427. inline BitString operator ^ (BitString& x, BitString& y)
  428. {
  429.   BitString r; xor(x, y, r); return r;
  430. }
  431.  
  432. inline BitString operator - (BitString& x, BitString& y)
  433. {
  434.   BitString r; difference(x, y, r); return r;
  435. }
  436.  
  437. inline BitString& BitString::operator &= (BitString& y)
  438. {
  439.   and(*this, y, *this); return *this;
  440. }
  441.  
  442. inline BitString& BitString::operator |= (BitString& y)
  443. {
  444.   or(*this, y, *this); return *this;
  445. }
  446.  
  447. inline BitString& BitString::operator ^= (BitString& y)
  448. {
  449.   xor(*this, y, *this); return *this;
  450. }
  451.  
  452. inline BitString& BitString::operator -= (BitString& y)
  453. {
  454.   difference(*this, y, *this); return *this;
  455. }
  456.  
  457. inline BitString operator << (BitString& x, int s)
  458. {
  459.   BitString r; rshift(x, s, r); return r;
  460. }
  461.  
  462. inline BitString operator >> (BitString& x, int s)
  463. {
  464.   BitString r; rshift(x, -s, r); return r;
  465. }
  466.  
  467. inline BitString& BitString::operator <<= (int s)
  468. {
  469.   rshift(*this, s, *this); return *this;
  470. }
  471.  
  472. inline BitString& BitString::operator >>= (int s)
  473. {
  474.   rshift(*this, -s, *this); return *this;
  475. }
  476.  
  477. inline int BitString::first(int b = 1)
  478. {
  479.   return next(-1, b);
  480. }
  481.  
  482. inline int BitString::last(int b = 1)
  483. {
  484.   return previous(rep->len, b);
  485. }
  486.  
  487. inline int BitString::index(int bit, int startpos = 0)
  488. {
  489.   if (startpos >= 0)
  490.     return next(startpos - 1, bit);
  491.   else
  492.     return previous(rep->len + startpos + 1, bit);
  493. }
  494.  
  495. inline void BitString::right_trim(int b)
  496. {
  497.   setlength(previous(rep->len, !b) + 1);
  498. }
  499.  
  500. inline void BitString::left_trim(int b)
  501. {
  502.   int p = next(-1, !b);
  503.   if (p < 0)
  504.     setlength(0);
  505.   else
  506.     copy(rep->s, p, rep->len);
  507. }
  508.  
  509. inline int BitString::operator ! ()
  510. {
  511.   return rep->len == 0;
  512. }
  513.  
  514. //#endif
  515.  
  516. #endif
  517.  
  518.