bitset.cpp

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

void CL_BitSet::MakeEmpty ()
{
    if (!PrepareToChange())
        return;
    ulong* p = _rep;
    for (long i = 0; i < _count; i++)
        *p++ = (ulong) 0;
    _size = 0;
    Notify();
}



// Make this the universal set:
void CL_BitSet::MakeUniversal ()
{
    if (!PrepareToChange())
        return;
    register ulong* p = _rep;
    for (register long i = 0; i < _count; i++)
        *p++ = (ulong) (-1);
    _size = __Mul32 (_count);
    Notify();
}


bool CL_BitSet::IsUniversal () const
{
    return Size() == __Mul32 (_count);
}

CL_IntegerSet CL_BitSet::AsSet () const
{
    CL_IntegerSet aSet;
    
    long offset = 0;
    for (long i = 0; i < _count; i++, offset += BitsInLong) {
        register ulong mask = 1;
        register ulong data = _rep[i];
        for (short j = 0; j < BitsInLong; j++) {
            if (data & mask)
                aSet.Add (offset + j);
            mask <<= 1;
        }
    }
    return aSet;
}


            
CL_BitSet& CL_BitSet::operator = (const CL_BitSet& o)
{
    if (!PrepareToChange())
        return *this;
    if (_count != o._count) {
        delete [] _rep;
        _rep = new ulong[_count = o._count];
        if (!_rep) {
            _count = 0;
            return *this;
        }
    }
    for (long i = 0; i < _count; i++)
        _rep[i] = o._rep[i];
    _size = o._size;
    Notify();
    return *this;
}





static void DoOr (ulong& w1, ulong w2)
{
    w1 |= w2;
}


static void DoAnd (ulong& w1, ulong w2)
{
    w1 &= w2;
}


static void DoDiff (ulong& w1, ulong w2)
{
    w1 &= ~w2;
}



CL_BitSet CL_BitSet::_DoOp (const CL_BitSet& s, void (*opr)(ulong&, ulong))
    const
{
    long cnt = maxl (s._count, _count);
    ulong* new_rep = new ulong[cnt];
    if (! new_rep)
        return *this; // No memory
    long i;
    for (i = 0; i < cnt; i++)
        new_rep[i] = (i < _count) ? _rep[i] : 0;
    for (i = 0; i < s._count; i++) {
        (*opr) (new_rep[i], s._rep[i]);
    }
    CL_BitSet o (cnt, new_rep);
    return o;
}


// Union:
CL_BitSet CL_BitSet::operator + (const CL_BitSet& s) const
{
    return _DoOp (s, DoOr);
}



// Difference:
CL_BitSet CL_BitSet::operator - (const CL_BitSet& s) const
{
    return _DoOp (s, DoDiff);
}



// Intersection:
CL_BitSet CL_BitSet::operator * (const CL_BitSet& s) const
{
    return _DoOp (s, DoAnd);
}

// Complement:
CL_BitSet CL_BitSet::operator ~ () const
{
    CL_BitSet s (*this);
    for (long i = 0; i < _count; i++)
        s._rep[i] = ~s._rep[i];
    s._size = s._count * BitsInLong - _size;
    return s;
}





// CL_Set<long> CL_BitSet::operator + (const CL_Set<long>& s) const
// {
//     CL_Set<long> t = s;
//     for (long i = 0; i < _count; i++) {
//         ulong b = _rep[i];
//         for (short j = 0; j < BitsInLong; j++) {
//             if (b & 1)
//                 t.Add (i*BitsInLong + j);
//             b >>= 1;
//         }
//     }
//     return t;
// }
// 
// 
// 
// // Difference:
// CL_Set<long> CL_BitSet::operator - (const CL_Set<long>& s) const
// {
//     CL_Set<long> t;
//     for (long i = 0; i < _count; i++) {
//         ulong b = _rep[i];
//         for (short j = 0; j < BitsInLong; j++) {
//             if (b & 1)
//                 t.Add (i*BitsInLong + j);
//             b >>= 1;
//         }
//     }
//     return t - s;
// }
// 
// 
// 
// // Intersection:
// CL_Set<long> CL_BitSet::operator * (const CL_Set<long>& s) const
// {
//     CL_Set<long> t;
//     for (long i = 0; i < _count; i++) {
//         ulong b = _rep[i];
//         for (short j = 0; j < BitsInLong; j++) {
//             if (b & 1)
//                 t.Add (i*BitsInLong + j);
//             b >>= 1;
//         }
//     }
//     return t * s;
// }
// 
// 
// 
// 
// 
bool CL_BitSet::operator == (const CL_IntegerSet& o) const
{
    if (Size() != o.Size())
        return FALSE;
    for (long i = 0; i < _count; i++) {
        ulong b = _rep[i];
        for (short j = 0; j < BitsInLong; j++) {
            if (b & 1)
                if (!o.Includes (i*BitsInLong + j))
                    return FALSE;
            b >>= 1;
        }
    }
    return TRUE;
}


bool CL_BitSet::operator == (const CL_BitSet& o) const
{
    if (_size != o._size)
        return FALSE;
    for (long i = 0; i < minl (o._count, _count); i++) {
        if (_rep[i] != o._rep[i])
            return FALSE;
    }
    return TRUE;
}



bool CL_BitSet::IncludesAll (const CL_IntegerSet& o) const
{
    long n = o.Size();
    for (long i = 0; i < n; i++)
        if (!Includes (o.ItemWithRank(i)))
            return FALSE;
    return TRUE;
}


bool CL_BitSet::IncludesAll (const CL_BitSet& o) const
{
    if (_size < o._size)
        return FALSE;
    register long n;
    if (o._count > _count) {
        for (register long i = _count; i < o._count; i++)
            if (o._rep[i] != 0)
                return FALSE;
        n = _count;
    }
    else
        n = o._count;  // n is the smaller of the two counts
    for (register long i = 0; i < n; i++) {
        register ulong p = _rep[i];
        register ulong q = o._rep[i];
        if (p | q != p)
            return FALSE;
    }
    return TRUE;
}



// ------------------------ Save/restore -------------------------

long CL_BitSet::StorableFormWidth() const
{
    return sizeof (CL_ClassId) + sizeof (long) + sizeof (ulong) +
        _count*sizeof (ulong);
}



bool CL_BitSet::ReadFrom (const CL_Stream& s)
{
    if (!PrepareToChange())
        return 0;
    if (!ReadClassId (s))
        return FALSE;
    long  new_count;
    if (!s.Read (new_count))
        return FALSE;
    if (!s.Read (_size))
        return FALSE;
    if (new_count != _count) {
        ulong* new_rep   = new ulong [new_count];
        if (!new_rep) 
            return FALSE; // No memory
        if (_rep)
            delete [] _rep;
        _rep = new_rep;
        _count = new_count;
    }
    if (!s.Read ((uchar*) _rep, _count*sizeof(ulong)))
        return FALSE;
//     _size = 0;
//     for (long i = 0; i < _count; i++) {
//         _size += BitCount (_rep[i]);
//     }
    Notify();
    return TRUE;
}

bool CL_BitSet::WriteTo  (CL_Stream& s) const
{
    return s.Write (ClassId())  &&
        s.Write (_count) && s.Write (_size) &&
        s.Write ((uchar*) _rep, _count*sizeof(ulong));
}




// ---------------------- BitSetIterator methods ----------------------

CL_BitSetIterator::CL_BitSetIterator (const CL_BitSet& o)
: _set (o)
{
    _count = _index = 0;
    _tblIndex = 0;
}





void CL_BitSetIterator::Reset ()
{
    _index = _count = 0;
    _tblIndex = 0;
}



void CL_BitSetIterator::BeginFromRank (long l)
{
    register ulong* p = _set._rep;
    _count = maxl (0, l);
    if (!p)
        return;
    register long i;
    for (i = 0; i < _set._count; i++, p++) {
        short q = BitCount (*p);
        if (l < q) break;
        l -= q;
    }
    _index = i;
    if (i < _set._count) {
        register ulong r = _set._rep[i];
        register short j;
        for (j = 0; j < BitsInLong; j++)
            if (BitTable[j] & r) {
                l--;
                if (l < 0)
                    break;
            }
        _tblIndex = j;
            
    }
}



bool CL_BitSetIterator::More () const
{
    return _count < _set.Size();
}


long CL_BitSetIterator::Next ()
{
    if (_count >= _set.Size())
        return -1;
    ulong* p = _set._rep;
    while (_index < _set._count) {
        ulong mask =  BitTable[_tblIndex];
    if (mask & p[_index]) break;
        _tblIndex++;
        if (_tblIndex >= BitsInLong) {
            _tblIndex = 0;
            _index++;
        }
    }
    if (_index < _set._count) {
        long ret = __Mul32 (_index) + _tblIndex;
        _count++;
        _tblIndex++;
        if (_tblIndex >= BitsInLong) {
            _tblIndex = 0;
            _index++;
        }
        return ret;
    }

    return -1;
}