// 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 the GNU C++ Library.  This library is free
software; you can redistribute it and/or modify it under the terms of
the GNU Library General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your
option) any later version.  This library is distributed in the hope
that it will be useful, but WITHOUT ANY WARRANTY; without even the
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE.  See the GNU Library General Public License for more details.
You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free Software
Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#ifndef _BitString_h
#ifdef __GNUG__
#pragma interface
#endif

#define _BitString_h 1

#include <stream.h>
#include <limits.h>

#define BITSTRBITS  (sizeof(short) * CHAR_BIT)

struct BitStrRep
{
  unsigned int    len;          // length in bits
  unsigned short  sz;           // allocated slots
  unsigned short  s[1];         // bits start here
};

extern BitStrRep*  BStr_alloc(BitStrRep*, const unsigned short*, int, int,int);
extern BitStrRep*  BStr_resize(BitStrRep*, int);
extern BitStrRep*  BStr_copy(BitStrRep*, const BitStrRep*);
extern BitStrRep*  cmpl(const BitStrRep*, BitStrRep*);
extern BitStrRep*  and(const BitStrRep*, const BitStrRep*, BitStrRep*);
extern BitStrRep*  or(const BitStrRep*, const BitStrRep*, BitStrRep*);
extern BitStrRep*  xor(const BitStrRep*, const BitStrRep*, BitStrRep*);
extern BitStrRep*  diff(const BitStrRep*, const BitStrRep*, BitStrRep*);
extern BitStrRep*  cat(const BitStrRep*, const BitStrRep*, BitStrRep*);
extern BitStrRep*  cat(const BitStrRep*, unsigned int, BitStrRep*);
extern BitStrRep*  lshift(const BitStrRep*, int, BitStrRep*);


class BitString;
class BitPattern;

class BitStrBit
{
protected:
  BitString&        src;
  unsigned int      pos;

 public:
                    BitStrBit(BitString& v, int p);
                    BitStrBit(const BitStrBit& b);
                   ~BitStrBit();
                    operator unsigned int() const;
  int               operator =  (unsigned int b);
};

class BitSubString
{
  friend class      BitString;
  friend class      BitPattern;

protected:

  BitString&        S;
  unsigned int      pos;
  unsigned int      len;

                    BitSubString(BitString& x, int p, int l);
                    BitSubString(const BitSubString& x);
public:
                    ~BitSubString();

  void              operator =  (const BitString&);
  void              operator =  (const BitSubString&);

  int               length() const;
  int               empty() const;

  int               OK() const;
};

class BitString
{
  friend class       BitSubString;
  friend class       BitPattern;
protected:
  BitStrRep*         rep;

  int                search(int, int, const unsigned short*, int, int) const;
  int                match(int, int, int, const unsigned short*,int,int) const;
  BitSubString       _substr(int first, int l);

public:

// constructors
                     BitString();
                     BitString(const BitString&);
                     BitString(const BitSubString& y);

                    ~BitString();

  void               operator =  (unsigned int bit);
  void               operator =  (const BitString& y);
  void               operator =  (const BitSubString& y);

// equality & subset tests

  friend int         operator == (const BitString&, const BitString&);
  friend int         operator != (const BitString&, const BitString&);
  friend int         operator <  (const BitString&, const BitString&);
  friend int         operator <= (const BitString&, const BitString&);
  friend int         operator >  (const BitString&, const BitString&);
  friend int         operator >= (const BitString&, const BitString&);

// procedural versions of operators


  friend void        and(const BitString&, const BitString&, BitString&);
  friend void        or(const BitString&, const BitString&, BitString&);
  friend void        xor(const BitString&, const BitString&, BitString&);
  friend void        diff(const BitString&, const BitString&, BitString&);
  friend void        cat(const BitString&, const BitString&, BitString&);
  friend void        cat(const BitString&, unsigned int, BitString&);
  friend void        lshift(const BitString&, int, BitString&);
  friend void        rshift(const BitString&, int, BitString&);

  friend void        complement(const BitString&, BitString&);

  friend int         lcompare(const BitString&, const BitString&); 

// assignment-based operators
// (constuctive versions decalred inline below

  void               operator |= (const BitString&);
  void               operator &= (const BitString&);
  void               operator -= (const BitString&);
  void               operator ^= (const BitString&);
  void               operator += (const BitString&);
  void               operator += (unsigned int b);
  void               operator <<=(int s);
  void               operator >>=(int s);

  void               complement();

// individual bit manipulation

  void               set(int pos);
  void               set(int from, int to);
  void               set();

  void               clear(int pos);
  void               clear(int from, int to);
  void               clear(); 

  void               invert(int pos);
  void               invert(int from, int to);

  int                test(int pos) const;
  int                test(int from, int to) const;

  void               assign(int p, unsigned int bit);

// indexing

  BitStrBit          operator [] (int pos);

// iterators

  int                first(unsigned int bit = 1) const;
  int                last(unsigned int b = 1) const;

  int                next(int pos, unsigned int b = 1) const;
  int                prev(int pos, unsigned int b = 1) const;
  int                previous(int pos, unsigned int b = 1) const
    { return prev(pos, b); } /* Obsolete synonym */

// searching & matching

  int                index(unsigned int bit, int startpos = 0) const ;      
  int                index(const BitString&, int startpos = 0) const;
  int                index(const BitSubString&, int startpos = 0) const;
  int                index(const BitPattern&, int startpos = 0) const;

  int                contains(const BitString&) const;
  int                contains(const BitSubString&) const;
  int                contains(const BitPattern&) const;

  int                contains(const BitString&, int pos) const;
  int                contains(const BitSubString&, int pos) const;
  int                contains(const BitPattern&, int pos) const;

  int                matches(const BitString&, int pos = 0) const;
  int                matches(const BitSubString&, int pos = 0) const;
  int                matches(const BitPattern&, int pos = 0) const;

// BitSubString extraction

  BitSubString       at(int pos, int len);
  BitSubString       at(const BitString&, int startpos = 0); 
  BitSubString       at(const BitSubString&, int startpos = 0); 
  BitSubString       at(const BitPattern&, int startpos = 0); 

  BitSubString       before(int pos);
  BitSubString       before(const BitString&, int startpos = 0);
  BitSubString       before(const BitSubString&, int startpos = 0);
  BitSubString       before(const BitPattern&, int startpos = 0);

  BitSubString       after(int pos);
  BitSubString       after(const BitString&, int startpos = 0);
  BitSubString       after(const BitSubString&, int startpos = 0);
  BitSubString       after(const BitPattern&, int startpos = 0);

// other friends & utilities

  friend BitString   common_prefix(const BitString&, const BitString&, 
                                   int pos = 0);
  friend BitString   common_suffix(const BitString&, const BitString&, 
                                   int pos = -1);
  friend BitString   reverse(const BitString&);

  void               right_trim(unsigned int bit);
  void               left_trim(unsigned int bit);

// status

  int                empty() const ;
  int                count(unsigned int bit = 1) const;
  int                length() const;

// convertors & IO

  friend BitString   atoBitString(const char* s, char f='0', char t='1');
  // BitStringtoa is deprecated; do not use in new programs!
  friend const char* BitStringtoa(const BitString&, char f='0', char t='1');
  void		     printon(ostream&, char f='0', char t='1') const;

  friend BitString   shorttoBitString(unsigned short);
  friend BitString   longtoBitString(unsigned long);

  friend ostream&    operator << (ostream& s, const BitString&);

// misc

  void      error(const char* msg) const;

// indirect friends

  friend BitPattern  atoBitPattern(const char* s,
                                  char f='0',char t='1',char x='X');
  friend const char* BitPatterntoa(const BitPattern& p, 
                                  char f='0',char t='1',char x='X');
  int                OK() const;
};


class BitPattern
{
public:
  BitString          pattern;
  BitString          mask;

                     BitPattern();
                     BitPattern(const BitPattern&);
                     BitPattern(const BitString& p, const BitString& m);

                    ~BitPattern();

  friend const char* BitPatterntoa(const BitPattern& p, 
                                 char f/*='0'*/,char t/*='1'*/,char x/*='X'*/);
  void		     printon(ostream&, char f='0',char t='1',char x='X') const;
  friend BitPattern atoBitPattern(const char* s, char f,char t, char x);
  friend ostream&   operator << (ostream& s, const BitPattern&);

  int               search(const unsigned short*, int, int) const;
  int               match(const unsigned short* xs, int, int, int) const;

  int               OK() const;
};

BitString  operator & (const BitString& x, const BitString& y);
BitString  operator | (const BitString& x, const BitString& y);
BitString  operator ^ (const BitString& x, const BitString& y);
BitString  operator << (const BitString& x, int y);
BitString  operator >> (const BitString& x, int y);
BitString  operator - (const BitString& x, const BitString& y);
BitString  operator + (const BitString& x, const BitString& y);
BitString  operator + (const BitString& x, unsigned int y);
BitString  operator ~ (const BitString& x);
int operator != (const BitString& x, const BitString& y);
int operator>(const BitString& x, const BitString& y);
int operator>=(const BitString& x, const BitString& y);

extern BitStrRep    _nilBitStrRep;
extern BitString    _nil_BitString;

// primitive bit extraction

// These must be inlined regardless of optimization.

inline int BitStr_index(int l) { return (unsigned)(l) / BITSTRBITS; }

inline int BitStr_pos(int l) { return l & (BITSTRBITS - 1); }


// constructors & assignment

inline BitString::BitString() :rep(&_nilBitStrRep) {}

inline BitString::BitString(const BitString& x) :rep(BStr_copy(0, x.rep)) {}

inline BitString::BitString(const BitSubString& y) 
   :rep (BStr_alloc(0, y.S.rep->s, y.pos, y.pos+y.len, y.len)) {}

inline BitString::~BitString()
{ 
  if (rep != &_nilBitStrRep) delete rep;
}

#if defined(__GNUG__) && !defined(NO_NRV)

inline BitString shorttoBitString(unsigned short w) return r
{ 
  r.rep = BStr_alloc(0, &w, 0, BITSTRBITS, BITSTRBITS);
}

inline BitString longtoBitString(unsigned long w) return r
{ 
  unsigned short u[2];
  u[0] = w & ((unsigned short)(~(0)));
  u[1] = w >> BITSTRBITS;
  r.rep = BStr_alloc(0, &u[0], 0, 2*BITSTRBITS, 2*BITSTRBITS);
}

#else

inline BitString shorttoBitString(unsigned short w) 
{ 
  BitString r; r.rep = BStr_alloc(0, &w, 0, BITSTRBITS, BITSTRBITS); return r;
}

inline BitString longtoBitString(unsigned long w) 
{ 
  BitString r;
  unsigned short u[2];
  u[0] = w & ((unsigned short)(~(0)));
  u[1] = w >> BITSTRBITS;
  r.rep = BStr_alloc(0, &u[0], 0, 2*BITSTRBITS, 2*BITSTRBITS);
  return r;
}

#endif

inline void BitString::operator =  (const BitString& y)
{ 
  rep = BStr_copy(rep, y.rep);
}

inline void BitString::operator = (unsigned int b)
{ 
  unsigned short bit = b;
  rep = BStr_alloc(rep, &bit, 0, 1, 1);
}

inline void BitString::operator=(const BitSubString&  y)
{
  rep = BStr_alloc(rep, y.S.rep->s, y.pos, y.pos+y.len, y.len);
}

inline BitSubString::BitSubString(const BitSubString& x) 
    :S(x.S), pos(x.pos), len(x.len) {}

inline BitSubString::BitSubString(BitString& x, int p, int l)
     : S(x), pos(p), len(l) {}

inline BitSubString::~BitSubString() {}

inline BitPattern::BitPattern(const BitString& p, const BitString& m)
    :pattern(p), mask(m) {}

inline BitPattern::BitPattern(const BitPattern& b)
    :pattern(b.pattern), mask(b.mask) {}

inline BitPattern::BitPattern() {}
inline BitPattern::~BitPattern() {}


// procedural versions of operators

inline void and(const BitString& x, const BitString& y, BitString& r)
{
  r.rep = and(x.rep, y.rep, r.rep);
}

inline void or(const BitString& x, const BitString& y, BitString& r)
{
  r.rep = or(x.rep, y.rep, r.rep);
}

inline void xor(const BitString& x, const BitString& y, BitString& r)
{
  r.rep = xor(x.rep, y.rep, r.rep);
}

inline void diff(const BitString& x, const BitString& y, BitString& r)
{
  r.rep = diff(x.rep, y.rep, r.rep);
}

inline void cat(const BitString& x, const BitString& y, BitString& r)
{
  r.rep = cat(x.rep, y.rep, r.rep);
}

inline void cat(const BitString& x, unsigned int y, BitString& r)
{
  r.rep = cat(x.rep, y, r.rep);
}

inline void rshift(const BitString& x, int y, BitString& r)
{
  r.rep = lshift(x.rep, -y, r.rep);
}

inline void lshift(const BitString& x, int y, BitString& r)
{
  r.rep = lshift(x.rep, y, r.rep);
}

inline void complement(const BitString& x, BitString& r)
{
  r.rep = cmpl(x.rep, r.rep);
}

// operators


inline void BitString::operator &= (const BitString& y)
{
  and(*this, y, *this);
}


inline void BitString::operator |= (const BitString& y)
{
  or(*this, y, *this);
}

inline void BitString::operator ^= (const BitString& y)
{
  xor(*this, y, *this);
}

inline void BitString::operator <<= (int y)
{
  lshift(*this, y, *this);
}

inline void BitString::operator >>= (int y)
{
  rshift(*this, y, *this);
}

inline void BitString::operator -= (const BitString& y)
{
  diff(*this, y, *this);
}

inline void BitString::operator += (const BitString& y)
{
  cat(*this, y, *this);
}

inline void BitString::operator += (unsigned int y)
{
  cat(*this, y, *this);
}

inline void BitString::complement()
{
  ::complement(*this, *this);
}

#if defined(__GNUG__) && !defined(NO_NRV)

inline BitString  operator & (const BitString& x, const BitString& y) return r
{
  and(x, y, r);
}

inline BitString  operator | (const BitString& x, const BitString& y) return r
{
  or(x, y, r);
}

inline BitString  operator ^ (const BitString& x, const BitString& y) return r
{
  xor(x, y, r);
}

inline BitString  operator << (const BitString& x, int y) return r
{
  lshift(x, y, r);
}

inline BitString  operator >> (const BitString& x, int y) return r
{
  rshift(x, y, r);
}

inline BitString  operator - (const BitString& x, const BitString& y) return r
{
  diff(x, y, r);
}

inline BitString  operator + (const BitString& x, const BitString& y) return r
{
  cat(x, y, r);
}

inline BitString  operator + (const BitString& x, unsigned int y) return r
{
  cat(x, y, r);
}

inline BitString  operator ~ (const BitString& x) return r
{
  complement(x, r);
}

#else /* NO_NRV */

inline BitString  operator & (const BitString& x, const BitString& y) 
{
  BitString r; and(x, y, r); return r;
}

inline BitString  operator | (const BitString& x, const BitString& y) 
{
  BitString r; or(x, y, r); return r;
}

inline BitString  operator ^ (const BitString& x, const BitString& y) 
{
  BitString r; xor(x, y, r); return r;
}

inline BitString  operator << (const BitString& x, int y) 
{
  BitString r; lshift(x, y, r); return r;
}

inline BitString  operator >> (const BitString& x, int y) 
{
  BitString r; rshift(x, y, r); return r;
}

inline BitString  operator - (const BitString& x, const BitString& y) 
{
  BitString r; diff(x, y, r); return r;
}

inline BitString  operator + (const BitString& x, const BitString& y) 
{
  BitString r; cat(x, y, r); return r;
}

inline BitString  operator + (const BitString& x, unsigned int y) 
{
  BitString r; cat(x, y, r); return r;
}

inline BitString  operator ~ (const BitString& x) 
{
  BitString r; complement(x, r); return r;
}

#endif

// status, matching

inline int BitString::length() const
{ 
  return rep->len;
}

inline int BitString::empty() const
{ 
  return rep->len == 0;
}

inline int BitString::index(const BitString& y, int startpos) const
{   
  return search(startpos, rep->len, y.rep->s, 0, y.rep->len);
}

inline int BitString::index(const BitSubString& y, int startpos) const
{   
  return search(startpos, rep->len, y.S.rep->s, y.pos, y.pos+y.len);
}

inline int BitString::contains(const BitString& y) const
{   
  return search(0, rep->len, y.rep->s, 0, y.rep->len) >= 0;
}

inline int BitString::contains(const BitSubString& y) const
{   
  return search(0, rep->len, y.S.rep->s, y.pos, y.pos+y.len) >= 0;
}

inline int BitString::contains(const BitString& y, int p) const
{
  return match(p, rep->len, 0, y.rep->s, 0, y.rep->len);
}

inline int BitString::matches(const BitString& y, int p) const
{
  return match(p, rep->len, 1, y.rep->s, 0, y.rep->len);
}

inline int BitString::contains(const BitSubString& y, int p) const
{
  return match(p, rep->len, 0, y.S.rep->s, y.pos, y.pos+y.len);
}

inline int BitString::matches(const BitSubString& y, int p) const
{
  return match(p, rep->len, 1, y.S.rep->s, y.pos, y.pos+y.len);
}

inline int BitString::contains(const BitPattern& r) const
{
  return r.search(rep->s, 0, rep->len) >= 0;
}

inline int BitString::contains(const BitPattern& r, int p) const
{
  return r.match(rep->s, p, rep->len, 0);
}

inline int BitString::matches(const BitPattern& r, int p) const
{
  return r.match(rep->s, p, rep->len, 1);
}

inline int BitString::index(const BitPattern& r, int startpos) const
{
  return r.search(rep->s, startpos, rep->len);
}

inline  int BitSubString::length() const
{ 
  return len;
}

inline  int BitSubString::empty() const
{ 
  return len == 0;
}

inline int operator != (const BitString& x, const BitString& y)
{
  return !(x == y);
}

inline int operator>(const BitString& x, const BitString& y)
{
  return y < x;
}

inline int operator>=(const BitString& x, const BitString& y)
{
  return y <= x;
}

inline int BitString::first(unsigned int b) const
{
  return next(-1, b);
}

inline int BitString::last(unsigned int b) const
{
  return prev(rep->len, b);
}

inline int BitString::index(unsigned int bit, int startpos) const
{
  if (startpos >= 0)
    return next(startpos - 1, bit);
  else
    return prev(rep->len + startpos + 1, bit);
}

inline void BitString::right_trim(unsigned int b) 
{
  int nb = (b == 0)? 1 : 0;
  rep = BStr_resize(rep, prev(rep->len, nb) + 1);
}

inline void BitString::left_trim(unsigned int b)
{
  int nb = (b == 0)? 1 : 0;
  int p = next(-1, nb);
  rep = BStr_alloc(rep, rep->s, p, rep->len, rep->len - p);
}

inline int BitString::test(int i) const
{
  return ((unsigned)(i) >= rep->len)? 0 : 
         ((rep->s[BitStr_index(i)] & (1 << (BitStr_pos(i)))) != 0);
}


// subscripting

inline BitStrBit::BitStrBit(const BitStrBit& b) :src(b.src), pos(b.pos) {}

inline BitStrBit::BitStrBit(BitString& v, int p) :src(v), pos(p) {}

inline BitStrBit::~BitStrBit() {}

inline BitStrBit::operator unsigned int() const
{
  return src.test(pos);
}

inline int BitStrBit::operator = (unsigned int b)
{
  src.assign(pos, b); return b;
}

inline BitStrBit BitString::operator [] (int i)
{
  if ((unsigned)(i) >= rep->len) error("illegal bit index");
  return BitStrBit(*this, i);
}

inline BitSubString BitString::_substr(int first, int l)
{
  if (first < 0 || l <= 0 || (unsigned)(first + l) > rep->len)
    return BitSubString(_nil_BitString, 0, 0) ;
  else 
    return BitSubString(*this, first, l);
}

#endif