bitvect.h

Go to the documentation of this file.

/// @addtogroup unifexp
/// @{

/////////////////////////////////////////////////////////////////////////////
///
/// @file bitvect.h
///
/// This file contains the definition of a simple bit vector class.
///
/// @author Pawel Pilarczyk
///
/////////////////////////////////////////////////////////////////////////////

// Copyright (C) 2007 by Pawel Pilarczyk.
//
// This file is part of my research program package.  This 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 software 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 software; see the file "license.txt".  If not, write to the
// Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// Started on March 8, 2007. Last revision: August 22, 2007.

#ifndef _bitvect_h_
#define _bitvect_h_

namespace unifexp {


// --------------------------------------------------
// ------------------- bit vector -------------------
// --------------------------------------------------

/// This class defines a bit vector of fixed length.
/// The bits are initially zero, and can be marked and unmarked.
/// Additionally, convenient functions are available to search
/// for the first marked/unmarked bit in the vector.
class bitVector
{
public:
        /// The constructor of a bit vector of the given size.
        bitVector (int length);

        /// The destructor.
        ~bitVector ();

        /// Marks the given bit.
        void mark (int bit);

        /// Unmarks the given bit.
        void unmark (int bit);

        /// Finds the first marked bit starting at the given position.
        /// If not found, returns 'length'.
        int findMarked (int start, int length) const;

        /// Finds the first unmarked bit starting at the given position.
        /// If not found, returns 'length'.
        int findUnmarked (int start, int length) const;

private:
        /// The copy constructor is not allowed.
        bitVector (const bitVector &b);

        /// The assignment operator is not allowed.
        bitVector &operator = (const bitVector &b);

        /// The array of bytes that represents the bitvector.
        unsigned char *buf;

        /// Temporarily: The actual size of the buffer.
        int bufSize;

}; /* class bitVector */

// --------------------------------------------------

inline bitVector::bitVector (int length)
{
        int size = (length + 7) >> 3;
        if (!size)
                size = 1;
        buf = new unsigned char [size];
        for (int i = 0; i < size; ++ i)
                buf [i] = 0;
        bufSize = size;
        return;
} /* bitVector::bitVector */

inline bitVector::~bitVector ()
{
        delete [] buf;
        return;
} /* bitVector::~bitVector */

inline bitVector::bitVector (const bitVector &)
{
        throw "Copy constructor not implemented for bit vectors.";
        return;
} /* bitVector::bitVector */

inline bitVector &bitVector::operator = (const bitVector &)
{
        throw "Assignment operator not implemented for bit vectors.";
        return *this;
} /* bitVector::operator = */

inline void bitVector::mark (int bit)
{
        int offset = bit >> 3;
        if (offset >= bufSize)
                throw "Wrong bit in a bit vector marked.";
        buf [offset] |= 1 << (bit & 7);
        return;
} /* bitVector::mark */

inline void bitVector::unmark (int bit)
{
        int offset = bit >> 3;
        if (offset >= bufSize)
                throw "Wrong bit in a bit vector marked.";
        buf [offset] &= ~(1 << (bit & 7));
        return;
} /* bitVector::unmark */

inline int bitVector::findMarked (int first, int length) const
{
        if (first >= length)
                return length;
        int offset = first >> 3;
        int maxoffset = (length + 7) >> 3;
        if (offset >= bufSize)
                throw "Wrong first marked bit in a bit vector to search.";
        if (maxoffset > bufSize)
                throw "Wrong length of a bit vector to search for marked.";
        if (buf [offset])
        {
                for (int i = first & 7; i < 8; ++ i)
                {
                        if (buf [offset] & (1 << i))
                                return ((offset << 3) + i);
                }
        }
        ++ offset;
        for (;offset < maxoffset; ++ offset)
        {
                if (!buf [offset])
                        continue;
                for (int i = 0; i < 8; ++ i)
                {
                        if (buf [offset] & (1 << i))
                                return ((offset << 3) + i);
                }
        }
        return length;
} /* bitVector::findMarked */

inline int bitVector::findUnmarked (int first, int length) const
{
//      if (first >= length)
//              return length;
        int offset = first >> 3;
        int maxoffset = (length + 7) >> 3;
        if (offset >= bufSize)
                throw "Wrong first unmarked bit in a bit vector to search.";
        if (maxoffset > bufSize)
                throw "Wrong length of a bit vector to search for unmarked.";
        if (buf [offset] != 0xFFu)
        {
                for (int i = first & 7; i < 8; ++ i)
                {
                        if (!(buf [offset] & (1 << i)))
                                return ((offset << 3) + i);
                }
        }
        ++ offset;
        for (;offset < maxoffset; ++ offset)
        {
                if (buf [offset] == 0xFFu)
                        continue;
                for (int i = 0; i < 8; ++ i)
                {
                        if (!(buf [offset] & (1 << i)))
                                return ((offset << 3) + i);
                }
        }
        return length;
} /* bitVector::findUnmarked */


} // namespace unifexp

#endif // _bitvect_h_

/// @}