home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 7 / FreshFishVol7.bin / bbs / gnu / libg++-2.6-fsf.lha / libg++-2.6 / libg++ / src / BitString.h < prev    next >
C/C++ Source or Header  |  1994-05-22  |  20KB  |  762 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 _BitString_h
  20. #ifdef __GNUG__
  21. #pragma interface
  22. #endif
  23.  
  24. #define _BitString_h 1
  25.  
  26. #include <stream.h>
  27. #include <limits.h>
  28.  
  29. #include <bitprims.h>
  30. #define BITSTRBITS  _BS_BITS_PER_WORD
  31.  
  32. struct BitStrRep
  33. {
  34.   unsigned int    len;          // length in bits
  35.   unsigned short  sz;           // allocated slots
  36.   _BS_word        s[1];         // bits start here
  37. };
  38.  
  39. extern BitStrRep*  BStr_alloc(BitStrRep*, const _BS_word*, int, int,int);
  40. extern BitStrRep*  BStr_resize(BitStrRep*, int);
  41. extern BitStrRep*  BStr_copy(BitStrRep*, const BitStrRep*);
  42. extern BitStrRep*  cmpl(const BitStrRep*, BitStrRep*);
  43. extern BitStrRep*  and(const BitStrRep*, const BitStrRep*, BitStrRep*);
  44. extern BitStrRep*  or(const BitStrRep*, const BitStrRep*, BitStrRep*);
  45. extern BitStrRep*  xor(const BitStrRep*, const BitStrRep*, BitStrRep*);
  46. extern BitStrRep*  diff(const BitStrRep*, const BitStrRep*, BitStrRep*);
  47. extern BitStrRep*  cat(const BitStrRep*, const BitStrRep*, BitStrRep*);
  48. extern BitStrRep*  cat(const BitStrRep*, unsigned int, BitStrRep*);
  49. extern BitStrRep*  lshift(const BitStrRep*, int, BitStrRep*);
  50.  
  51.  
  52. class BitString;
  53. class BitPattern;
  54.  
  55. class BitStrBit
  56. {
  57. protected:
  58.   BitString&        src;
  59.   unsigned int      pos;
  60.  
  61.  public:
  62.                     BitStrBit(BitString& v, int p);
  63.                     BitStrBit(const BitStrBit& b);
  64.                    ~BitStrBit();
  65.                     operator unsigned int() const;
  66.   int               operator =  (unsigned int b);
  67. };
  68.  
  69. class BitSubString
  70. {
  71.   friend class      BitString;
  72.   friend class      BitPattern;
  73.  
  74. protected:
  75.  
  76.   BitString&        S;
  77.   unsigned int      pos;
  78.   unsigned int      len;
  79.  
  80.                     BitSubString(BitString& x, int p, int l);
  81.                     BitSubString(const BitSubString& x);
  82. public:
  83.                     ~BitSubString();
  84.  
  85.   BitSubString&     operator =  (const BitString&);
  86.   BitSubString&     operator =  (const BitSubString&);
  87.  
  88.   int               length() const;
  89.   int               empty() const;
  90.  
  91.   int               OK() const;
  92. };
  93.  
  94. class BitString
  95. {
  96.   friend class       BitSubString;
  97.   friend class       BitPattern;
  98. protected:
  99.   BitStrRep*         rep;
  100.  
  101.   int                search(int, int, const _BS_word*, int, int) const;
  102.   int                match(int, int, int, const _BS_word*,int,int) const;
  103.   BitSubString       _substr(int first, int l);
  104.  
  105. public:
  106.  
  107. // constructors
  108.                      BitString();
  109.                      BitString(const BitString&);
  110.                      BitString(const BitSubString& y);
  111.  
  112.                     ~BitString();
  113.  
  114.   BitString&         operator =  (unsigned int bit);
  115.   BitString&         operator =  (const BitString& y);
  116.   BitString&         operator =  (const BitSubString& y);
  117.  
  118. // equality & subset tests
  119.  
  120.   friend int         operator == (const BitString&, const BitString&);
  121.   friend int         operator != (const BitString&, const BitString&);
  122.   friend int         operator <  (const BitString&, const BitString&);
  123.   friend int         operator <= (const BitString&, const BitString&);
  124.   friend int         operator >  (const BitString&, const BitString&);
  125.   friend int         operator >= (const BitString&, const BitString&);
  126.  
  127. // procedural versions of operators
  128.  
  129.  
  130.   friend void        and(const BitString&, const BitString&, BitString&);
  131.   friend void        or(const BitString&, const BitString&, BitString&);
  132.   friend void        xor(const BitString&, const BitString&, BitString&);
  133.   friend void        diff(const BitString&, const BitString&, BitString&);
  134.   friend void        cat(const BitString&, const BitString&, BitString&);
  135.   friend void        cat(const BitString&, unsigned int, BitString&);
  136.   friend void        lshift(const BitString&, int, BitString&);
  137.   friend void        rshift(const BitString&, int, BitString&);
  138.  
  139.   friend void        complement(const BitString&, BitString&);
  140.  
  141.   friend int         lcompare(const BitString&, const BitString&); 
  142.  
  143. // assignment-based operators
  144. // (constuctive versions decalred inline below
  145.  
  146.   BitString&         operator |= (const BitString&);
  147.   BitString&         operator &= (const BitString&);
  148.   BitString&         operator -= (const BitString&);
  149.   BitString&         operator ^= (const BitString&);
  150.   BitString&         operator += (const BitString&);
  151.   BitString&         operator += (unsigned int b);
  152.   BitString&         operator <<=(int s);
  153.   BitString&         operator >>=(int s);
  154.  
  155.   void               complement();
  156.  
  157. // individual bit manipulation
  158.  
  159.   void               set(int pos);
  160.   void               set(int from, int to);
  161.   void               set();
  162.  
  163.   void               clear(int pos);
  164.   void               clear(int from, int to);
  165.   void               clear(); 
  166.  
  167.   void               invert(int pos);
  168.   void               invert(int from, int to);
  169.  
  170.   int                test(int pos) const;
  171.   int                test(int from, int to) const;
  172.  
  173.   void               assign(int p, unsigned int bit);
  174.  
  175. // indexing
  176.  
  177.   BitStrBit          operator [] (int pos);
  178.  
  179. // iterators
  180.  
  181.   int                first(unsigned int bit = 1) const;
  182.   int                last(unsigned int b = 1) const;
  183.  
  184.   int                next(int pos, unsigned int b = 1) const;
  185.   int                prev(int pos, unsigned int b = 1) const;
  186.   int                previous(int pos, unsigned int b = 1) const
  187.     { return prev(pos, b); } /* Obsolete synonym */
  188.  
  189. // searching & matching
  190.  
  191.   int                index(unsigned int bit, int startpos = 0) const ;      
  192.   int                index(const BitString&, int startpos = 0) const;
  193.   int                index(const BitSubString&, int startpos = 0) const;
  194.   int                index(const BitPattern&, int startpos = 0) const;
  195.  
  196.   int                contains(const BitString&) const;
  197.   int                contains(const BitSubString&) const;
  198.   int                contains(const BitPattern&) const;
  199.  
  200.   int                contains(const BitString&, int pos) const;
  201.   int                contains(const BitSubString&, int pos) const;
  202.   int                contains(const BitPattern&, int pos) const;
  203.  
  204.   int                matches(const BitString&, int pos = 0) const;
  205.   int                matches(const BitSubString&, int pos = 0) const;
  206.   int                matches(const BitPattern&, int pos = 0) const;
  207.  
  208. // BitSubString extraction
  209.  
  210.   BitSubString       at(int pos, int len);
  211.   BitSubString       at(const BitString&, int startpos = 0); 
  212.   BitSubString       at(const BitSubString&, int startpos = 0); 
  213.   BitSubString       at(const BitPattern&, int startpos = 0); 
  214.  
  215.   BitSubString       before(int pos);
  216.   BitSubString       before(const BitString&, int startpos = 0);
  217.   BitSubString       before(const BitSubString&, int startpos = 0);
  218.   BitSubString       before(const BitPattern&, int startpos = 0);
  219.  
  220.   BitSubString       after(int pos);
  221.   BitSubString       after(const BitString&, int startpos = 0);
  222.   BitSubString       after(const BitSubString&, int startpos = 0);
  223.   BitSubString       after(const BitPattern&, int startpos = 0);
  224.  
  225. // other friends & utilities
  226.  
  227.   friend BitString   common_prefix(const BitString&, const BitString&, 
  228.                                    int pos = 0);
  229.   friend BitString   common_suffix(const BitString&, const BitString&, 
  230.                                    int pos = -1);
  231.   friend BitString   reverse(const BitString&);
  232.  
  233.   void               right_trim(unsigned int b