bitset.cpp

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C++ 代码 · 共 805 行 · 第 1/2 页

/*
 *
 *          Copyright (C) 1994, M. A. Sridhar
 *  
 *
 *     This software is Copyright M. A. Sridhar, 1994. You are free
 *     to copy, modify or distribute this software  as you see fit,
 *     and to use  it  for  any  purpose, provided   this copyright
 *     notice and the following   disclaimer are included  with all
 *     copies.
 *
 *                        DISCLAIMER
 *
 *     The author makes no warranties, either expressed or implied,
 *     with respect  to  this  software, its  quality, performance,
 *     merchantability, or fitness for any particular purpose. This
 *     software is distributed  AS IS.  The  user of this  software
 *     assumes all risks  as to its quality  and performance. In no
 *     event shall the author be liable for any direct, indirect or
 *     consequential damages, even if the  author has been  advised
 *     as to the possibility of such damages.
 *
 */





#include "base/bitset.h"
#include "base/bytestrm.h"
#include "base/intset.h"

static const short BitsInLong = sizeof (ulong)*8;

// The following inline functions are used for indexing into the array of
// ulong's, and assume that a ulong has 32 bits.
inline long __Div32 (long x)
{
    return (x >> 5) & ((1L << 27) - 1);
}

inline long __Mod32 (long x)
{
    return x & ((1L << 5) - 1);
}

inline ulong __Mul32 (long x)
{
    return x << 5;
}


static ulong __FAR BitTable [32] = {
    0x00000001, 0x00000002, 0x00000004, 0x00000008,
    0x00000010, 0x00000020, 0x00000040, 0x00000080,
    0x00000100, 0x00000200, 0x00000400, 0x00000800,
    0x00001000, 0x00002000, 0x00004000, 0x00008000,
    0x00010000, 0x00020000, 0x00040000, 0x00080000,
    0x00100000, 0x00200000, 0x00400000, 0x00800000,
    0x01000000, 0x02000000, 0x04000000, 0x08000000,
    0x10000000, 0x20000000, 0x40000000, 0x80000000
};

static short BitCount (ulong n)
{
    short count = 0;
    while (n != 0) {
        n &= n-1;
        count++;
    }
    return count;
}



inline bool DoAdd (ulong _rep[], long value)
{
    ulong mask = (1L << (__Mod32 (value)));
    long index = __Div32 (value);
    if (_rep [index] & mask)
        return FALSE;
    _rep[index] |= mask;
    return TRUE;
}


CL_DEFINE_CLASS(CL_BitSet, _CL_Sequence_CLASSID);

CL_BitSet::CL_BitSet  (long max_size)
{
    long div = __Div32 (max_size);
    long mod = __Mod32 (max_size);
    _count = (mod == 0) ? div : div+1;
    _rep = new ulong [_count];
    if (!_rep) {
        _count = 0;
        return;
    }
    register ulong* p = _rep;
    for (register long i = 0; i < _count; i++)
        *p++ = 0L;
    _size = 0;
}

CL_BitSet::CL_BitSet  (const CL_BitSet& o)
{
    _count = o._count;
    _rep = new ulong [_count];
    if (!_rep) {
        _count = 0;
        return;
    }
    register ulong *p, *q;
    p = _rep; q = o._rep;
    for (long i = 0; i < _count; i++)
        *p++ = *q++;
    _size = o._size;
}


CL_BitSet::CL_BitSet (long lo, long hi, long max_size)
{
    long div = __Div32 (max_size);
    long mod = __Mod32 (max_size);
    _count = (mod == 0) ? div : div+1;
    _rep = new ulong [_count];
    if (!_rep) {
        _count = 0;
        return;
    }
    register ulong* p = _rep;
    long i;
    for (i = 0; i < _count; i++)
        *p++ = 0L;
    _size = 0;
    for (i = lo; i <= hi; i++)
        Add (i);
}

CL_BitSet::CL_BitSet  (CL_ByteArray& o)
{
    CL_ByteStream s (o);
    ReadFrom (s);
}


// Protected constructor
CL_BitSet::CL_BitSet (long wordCount, ulong* array)
{
    _rep = array;
    _size = 0;
    _count = wordCount;
    for (long i = 0; i < _count; i++) {
        _size += BitCount (_rep[i]);
    }
}


CL_BitSet::~CL_BitSet ()
{
    if (_rep)
        delete [] _rep;
}



// ----------------------- Element methods ------------------

bool CL_BitSet::Includes     (const long& value) const
{
    if (value < 0 || value >= __Mul32 (_count))
        return FALSE;
    return (_rep [__Div32 (value)] &
            (1L << (__Mod32 (value)))) ? TRUE : FALSE;
}

long CL_BitSet::Remove    (const long& value)
{
    if (!PrepareToChange())
        return FALSE;
    if (value < 0 || value >= __Mul32 (_count))
        return 0;
    long index = __Div32(value);
    ulong mask = 1L << __Mod32 (value);
    if (!(_rep [index] & mask))
        return 0;
    _rep[index] &= ~mask;
    _size --;
    Notify();
    return value;
}



bool CL_BitSet::Add  (const long& value)
{
    if (!PrepareToChange())
        return FALSE;
    if (value < 0 || value >= __Mul32 (_count))
        return FALSE;
    if (DoAdd (_rep, value)) {
        _size++;
        Notify();
        return TRUE;
    }
    return FALSE;
}


long CL_BitSet::Largest () const
{
    // This implementation is likely to be more efficient than simply using
    // ItemWithRank.
    if (_size <= 0)
        return -1;
    register short i = _count-1;
    register ulong* p = _rep;
    while (i >= 0 && *p == 0)
        i--, p--;
    if (i < 0) {
        // Can't be: we checked for size > 0 already
        CL_Error::Warning ("CL_BitSet::Largest: internal error");
        return -1;
    }
    register ulong data = *p;
    short j;
    for (j = 31; j >= 0; j--) {
        if (data & BitTable[j])
            break;
    }
    return __Mul32(i) + j;
}


long CL_BitSet::Smallest () const
{
    // This implementation is likely to be more efficient than simply using
    // ItemWithRank.
    if (_size <= 0)
        return -1;
    register short i = 0;
    register ulong* p = _rep;
    while (i < _count && *p == 0)
        i++, p++;
    if (i >= _count) {
        // Can't be: we checked for size > 0 already
        CL_Error::Warning ("CL_BitSet::Smallest: internal error");
        return 0;
    }
    register ulong data = *p;
    short j;
    for (j = 0; j < 32; j++) {
        if (data & BitTable[j])
            break;
    }
    return __Mul32 (i) + j;
}




long  CL_BitSet::Successor (long n) const
{
    if (_size <= 0)
        return -1;
    long index = __Div32 (n);
    short offs = __Mod32 (n);
    if (index >= _count)
        return -1;
    else if (index < 0)
        index = 0;
    register ulong word = _rep[index];
    register short j;
    // See if next larger element is in the same long cell as n
    for (j = offs+1; j < BitsInLong; j++)
        if (BitTable [j] & word)
            return __Mul32 (index) + j;

    // No, it isn't. Scan the rest of the cells, from index+1 up
    register long i;
    for (i = index+1; i < _count; i++) {
        word = _rep[i];
        if (word)
            break;
    }
    if (i >= _count)
        return -1;
    for (j = 0; j < BitsInLong; j++)
        if (word & BitTable[j])
            return __Mul32 (i) + j;
    // Huh? We found a non-zero cell, but no 1-bit in it??
    CL_Error::Warning ("BitSet::Successor: internal error");
    return -1;
}


long  CL_BitSet::SmallestNonMember () const
{
    if (_size <= 0)
        return 0;
    if (_size == __Mul32 (_count))
        return -1;
    register long i = 0;
    register ulong* p = _rep;
    while (i < _count && *p == (ulong) -1)
        i++, p++;
    if (i >= _count)
        return __Mul32 (_count);
    register ulong data = ~ (*p);
    short j;
    for (j = 0; j < 32; j++) {
        if (data & BitTable[j])
            break;
    }
    return __Mul32(i) + j;
}


long CL_BitSet::RankOf (const long& value) const
{
    if (_size <= 0 || value <= 0)
        return 0;
    long index = minl (__Div32(value), _count-1);
    register long mod32 = __Mod32 (value);
    ulong mask = (-1L) << mod32; // Shift in zeros at right
    long rank = 0;
    for (register long i = 0; i < index; i++)
        rank += BitCount (_rep[i]);
    register ulong tmp = _rep[index];
    rank += BitCount (tmp & ~mask);
    return rank;
}



long CL_BitSet::ItemWithRank (long rank) const
{
    if (_size <= 0)
        return -1;
    rank = maxl (0, minl (rank, _size - 1));
    long r = 0, l = 0;
    long i;
    for (i = 0; i < _count; i++) {
        l = BitCount (_rep[i]);
        if (r + l > rank)
            break;
        r += l;
    }
    if (i >= _count) // We've looked at all the words in _rep
        i = _count-1;
    long m = _rep[i];
    short j;
    for (j = 0; j < 32; j++) {
        if (m & 1) {
            if (r == rank)
                break;
            r++;
        }
        m >>= 1;
    }
    return __Mul32(i) + j;
}



CL_BitSet CL_BitSet::operator + (long value) const
{
    CL_BitSet s (*this);
    s.Add (value);
    return s;
}


// void CL_BitSet::operator= (const CL_Set<long>& s)
// {
//     if (!PrepareToChange ())
//         return;
//     if (this == &s)
//         return;
//     MakeEmpty();
//     long n = s.Size();
//     for (long i = 0; i < n; i++)
//         Add (s.ItemWithRank(i));
//     Notify ();
// }

// void CL_BitSet::operator= (const CL_Sequence<long>& s)
// {
//     if (!PrepareToChange ())
//         return;
//     MakeEmpty();
//     register long n = s.Size();
//     for (long i = 0; i < n; i++)
//         Add (s[i]);
//     Notify ();
// }

// ----------------------- Set methods ----------------------