// -*- c++ -*- /* * Jakelib2 - General purpose C++ library * Copyright (C) 2001 Florian Wolff (florian@donuz.de) * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 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 * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * * $Id: BitSet.jlc,v 1.5 2003/09/27 08:10:29 florian Exp $ */ #include "jakelib2.h" #include "jakelib2/util/BitSet.h" #include "jakelib2/lang/Integer.h" #include "jakelib2/lang/Math.h" using namespace jakelib::lang; using namespace jakelib::util; JAKELIB_IMPLEMENT_CLASS("jakelib.util.BitSet", BitSet, Object) int BitSet::ADDRESS_BITS_PER_UNIT = 6; int BitSet::BITS_PER_UNIT = 1 << ADDRESS_BITS_PER_UNIT; int BitSet::BIT_INDEX_MASK = BITS_PER_UNIT - 1; int BitSet::UNIT_SIZE = sizeof(long) * 8; /*****************************************************************************\ * BitSet | *****************************************************************************/ BitSet::BitSet() { init(BITS_PER_UNIT); } BitSet::BitSet(int nbits) { init(nbits); } BitSet::~BitSet() { free(bits); } /*****************************************************************************\ * init | *****************************************************************************/ void BitSet::init(int nbits) { /* nbits can't be negative; size 0 is OK */ if (nbits < 0) throw new IllegalArgumentException(`""` .. nbits .. `" < 0"` .. JAKELIB_AT2("jakelib.util.BitSet.init")); bits_length = (unitIndex(nbits-1) + 1); bits = (long*) malloc(sizeof(long) * bits_length); unitsInUse = 0; } /*****************************************************************************\ * ensureCapacity | *****************************************************************************/ void BitSet::ensureCapacity(int unitsRequired) { if (bits_length < unitsRequired) { // Allocate larger of doubled size or required size int request = Math::max(2 * bits_length, unitsRequired); long* newBits = (long*) realloc(bits, sizeof(long) * request); if (newBits == null) throw new MemoryException(`"BitSet.ensureCapacity"` .. JAKELIB_AT2("jakelib.util.BitSet.ensureCapacity")); bits = newBits; bits_length = request; } } /*****************************************************************************\ * unitIndex | *****************************************************************************/ int BitSet::unitIndex(int bitIndex) { // return bitIndex >> ADDRESS_BITS_PER_UNIT; return bitIndex / 64; } /*****************************************************************************\ * bit | *****************************************************************************/ long BitSet::bit(int bitIndex) { return 1L << bitIndex; } /*****************************************************************************\ * recalculateUnitsInUse | *****************************************************************************/ void BitSet::recalculateUnitsInUse() { /* Traverse the bitset until a used unit is found */ int i; for (i = unitsInUse-1; i >= 0; i--) if(bits[i] != 0) break; //this unit is in use! unitsInUse = i+1; //the new logical size } /*****************************************************************************\ * length | *****************************************************************************/ int BitSet::length() { if (unitsInUse == 0) return 0; int highestBit = (unitsInUse - 1) * UNIT_SIZE; long highestUnit = bits[unitsInUse - 1]; do { highestUnit = highestUnit >> 1; highestBit++; } while(highestUnit > 0); return highestBit; } /*****************************************************************************\ * set | *****************************************************************************/ void BitSet::set(int bitIndex) { if (bitIndex < 0) throw new IndexOutOfBoundsException(Integer::toString(bitIndex)); int unitIndex = BitSet::unitIndex(bitIndex); int unitsRequired = unitIndex+1; if (unitsInUse < unitsRequired) { ensureCapacity(unitsRequired); bits[unitIndex] |= bit(bitIndex); unitsInUse = unitsRequired; } else { bits[unitIndex] |= bit(bitIndex); } } /*****************************************************************************\ * clear | *****************************************************************************/ void BitSet::clear(int bitIndex) { if (bitIndex < 0) throw new IndexOutOfBoundsException(Integer::toString(bitIndex)); int unitIndex = BitSet::unitIndex(bitIndex); if (unitIndex >= unitsInUse) return; bits[unitIndex] &= ~bit(bitIndex); if (bits[unitsInUse-1] == 0) recalculateUnitsInUse(); } /*****************************************************************************\ * andNotOp | *****************************************************************************/ void BitSet::andNotOp(BitSet* set) { int unitsInCommon = Math::min(unitsInUse, set->unitsInUse); // perform logical (a & !b) on bits in common for (int i=0; i < unitsInCommon; i++) { bits[i] &= ~set->bits[i]; } recalculateUnitsInUse(); } /*****************************************************************************\ * get | *****************************************************************************/ jboolean BitSet::get(int bitIndex) { if (bitIndex < 0) throw new IndexOutOfBoundsException(Integer::toString(bitIndex)); jboolean result; int unitIndex = BitSet::unitIndex(bitIndex); if (unitIndex < unitsInUse) result = ((bits[unitIndex] & bit(bitIndex)) != 0); else result = false; return result; } /*****************************************************************************\ * andOp | *****************************************************************************/ void BitSet::andOp(BitSet* set) { // perform logical AND on bits in common int oldUnitsInUse = unitsInUse; unitsInUse;// = min(unitsInUse, set.unitsInUse); int i; for(i=0; ibits[i]; // clear out units no longer used for( ; i < oldUnitsInUse; i++) bits[i] = 0; // Recalculate units in use if necessary if (unitsInUse > 0 && bits[unitsInUse - 1] == 0) recalculateUnitsInUse(); } /*****************************************************************************\ * orOp | *****************************************************************************/ void BitSet::orOp(BitSet* set) { ensureCapacity(set->unitsInUse); // perform logical OR on bits in common int unitsInCommon = Math::min(unitsInUse, set->unitsInUse); int i; for(i=0; ibits[i]; // copy any remaining bits for(; iunitsInUse; i++) bits[i] = set->bits[i]; if (unitsInUse < set->unitsInUse) unitsInUse = set->unitsInUse; } /*****************************************************************************\ * xorOp | *****************************************************************************/ void BitSet::xorOp(BitSet* set) { int unitsInCommon; if (unitsInUse >= set->unitsInUse) { unitsInCommon = set->unitsInUse; } else { unitsInCommon = unitsInUse; int newUnitsInUse = set->unitsInUse; ensureCapacity(newUnitsInUse); unitsInUse = newUnitsInUse; } // perform logical XOR on bits in common int i; for (i=0; ibits[i]; // copy any remaining bits for ( ; iunitsInUse; i++) bits[i] = set->bits[i]; recalculateUnitsInUse(); } /*****************************************************************************\ * hashCode | *****************************************************************************/ int BitSet::hashCode() { long h = 1234; for (int i = bits_length; --i >= 0; ) h ^= bits[i] * (i + 1); return (int) h; } /*****************************************************************************\ * size | *****************************************************************************/ int BitSet::size() { // return bits_length << ADDRESS_BITS_PER_UNIT; return 0; } /*****************************************************************************\ * equals | *****************************************************************************/ jboolean BitSet::equals(Object* obj) { if (obj == null || !obj->getClass()->isInstance(this)) return false; BitSet* set = (BitSet*) obj; int minUnitsInUse = Math::min(unitsInUse, set->unitsInUse); // Check units in use by both BitSets for (int i = 0; i < minUnitsInUse; i++) if (bits[i] != set->bits[i]) return false; // Check any units in use by only one BitSet (must be 0 in other) if (unitsInUse > minUnitsInUse) { for (int i = minUnitsInUse; iunitsInUse; i++) if (set->bits[i] != 0) return false; } return true; } /*****************************************************************************\ * clone | *****************************************************************************/ Object* BitSet::clone() { // FIXME: BitSet::clone() /*BitSet* result = null; try { result = (BitSet) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } result.bits = new long[bits.length]; System.arraycopy(bits, 0, result.bits, 0, unitsInUse); return result;*/ return null; } /*****************************************************************************\ * toString | *****************************************************************************/ String* BitSet::toString() { int numBits = unitsInUse << ADDRESS_BITS_PER_UNIT; StringBuffer buf; String separator; buf.append('{'); for (int i = 0 ; i < numBits; i++) { if (get(i)) { buf.append(&separator); separator = ", "; //buffer.append(i); } } buf.append('}'); return buf.toString(); }