---

vbitset.hh

Go to the documentation of this file.

/*
 *  File:       vbitset.hh
 *              $Id: vbitset.hh,v 1.11 2002/07/09 03:04:58 alec Exp $
 *
 *  Author:     Alec Panoviciu (alecu@email.com)
 *
 *  Comments:
 *
 *  Revision history:
 *
 *  $Log: vbitset.hh,v $
 *  Revision 1.11  2002/07/09 03:04:58  alec
 *  OWN_STRINGS bu*beep*it finally vanished
 *  gcc 3.1&mingw - related cleanups
 *
 *  Revision 1.10  2002/06/26 20:51:31  alec
 *  g++ 3.x happy
 *
 *  Revision 1.9  2002/05/27 03:04:16  alec
 *  doc update
 *
 *  Revision 1.8  2002/05/22 01:44:16  alec
 *  length update bugfix
 *
 *  Revision 1.7  2002/05/16 21:22:35  alec
 *  in-depth coppy operator added (oops :)
 *  destructor
 *
 *  Revision 1.6  2002/05/01 16:32:14  alec
 *  dfa ok. huh !
 *
 *  Revision 1.5  2002/05/01 09:18:26  alec
 *  - vBitset fixes
 *  - FOLLOWPOS written (not tested yet)
 *
 *  Revision 1.4  2002/04/30 16:24:38  alec
 *  tested the scanner ptree & vBitVector implementation -> ok
 *
 *  Revision 1.3  2002/04/30 09:22:32  alec
 *  bitset fixes
 *
 *  Revision 1.2  2002/04/29 17:55:41  alec
 *  regexps almost done
 *
 *  Revision 1.1  2002/04/29 09:40:01  alec
 *  *** empty log message ***
 *
 */


/* 
  Copyright (C) 2002 Alexandru Panoviciu (alecu@email.com)

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.

  This program 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 General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 */

#ifndef __VBITSET_HH__
#define __VBITSET_HH__

#include <memory>
using namespace std;

#include "debug.h"

extern unsigned char vBitset_bit_count[];

#ifdef DEBUG
  extern unsigned long vBitset_usecnt;
#endif

template<class W, class A = allocator<W> > class vBitset_base
{
  /* NOTE: the implementation assumes at various points (mostly logic and
     relational operators implementations) that, if more storage is allocated
     than it is required for the actual length of the bitset, the extra bits are
     0. If this condition is false, the operators' behaviour is undefined (for
     instance, == will most certainly return the wrong results. This is ok for
     now, as a bit set can only grow but however, if a shrink operation will be
     implemented, it should take care to clean those remaining bits.
  */
public:

  typedef W WordType;

  typedef A AllocatorType;

  typedef WordType *Mptr;

  typedef WordType &Mref;

  typedef size_t  SizeType;

  static const SizeType WORDBITS = sizeof(WordType) * 8;

  static const SizeType WORDBYTES = sizeof(WordType);

  static SizeType whichWord (SizeType bits)
  {
    return bits / WORDBITS;
  }

  static SizeType whichBit (SizeType bits)
  {
    return bits % WORDBITS;
  }

  static WordType maskBit (SizeType bits)
  {
    return static_cast<WordType>(1) << whichBit(bits);
  }
  
  class reference
  {
    friend class vBitset_base;
    
  public:

    reference (const vBitset_base &set_, SizeType bit_) :
      wp(set_.getWord(bit_)), mask(maskBit(bit_))
    {}

    reference (const reference &o) :
      wp(o.wp), mask(o.mask)
    {}

    reference () : wp(0), mask(0)
    {}

    ~reference ()
    {}

    reference& operator = (const reference &o)
    {
      wp = o.wp;
      mask = o.mask;
      return *this;
    }

    bool set (bool b = 1) const
    {
      check();
      if (b) *wp |= mask; else *wp &= ~mask;
      return b;
    }

    bool get () const
    {
      return *wp & mask;
    }

    bool eq (const reference &o)
    {
      return (wp == o.wp) && (mask == o.mask);
    }

    bool neq (const reference &o)
    {
      return !eq(o);
    }

    bool lt (const reference &o)
    {
      return (wp < o.wp) || ((wp == o.wp) && (mask < o.mask));
    }

    bool le (const reference &o)
    {
      return lt(o) || eq(o);
    }

    bool gt (const reference &o)
    {
      return !le(o);
    }

    bool ge (const reference &o)
    {
      return !lt(o);
    }

    /* @} */

    reference& next ()
    {
      if (mask == (static_cast<WordType>(1) << (WORDBITS - 1))) {
        mask = (WordType) 1;
        ++wp;
      } else {
        mask <<= 1;
      }
      return *this;
    }

    reference& prev ()
    {
      if (mask == static_cast<WordType>(1)) {
        mask = static_cast<WordType>(1) << (WORDBITS - 1);
        --wp;
      } else {
        mask >>= 1;
      }
      return this;
    }

    void check() const
    {
      /* yeahhhh SURE ! */
    }

  protected:

    void move (const vBitset_base &set_, SizeType bit_)
    {
      wp = set_.getWord(bit_);
      mask = maskBit(bit_);
    }

    
  private:
    Mptr wp;
    WordType mask;
  };

  vBitset_base (SizeType len_ = 1) :
    len(len_ ? len_ : 1)
  {
    SizeType cap = whichWord(len) + 1;
    data = M_alloc.allocate(cap);
    endOfData = data + cap;
    for (Mptr q = data; q < endOfData; *q++ = 0);
    updateLimits();
#ifdef DEBUG
    vBitset_usecnt++;
#endif
  }

  vBitset_base (const vBitset_base &o)
  {
    len = o.len;
    data = M_alloc.allocate(o.capacity());
    endOfData = data + o.capacity();
    for(Mptr p = data, q = o.data; p < endOfData; *p++ = *q++);
    updateLimits();
#ifdef DEBUG
    vBitset_usecnt++;
#endif
  }


  vBitset_base& operator = (const vBitset_base &o)
  {
    if (this == &o) return *this;
    M_alloc.deallocate(data, capacity());
    len = o.len;
    data = M_alloc.allocate(o.capacity());
    endOfData = data + o.capacity();
    for(Mptr p = data, q = o.data; p < endOfData; *p++ = *q++);
    updateLimits();
  }

  ~vBitset_base ()
  {
    M_alloc.deallocate(data, capacity());
  }


  reference operator [] (SizeType n)
  {
    return reference(*this, n);
  }

  reference begin ()
  {
    return _begin;
  }

  reference end ()
  {
    return _end;
  }

  void resize (SizeType n)
  {
    grow(n);
  }

  SizeType size () const
  {
    return len;
  }

  SizeType length () const
  {
    return size();
  }

  SizeType capacity () const
  {
    return endOfData - data;
  }

  bool all0 () const
  {
    return count1() == 0;
  }

  bool all1 () const
  {
    return !all0();
  }

  SizeType count1 () const
  {
    SizeType res = 0;
    
    for (unsigned char* p = (unsigned char *) data;
         p < (unsigned char *)endOfData; p++)
    {
      res += vBitset_bit_count[*p];
    }

    return res;
  }

  SizeType count0 () const
  {
    return length() - count1();
  }

  void flip ()
  {
    for (Mptr q = data; q < endOfData; q++) *q = ~*q;
  }

  void doOr (const vBitset_base &o)
  {
    Mptr p = data, q = o.data;
    if (capacity() < o.capacity()) {
      while (p < endOfData) *p++ |= *q++;
      grow_fill(o.length(), q); // 0 | q[i] == q[i]
    } else {
      while (q < o.endOfData) *p++ |= *q++; // 0 | p[i] == p[i]
      if (o.len > len) { // capacity == o.capacity, but o.len > len
        len = o.len;
        updateLimits();
      }
    }
  }
  
  vBitset_base& operator |= (const vBitset_base &o)
  {
    doOr(o);
    return *this;
  }

  void doAnd (const vBitset_base &o)
  {
    Mptr p = data, q = o.data;
    if (capacity() < o.capacity()) {
      while (p < endOfData) *p++ &= *q++;
      grow(o.length()); // 0 & q[i] == 0
    } else {
      while (q < o.endOfData) *p++ &= *q++;
      while (p < endOfData) *p++ = 0; // 0 & p[i] == 0
      if (o.len > len) { // capacity == o.capacity, but o.len is actually > len
        len = o.len;
        updateLimits();
      }
    }
  }
  
  vBitset_base& operator &= (const vBitset_base &o)
  {
    doAnd(o);
    return *this;
  }

  bool operator == (const vBitset_base &o) const
  {
    if (this == &o) return true;

    if (o.capacity() > capacity()) return o == *this;

    // pre: capacity() >= o.capacity()
    Mptr p = data, q = o.data;
    while (q < o.endOfData) if (*p++ != *q++) return false;
    while (p < endOfData) if (*p++ != static_cast<WordType>(0)) return false;
    return true;
  }

  bool operator != (const vBitset_base &o) const
  {
    return ! (*this== o);
  }

  void clear ()
  {
    for (Mptr p = data; p < endOfData; *p++ = static_cast<WordType>(0));
    len = 1;
    updateLimits();
  }
  
protected:

  Mptr getWord (SizeType n) const
  {
    return data + whichWord(n);
  }

  void grow (SizeType n)
  {
    SizeType newCap = whichWord(n) + 1;
    if (capacity() < newCap)
    {
      Mptr q = data, pS = M_alloc.allocate(newCap), pE = pS;
    
      while (q < endOfData) *pE++ = *q++;
      while (pE < pS + newCap) *pE++ = static_cast<WordType>(0);
    
      M_alloc.deallocate(data, capacity());
    
      data = pS;
      endOfData = pE;
    }
    len = n;
    updateLimits();
  }

  void grow_fill (SizeType n, Mptr d)
  {
    SizeType newCap = whichWord(n) + 1;
    if (capacity() < newCap)
    {
      Mptr q = data, pS = M_alloc.allocate(newCap), pE = pS;
      
      while (q < endOfData) *pE++ = *q++;
      while (pE < pS + newCap) *pE++ = *d++;
      
      M_alloc.deallocate(data, capacity());
      
      data = pS;
      endOfData = pE;
    }
    len = n;
    updateLimits();
  }

  void updateLimits ()
  {
    _begin.move(*this, 0);
    _end.move(*this, len);
  }
  
private:

  Mptr data;

  Mptr endOfData;

  SizeType len;

  reference _begin;

  reference _end;
  
  static AllocatorType M_alloc;
};


typedef vBitset_base<unsigned long> vBitset;

template<class W, class A>
vBitset_base<W, A> operator | (const vBitset_base<W, A> &a,
                               const vBitset_base<W, A> &b)
{
  vBitset_base<W, A> res(a);
  res |= b;
  return res;
}

template<class W, class A>
vBitset_base<W, A> operator & (const vBitset_base<W, A> &a,
                               const vBitset_base<W, A> &b)
{
  vBitset_base<W, A> res(a);
  res &= b;
  return res;
}

template<class W, class A>
vBitset_base<W, A> operator ^ (const vBitset_base<W, A> &a,
                               const vBitset_base<W, A> &b)
{
  vBitset_base<W, A> res(a);
  res ^= b;
  return res;
}

template<class W, class A>
vBitset_base<W, A> operator << (const vBitset_base<W, A> &a,
                                typename vBitset_base<W, A>::SizeType n)
{
  vBitset_base<W, A> res(a);
  res <<= n;
  return res;
}

template<class W, class A>
vBitset_base<W, A> operator >> (const vBitset_base<W, A> &a,
                                typename vBitset_base<W, A>::SizeType n)
{
  vBitset_base<W, A> res(a);
  res >>= n;
  return res;
}

#endif /* #ifndef __VBITSET_HH__ */

---