bitstring.cc

麻省理工开发的免费遗传算法类库GAlib,很好用

  const _BS_word* ys = pattern.rep->s;
  int righty = pattern.rep->len - 1;
  _BS_word* ms = mask.rep->s;
  int rightm = mask.rep->len - 1;

  int rightx;
  int rev = startx < 0;
  if (rev)
  {
    rightx = lengthx + startx;
    startx = rightx - righty;
    if (exact && startx != 0)
      return 0;
  }
  else
  {
    rightx = lengthx - 1;
    if (exact && rightx - startx != righty)
      return 0;
  }

  if (righty < 0) return 1;
  if (startx < 0 || startx >= lengthx) return 0;
  
  int xind = BitStr_index(startx);
  int xpos = BitStr_pos(startx);
  int yind = 0;

  int rightxind = BitStr_index(rightx);
  int rightyind = BitStr_index(righty);
  int rightmind = BitStr_index(rightm);

  for(;;)
  {
    _BS_word m = safe_borrow_hi(ms, yind, rightmind, 0);
    _BS_word x = safe_borrow_hi(xs, xind, rightxind, xpos) & m;
    _BS_word y = safe_borrow_hi(ys, yind, rightyind, 0) & m;
    if (x != y)
      return 0;
    else if (++yind > rightyind || ++xind > rightxind)
      return 1;
  }
}

BitSubString& BitSubString::operator = (const BitString& y)
{
  if (&S == &_nil_BitString)
    return *this;
  BitStrRep* targ = S.rep;

  unsigned int ylen = y.rep->len;
  int sl = targ->len - len + ylen;

  if (y.rep == targ || ylen > len)
  {
    BitStrRep* oldtarg = targ;
    targ = BStr_alloc(0, 0, 0, 0, sl);
    _BS_copy (targ->s, 0, oldtarg->s, 0, pos);
    copy_bits (targ->s, pos, y.rep->s, 0, ylen);
    copy_bits (targ->s, pos + ylen, oldtarg->s, pos+len, oldtarg->len-pos-len);
    delete oldtarg;
  }
  else if (len == ylen)
    copy_bits (targ->s, pos, y.rep->s, 0, len);
  else if (ylen < len)
  {
    copy_bits (targ->s, pos, y.rep->s, 0, ylen);
    copy_bits (targ->s, pos + ylen, targ->s, pos + len, targ->len - pos - len);
    targ->len = sl;
  }
  check_last(targ);
  S.rep = targ;
  return *this;
}

BitSubString& BitSubString::operator = (const BitSubString& y)
{
  if (&S == &_nil_BitString)
    return *this;
  BitStrRep* targ = S.rep;
  
  if (len == 0 || pos >= targ->len)
    return *this;
  
  int sl = targ->len - len + y.len;
  
  if (y.S.rep == targ || y.len > len)
  {
    BitStrRep* oldtarg = targ;
    targ = BStr_alloc(0, 0, 0, 0, sl);
    _BS_copy_0(targ->s, oldtarg->s, pos);
    copy_bits (targ->s, pos, y.S.rep->s, y.pos, y.len);
    copy_bits (targ->s, pos + y.len, oldtarg->s, pos+len,
	       oldtarg->len-pos-len);
    delete oldtarg;
  }
  else if (len == y.len)
    copy_bits (targ->s, pos, y.S.rep->s, y.pos, y.len);
  else if (y.len < len)
  {
    copy_bits (targ->s, pos, y.S.rep->s, y.pos, y.len);
    copy_bits (targ->s, pos + y.len, targ->s, pos + len,
	       targ->len - pos - len);
    targ->len = sl;
  }
  check_last(targ);
  S.rep = targ;
  return *this;
}

BitSubString BitString::at(int first, int len)
{
  return _substr(first, len);
}

BitSubString BitString::before(int pos)
{
  return _substr(0, pos);
}

BitSubString BitString::after(int pos)
{
  return _substr(pos + 1, rep->len - (pos + 1));
}

BitSubString BitString::at(const BitString& y, int startpos)
{
  int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  return _substr(first,  y.rep->len);
}

BitSubString BitString::before(const BitString& y, int startpos)
{
  int last = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  return _substr(0, last);
}

BitSubString BitString::after(const BitString& y, int startpos)
{
  int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  if (first >= 0) first += y.rep->len;
  return _substr(first, rep->len - first);
}


BitSubString BitString::at(const BitSubString& y, int startpos)
{
  int first = search(startpos, rep->len, y.S.rep->s, y.pos, y.len);
  return _substr(first, y.len);
}

BitSubString BitString::before(const BitSubString& y, int startpos)
{
  int last = search(startpos, rep->len, y.S.rep->s, y.pos, y.len);
  return _substr(0, last);
}

BitSubString BitString::after(const BitSubString& y, int startpos)
{
  int first = search(startpos, rep->len, y.S.rep->s, y.pos, y.len);
  if (first >= 0) first += y.len;
  return _substr(first, rep->len - first);
}

BitSubString BitString::at(const BitPattern& r, int startpos)
{
  int first = r.search(rep->s, startpos, rep->len);
  return _substr(first, r.pattern.rep->len);
}


BitSubString BitString::before(const BitPattern& r, int startpos)
{
  int first = r.search(rep->s, startpos, rep->len);
  return _substr(0, first);
}

BitSubString BitString::after(const BitPattern& r, int startpos)
{
  int first = r.search(rep->s, startpos, rep->len);
  if (first >= 0) first += r.pattern.rep->len;
  return _substr(first, rep->len - first);
}

#if defined(__GNUG__) && !defined(_G_NO_NRV)
#define RETURN(r) return
#define RETURNS(r) return r;
#define RETURN_OBJECT(TYPE, NAME) /* nothing */
#define USE_UNSIGNED 1 /* probably correct */
#else /* _G_NO_NRV */
#define RETURN(r) return r
#define RETURNS(r) /* nothing */
#define RETURN_OBJECT(TYPE, NAME) TYPE NAME;
#define USE_UNSIGNED 0 /* probably old bug */
#endif

BitString
common_prefix (const BitString& x, const BitString& y, int startpos)
     RETURNS(r)
{
  RETURN_OBJECT(BitString, r);
  unsigned int  xl = x.rep->len;
  unsigned int  yl = y.rep->len;

  unsigned int startx, starty;
  if (startpos < 0)
  {
    startx = xl + startpos;
    starty = yl + startpos;
  }
  else
    startx = starty = startpos;

  if (startx >= xl || starty >= yl)
    RETURN(r);

  const _BS_word* xs = &(x.rep->s[BitStr_index(startx)]);
  _BS_word a = *xs++;
  unsigned int xp = startx;

  const _BS_word* ys = &(y.rep->s[BitStr_index(starty)]);
  _BS_word b = *ys++;
  unsigned int yp = starty;

  for(; xp < xl && yp < yl; ++xp, ++yp)
  {
    _BS_word xbit = ((_BS_word)1) << (BitStr_pos(xp));
    _BS_word ybit = ((_BS_word)1) << (BitStr_pos(yp));
    if (((a & xbit) == 0) != ((b & ybit) == 0))
      break;
    if (xbit == MAXBIT)
      a = *xs++;
    if (ybit == MAXBIT)
      b = *ys++;
  }
  r.rep = BStr_alloc(0, x.rep->s, startx, xp, xp - startx);
  RETURN(r);
}


BitString
common_suffix (const BitString& x, const BitString& y, int startpos)
     RETURNS(r)
{
  RETURN_OBJECT(BitString, r);
  unsigned int  xl = x.rep->len;
  unsigned int  yl = y.rep->len;

  unsigned int startx, starty;
  if (startpos < 0)
  {
    startx = xl + startpos;
    starty = yl + startpos;
  }
  else
    startx = starty = startpos;

  if (startx >= xl || starty >= yl)
    RETURN(r);

  const _BS_word* xs = &(x.rep->s[BitStr_index(startx)]);
  _BS_word a = *xs--;
  int xp = startx;

  const _BS_word* ys = &(y.rep->s[BitStr_index(starty)]);
  _BS_word b = *ys--;
  int yp = starty;

  for(; xp >= 0 && yp >= 0; --xp, --yp)
  {
    _BS_word xbit = ((_BS_word)1) << (BitStr_pos(xp));
    _BS_word ybit = ((_BS_word)1) << (BitStr_pos(yp));
    if (((a & xbit) == 0) != ((b & ybit) == 0))
      break;
    if (xbit == 1)
      a = *xs--;
    if (ybit == 1)
      b = *ys--;
  }
  r.rep = BStr_alloc(0, x.rep->s, xp+1, startx+1, startx - xp);
  RETURN(r);
}

BitString reverse (const BitString& x)
     RETURNS(r)
{
  RETURN_OBJECT(BitString, r);
  unsigned int  yl = x.rep->len;
  BitStrRep* y = BStr_resize(0, yl);
  if (yl > 0)
  {
    const _BS_word* ls = x.rep->s;
    _BS_word lm = 1;
    _BS_word* rs = &(y->s[BitStr_index(yl - 1)]);
    _BS_word rm = ((_BS_word)1) << (BitStr_pos(yl - 1));
    for (unsigned int  l = 0; l < yl; ++l)
    {
      if (*ls & lm)
        *rs |= rm;
      if (lm == MAXBIT)
      {
        ++ls;
        lm = 1;
      }
      else
        lm <<= 1;
      if (rm == 1)
      {
        --rs;
        rm = MAXBIT;
      }
      else
        rm >>= 1;
    }
  }
  r.rep = y;
  RETURN(r);
}

BitString
atoBitString (const char* s, char f, char t)
     RETURNS(res)
{
  RETURN_OBJECT(BitString, res);
  int sl = strlen(s);
  BitStrRep* r = BStr_resize(0, sl);
  if (sl != 0)
  {
    unsigned int  rl = 0;
    _BS_word* rs = r->s;
    _BS_word a = 0;
    _BS_word m = 1;
    unsigned int  i = 0;
    for(;;)
    {
      char ch = s[i];
      if (ch != t && ch != f)
      {
        *rs = a;
        break;
      }
      ++rl;
      if (ch == t)
        a |= m;
      if (++i == sl)
      {
        *rs = a;
        break;
      }
      else if (i % BITSTRBITS == 0)
      {
        *rs++ = a;
        a = 0;
        m = 1;
      }
      else
        m <<= 1;
    }
    r = BStr_resize(r, rl);
  }
  res.rep = r;
  RETURN(res);
}

BitPattern
atoBitPattern (const char* s, char f,char t,char x)
     RETURNS(r)
{
  RETURN_OBJECT(BitPattern, r);
  int sl = strlen(s);
  if (sl != 0)
  {
    unsigned int  rl = 0;
    r.pattern.rep = BStr_resize(r.pattern.rep, sl);
    r.mask.rep = BStr_resize(r.mask.rep, sl);
    _BS_word* rs = r.pattern.rep->s;
    _BS_word* ms = r.mask.rep->s;
    _BS_word a = 0;
    _BS_word b = 0;
    _BS_word m = 1;
    unsigned int  i = 0;
    for(;;)
    {
      char ch = s[i];
      if (ch != t && ch != f && ch != x)
      {
        *rs = a;
        *ms = b;
        break;
      }
      ++rl;
      if (ch == t)
      {
        a |= m;
        b |= m;
      }
      else if (ch == f)
      {
        b |= m;
      }
      if (++i == sl)
      {
        *rs = a;
        *ms = b;
        break;
      }
      else if (i % BITSTRBITS == 0)
      {
        *rs++ = a;
        *ms++ = b;
        a = 0;
        b = 0;
        m = 1;
      }
      else
        m <<= 1;
    }
    r.pattern.rep = BStr_resize(r.pattern.rep, rl);
    r.mask.rep = BStr_resize(r.mask.rep, rl);
  }
  RETURN(r);
}

//extern AllocRing _libgxx_fmtq;

void BitString::printon (ostream& os, char f, char t) const
{
  unsigned int  xl = rep->len;
  const _BS_word* ptr = rep->s;
  register streambuf *sb = os.rdbuf();
  _BS_word a = 0;

  for (unsigned int  i = 0; i < xl; ++i)
  {
    if (i % BITSTRBITS == 0)
      a = *ptr++;
    sb->sputc((a & 1)? t : f);
    a >>= 1;
  }
}

/*
const char* BitStringtoa(const BitString& x, char f, char t)
{
  int wrksiz = x.length() + 2;
  char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  ostrstream stream(fmtbase, wrksiz);
  
  x.printon(stream, f, t);
  stream << ends;
  return fmtbase;
}
*/

ostream& operator << (ostream& s, const BitString& x)
{
  if (s.opfx())
    x.printon(s);
  return s;
}

/*
const char* BitPatterntoa(const BitPattern& p, char f,char t,char x)
{
  unsigned int  pl = p.pattern.rep->len;
  unsigned int  ml = p.mask.rep->len;
  unsigned int  l = (pl <= ml)? pl : ml;

  int wrksiz = l + 2;
  char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  ostrstream stream(fmtbase, wrksiz);
  
  p.printon(stream, f, t, x);
  stream << ends;
  return fmtbase;
}
*/

void BitPattern::printon(ostream& s, char f,char t,char x) const
{
  unsigned int  pl = pattern.rep->len;
  unsigned int  ml = mask.rep->len;
  unsigned int  l = (pl <= ml)? pl : ml;
  register streambuf *sb = s.rdbuf();

  const _BS_word* ps = pattern.rep->s;
  const _BS_word* ms = mask.rep->s;
  _BS_word a = 0;
  _BS_word m = 0;

  for (unsigned int  i = 0; i < l; ++i)
  {
    if (i % BITSTRBITS == 0)
    {
      a = *ps++;
      m = *ms++;
    }
    if (m & 1)
      sb->sputc((a & 1)? t : f);
    else
      sb->sputc(x);
    a >>= 1;
    m >>= 1;
  }
}

ostream& operator << (ostream& s, const BitPattern& x)
{
  if (s.opfx())
    x.printon(s);
  return s;
}


int BitString::OK() const
{
  int v = rep != 0;             // have a rep;
  v &= BitStr_len(rep->len) <= rep->sz; // within allocated size
  if (!v) error("invariant failure");
  return v;
}

int BitSubString::OK() const
{
  int v = S.OK();               // valid BitString
  v &= pos + len <= S.rep->len; // within bounds of targ
  if (!v) S.error("BitSubString invariant failure");
  return v;
}

int BitPattern::OK() const
{
  int v = pattern.OK() && mask.OK();
  if (!v) pattern.error("BitPattern invariant failure");
  return v;
}