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