⟦de64a7b86⟧

TextFile

// 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
#pragma once

#define _BitString_h 1

#include <stream.h>
#include <values.h>

#define BITSTRBITS   BITS(short)

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

  friend BitStrRep*  BStr_alloc(BitStrRep*, unsigned short*, int, int, int);
  friend BitStrRep*  BStr_resize(BitStrRep*, int);
  friend BitStrRep*  BStr_copy(BitStrRep*, BitStrRep*);
  friend BitStrRep*  cmpl(BitStrRep*, BitStrRep*);
  friend BitStrRep*  and(BitStrRep*, BitStrRep*, BitStrRep*);
  friend BitStrRep*  or(BitStrRep*, BitStrRep*, BitStrRep*);
  friend BitStrRep*  xor(BitStrRep*, BitStrRep*, BitStrRep*);
  friend BitStrRep*  difference(BitStrRep*, BitStrRep*, BitStrRep*);
  friend BitStrRep*  concat(BitStrRep*, BitStrRep*, BitStrRep*);
  friend BitStrRep*  concat(BitStrRep*, int, BitStrRep*);
  friend BitStrRep*  rshift(BitStrRep*, int, BitStrRep*);

};

extern BitStrRep    _nilBitStrRep;

class BitString;
class BitPattern;
class BitStrTmp;

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

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

class BitSubString
{
  friend class      BitString;
  friend class      BitStrTmp;
  friend class      BitPattern;

protected:

  BitString*        S;
  int               pos;
  int               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();

  int               OK();
};

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

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

public:

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

                     ~BitString();

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

// 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


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

  BitStrTmp          operator ~ ();
  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);
  int                test(int from, int to);

  void               assign(int p, int bit);

// indexing

  BitStrBit          operator [] (int pos);

// 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 BitStrTmp   common_prefix(BitString& x, BitString& y, int pos = 0);
  friend BitStrTmp   common_suffix(BitString& x, BitString& y, int pos = -1);
  friend BitStrTmp   reverse(BitString& x);

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

// status

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

// convertors & IO

  friend BitStrTmp   atoBitString(const char* s, char f='0', char t='1');
  friend const char* BitStringtoa(BitString& x, char f='0', char t='1');

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

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

// misc

  void               error(char* msg);

// 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');

  int                OK();
};

class BitStrTmp : public BitString
{
  friend class       BitSubString;
  friend class       BitString;
public:
                     BitStrTmp(BitStrRep*);
                     BitStrTmp(BitString& x);
                     BitStrTmp(BitStrTmp& x);
                     ~BitStrTmp();

  BitStrTmp          operator |  (BitString& y);
  BitStrTmp          operator &  (BitString& y);
  BitStrTmp          operator -  (BitString& y);
  BitStrTmp          operator ^  (BitString& y);
  BitStrTmp          operator +  (BitString& y);
  BitStrTmp          operator +  (int b);
  BitStrTmp          operator << (int s);
  BitStrTmp          operator >> (int s);

  BitStrTmp          operator ~ ();
};

class BitPattern
{
public:
  BitString          pattern;
  BitString          mask;

                     BitPattern();
                     BitPattern(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 short*, int, int);
  int               match(unsigned short* xs, int, int, int);

  int               OK();
};


//#ifdef __OPTIMIZE__


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

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

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

inline BitStrTmp shorttoBitString(unsigned short w)
{ 
  return BStr_alloc(0, &w, 0, BITSTRBITS, BITSTRBITS);
}

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


inline BitStrTmp::BitStrTmp(BitStrRep* r)
{ 
  rep = r;
}

inline BitStrTmp::BitStrTmp(BitStrTmp& x)
{
  rep = x.rep; x.rep = &_nilBitStrRep;
}

inline BitStrTmp::BitStrTmp(BitString& x)
{
  rep = x.rep; x.rep = &_nilBitStrRep;
}

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

inline BitString::BitString(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;
}

inline BitStrTmp::~BitStrTmp() {}

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

inline void BitString::operator =  (BitStrTmp& y)
{ 
  if (rep != &_nilBitStrRep) delete rep;
  rep = y.rep; y.rep = &_nilBitStrRep; 
}

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

inline void BitString::operator=(BitSubString&  y)
{
  rep = BStr_alloc(rep, y.S->rep->s, y.pos, y.pos+y.len, y.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(BitPattern& b)
{ 
  pattern = b.pattern; mask = b.mask;
}

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

inline BitStrTmp  BitString::operator & (BitString& y)
{
  return and(rep, y.rep, 0);
}

inline BitStrTmp   BitString::operator & (BitStrTmp& y)
{
  y.rep =  and(rep, y.rep, y.rep); return y;
}

inline BitStrTmp   BitStrTmp::operator & (BitString& y)
{
  rep =  and(rep, y.rep, rep); return *this;
}

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


inline BitStrTmp  BitString::operator | (BitString& y)
{
  return or(rep, y.rep, 0);
}

inline BitStrTmp   BitString::operator | (BitStrTmp& y)
{
  y.rep =  or(rep, y.rep, y.rep); return y;
}

inline BitStrTmp   BitStrTmp::operator | (BitString& y)
{
  rep =  or(rep, y.rep, rep); return *this;
}

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

inline BitStrTmp  BitString::operator ^ (BitString& y)
{
  return xor(rep, y.rep, 0);
}

inline BitStrTmp   BitString::operator ^ (BitStrTmp& y)
{
  y.rep =  xor(rep, y.rep, y.rep); return y;
}

inline BitStrTmp   BitStrTmp::operator ^ (BitString& y)
{
  rep =  xor(rep, y.rep, rep); return *this;
}

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


inline BitStrTmp  BitString::operator - (BitString& y)
{
  return difference(rep, y.rep, 0);
}

inline BitStrTmp   BitString::operator - (BitStrTmp& y)
{
  y.rep =  difference(rep, y.rep, y.rep); return y;
}

inline BitStrTmp   BitStrTmp::operator - (BitString& y)
{
  rep =  difference(rep, y.rep, rep); return *this;
}

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

inline BitStrTmp  BitString::operator + (BitString& y)
{
  return concat(rep, y.rep, 0);
}

inline BitStrTmp  BitString::operator + (int bit)
{
  return concat(rep, bit, 0);
}

inline BitStrTmp   BitString::operator + (BitStrTmp& y)
{
  y.rep =  concat(rep, y.rep, y.rep); return y;
}

inline BitStrTmp   BitStrTmp::operator + (BitString& y)
{
  rep =  concat(rep, y.rep, rep); return *this;
}

inline BitStrTmp   BitStrTmp::operator + (int bit)
{
  rep =  concat(rep, bit, rep); return *this;
}

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

inline void        BitString::operator += (int bit)
{
  rep =  concat(rep, bit, rep);
}

inline BitStrTmp  BitString::operator << (int y)
{
  return rshift(rep, y, 0);
}

inline BitStrTmp   BitStrTmp::operator << (int y)
{
  rep =  rshift(rep, y, rep); return *this;
}

inline void        BitString::operator <<= (int y)
{
  rep =  rshift(rep, y, rep);
}

inline BitStrTmp  BitString::operator >> (int y)
{
  return rshift(rep, -y, 0);
}

inline BitStrTmp   BitStrTmp::operator >> (int y)
{
  rep =  rshift(rep, -y, rep); return *this;
}

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

inline void        BitString::complement()
{
  rep =  cmpl(rep, rep);
}

inline BitStrTmp   BitStrTmp::operator ~()
{
  rep =  cmpl(rep, rep); return *this;
}

inline BitStrTmp  BitString::operator ~()
{
  return cmpl(rep, 0);
}

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 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)
{
  int nb = (b == 0)? 1 : 0;
  rep = BStr_resize(rep, previous(rep->len, nb) + 1);
}

inline void BitString::left_trim(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)
{
  return ((unsigned)(i) >= rep->len)? 0 : 
         ((rep->s[BitStr_index(i)] & (1 << (BitStr_pos(i)))) != 0);
}


inline BitStrBit::BitStrBit(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 int()
{
  return src->test(pos);
}

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

inline int BitStrBit::operator == (int b)
{
  return src->test(pos) == b;
}

inline int BitStrBit::operator != (int b)
{
  return src->test(pos) != b;
}

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

//#endif

#endif
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦de64a7b86⟧ TextFile

Derivation

TextFile
