bitsets.h

Go to the documentation of this file.

// Copyright (C) 1997-2010 by Pawel Pilarczyk.
//
// This file is part of the Homology Library.  This library 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 library 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 February 22, 2007. Last revision: June 11, 2010.


#ifndef _CHOMP_STRUCT_BITSETS_H_
#define _CHOMP_STRUCT_BITSETS_H_

#include "chomp/system/config.h"

#include <iostream>
#include <cstdlib>

namespace chomp {
namespace homology {


// --------------------------------------------------
// ------------------- BitSets ---------------------
// --------------------------------------------------

class BitSets
{
public:
        BitSets (int_t _nsets, int_t _nelem);

        BitSets (const BitSets &s);

        BitSets &operator = (const BitSets &s);

        ~BitSets ();

        void add (int_t n, int_t e);

        void remove (int_t n, int_t e);

        bool check (int_t n, int_t e) const;

        void addset (int_t n, int_t m);

        int_t get (int_t n, int_t start = 0) const;

private:
        int_t nsets;
        
        int_t nelem;

        int_t nbytes;

        unsigned char *bits;

}; /* BitSets */

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

inline BitSets::BitSets (int_t _nsets, int_t _nelem):
        nsets (_nsets), nelem (_nelem), nbytes ((_nelem + 7) >> 3), bits (0)
{
        int_t size = nsets * nbytes;
        bits = new unsigned char [size];
        for (int_t i = 0; i < size; ++ i)
                bits [i] = 0;
        return;
} /* BitSets::BitSets */

inline BitSets::BitSets (const BitSets &s):
        nsets (s. nsets), nelem (s. nelem), nbytes (s. nbytes), bits (0)
{
        int_t size = nsets * nbytes;
        bits = new unsigned char [size];
        for (int_t i = 0; i < size; ++ i)
                bits [i] = s. bits [i];
        return;
} /* BitSets::BitSets */

inline BitSets &BitSets::operator = (const BitSets &s)
{
        delete [] bits;
        nsets = s. nsets;
        nelem = s. nelem;
        nbytes = s. nbytes;
        int_t size = nsets * nbytes;
        bits = new unsigned char [size];
        for (int_t i = 0; i < size; ++ i)
                bits [i] = s. bits [i];
        return *this;
} /* BitSets::operator = */

inline BitSets::~BitSets ()
{
        delete [] bits;
        return;
} /* BitSets::~BitSets */

inline void BitSets::add (int_t n, int_t e)
{
//      sbug << "Add " << e << " to " << n << ".\n";
        unsigned char *buf = bits + n * nbytes;
        buf [e >> 3] |= (unsigned char) (0x01 << (e & 0x07));
        return;
} /* BitSets::add */

inline void BitSets::remove (int_t n, int_t e)
{
        unsigned char *buf = bits + n * nbytes;
        buf [e >> 3] &= (unsigned char) ~(0x01 << (e & 0x07));
        return;
} /* BitSets::remove */

inline bool BitSets::check (int_t n, int_t e) const
{
        unsigned char *buf = bits + n * nbytes;
        return !!(buf [e >> 3] & (0x01 << (e & 0x07)));
} /* BitSets::check */

inline void BitSets::addset (int_t n, int_t m)
{
        unsigned char *nbuf = bits + n * nbytes;
        unsigned char *mbuf = bits + m * nbytes;
        for (int_t i = 0; i < nbytes; ++ i)
                *(nbuf ++) |= *(mbuf ++);
        return;
} /* BitSets::addset */

inline int_t BitSets::get (int_t n, int_t start) const
{
        if (start >= nelem)
                return -1;
        unsigned char *buf = bits + n * nbytes;
        int_t offset = start >> 3;
        int bit = start & 0x07;
        if (buf [offset] & (0xFF << bit))
        {
                for (; bit < 8; ++ bit)
                {
                        if (buf [offset] & (0x01 << bit))
                                return (offset << 3) + bit;
                }
                throw "Wrong bit number in BitSets.";
        }
        for (++ offset; offset < nbytes; ++ offset)
        {
                if (!buf [offset])
                        continue;
                for (int bit = 0; bit < 8; ++ bit)
                {
                        if (buf [offset] & (0x01 << bit))
                                return (offset << 3) + bit;
                }
                throw "False bit in BitSets.";
        }
        return -1;
} /* BitSets::get */


} // namespace homology
} // namespace chomp

#endif // _CHOMP_STRUCT_BITSETS_H_