bitsets.h

Go to the documentation of this file.

 
 
 
// Copyright (C) 1997-2020 by Pawel Pilarczyk.
//
// This file is part of my research software 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 3 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,
// please, see <https://www.gnu.org/licenses/>.
 
// Started on February 22, 2007. Last revision: March 29, 2011.
 
 
#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
{
        static const int_t longBits = sizeof (long) * 8;
        static const int_t longBitMask = longBits - 1;
        static const int_t longBitShift = (sizeof (long) == 8) ? 6 : 5;
 
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 nunits;
 
        unsigned long *bits;
 
        int_t arraySize ();
 
}; /* BitSets */
 
// --------------------------------------------------
 
inline int_t BitSets::arraySize ()
{
        long size = static_cast<long> (nsets) * static_cast<long> (nunits);
        if (static_cast<long> (static_cast<int_t> (size)) != size)
                throw "Too large BitSets requested.";
        return static_cast<int_t> (size);
} /* BitSets::arraySize */
 
inline BitSets::BitSets (int_t _nsets, int_t _nelem):
        nsets (_nsets), nelem (_nelem),
        nunits ((_nelem + (sizeof (unsigned long) << 3) - 1) /
        (sizeof (unsigned long) << 3)), bits (0)
{
        int_t size = arraySize ();
        bits = new unsigned long [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), nunits (s. nunits), bits (0)
{
        int_t size = arraySize ();
        bits = new unsigned long [size];
        for (int_t i = 0; i < size; ++ i)
                bits [i] = s. bits [i];
        return;
} /* BitSets::BitSets */
 
inline BitSets &BitSets::operator = (const BitSets &s)
{
        if (this == &s)
                return *this;
        delete [] bits;
        nsets = s. nsets;
        nelem = s. nelem;
        nunits = s. nunits;
        int_t size = arraySize ();
        bits = new unsigned long [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 long *buf = bits + n * nunits;
        buf [e >> longBitShift] |= (1ul << (e & longBitMask));
        return;
} /* BitSets::add */
 
inline void BitSets::remove (int_t n, int_t e)
{
        unsigned long *buf = bits + n * nunits;
        buf [e >> longBitShift] &= ~(1ul << (e & longBitMask));
        return;
} /* BitSets::remove */
 
inline bool BitSets::check (int_t n, int_t e) const
{
        unsigned long *buf = bits + n * nunits;
        return !!(buf [e >> longBitShift] & (1ul << (e & longBitMask)));
} /* BitSets::check */
 
inline void BitSets::addset (int_t n, int_t m)
{
        unsigned long *nbuf = bits + n * nunits;
        unsigned long *mbuf = bits + m * nunits;
        for (int_t i = 0; i < nunits; ++ i)
                *(nbuf ++) |= *(mbuf ++);
        return;
} /* BitSets::addset */
 
inline int_t BitSets::get (int_t n, int_t start) const
{
        if (start >= nelem)
                return -1;
        unsigned long *buf = bits + n * nunits;
        int_t offset = start >> longBitShift;
        int bit = start & longBitMask;
        if (buf [offset] & (~0ul << bit))
        {
                for (; bit < longBits; ++ bit)
                {
                        if (buf [offset] & (1ul << bit))
                                return (offset << longBitShift) + bit;
                }
                throw "Wrong bit number in BitSets.";
        }
        for (++ offset; offset < nunits; ++ offset)
        {
                if (!buf [offset])
                        continue;
                for (int bit = 0; bit < longBits; ++ bit)
                {
                        if (buf [offset] & (1ul << bit))
                                return (offset << longBitShift) + bit;
                }
                throw "False bit in BitSets.";
        }
        return -1;
} /* BitSets::get */
 
 
} // namespace homology
} // namespace chomp
 
#endif // _CHOMP_STRUCT_BITSETS_H_