slidingbitset.h

用于词法分析的词法分析器

/* $Id: SlidingBitset.h,v 1.1 1997/02/15 01:32:49 matt Exp $

   Sliding bitset class.  This is a wierd bitset that "slides"
   right. The set stores SIZE elements, so that at the start indexes
   0..SIZE-1 are in the set.  After the first slide indexes 1..SIZE
   are in the set etc.  All values remain unchanged as long as they
   remain within the set, they become false as they go outside the
   set.

   (c) Feb 97 Matt Phillips. */

#ifndef _SLIDING_BITSET_H
#define _SLIDING_BITSET_H

#include <string.h>

template <int SIZE>
class SlidingBitset
{
public:

  SlidingBitset (int init = 0);

  void setAll (int value = 1);

  int get (int index) const;
  void set (int index);
  void unset (int index);
  void slide ();

protected:

  typedef unsigned char byte;

  // the size of the bitset in bytes
  enum {BITSET_BYTES = SIZE / 8 + (SIZE % 8 != 0)};

  byte bitset [BITSET_BYTES];
  int start;
};

template <int SIZE>
SlidingBitset<SIZE>::SlidingBitset (int init)
{
  start = 0;
  setAll (init);
}

template <int SIZE>
void SlidingBitset<SIZE>::setAll (int value)
{
  memset (bitset, value ? 0xFF : 0, BITSET_BYTES * sizeof (byte));
}

template <int SIZE>
int SlidingBitset<SIZE>::get (int index) const
{
  if (index >= start && index < start + SIZE)
  {
    index %= SIZE;
    return (bitset [index / 8]) & (1 << (index % 8));
  } else
    return 0;
}

template <int SIZE>
void SlidingBitset<SIZE>::set (int index)
{
  if (index >= start && index < start + SIZE)
  {
    index %= SIZE;
    (bitset [index / 8]) |= (1 << (index % 8));
  }
}

template <int SIZE>
void SlidingBitset<SIZE>::unset (int index)
{
  if (index >= start && index < start + SIZE)
  {
    index %= SIZE;
    (bitset [index / 8]) &= ((1 << (index % 8)) ^ 0xFF);
  }
}

template <int SIZE>
void SlidingBitset<SIZE>::slide ()
{
  start++;
  unset (start + SIZE - 1);
}

#endif