home *** CD-ROM | disk | FTP | other *** search
- // This may look like C code, but it is really -*- C++ -*-
- /*
- Copyright (C) 1988 Free Software Foundation
- written by Doug Lea (dl@rocky.oswego.edu)
-
- This file is part of GNU CC.
-
- GNU CC is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY. No author or distributor
- accepts responsibility to anyone for the consequences of using it
- or for whether it serves any particular purpose or works at all,
- unless he says so in writing. Refer to the GNU CC General Public
- License for full details.
-
- Everyone is granted permission to copy, modify and redistribute
- GNU CC, but only under the conditions described in the
- GNU CC General Public License. A copy of this license is
- supposed to have been given to you along with GNU CC so you
- can know your rights and responsibilities. It should be in a
- file named COPYING. Among other things, the copyright notice
- and this notice must be preserved on all copies.
- */
-
- #ifndef _BitString_h
-
- #define _BitString_h 1
-
- #include <stream.h>
-
- struct _BitStringrep
- {
- unsigned long len; // length in bits
- unsigned short sz; // allocated slots
- short ref; // reference count
- unsigned long s[1]; // bits start here
- };
-
- extern _BitStringrep _nil_BitStringrep;
-
- class BitString;
- class BitPattern;
-
- class BitSubString
- {
- friend class BitString;
- friend class BitPattern;
-
- BitString* S;
- long pos;
- long len;
-
- BitSubString(BitString* x, int p, int l);
- BitSubString(BitSubString& x);
- public:
- ~BitSubString();
-
- void operator = (BitString& y);
- void operator = (BitSubString& y);
- int length();
- int empty();
- };
-
- class BitString
- {
- friend class BitSubString;
- friend class BitPattern;
-
- _BitStringrep* rep;
-
- void copy(unsigned long*, int, int);
- int search(int, int, unsigned long*, int, int);
- int match(int, int, int, unsigned long*, int, int);
-
- public:
-
- // constructors
- BitString();
- BitString(BitString&);
- BitString(BitSubString& y);
-
- ~BitString();
-
- BitString& operator = (BitString& y);
- BitString& operator = (BitSubString& y);
- BitString& nullify();
-
- // equality & subset tests
-
- friend int operator == (BitString& x, BitString& y);
- friend int operator != (BitString& x, BitString& y);
- friend int operator < (BitString& x, BitString& y);
- friend int operator <= (BitString& x, BitString& y);
- friend int operator > (BitString& x, BitString& y);
- friend int operator >= (BitString& x, BitString& y);
-
- friend int lcompare(BitString& x, BitString& y); // lexigraphic comp
-
- // set operators
-
- friend BitString operator | (BitString& x, BitString& y);
- friend BitString operator & (BitString& x, BitString& y);
- friend BitString operator - (BitString& x, BitString& y);
- friend BitString operator ^ (BitString& x, BitString& y);
- friend BitString operator << (BitString& x, int s);
- friend BitString operator >> (BitString& x, int s);
-
- BitString operator ~ ();
- BitString& complement();
-
- BitString& operator |= (BitString& y);
- BitString& operator &= (BitString& y);
- BitString& operator -= (BitString& y);
- BitString& operator ^= (BitString& y);
- BitString& operator <<=(int s);
- BitString& operator >>=(int s);
-
- // concatenation
-
- friend BitString operator + (BitString& x, BitString& y);
- BitString& operator += (BitString& y);
-
- // individual bit manipulation
-
- void set(int pos);
- void set(int from, int to);
-
- void clear(int pos);
- void clear(int from, int to);
-
- void invert(int pos);
- void invert(int from, int to);
-
- int test(int pos);
- int test(int from, int to);
-
- // iterators
-
- int first(int b = 1);
- int last(int b = 1);
-
- int next(int pos, int b = 1);
- int previous(int pos, int b = 1);
-
- // searching & matching
-
- int index(int bit, int startpos = 0);
- int index(BitString& y, int startpos = 0);
- int index(BitSubString& y, int startpos = 0);
- int index(BitPattern& r, int startpos = 0);
-
- int contains(BitString& y);
- int contains(BitSubString& y);
- int contains(BitPattern& r);
-
- int contains(BitString& y, int pos);
- int contains(BitSubString& y, int pos);
- int contains(BitPattern& r, int pos);
-
- int matches(BitString& y, int pos = 0);
- int matches(BitSubString& y, int pos = 0);
- int matches(BitPattern& r, int pos = 0);
-
- // BitSubString extraction
-
- BitSubString at(int pos, int len);
- BitSubString at(BitString& x, int startpos = 0);
- BitSubString at(BitSubString& x, int startpos = 0);
- BitSubString at(BitPattern& r, int startpos = 0);
-
- BitSubString before(int pos);
- BitSubString before(BitString& x, int startpos = 0);
- BitSubString before(BitSubString& x, int startpos = 0);
- BitSubString before(BitPattern& r, int startpos = 0);
-
- BitSubString after(int pos);
- BitSubString after(BitString& x, int startpos = 0);
- BitSubString after(BitSubString& x, int startpos = 0);
- BitSubString after(BitPattern& r, int startpos = 0);
-
- // other friends & utilities
-
- friend BitString common_prefix(BitString& x, BitString& y, int pos = 0);
- friend BitString common_suffix(BitString& x, BitString& y, int pos = -1);
- friend BitString reverse(BitString& x);
-
- void right_trim(int bit);
- void left_trim(int bit);
-
- // status
-
- int empty();
- int count(int bit = 1);
- int length();
- int operator ! ();
-
- // convertors & IO
-
- friend BitString atoBitString(const char* s, char f='0', char t='1');
- friend const char* BitStringtoa(BitString& x, char f='0', char t='1');
-
- friend ostream& operator << (ostream& s, BitString& x);
-
- // misc
-
- void setlength(int len, int clear = 0);
- void make_unique();
- void error(char* msg);
-
-
- // non-operator versions
-
- friend void and(BitString& x, BitString& y, BitString& r);
- friend void or(BitString& x, BitString& y, BitString& r);
- friend void xor(BitString& x, BitString& y, BitString& r);
- friend void difference(BitString& x, BitString& y, BitString& r);
- friend void concat(BitString& x, BitString& y, BitString& r);
- friend void rshift(BitString& x, int s, BitString& y);
- void copy(BitString& y);
-
- // indirect friends
-
- friend const char* BitPatterntoa(BitPattern& p,
- char f='0',char t='1',char x='X');
- friend BitPattern atoBitPattern(const char* s,
- char f='0',char t='1',char x='X');
- };
-
- class BitPattern
- {
- public:
- BitString pattern;
- BitString mask;
-
- BitPattern();
- BitPattern(BitString& p, BitString& m);
- ~BitPattern();
-
- friend const char* BitPatterntoa(BitPattern& p,
- char f='0',char t='1',char x='X');
- friend BitPattern atoBitPattern(const char* s,
- char f='0',char t='1',char x='X');
- friend ostream& operator << (ostream& s, BitPattern& x);
-
- int search(unsigned long*, int, int);
- int match(unsigned long* xs, int, int, int);
- };
-
- // error handlers
-
- extern void default_BitString_error_handler(char*);
- extern one_arg_error_handler_t BitString_error_handler;
-
- extern one_arg_error_handler_t
- set_BitString_error_handler(one_arg_error_handler_t f);
-
- //#ifdef __OPTIMIZE__
-
- inline BitString::BitString()
- {
- rep = &_nil_BitStringrep;
- }
-
- inline BitString::BitString(BitString& x)
- {
- rep = x.rep; if (rep->ref > 0) rep->ref++;
- }
-
- inline BitString::BitString(BitSubString& y)
- {
- rep = &_nil_BitStringrep; copy(y.S->rep->s, y.pos, y.pos+y.len);
- }
-
- inline BitString::~BitString()
- {
- if (rep->ref > 0 && --rep->ref == 0) delete rep;
- }
-
- inline BitString& BitString::operator = (BitString& y)
- {
- y.rep->ref++;
- if (rep->ref > 0 && --rep->ref == 0) delete rep;
- rep = y.rep;
- return *this;
- }
-
- inline BitString& BitString::nullify()
- {
- if (rep->ref > 0 && --rep->ref == 0) delete rep;
- rep = &_nil_BitStringrep;
- return *this;
- }
-
- inline BitString& BitString::operator=(BitSubString& y)
- {
- copy(y.S->rep->s, y.pos, y.pos+y.len); return *this;
- }
-
- inline void BitString::copy(BitString& y)
- {
- copy(y.rep->s, 0, y.rep->len);
- }
-
- inline BitSubString::BitSubString(BitSubString& x)
- {
- S = x.S; pos = x.pos; len = x.len;
- }
-
- inline BitSubString::~BitSubString() {}
-
- inline BitPattern::BitPattern(BitString& p, BitString& m)
- {
- pattern = p; mask = m;
- }
-
- inline BitPattern::BitPattern() {}
- inline BitPattern::~BitPattern() {}
-
- inline BitString& BitString::operator+=(BitString& y)
- {
- concat(*this, y, *this); return *this;
- }
-
- inline BitString operator + (BitString& x, BitString& y)
- {
- BitString r; concat(x, y, r); return r;
- }
-
- inline int BitString::length()
- {
- return rep->len;
- }
-
- inline int BitString::empty()
- {
- return rep->len == 0;
- }
-
- inline int BitString::index(BitString& y, int startpos = 0)
- {
- return search(startpos, rep->len, y.rep->s, 0, y.rep->len);
- }
-
- inline int BitString::index(BitSubString& y, int startpos = 0)
- {
- return search(startpos, rep->len, y.S->rep->s, y.pos, y.pos+y.len);
- }
-
- inline int BitString::contains(BitString& y)
- {
- return search(0, rep->len, y.rep->s, 0, y.rep->len) >= 0;
- }
-
- inline int BitString::contains(BitSubString& y)
- {
- return search(0, rep->len, y.S->rep->s, y.pos, y.pos+y.len) >= 0;
- }
-
- inline int BitString::contains(BitString& y, int p)
- {
- return match(p, rep->len, 0, y.rep->s, 0, y.rep->len);
- }
-
- inline int BitString::matches(BitString& y, int p = 0)
- {
- return match(p, rep->len, 1, y.rep->s, 0, y.rep->len);
- }
-
- inline int BitString::contains(BitSubString& y, int p)
- {
- return match(p, rep->len, 0, y.S->rep->s, y.pos, y.pos+y.len);
- }
-
- inline int BitString::matches(BitSubString& y, int p = 0)
- {
- return match(p, rep->len, 1, y.S->rep->s, y.pos, y.pos+y.len);
- }
-
- inline int BitString::contains(BitPattern& r)
- {
- return r.search(rep->s, 0, rep->len) >= 0;
- }
-
- inline int BitString::contains(BitPattern& r, int p)
- {
- return r.match(rep->s, p, rep->len, 0);
- }
-
- inline int BitString::matches(BitPattern& r, int p = 0)
- {
- return r.match(rep->s, p, rep->len, 1);
- }
-
- inline int BitString::index(BitPattern& r, int startpos = 0)
- {
- return r.search(rep->s, startpos, rep->len);
- }
-
- inline int BitSubString::length()
- {
- return len;
- }
-
- inline int BitSubString::empty()
- {
- return len == 0;
- }
-
- inline int operator != (BitString& x, BitString& y)
- {
- return !(x == y);
- }
-
- inline int operator>(BitString& x, BitString& y)
- {
- return y < x;
- }
-
- inline int operator>=(BitString& x, BitString& y)
- {
- return y <= x;
- }
-
- inline void BitString::make_unique()
- {
- if (rep->ref != 1) setlength(rep->len);
- }
-
- inline BitString operator & (BitString& x, BitString& y)
- {
- BitString r; and(x, y, r); return r;
- }
-
- inline BitString operator | (BitString& x, BitString& y)
- {
- BitString r; or(x, y, r); return r;
- }
-
- inline BitString operator ^ (BitString& x, BitString& y)
- {
- BitString r; xor(x, y, r); return r;
- }
-
- inline BitString operator - (BitString& x, BitString& y)
- {
- BitString r; difference(x, y, r); return r;
- }
-
- inline BitString& BitString::operator &= (BitString& y)
- {
- and(*this, y, *this); return *this;
- }
-
- inline BitString& BitString::operator |= (BitString& y)
- {
- or(*this, y, *this); return *this;
- }
-
- inline BitString& BitString::operator ^= (BitString& y)
- {
- xor(*this, y, *this); return *this;
- }
-
- inline BitString& BitString::operator -= (BitString& y)
- {
- difference(*this, y, *this); return *this;
- }
-
- inline BitString operator << (BitString& x, int s)
- {
- BitString r; rshift(x, s, r); return r;
- }
-
- inline BitString operator >> (BitString& x, int s)
- {
- BitString r; rshift(x, -s, r); return r;
- }
-
- inline BitString& BitString::operator <<= (int s)
- {
- rshift(*this, s, *this); return *this;
- }
-
- inline BitString& BitString::operator >>= (int s)
- {
- rshift(*this, -s, *this); return *this;
- }
-
- inline int BitString::first(int b = 1)
- {
- return next(-1, b);
- }
-
- inline int BitString::last(int b = 1)
- {
- return previous(rep->len, b);
- }
-
- inline int BitString::index(int bit, int startpos = 0)
- {
- if (startpos >= 0)
- return next(startpos - 1, bit);
- else
- return previous(rep->len + startpos + 1, bit);
- }
-
- inline void BitString::right_trim(int b)
- {
- setlength(previous(rep->len, !b) + 1);
- }
-
- inline void BitString::left_trim(int b)
- {
- int p = next(-1, !b);
- if (p < 0)
- setlength(0);
- else
- copy(rep->s, p, rep->len);
- }
-
- inline int BitString::operator ! ()
- {
- return rep->len == 0;
- }
-
- //#endif
-
- #endif
-
-