devel/libmdw/trunk/libmdw/src/BitSet.cpp

/***************************************************************************
 *   Copyright (C) 2010 by Jean-Baptiste Wons   *
 *   wonsjb@gmail.com   *
 *                                                                         *
 *   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.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/
#include "BitSet.h"

namespace mdw
{
namespace
{
typedef unsigned long internalItemType;
static const int internalItemSize = 64;
static const int positionShift = 6;
static const int positionMask = 0x3F;
static const internalItemType totalMask = 0xFFFFFFFFFFFFFFFFL;
static const internalItemType zero = 0L;


int numberOfLeadingZeros (internalItemType i)
{
    if (i == 0L)
        return 64;
    int n = 1;
    int x = (int) (i >> 32);
    if (x == 0)
    {
        n += 32;
        x = (int) i;
    }
    if (x >> 16 == 0)
    {
        n += 16;
        x <<= 16;
    }
    if (x >> 24 == 0)
    {
        n +=  8;
        x <<=  8;
    }
    if (x >> 28 == 0)
    {
        n +=  4;
        x <<=  4;
    }
    if (x >> 30 == 0)
    {
        n +=  2;
        x <<=  2;
    }
    n -= x >> 31;
    return n;
}


}

BitSet::BitSet (int size)
{
    int arraySize = ( (size - 1) / internalItemSize) + 1;
    _array = new internalItemType[arraySize];
    _size = size;
}


BitSet::~BitSet()
{
    delete[] ( (internalItemType*) _array);
}

void BitSet::clearAll()
{
    int arraySize = ( (_size - 1) / internalItemSize) + 1;
    for (int i = 0; i < arraySize; ++i)
    {
        ( (internalItemType*) _array) [i] = zero;
    }
}

void BitSet::clearBetween (int from, int to)
{
    ++from;
    --to;
    int posArrayFrom = from >> positionShift;
    int posItemFrom = from & positionMask;
    int posArrayTo = to >> positionShift;
    int posItemTo = to & positionMask;
    if (posArrayFrom == posArrayTo)
    {
        internalItemType mask = (totalMask << posItemFrom) & totalMask >> (internalItemSize - 1 - posItemTo);
        ( (internalItemType*) _array) [posArrayFrom] &= ~mask;
    }
    else
    {
        ( (internalItemType*) _array) [posArrayFrom] &= ~ (totalMask << posItemFrom);
        ( (internalItemType*) _array) [posArrayTo] &= ~ (totalMask >> (internalItemSize - 1 - posItemTo));
        for (int i = posArrayFrom + 1; i < posArrayTo; ++i)
        {
            ( (internalItemType*) _array) [i] = zero;
        }
    }
}

bool BitSet::isSet (int pos)
{
    int positionArray = pos >> positionShift;
    internalItemType localMask = 1L << (pos & positionMask);
    return ( ( (internalItemType*) _array) [positionArray] & localMask) == localMask;;
}

void BitSet::set (int pos)
{
    int positionArray = pos >> positionShift;
    internalItemType localMask = 1L << (pos & positionMask);
    ( (internalItemType*) _array) [positionArray] |= localMask;
}

void BitSet::clear (int pos)
{
    int positionArray = pos >> positionShift;
    internalItemType localMask = 1L << (pos & positionMask);
    ( (internalItemType*) _array) [positionArray] &= ~localMask;
}

int BitSet::getPreviousSet (int pos)
{
    if (pos == 0)
    {
        return -1;
    }
    pos--;
    int positionArray = pos >> positionShift;
    int positionItem = pos & positionMask;

    internalItemType mask = ~ (totalMask << positionItem + 1);
    internalItemType word = ( (internalItemType*) _array) [positionArray] & mask;

    while (true)
    {
        if (word != 0)
        {
            return (positionArray * internalItemSize) + internalItemSize - 1 - numberOfLeadingZeros (word);
        }

        if (positionArray == 0)
        {
            return -1;
        }
        --positionArray;
        word = ( (internalItemType*) _array) [positionArray];
    }


}

}

---