| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #include "BitSet.h" |
| |
| #include <decaf/lang/exceptions/IndexOutOfBoundsException.h> |
| #include <decaf/lang/exceptions/NegativeArraySizeException.h> |
| #include <decaf/lang/exceptions/OutOfMemoryError.h> |
| |
| #include <decaf/lang/System.h> |
| #include <decaf/lang/Integer.h> |
| #include <decaf/lang/Math.h> |
| |
| using namespace std; |
| using namespace decaf; |
| using namespace decaf::lang; |
| using namespace decaf::lang::exceptions; |
| using namespace decaf::util; |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| namespace { |
| |
| static const int OFFSET = 6; |
| static const int ELM_SIZE = 1 << OFFSET; |
| static const int RIGHT_BITS = ELM_SIZE - 1; |
| |
| static unsigned long long TWO_N_ARRAY[64] = { |
| 0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000004ULL, |
| 0x0000000000000008ULL, 0x0000000000000010ULL, 0x0000000000000020ULL, |
| 0x0000000000000040ULL, 0x0000000000000080ULL, 0x0000000000000100ULL, |
| 0x0000000000000200ULL, 0x0000000000000400ULL, 0x0000000000000800ULL, |
| 0x0000000000001000ULL, 0x0000000000002000ULL, 0x0000000000004000ULL, |
| 0x0000000000008000ULL, 0x0000000000010000ULL, 0x0000000000020000ULL, |
| 0x0000000000040000ULL, 0x0000000000080000ULL, 0x0000000000100000ULL, |
| 0x0000000000200000ULL, 0x0000000000400000ULL, 0x0000000000800000ULL, |
| 0x0000000001000000ULL, 0x0000000002000000ULL, 0x0000000004000000ULL, |
| 0x0000000008000000ULL, 0x0000000010000000ULL, 0x0000000020000000ULL, |
| 0x0000000040000000ULL, 0x0000000080000000ULL, 0x0000000100000000ULL, |
| 0x0000000200000000ULL, 0x0000000400000000ULL, 0x0000000800000000ULL, |
| 0x0000001000000000ULL, 0x0000002000000000ULL, 0x0000004000000000ULL, |
| 0x0000008000000000ULL, 0x0000010000000000ULL, 0x0000020000000000ULL, |
| 0x0000040000000000ULL, 0x0000080000000000ULL, 0x0000100000000000ULL, |
| 0x0000200000000000ULL, 0x0000400000000000ULL, 0x0000800000000000ULL, |
| 0x0001000000000000ULL, 0x0002000000000000ULL, 0x0004000000000000ULL, |
| 0x0008000000000000ULL, 0x0010000000000000ULL, 0x0020000000000000ULL, |
| 0x0040000000000000ULL, 0x0080000000000000ULL, 0x0100000000000000ULL, |
| 0x0200000000000000ULL, 0x0400000000000000ULL, 0x0800000000000000ULL, |
| 0x1000000000000000ULL, 0x2000000000000000ULL, 0x4000000000000000ULL, |
| 0x8000000000000000ULL }; |
| |
| int pop(unsigned long long x) { |
| x = x - ((x >> 1) & 0x55555555); |
| x = (x & 0x33333333) + ((x >> 2) & 0x33333333); |
| x = (x + (x >> 4)) & 0x0f0f0f0f; |
| x = x + (x >> 8); |
| x = x + (x >> 16); |
| return (int) x & 0x0000003f; |
| } |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| BitSet::BitSet() : bits(new unsigned long long[1]), bitsSize(1), needClear(false), actualArrayLength(0), isLengthActual(true) { |
| bits[0] = 0ULL; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| BitSet::BitSet(int bitCount) : bits(0), bitsSize(0), needClear(false), actualArrayLength(0), isLengthActual(true) { |
| |
| if (bitCount < 0) { |
| throw NegativeArraySizeException(__FILE__, __LINE__, ""); |
| } |
| |
| bitsSize = (bitCount >> OFFSET) + ((bitCount & RIGHT_BITS) > 0 ? 1 : 0); |
| try { |
| bits = new unsigned long long[bitsSize]; |
| |
| if (bits == NULL) { |
| throw OutOfMemoryError(__FILE__, __LINE__, "Failed to allocate bit array."); |
| } |
| |
| for (int i = 0; i < bitsSize; ++i) { |
| bits[i] = 0ULL; |
| } |
| } catch (std::bad_alloc& e) { |
| throw OutOfMemoryError(__FILE__, __LINE__, "Failed to allocate bit array."); |
| } |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| BitSet::BitSet(unsigned long long* bits, int bitsSize, bool needClear, int actualArrayLength, bool isLengthActual) : |
| bits(bits), bitsSize(bitsSize), needClear(needClear), actualArrayLength(actualArrayLength), isLengthActual(isLengthActual) { |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| BitSet::~BitSet() { |
| try { |
| delete [] bits; |
| } |
| DECAF_CATCHALL_NOTHROW() |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| BitSet::BitSet(const BitSet& set) : bits(0), bitsSize(0), needClear(false), actualArrayLength(0), isLengthActual(true) { |
| |
| this->actualArrayLength = set.actualArrayLength; |
| this->isLengthActual = set.isLengthActual; |
| this->needClear = set.needClear; |
| this->bitsSize = set.bitsSize; |
| |
| try { |
| bits = new unsigned long long[bitsSize]; |
| |
| if (bits == NULL) { |
| throw OutOfMemoryError(__FILE__, __LINE__, "Failed to allocate bit array."); |
| } |
| |
| System::arraycopy(set.bits, 0, bits, 0, set.bitsSize); |
| |
| } catch (std::bad_alloc& e) { |
| throw OutOfMemoryError(__FILE__, __LINE__, "Failed to allocate bit array."); |
| } |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| BitSet& BitSet::operator= (const BitSet& set) { |
| |
| delete [] this->bits; |
| |
| this->actualArrayLength = set.actualArrayLength; |
| this->isLengthActual = set.isLengthActual; |
| this->needClear = set.needClear; |
| this->bitsSize = set.bitsSize; |
| |
| try { |
| bits = new unsigned long long[bitsSize]; |
| |
| if (bits == NULL) { |
| throw OutOfMemoryError(__FILE__, __LINE__, "Failed to allocate bit array."); |
| } |
| |
| System::arraycopy(set.bits, 0, bits, 0, set.bitsSize); |
| |
| } catch (std::bad_alloc& e) { |
| throw OutOfMemoryError(__FILE__, __LINE__, "Failed to allocate bit array."); |
| } |
| |
| return *this; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| void BitSet::AND(const BitSet& set) { |
| |
| unsigned long long* bsBits = set.bits; |
| |
| if (!needClear) { |
| return; |
| } |
| |
| int length1 = actualArrayLength, length2 = set.actualArrayLength; |
| if (length1 <= length2) { |
| for (int i = 0; i < length1; i++) { |
| bits[i] &= bsBits[i]; |
| } |
| } else { |
| for (int i = 0; i < length2; i++) { |
| bits[i] &= bsBits[i]; |
| } |
| for (int i = length2; i < length1; i++) { |
| bits[i] = 0; |
| } |
| actualArrayLength = length2; |
| } |
| isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0)); |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| void BitSet::andNot(const BitSet& set) { |
| unsigned long long* bsBits = set.bits; |
| |
| if (!needClear) { |
| return; |
| } |
| |
| int range = actualArrayLength < set.actualArrayLength ? actualArrayLength : set.actualArrayLength; |
| for (int i = 0; i < range; i++) { |
| bits[i] &= ~bsBits[i]; |
| } |
| |
| if (actualArrayLength < range) { |
| actualArrayLength = range; |
| } |
| |
| isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0)); |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| int BitSet::cardinality() { |
| if (!needClear) { |
| return 0; |
| } |
| int count = 0; |
| int length = bitsSize; |
| // FIXME: need to test performance, if still not satisfied, change it to |
| // 256-bits table based |
| for (int idx = 0; idx < length; idx++) { |
| count += pop(bits[idx] & 0xffffffffL); |
| count += pop((bits[idx] >> 32)); |
| } |
| return count; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| void BitSet::clear() { |
| if (needClear) { |
| for (int i = 0; i < bitsSize; i++) { |
| bits[i] = 0ULL; |
| } |
| actualArrayLength = 0; |
| isLengthActual = true; |
| needClear = false; |
| } |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| void BitSet::clear(int index) { |
| |
| if (index < 0) { |
| throw IndexOutOfBoundsException(__FILE__, __LINE__, "Index given was negative"); |
| } |
| |
| if (!needClear) { |
| return; |
| } |
| int arrayPos = index >> OFFSET; |
| if (arrayPos < actualArrayLength) { |
| bits[arrayPos] &= ~(TWO_N_ARRAY[index & RIGHT_BITS]); |
| if (bits[actualArrayLength - 1] == 0) { |
| isLengthActual = false; |
| } |
| } |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| void BitSet::clear(int fromIndex, int toIndex) { |
| if (fromIndex < 0 || toIndex < 0 || toIndex < fromIndex) { |
| throw IndexOutOfBoundsException(__FILE__, __LINE__, "Invalid from or to index given"); |
| } |
| |
| if (!needClear) { |
| return; |
| } |
| |
| int last = (actualArrayLength << OFFSET); |
| if (fromIndex >= last || fromIndex == toIndex) { |
| return; |
| } |
| if (toIndex > last) { |
| toIndex = last; |
| } |
| |
| int idx1 = fromIndex >> OFFSET; |
| int idx2 = (toIndex - 1) >> OFFSET; |
| unsigned long long factor1 = (~0ULL) << (fromIndex & RIGHT_BITS); |
| int shift = (ELM_SIZE - (toIndex & RIGHT_BITS)); |
| unsigned long long factor2 = shift < 64 ? (~0ULL) >> shift : (~0ULL); |
| |
| if (idx1 == idx2) { |
| bits[idx1] &= ~(factor1 & factor2); |
| } else { |
| bits[idx1] &= ~factor1; |
| bits[idx2] &= ~factor2; |
| for (int i = idx1 + 1; i < idx2; i++) { |
| bits[i] = 0ULL; |
| } |
| } |
| |
| if ((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0)) { |
| isLengthActual = false; |
| } |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| void BitSet::OR(const BitSet& set) { |
| int setActualLen = set.getActualArrayLength(); |
| |
| if (setActualLen > bitsSize) { |
| unsigned long long* tempBits = new unsigned long long[setActualLen]; |
| System::arraycopy(set.bits, 0, tempBits, 0, set.actualArrayLength); |
| for (int i = 0; i < actualArrayLength; i++) { |
| tempBits[i] |= bits[i]; |
| } |
| delete [] bits; |
| bits = tempBits; |
| actualArrayLength = setActualLen; |
| isLengthActual = true; |
| } else { |
| unsigned long long* bsBits = set.bits; |
| for (int i = 0; i < setActualLen; i++) { |
| bits[i] |= bsBits[i]; |
| } |
| if (setActualLen > actualArrayLength) { |
| actualArrayLength = setActualLen; |
| isLengthActual = true; |
| } |
| } |
| needClear = true; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| bool BitSet::equals(const BitSet& set) const { |
| |
| if (this == &set) { |
| return true; |
| } |
| |
| unsigned long long* bsBits = set.bits; |
| int length1 = this->actualArrayLength; |
| int length2 = set.actualArrayLength; |
| if (this->isLengthActual && set.isLengthActual && length1 != length2) { |
| return false; |
| } |
| |
| // If one of the BitSets is larger than the other, check to see if |
| // any of its extra bits are set. If so return false. |
| if (length1 <= length2) { |
| for (int i = 0; i < length1; i++) { |
| if (bits[i] != bsBits[i]) { |
| return false; |
| } |
| } |
| for (int i = length1; i < length2; i++) { |
| if (bsBits[i] != 0) { |
| return false; |
| } |
| } |
| } else { |
| for (int i = 0; i < length2; i++) { |
| if (bits[i] != bsBits[i]) { |
| return false; |
| } |
| } |
| for (int i = length2; i < length1; i++) { |
| if (bits[i] != 0) { |
| return false; |
| } |
| } |
| } |
| return true; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| void BitSet::flip(int index) { |
| if (index < 0) { |
| throw IndexOutOfBoundsException(__FILE__, __LINE__, "Index given was negative"); |
| } |
| |
| int len = (index >> OFFSET) + 1; |
| if (len > bitsSize) { |
| ensureCapacity(len); |
| } |
| bits[len - 1] ^= TWO_N_ARRAY[index & RIGHT_BITS]; |
| if (len > actualArrayLength) { |
| actualArrayLength = len; |
| } |
| isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0)); |
| needClear = true; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| void BitSet::flip(int fromIndex, int toIndex) { |
| if (fromIndex < 0 || toIndex < 0 || toIndex < fromIndex) { |
| throw IndexOutOfBoundsException(__FILE__, __LINE__, "Invalid from or to index given"); |
| } |
| |
| if (fromIndex == toIndex) { |
| return; |
| } |
| int len2 = ((toIndex - 1) >> OFFSET) + 1; |
| if (len2 > bitsSize) { |
| ensureCapacity(len2); |
| } |
| |
| int idx1 = fromIndex >> OFFSET; |
| int idx2 = (toIndex - 1) >> OFFSET; |
| unsigned long long factor1 = (~0ULL) << (fromIndex & RIGHT_BITS); |
| int shift = (ELM_SIZE - (toIndex & RIGHT_BITS)); |
| unsigned long long factor2 = shift < 64 ? (~0ULL) >> shift : (~0ULL); |
| |
| if (idx1 == idx2) { |
| bits[idx1] ^= (factor1 & factor2); |
| } else { |
| bits[idx1] ^= factor1; |
| bits[idx2] ^= factor2; |
| for (int i = idx1 + 1; i < idx2; i++) { |
| bits[i] ^= (~0ULL); |
| } |
| } |
| if (len2 > actualArrayLength) { |
| actualArrayLength = len2; |
| } |
| isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0)); |
| needClear = true; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| bool BitSet::get(int index) const { |
| |
| if (index < 0) { |
| throw IndexOutOfBoundsException(__FILE__, __LINE__, "Index given was negative"); |
| } |
| |
| int arrayPos = index >> OFFSET; |
| if (arrayPos < actualArrayLength) { |
| return (bits[arrayPos] & TWO_N_ARRAY[index & RIGHT_BITS]) != 0; |
| } |
| return false; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| BitSet BitSet::get(int fromIndex, int toIndex) const { |
| if (fromIndex < 0 || toIndex < 0 || toIndex < fromIndex) { |
| throw IndexOutOfBoundsException(__FILE__, __LINE__, "Invalid from or to index given"); |
| } |
| |
| int last = actualArrayLength << OFFSET; |
| if (fromIndex >= last || fromIndex == toIndex) { |
| return BitSet(0); |
| } |
| if (toIndex > last) { |
| toIndex = last; |
| } |
| |
| int idx1 = fromIndex >> OFFSET; |
| int idx2 = (toIndex - 1) >> OFFSET; |
| unsigned long long factor1 = (~0ULL) << (fromIndex & RIGHT_BITS); |
| int shift = (ELM_SIZE - (toIndex & RIGHT_BITS)); |
| unsigned long long factor2 = shift < 64 ? (~0ULL) >> shift : (~0ULL); |
| |
| if (idx1 == idx2) { |
| unsigned long long result = (bits[idx1] & (factor1 & factor2)) >> (fromIndex % ELM_SIZE); |
| if (result == 0) { |
| return BitSet(0); |
| } |
| |
| unsigned long long* newBits = new unsigned long long[1]; |
| newBits[0] = result; |
| return BitSet(newBits, 1, needClear, 1, true); |
| } |
| |
| int newBitsSize = idx2 - idx1 + 1; |
| unsigned long long* newbits = new unsigned long long[newBitsSize]; |
| |
| // first fill in the first and last indexes in the new bitset |
| newbits[0] = bits[idx1] & factor1; |
| newbits[newBitsSize - 1] = bits[idx2] & factor2; |
| |
| // fill in the in between elements of the new bitset |
| for (int i = 1; i < idx2 - idx1; i++) { |
| newbits[i] = bits[idx1 + i]; |
| } |
| |
| // shift all the elements in the new bitset to the right by fromIndex % ELM_SIZE |
| int numBitsToShift = fromIndex & RIGHT_BITS; |
| int actualLen = newBitsSize; |
| if (numBitsToShift != 0) { |
| for (int i = 0; i < newBitsSize; i++) { |
| // shift the current element to the right regardless of sign |
| newbits[i] = newbits[i] >> (numBitsToShift); |
| |
| // apply the last x bits of newbits[i+1] to the current element |
| if (i != newBitsSize - 1) { |
| newbits[i] |= newbits[i + 1] << (ELM_SIZE - (numBitsToShift)); |
| } |
| |
| if (newbits[i] != 0) { |
| actualLen = i + 1; |
| } |
| } |
| } |
| |
| return BitSet(newbits, newBitsSize, needClear, actualLen, newbits[actualLen - 1] != 0); |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| bool BitSet::intersects(const BitSet& set) const { |
| unsigned long long* bsBits = set.bits; |
| int length1 = actualArrayLength; |
| int length2 = set.actualArrayLength; |
| |
| if (length1 <= length2) { |
| for (int i = 0; i < length1; i++) { |
| if ((bits[i] & bsBits[i]) != 0ULL) { |
| return true; |
| } |
| } |
| } else { |
| for (int i = 0; i < length2; i++) { |
| if ((bits[i] & bsBits[i]) != 0ULL) { |
| return true; |
| } |
| } |
| } |
| |
| return false; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| bool BitSet::isEmpty() const { |
| if (!needClear) { |
| return true; |
| } |
| |
| for (int idx = 0; idx < bitsSize; idx++) { |
| if (bits[idx] != 0ULL) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| int BitSet::length() const { |
| |
| int idx = actualArrayLength - 1; |
| while (idx >= 0 && bits[idx] == 0) { |
| --idx; |
| } |
| actualArrayLength = idx + 1; |
| if (idx == -1) { |
| return 0; |
| } |
| int i = ELM_SIZE - 1; |
| unsigned long long val = bits[idx]; |
| while ((val & (TWO_N_ARRAY[i])) == 0 && i > 0) { |
| i--; |
| } |
| return (idx << OFFSET) + i + 1; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| int BitSet::nextClearBit(int index) const { |
| if (index < 0) { |
| throw IndexOutOfBoundsException(__FILE__, __LINE__, "Index given was negative"); |
| } |
| |
| int length = actualArrayLength; |
| int bssize = length << OFFSET; |
| if (index >= bssize) { |
| return index; |
| } |
| |
| int idx = index >> OFFSET; |
| // first check in the same bit set element |
| if (bits[idx] != (~0ULL)) { |
| for (int j = index % ELM_SIZE; j < ELM_SIZE; j++) { |
| if (((bits[idx] & (TWO_N_ARRAY[j])) == 0)) { |
| return idx * ELM_SIZE + j; |
| } |
| } |
| } |
| idx++; |
| while (idx < length && bits[idx] == (~0ULL)) { |
| idx++; |
| } |
| if (idx == length) { |
| return bssize; |
| } |
| |
| // we know for sure there is a bit set to true in this element |
| // since the bitset value is not 0ULL |
| for (int j = 0; j < ELM_SIZE; j++) { |
| if (((bits[idx] & (TWO_N_ARRAY[j])) == 0)) { |
| return (idx << OFFSET) + j; |
| } |
| } |
| |
| return bssize; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| int BitSet::nextSetBit(int index) const { |
| if (index < 0) { |
| throw IndexOutOfBoundsException(__FILE__, __LINE__, "Index given was negative"); |
| } |
| |
| if (index >= actualArrayLength << OFFSET) { |
| return -1; |
| } |
| |
| int idx = index >> OFFSET; |
| // first check in the same bit set element |
| if (bits[idx] != 0ULL) { |
| for (int j = index & RIGHT_BITS; j < ELM_SIZE; j++) { |
| if (((bits[idx] & (TWO_N_ARRAY[j])) != 0)) { |
| return (idx << OFFSET) + j; |
| } |
| } |
| } |
| |
| idx++; |
| while (idx < actualArrayLength && bits[idx] == 0ULL) { |
| idx++; |
| } |
| if (idx == actualArrayLength) { |
| return -1; |
| } |
| |
| // we know for sure there is a bit set to true in this element |
| // since the bitset value is not 0ULL |
| for (int j = 0; j < ELM_SIZE; j++) { |
| if (((bits[idx] & (TWO_N_ARRAY[j])) != 0)) { |
| return (idx << OFFSET) + j; |
| } |
| } |
| |
| return -1; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| void BitSet::set(int index) { |
| |
| if (index < 0) { |
| throw IndexOutOfBoundsException(__FILE__, __LINE__, "Index given was negative"); |
| } |
| |
| int len = (index >> OFFSET) + 1; |
| if (len > bitsSize) { |
| ensureCapacity(len); |
| } |
| bits[len - 1] |= TWO_N_ARRAY[index & RIGHT_BITS]; |
| if (len > actualArrayLength) { |
| actualArrayLength = len; |
| isLengthActual = true; |
| } |
| |
| this->needClear = true; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| void BitSet::set(int index, bool value) { |
| |
| if (value) { |
| set(index); |
| } else { |
| clear(index); |
| } |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| void BitSet::set(int fromIndex, int toIndex) { |
| |
| if (fromIndex < 0 || toIndex < 0 || toIndex < fromIndex) { |
| throw IndexOutOfBoundsException(__FILE__, __LINE__, "Invalid from or to index given"); |
| } |
| |
| if (fromIndex == toIndex) { |
| return; |
| } |
| int len2 = ((toIndex - 1) >> OFFSET) + 1; |
| if (len2 > bitsSize) { |
| ensureCapacity(len2); |
| } |
| |
| int idx1 = fromIndex >> OFFSET; |
| int idx2 = (toIndex - 1) >> OFFSET; |
| unsigned long long factor1 = (~0ULL) << (fromIndex & RIGHT_BITS); |
| int shift = (ELM_SIZE - (toIndex & RIGHT_BITS)); |
| unsigned long long factor2 = shift < 64 ? (~0ULL) >> shift : (~0ULL); |
| |
| if (idx1 == idx2) { |
| bits[idx1] |= (factor1 & factor2); |
| } else { |
| bits[idx1] |= factor1; |
| bits[idx2] |= factor2; |
| for (int i = idx1 + 1; i < idx2; i++) { |
| bits[i] |= (~0ULL); |
| } |
| } |
| if (idx2 + 1 > actualArrayLength) { |
| actualArrayLength = idx2 + 1; |
| isLengthActual = true; |
| } |
| |
| needClear = true; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| void BitSet::set(int fromIndex, int toIndex, bool value) { |
| |
| if (value) { |
| set(fromIndex, toIndex); |
| } else { |
| clear(fromIndex, toIndex); |
| } |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| int BitSet::size() const { |
| return bitsSize << OFFSET; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| std::string BitSet::toString() const { |
| std::string sb; |
| int bitCount = 0; |
| |
| sb.append("{"); |
| bool comma = false; |
| for (int i = 0; i < bitsSize; i++) { |
| if (bits[i] == 0) { |
| bitCount += ELM_SIZE; |
| continue; |
| } |
| for (int j = 0; j < ELM_SIZE; j++) { |
| if (((bits[i] & (TWO_N_ARRAY[j])) != 0)) { |
| if (comma) { |
| sb.append(", "); |
| } |
| sb.append(Integer::toString(bitCount)); |
| comma = true; |
| } |
| bitCount++; |
| } |
| } |
| sb.append("}"); |
| return sb; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| void BitSet::XOR(const BitSet& set) { |
| int setActualLength = set.getActualArrayLength(); |
| if (setActualLength > bitsSize) { |
| unsigned long long* tempBits = new unsigned long long[setActualLength]; |
| System::arraycopy(set.bits, 0, tempBits, 0, set.actualArrayLength); |
| for (int i = 0; i < actualArrayLength; i++) { |
| tempBits[i] ^= bits[i]; |
| } |
| delete [] bits; |
| bits = tempBits; |
| actualArrayLength = setActualLength; |
| isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0)); |
| } else { |
| unsigned long long* bsBits = set.bits; |
| for (int i = 0; i < setActualLength; i++) { |
| bits[i] ^= bsBits[i]; |
| } |
| if (setActualLength > actualArrayLength) { |
| actualArrayLength = setActualLength; |
| isLengthActual = true; |
| } |
| } |
| |
| this->needClear = true; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| void BitSet::ensureCapacity(int length) { |
| int newSize = Math::max(length, bitsSize * 2); |
| unsigned long long* tempBits = new unsigned long long[newSize]; |
| System::arraycopy(bits, 0, tempBits, 0, this->actualArrayLength); |
| for (int i = this->actualArrayLength; i < newSize; ++i) { |
| tempBits[i] = 0ULL; |
| } |
| delete [] bits; |
| bits = tempBits; |
| bitsSize = newSize; |
| } |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| int BitSet::getActualArrayLength() const { |
| if (isLengthActual) { |
| return actualArrayLength; |
| } |
| int idx = actualArrayLength - 1; |
| while (idx >= 0 && bits[idx] == 0) { |
| --idx; |
| } |
| actualArrayLength = idx + 1; |
| isLengthActual = true; |
| return actualArrayLength; |
| } |