bitstring.cc

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

/* 
Copyright (C) 1988 Free Software Foundation
    written by Doug Lea ([e-mail])

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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/

/* 
  BitString class implementation
 */
 
#ifdef __GNUG__
#pragma implementation
#endif
#include <BitString.h>
#include <std.h>
#include <limits.h>
#include <Obstack.h>
#include <AllocRing.h>
#include <new.h>
#include <builtin.h>
#include <strstream.h>

#undef OK

void BitString::error(const char* msg) const
{
  (*lib_error_handler)("BitString", msg);
}

//  globals

BitStrRep    _nilBitStrRep = {  0, 1, {0} };

BitString _nil_BitString;

#define MINBitStrRep_SIZE  8
#define MAXBitStrRep_SIZE  ((1 << (sizeof(short)*CHAR_BIT - 1)) - 1)

#ifndef MALLOC_MIN_OVERHEAD
#define MALLOC_MIN_OVERHEAD    4
#endif

#define ONES  ((_BS_word)(~0L))
#define MAXBIT  (((_BS_word)1) << (BITSTRBITS - 1))

/*
 *  bit manipulation utilities
*/

// break things up into .s indices and positions

inline static int BitStr_len(int l)
{
  return (unsigned)(l) / BITSTRBITS + 1;
}


// mask out low bits

static inline _BS_word lmask(int p)
{
  return ONES _BS_RIGHT p;
}

// mask out high bits

static inline _BS_word rmask(int p)
{
  int s = BITSTRBITS - 1 - p;
  if (s <= 0)
    return ONES;
  else
    return ONES _BS_LEFT s;
}


// mask out unused bits in last word of rep

inline static void check_last(BitStrRep* r)
{
  int bit_len_mod = r->len & (BITSTRBITS - 1);
  if (bit_len_mod)
    r->s[r->len / BITSTRBITS] &= ONES _BS_LEFT (BITSTRBITS - bit_len_mod);
}

// merge bits from next word

static inline _BS_word borrow_hi(const _BS_word a[], int ind, 
                                      int maxind, int p)
{
  if (p == 0)
    return a[ind];
  else if (ind < maxind)
    return (a[ind] _BS_LEFT p) | (a[ind+1] _BS_RIGHT (BITSTRBITS - p));
  else
    return (a[ind] _BS_LEFT p);
}

// merge bits from prev word

static inline _BS_word borrow_lo(const _BS_word a[], int ind, 
                                      int minind, int p)
{
  _BS_word word = a[ind] _BS_RIGHT (BITSTRBITS - 1 - p);
  if (ind > minind)
    word |= (a[ind-1] _BS_LEFT (p + 1));
  return word;
}

// same with bounds check (for masks shorter than patterns)

static inline _BS_word safe_borrow_hi(const _BS_word a[], int ind, 
                                           int maxind, int p)
{
  if (ind > maxind)
    return 0;
  else if (p == 0)
    return a[ind];
  else if (ind == maxind)
    return a[ind] _BS_LEFT p;
  else
    return (a[ind] _BS_LEFT p) | (a[ind+1] _BS_RIGHT (BITSTRBITS - p));
}


// allocate a new rep; pad to near a power of two

inline static BitStrRep* BSnew(int newlen)
{
  unsigned int siz = sizeof(BitStrRep) + BitStr_len(newlen) * sizeof(_BS_word) 
    + MALLOC_MIN_OVERHEAD;
  unsigned int allocsiz = MINBitStrRep_SIZE;;
  while (allocsiz < siz) allocsiz <<= 1;
  allocsiz -= MALLOC_MIN_OVERHEAD;
  if (allocsiz >= MAXBitStrRep_SIZE * sizeof(_BS_word))
    (*lib_error_handler)("BitString", "Requested length out of range");
    
  BitStrRep* rep = new (operator new (allocsiz)) BitStrRep;
  memset(rep, 0, allocsiz);
  rep->sz =
    (allocsiz - sizeof(BitStrRep) + sizeof(_BS_word)) / sizeof(_BS_word);
  return rep;
}

inline void
copy_bits (_BS_word* pdst, _BS_size_t dstbit,
	   const _BS_word* psrc, _BS_size_t srcbit,
	   _BS_size_t length)
{
  _BS_NORMALIZE (pdst, dstbit);
  _BS_NORMALIZE (psrc, srcbit);
  _BS_copy (pdst, dstbit, psrc, srcbit, length);
}

BitStrRep* BStr_alloc(BitStrRep* old, const _BS_word* src,
                      int startpos, int endp, int newlen)
{
  if (old == &_nilBitStrRep) old = 0; 
  if (newlen < 0) newlen = 0;
  int news = BitStr_len(newlen);
  BitStrRep* rep;
  if (old == 0 || news > old->sz)
    rep = BSnew(newlen);
  else
    rep = old;
  rep->len = newlen;

  if (src != 0 && endp > 0 && (src != rep->s || startpos > 0))
    copy_bits (rep->s, 0, src, startpos, endp - startpos);

  check_last(rep);

  if (old != rep && old != 0) delete old;

  return rep;
}

BitStrRep* BStr_resize(BitStrRep* old, int newlen)
{
  BitStrRep* rep;
  if (newlen < 0) newlen = 0;
  int news = BitStr_len(newlen);
  if (old == 0 || old == &_nilBitStrRep)
  {
    rep = BSnew(newlen);
  }
  else if (news > old->sz)
  {
    rep = BSnew(newlen);
    memcpy(rep->s, old->s, BitStr_len(old->len) * sizeof(_BS_word));
    delete old;
  }
  else
    rep = old;

  rep->len = newlen;
  check_last(rep);
  return rep;
}

BitStrRep* BStr_copy(BitStrRep* old, const BitStrRep* src)
{
  BitStrRep* rep;
  if (old == src && old != &_nilBitStrRep) return old; 
  if (old == &_nilBitStrRep) old = 0;
  if (src == &_nilBitStrRep) src = 0;
  if (src == 0)
  {
    if (old == 0)
      rep = BSnew(0);
    else
      rep = old;
    rep->len = 0;
  }
  else 
  {
    int newlen = src->len;
    int news = BitStr_len(newlen);
    if (old == 0 || news  > old->sz)
    {
      rep = BSnew(newlen);
      if (old != 0) delete old;
    }
    else
      rep = old;
    
    memcpy(rep->s, src->s, news * sizeof(_BS_word));
    rep->len = newlen;
  }
  check_last(rep);
  return rep;
}


int operator == (const BitString& x, const BitString& y)
{
  return x.rep->len == y.rep->len && 
    memcmp((void*)x.rep->s, (void*)y.rep->s, 
         BitStr_len(x.rep->len) * sizeof(_BS_word)) == 0;
}

int operator <= (const BitString& x, const BitString& y)
{
  unsigned int  xl = x.rep->len;
  unsigned int  yl = y.rep->len;
  if (xl > yl)
    return 0;

  const _BS_word* xs = x.rep->s;
  const _BS_word* topx = &(xs[BitStr_len(xl)]);
  const _BS_word* ys = y.rep->s;

  while (xs < topx)
  {
    _BS_word a = *xs++;
    _BS_word b = *ys++;
    if ((a | b) != b)
      return 0;
  }
  return 1;
}

int operator < (const BitString& x, const BitString& y)
{
  unsigned short xl = x.rep->len;
  unsigned short yl = y.rep->len;
  if (xl > yl)
    return 0;

  const _BS_word* xs = x.rep->s;
  const _BS_word* ys = y.rep->s;
  const _BS_word* topx = &(xs[BitStr_len(xl)]);
  const _BS_word* topy = &(ys[BitStr_len(yl)]);
  int one_diff = 0;
  while (xs < topx)
  {
    _BS_word a = *xs++;
    _BS_word b = *ys++;
    _BS_word c = a | b;
    if (c != b)
      return 0;
    else if (c != a)
      one_diff = 1;
  }
  if (one_diff)
    return 1;
  else
  {
    while (ys < topy)
      if (*ys++ != 0)
        return 1;
    return 0;
  }
}

int lcompare(const BitString& x, const BitString& y)
{
  return _BS_lcompare_0 (x.rep->s, x.rep->len, y.rep->s, y.rep->len);
}

int BitString::count(unsigned int b) const
{
  int count = _BS_count (rep->s, 0, rep->len);
  if (!b)
    count = rep->len - count;
  return count;
}


BitStrRep* cmpl(const BitStrRep* src, BitStrRep* r)
{
  r = BStr_copy(r, src);
  _BS_word* rs = r->s;
  _BS_word* topr = &(rs[BitStr_len(r->len)]);
  while (rs < topr)
  {
    _BS_word cmp = ~(*rs);
    *rs++ = cmp;
  }
  check_last(r);
  return r;
}


BitStrRep* and(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
{
  int xrsame = x == r;
  int yrsame = y == r;

  unsigned int  xl = x->len;
  unsigned int  yl = y->len;
  unsigned int  rl = (xl <= yl)? xl : yl;

  r = BStr_resize(r, rl);

  _BS_word* rs = r->s;
  _BS_word* topr = &(rs[BitStr_len(rl)]);
  const _BS_word* xs = (xrsame)? rs : x->s;
  const _BS_word* ys = (yrsame)? rs : y->s;

  while (rs < topr) *rs++ = *xs++ & *ys++;
  check_last(r);
  return r;
}

BitStrRep* or(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
{
  unsigned int  xl = x->len;
  unsigned int  yl = y->len;
  unsigned int  rl = (xl >= yl)? xl : yl;
  int xrsame = x == r;
  int yrsame = y == r;

  r = BStr_resize(r, rl);

  _BS_word* rs = r->s;
  const _BS_word* xs = (xrsame)? rs : x->s;
  const _BS_word* topx = &(xs[BitStr_len(xl)]);
  const _BS_word* ys = (yrsame)? rs : y->s;
  const _BS_word* topy = &(ys[BitStr_len(yl)]);

  if (xl <= yl)
  {
    while (xs < topx) *rs++ = *xs++ | *ys++;
    if (rs != ys) while (ys < topy) *rs++ = *ys++;
  }
  else
  {
    while (ys < topy) *rs++ = *xs++ | *ys++;
    if (rs != xs) while (xs < topx) *rs++ = *xs++;
  }
  check_last(r);
  return r;
}


BitStrRep* xor(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
{
  unsigned int  xl = x->len;
  unsigned int  yl = y->len;
  unsigned int  rl = (xl >= yl)? xl : yl;
  int xrsame = x == r;
  int yrsame = y == r;

  r = BStr_resize(r, rl);

  _BS_word* rs = r->s;
  const _BS_word* xs = (xrsame)? rs : x->s;
  const _BS_word* topx = &(xs[BitStr_len(xl)]);
  const _BS_word* ys = (yrsame)? rs : y->s;
  const _BS_word* topy = &(ys[BitStr_len(yl)]);

  if (xl <= yl)
  {
    while (xs < topx) *rs++ = *xs++ ^ *ys++;
    if (rs != ys) while (ys < topy) *rs++ = *ys++;
  }
  else
  {
    while (ys < topy) *rs++ = *xs++ ^ *ys++;
    if (rs != xs) while (xs < topx) *rs++ = *xs++;
  }
  check_last(r);
  return r;
}


BitStrRep* diff(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
{
  unsigned int  xl = x->len;
  unsigned int  yl = y->len;
  int xrsame = x == y;
  int yrsame = y == r;

  r = BStr_resize(r, xl);

  _BS_word* rs = r->s;
  const _BS_word* xs = (xrsame)? rs : x->s;
  const _BS_word* topx = &(xs[BitStr_len(xl)]);
  const _BS_word* ys = (yrsame)? rs : y->s;
  const _BS_word* topy = &(ys[BitStr_len(yl)]);

  if (xl <= yl)
  {
    while (xs < topx) *rs++ = *xs++ & ~(*ys++);
  }
  else
  {
    while (ys < topy) *rs++ = *xs++ & ~(*ys++);
    if (rs != xs) while (xs < topx) *rs++ = *xs++;
  }
  check_last(r);
  return r;
}


BitStrRep* cat(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
{
  unsigned int  xl = x->len;
  unsigned int  yl = y->len;
  unsigned int  rl = xl + yl;
  int xrsame = x == r;
  int yrsame = y == r;

  if (yrsame)
  {
    if (xrsame)
    {
      r = BStr_resize(r, rl);
      copy_bits (r->s, xl, r->s, 0, yl);
    }
    else
    {
      BitStrRep* tmp = BStr_copy(0, y);
      r = BStr_resize(r, rl);
      _BS_copy_0(r->s, x->s, xl);
      copy_bits (r->s, xl, tmp->s, 0, yl);
      delete tmp;
    }
  }
  else
  {
    r = BStr_resize(r, rl);
    if (!xrsame) _BS_copy_0(r->s, x->s, xl);
    copy_bits (r->s, xl, y->s, 0, yl);
  }
  check_last(r);
  return r;
}

BitStrRep* cat(const BitStrRep* x, unsigned int bit, BitStrRep* r)
{
  unsigned int  xl = x->len;
  int xrsame = x == r;
  r = BStr_resize(r, xl+1);
  if (!xrsame)
    _BS_copy_0(r->s, x->s, xl);
  if (bit)
    r->s[BitStr_index(xl)] |= _BS_BITMASK(BitStr_pos(xl));
  else
    r->s[BitStr_index(xl)] &= ~(_BS_BITMASK(BitStr_pos(xl)));
  check_last(r);
  return r;
}

BitStrRep* lshift(const BitStrRep* x, int s, BitStrRep* r)
{
  int xrsame = x == r;
  int  xl = x->len;
  int  rl = xl + s;
  if (s == 0)
    r = BStr_copy(r, x);
  else if (rl <= 0)
  {
    r = BStr_resize(r, 0);
    r->len = 0;
    r->s[0] = 0;
  }
  else if (s > 0)
  {
    r = BStr_resize(r, rl);
    const _BS_word* xs = (xrsame)? r->s : x->s;
    copy_bits (r->s, s, xs, 0, xl);
    _BS_clear (r->s, 0, s);
  }
  else if (xrsame)
  {
    r = BStr_resize(r, xl);
    r->len = rl;
    copy_bits (r->s, 0, r->s, -s, xl + s);
  }
  else
  {
    r = BStr_resize(r, rl);
    copy_bits (r->s, 0, x->s, -s, xl + s);
  }
  check_last(r);
  return r;
}


void BitString::set(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));
}