bitstring.cc

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

void BitString::assign(int p, unsigned int bit)
{
  if (p < 0) error("Illegal bit index");
  if ((unsigned)(p) >= rep->len) rep = BStr_resize(rep, p + 1);
  if (bit)
    rep->s[BitStr_index(p)] |= _BS_BITMASK(BitStr_pos(p));
  else
      rep->s[BitStr_index(p)] &= ~(_BS_BITMASK(BitStr_pos(p)));
}

void BitString::clear(int p)
{
  if (p < 0) error("Illegal bit index");
  if ((unsigned)(p) >= rep->len) rep = BStr_resize(rep, p + 1);
  rep->s[BitStr_index(p)] &= ~(_BS_BITMASK(BitStr_pos(p)));
}

void BitString::clear()
{
  if (rep == &_nilBitStrRep) return;
  _BS_clear (rep->s, 0, rep->len);
}

void BitString::set()
{
  if (rep == &_nilBitStrRep) return;
  _BS_word* s = rep->s;
  _BS_word* tops = &(s[BitStr_len(rep->len)]);
  while (s < tops) *s++ = ONES;
  check_last(rep);
}

void BitString::invert(int p)
{
  if (p < 0) error("Illegal bit index");
  if ((unsigned)(p) >= rep->len) rep = BStr_resize(rep, p + 1);
  rep->s[BitStr_index(p)] ^= _BS_BITMASK(BitStr_pos(p));
}

void BitString::set(int from, int to)
{
  if (from < 0 || from > to) error("Illegal bit index");
  if ((unsigned)(to) >= rep->len) rep = BStr_resize(rep, to+1);

  _BS_size_t len = to - from + 1;
  _BS_word* xs = rep->s;
  _BS_NORMALIZE (xs, from);
  _BS_invert (xs, from, len);
}

void BitString::clear(int from, int to)
{
  if (from < 0 || from > to) error("Illegal bit index");
  if ((unsigned)(to) >= rep->len) rep = BStr_resize(rep, to+1);

  _BS_size_t len = to - from + 1;
  _BS_word* xs = rep->s;
  _BS_NORMALIZE (xs, from);
  _BS_clear (xs, from, len);
}

void BitString::invert(int from, int to)
{
  if (from < 0 || from > to) error("Illegal bit index");
  if ((unsigned)(to) >= rep->len) rep = BStr_resize(rep, to+1);
  _BS_size_t len = to - from + 1;
  _BS_word* xs = rep->s;
  _BS_NORMALIZE (xs, from);
  _BS_invert (xs, from, len);
}


int BitString::test(int from, int to) const
{
  if (from < 0 || from > to || (unsigned)(from) >= rep->len) return 0;
  
  _BS_size_t len = to - from + 1;
  _BS_word* xs = rep->s;
  _BS_NORMALIZE (xs, from);
  return _BS_any (xs, from, len);
}

int BitString::next(int p, unsigned int b) const
{
  if ((unsigned)(++p) >= rep->len)
    return -1;

  int ind = BitStr_index(p);
  int pos = BitStr_pos(p);
  int l = BitStr_len(rep->len);

  int j = ind;
  const _BS_word* s = rep->s;
  _BS_word a = s[j] >> pos;
  int i = pos;

  if (b != 0)
  {
    for (; i < BITSTRBITS && a != 0; ++i)
    {
      if (a & 1)
        return j * BITSTRBITS + i;
      a >>= 1;
    }
    for (++j; j < l; ++j)
    {
      a = s[j];
      for (i = 0; i < BITSTRBITS && a != 0; ++i)
      {
        if (a & 1)
          return j * BITSTRBITS + i;
        a >>= 1;
      }
    }
    return -1;
  }
  else
  {
    int last = BitStr_pos(rep->len);
    if (j == l - 1)
    {
      for (; i < last; ++i)
      {
        if ((a & 1) == 0)
          return j * BITSTRBITS + i;
        a >>= 1;
      }
      return -1;
    }

    for (; i < BITSTRBITS; ++i)
    {
      if ((a & 1) == 0)
        return j * BITSTRBITS + i;
      a >>= 1;
    }
    for (++j; j < l - 1; ++j)
    {
      a = s[j];
      if (a != ONES)
      {
        for (i = 0; i < BITSTRBITS; ++i)
        {
          if ((a & 1) == 0)
            return j * BITSTRBITS + i;
          a >>= 1;
        }
      }
    }
    a = s[j];
    for (i = 0; i < last; ++i)
    {
      if ((a & 1) == 0)
        return j * BITSTRBITS + i;
      a >>= 1;
    }
    return -1;
  }
}

int BitString::prev(int p, unsigned int b) const
{
  if (--p < 0)
    return -1;

  int ind = BitStr_index(p);
  int pos = BitStr_pos(p);

  const _BS_word* s = rep->s;

  if ((unsigned)(p) >= rep->len)
  {
    ind = BitStr_index(rep->len - 1);
    pos = BitStr_pos(rep->len - 1);
  }

  int j = ind;
  _BS_word a = s[j];

  int i = pos;
  _BS_word maxbit = ((_BS_word)1) << pos;

  if (b != 0)
  {
    for (; i >= 0 && a != 0; --i)
    {
      if (a & maxbit)
        return j * BITSTRBITS + i;
      a <<= 1;
    }
    maxbit = ((_BS_word)1) << (BITSTRBITS - 1);
    for (--j; j >= 0; --j)
    {
      a = s[j];
      for (i = BITSTRBITS - 1; i >= 0 && a != 0; --i)
      {
        if (a & maxbit)
          return j * BITSTRBITS + i;
        a <<= 1;
      }
    }
    return -1;
  }
  else
  {
    if (a != ONES)
    {
      for (; i >= 0; --i)
      {
        if ((a & maxbit) == 0)
          return j * BITSTRBITS + i;
        a <<= 1;
      }
    }
    maxbit = ((_BS_word)1) << (BITSTRBITS - 1);
    for (--j; j >= 0; --j)
    {
      a = s[j];
      if (a != ONES)
      {
        for (i = BITSTRBITS - 1; i >= 0; --i)
        {
          if ((a & maxbit) == 0)
            return j * BITSTRBITS + i;
          a <<= 1;
        }
      }
    }
    return -1;
  }
}


int BitString::search(int startx, int lengthx, 
                      const _BS_word* ys, int starty, int lengthy) const
{
  const _BS_word* xs = rep->s;
  int ylen = lengthy - starty;
  int righty = lengthy - 1;
  int rev = startx < 0;
  if (rev)
  {
    int leftx = 0;
    int rightx = lengthx + startx;
    startx = rightx - ylen + 1;
    if (ylen == 0) return startx;
    if (starty < 0 || righty < 0 || startx < 0 || startx >= lengthx) return -1;
    
    int xind = BitStr_index(startx);
    int xpos = BitStr_pos(startx);
    int yind = BitStr_index(starty);
    int ypos = BitStr_pos(starty);
    
    int rightxind = BitStr_index(rightx);

    _BS_word x = borrow_hi(xs, xind, rightxind, xpos);
  
    int rightyind = BitStr_index(righty);
    int rightypos = BitStr_pos(righty);
    _BS_word y = borrow_hi(ys, yind, rightyind, ypos);
    _BS_word ymask;
    if (yind == rightyind)
      ymask = rmask(rightypos);
    else if (yind+1 == rightyind)
      ymask = rmask(BITSTRBITS - ypos + rightypos + 1);
    else
      ymask = ONES;
    
    int p = startx;
    for (;;)
    {
      if ((x & ymask) == y)
      {
        int xi = xind;
        int yi = yind;
        for (;;)
        {
          if (++yi > rightyind || ++xi > rightxind)
            return p;
          _BS_word tx = borrow_hi(xs, xi, rightxind, xpos);
          _BS_word ty = borrow_hi(ys, yi, rightyind, ypos);
          if (yi == rightyind)
            tx &= rmask(rightypos);
          else if (yi+1 == rightyind)
            tx &= rmask(BITSTRBITS - ypos + rightypos + 1);
          if (tx != ty)
            break;
        }
      }
      if (--p < leftx)
        return -1;
      if (--xpos < 0)
      {
        xpos = BITSTRBITS - 1;
        --xind;
      }
      x = borrow_hi(xs, xind, rightxind, xpos);
    }
  }
  else
  {

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

    int rightxind = BitStr_index(rightx);

    _BS_word x = borrow_hi(xs, xind, rightxind, xpos);
    _BS_word nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos);
  
    int rightyind = BitStr_index(righty);
    int rightypos = BitStr_pos(righty);
    _BS_word y = borrow_hi(ys, yind, rightyind, ypos);
    _BS_word ymask;
    if (yind == rightyind)
      ymask = rmask(rightypos);
    else if (yind+1 == rightyind)
      ymask = rmask(BITSTRBITS - ypos + rightypos + 1);
    else
      ymask = ONES;
  
    int p = startx;
    for (;;)
    {
      if ((x & ymask) == y)
      {
        int xi = xind;
        int yi = yind;
        for (;;)
        {
          if (++yi > rightyind || ++xi > rightxind)
            return p;
          _BS_word tx = borrow_hi(xs, xi, rightxind, xpos);
          _BS_word ty = borrow_hi(ys, yi, rightyind, ypos);
          if (yi == rightyind)
            tx &= rmask(rightypos);
          else if (yi+1 == rightyind)
            tx &= rmask(BITSTRBITS - ypos + rightypos + 1);
          if (tx != ty)
            break;
        }
      }
      if (++p > rightx)
        return -1;
      if (++xpos == BITSTRBITS)
      {
        xpos = 0;
        x = xs[++xind];
        nextx = (xind >= rightxind) ? 0 : xs[xind+1];
      }
      else
      {
        x >>= 1;
        if (nextx & 1)
          x |= MAXBIT;
        nextx >>= 1;
      }
    }
  }
}


int BitPattern::search(const _BS_word* xs, int startx, int lengthx) const
{
  const _BS_word* ys = pattern.rep->s;
  const _BS_word* ms = mask.rep->s;
  int righty = pattern.rep->len - 1;
  int rightm = mask.rep->len - 1;

  int rev = startx < 0;
  if (rev)
  {
    int leftx = 0;
    int rightx = lengthx + startx;
    startx = rightx - righty;

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

    int rightmind = BitStr_index(rightm);
    int rightyind = BitStr_index(righty);
    
    _BS_word x = safe_borrow_hi(xs, xind, rightxind, xpos);
    _BS_word m = safe_borrow_hi(ms, 0, rightmind, 0);
    _BS_word y = safe_borrow_hi(ys, 0, rightyind, 0) & m;
    
    int p = startx;
    for (;;)
    {
      if ((x & m) == y)
      {
        int xi = xind;
        int yi = 0;
        for (;;)
        {
          if (++yi > rightyind || ++xi > rightxind)
            return p;
          _BS_word tm = safe_borrow_hi(ms, yi, rightmind, 0);
          _BS_word ty = safe_borrow_hi(ys, yi, rightyind, 0);
          _BS_word tx = safe_borrow_hi(xs, xi, rightxind, xpos);
          if ((tx & tm) != (ty & tm))
            break;
        }
      }
      if (--p < leftx)
        return -1;
      if (--xpos < 0)
      {
        xpos = BITSTRBITS - 1;
        --xind;
      }
      x = safe_borrow_hi(xs, xind, rightxind, xpos);
    }
  }
  else
  {

    int rightx = lengthx - 1;

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

    int rightmind = BitStr_index(rightm);
    int rightyind = BitStr_index(righty);
    
    _BS_word x = safe_borrow_hi(xs, xind, rightxind, xpos);
    _BS_word m = safe_borrow_hi(ms, 0, rightmind, 0);
    _BS_word y = safe_borrow_hi(ys, 0, rightyind, 0) & m;

    _BS_word nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos);
    
    int p = startx;
    for (;;)
    {
      if ((x & m) == y)
      {
        int xi = xind;
        int yi = 0;
        for (;;)
        {
          if (++yi > rightyind || ++xi > rightxind)
            return p;
          _BS_word tm = safe_borrow_hi(ms, yi, rightmind, 0);
          _BS_word ty = safe_borrow_hi(ys, yi, rightyind, 0);
          _BS_word tx = safe_borrow_hi(xs, xi, rightxind, xpos);
          if ((tx & tm) != (ty & tm))
            break;
        }
      }
      if (++p > rightx)
        return -1;
      if (++xpos == BITSTRBITS)
      {
        xpos = 0;
        x = xs[++xind];
        nextx = (xind >= rightxind) ? 0 : xs[xind+1];
      }
      else
      {
        x >>= 1;
        if (nextx & 1)
          x |= MAXBIT;
        nextx >>= 1;
      }
    }
  }
}

int BitString::match(int startx, int lengthx, int exact, 
                     const _BS_word* ys, int starty, int yl) const
{
  const _BS_word* xs = rep->s;
  int ylen = yl - starty;
  int righty = yl - 1;

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

  if (ylen == 0) return 1;
  if (righty < 0 || startx < 0 || startx >= lengthx) return 0;
  
  int xi   = BitStr_index(startx);
  int xpos = BitStr_pos(startx);
  int yi   = BitStr_index(starty);
  int ypos = BitStr_pos(starty);

  int rightxind = BitStr_index(rightx);
  int rightyind = BitStr_index(righty);
  int rightypos = BitStr_pos(righty);

  for (;;)
  {
    _BS_word x = borrow_hi(xs, xi, rightxind, xpos);
    _BS_word y = borrow_hi(ys, yi, rightyind, ypos);
    if (yi == rightyind)
      x &= rmask(rightypos);
    else if (yi+1 == rightyind)
      x &= rmask(BITSTRBITS - ypos + rightypos + 1);
    if (x != y)
      return 0;
    else if (++yi > rightyind || ++xi > rightxind)
      return 1;
  }
}

int BitPattern::match(const _BS_word* xs, int startx, 
                      int lengthx, int exact) const
{