bitvec.hxx

Go to the documentation of this file.

/*
 *   xyzzy
 *   Copyright (C) 2007    Karl W. Pfalzer
 *
 *   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.
 *   51 Franklin Street, Fifth Floor
 *   Boston, MA  02110-1301, USA.
 */
#if !defined(_xyzzy_bitvec_hxx_)
#    define  _xyzzy_bitvec_hxx_

#include "xyzzy/portable.hxx"
#include "xyzzy/exception.hxx"
#include "xyzzy/assert.hxx"
#include "xyzzy/util.hxx"

namespace xyzzy
{

//  Base class
class TBvBase
{
public:
    unsigned length() const
    {
        return length(lb, rb);
    }

    bool isDescending() const
    {
        return isDescending(lb, rb);
    }

    unsigned left() const
    {
        return lb;
    }

    unsigned right() const
    {
        return rb;
    }

    unsigned offset(unsigned right) const;

    bool checkBounds(unsigned left, unsigned right) const;

    static unsigned length(unsigned left, unsigned right);

    static bool isDescending(unsigned left, unsigned right)
    {
        return (left >= right);
    }

protected:
    explicit TBvBase(unsigned lb, unsigned rb)
    :   lb(lb), rb(rb)
    {}

    const unsigned  lb, rb;

private:
};

template<typename T>
class PTBitVecMethods
{
public:
    static const T& assign(T& lhs);
    static const T& assign(T& lhs, const TBvBase& bref, const T v);
    static T assign(T& lhs, const TBvBase& bref, const T& v,
                    unsigned lb, unsigned rb);
    static T valueAt(const T& v, const TBvBase& bref,
                     unsigned lb, unsigned rb);
    static bool valueAt(const T& v, const TBvBase& bref, unsigned ix);
    static unsigned getMaxBits();
    
    static const unsigned stMaxBits;

    static const T stAllOnes;

private:
    static T onesMask(unsigned lb, unsigned rb);
};

template<typename T>
class PTBitVec : public TBvBase
{
public:
    explicit PTBitVec(unsigned lb, unsigned rb)
    :   TBvBase(lb, rb)
    {
        invariant(PTBitVecMethods<T>::stMaxBits >= length());
        PTBitVecMethods<T>::assign(val);
    }

    explicit PTBitVec(unsigned len)
    :   TBvBase(len - 1, 0)
    {
        invariant(PTBitVecMethods<T>::stMaxBits >= length());
        PTBitVecMethods<T>::assign(val);
    }

    explicit PTBitVec(const PTBitVec& r)
    :   TBvBase(r.lb, r.rb)
    {
        invariant(PTBitVecMethods<T>::stMaxBits >= length());
        PTBitVecMethods<T>::assign(val, *this, r.val);
    }
    
    const PTBitVec& operator =(const PTBitVec& r)
    {
        //TODO: range check !
        val = r.val;
        return *this;
    }
    
    const PTBitVec& operator =(const T& v)
    {
        //TODO: valid range check
        PTBitVecMethods<T>::assign(val, *this, v);
        return *this;
    }
    
    class TAccessor
    {
    private:
        explicit TAccessor(PTBitVec &r, unsigned lb, unsigned rb)
        :   ref(r), lb(lb), rb(rb)
        {}

    public:
        operator T() const
        {
            return PTBitVecMethods<T>::valueAt(ref.val, ref, lb, rb);
        }

        T operator =(const TAccessor& v)
        {
            //T vt = v;
            return PTBitVecMethods<T>::assign(ref.val, ref, v, lb, rb);
        }

        T operator =(const T& v)
        {
            return PTBitVecMethods<T>::assign(ref.val, ref, v, lb, rb);
        }

    private:
        PTBitVec&   ref;
        unsigned    lb, rb;

        friend class PTBitVec;
    };

    TAccessor operator ()(unsigned l, unsigned r)
    {
        return TAccessor(*this, l, r);
    }

    TAccessor operator ()(unsigned ix)
    {
        return TAccessor(*this, ix, ix);
    }

    TAccessor operator [](unsigned ix)
    {
        return operator()(ix);
    }

    operator T () const
    {
        return val;
    }

private:
    T   val;

    friend class TAccessor;
};

#define GEN_BOUNDS(lb_, rb_) (rb_ != ~0u) ? lb_ : (lb_-1), (rb_ != ~0u) ? rb_ : 0

template<unsigned LB, unsigned RB = ~0>
class TBitVec : public PTBitVec<TUint32>
{
public:
    explicit TBitVec()
    :   PTBitVec<TUint32>(GEN_BOUNDS(LB,RB))
    {}

    TBitVec(TUint32 n)
    :   PTBitVec<TUint32>(GEN_BOUNDS(LB,RB))
    {
        PTBitVec<TUint32>::operator =(n);
    }
    
    const TBitVec& operator =(TUint32 v)
    {
        PTBitVec<TUint32>::operator =(v);
        return *this;
    }
};

template<unsigned LB, unsigned RB = ~0>
class TBitVec64 : public PTBitVec<TUint64>
{
public:
    explicit TBitVec64()
    :   PTBitVec<TUint64>(GEN_BOUNDS(LB,RB))
    {}

    TBitVec64(TUint64 n)
    :   PTBitVec<TUint64>(GEN_BOUNDS(LB,RB))
    {
        PTBitVec<TUint64>::operator =(n);
    }
    
    const TBitVec64& operator =(TUint64 v)
    {
        PTBitVec<TUint64>::operator =(v);
        return *this;
    }
};

#undef GEN_BOUNDS

// BEGIN: template definitions
template<typename T>
const T&
PTBitVecMethods<T>::assign(T& lhs)
{
    lhs = 0xdeadbeef;
    return lhs;
}

template<typename T>
T 
PTBitVecMethods<T>::onesMask(unsigned lb, unsigned rb)
{
    const unsigned n = TBvBase::length(lb, rb);
    return ~((stMaxBits == n) ? 0 : (stAllOnes << n));
}

template<typename T>
const T&
PTBitVecMethods<T>::assign(T& lhs, const TBvBase& bref, 
                           const T v)
{
    lhs = v & onesMask(bref.left(), bref.right());
    return lhs;
}

template<typename T>
T
PTBitVecMethods<T>::valueAt(const T& v, const TBvBase& bref,
                            unsigned lb, unsigned rb)
{
    bref.checkBounds(lb, rb);
    T rval = (v >> bref.offset(rb)) & onesMask(lb, rb);
    return rval;
}

template<typename T>
T
PTBitVecMethods<T>::assign(T& lhs, const TBvBase& bref, 
                           const T& v,
                           unsigned lb, unsigned rb)
{
    bref.checkBounds(lb, rb);
    T val = lhs;
    // zero out bit slots we will set
    unsigned offset = bref.offset(rb);
    ASSERT_TRUE(offset < stMaxBits);
    T mask = onesMask(lb, rb) << offset; // mask <= 1s covering [lb,rb]
    val &= ~mask;    // val <= zero out [lb,rb]
    T v2 = v;
    v2 <<= offset;  // ...v000
    v2 &= mask;
    val |= v2;
    lhs = val;
    return valueAt(lhs, bref, lb, rb);
}

template<typename T>
bool
PTBitVecMethods<T>::valueAt(const T& v, const TBvBase& bref,
                            unsigned ix)
{
    return (0 != valueAt(v, bref, ix, ix)) ? true : false;
}
// END: template definitions

};

#endif //defined(_xyzzy_bitvec_hxx_)

---