/* 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.
*/
package java.util;
/**
* This is a concrete subclass of EnumSet designed specifically for enum type
* with more than 64 elements.
*
*/
@SuppressWarnings("serial")
final class HugeEnumSet<E extends Enum<E>> extends EnumSet<E> {
final private E[] enums;
private long[] bits;
private int size;
private static final int BIT_IN_LONG = 64;
// BEGIN android-changed
/**
* Constructs an instance.
*
* @param elementType non-null; type of the elements
* @param enums non-null; prepopulated array of constants in ordinal
* order
*/
HugeEnumSet(Class<E> elementType, E[] enums) {
super(elementType);
this.enums = enums;
bits = new long[(enums.length + BIT_IN_LONG - 1) / BIT_IN_LONG];
Arrays.fill(bits, 0);
}
// END android-changed
private class HugeEnumSetIterator implements Iterator<E> {
private long[] unProcessedBits;
private int bitsPosition = 0;
/*
* Mask for current element.
*/
private long currentElementMask = 0;
boolean canProcess = true;
private HugeEnumSetIterator() {
unProcessedBits = new long[bits.length];
System.arraycopy(bits, 0, unProcessedBits, 0, bits.length);
bitsPosition = unProcessedBits.length;
findNextNoneZeroPosition(0);
if (bitsPosition == unProcessedBits.length) {
canProcess = false;
}
}
private void findNextNoneZeroPosition(int start) {
for (int i = start; i < unProcessedBits.length; i++) {
if (0 != bits[i]) {
bitsPosition = i;
break;
}
}
}
public boolean hasNext() {
return canProcess;
}
public E next() {
if (!canProcess) {
throw new NoSuchElementException();
}
currentElementMask = unProcessedBits[bitsPosition]
& (-unProcessedBits[bitsPosition]);
unProcessedBits[bitsPosition] -= currentElementMask;
if (0 == unProcessedBits[bitsPosition]) {
int oldBitsPosition = bitsPosition;
findNextNoneZeroPosition(bitsPosition + 1);
if (bitsPosition == oldBitsPosition) {
canProcess = false;
}
}
return enums[Long.numberOfTrailingZeros(currentElementMask)
+ bitsPosition * BIT_IN_LONG];
}
public void remove() {
if (currentElementMask == 0) {
throw new IllegalStateException();
}
bits[bitsPosition] &= ~currentElementMask;
size--;
currentElementMask = 0;
}
}
@Override
public boolean add(E element) {
if (!isValidType(element.getDeclaringClass())) {
throw new ClassCastException();
}
calculateElementIndex(element);
bits[bitsIndex] |= (1l << elementInBits);
if (oldBits == bits[bitsIndex]) {
return false;
}
size++;
return true;
}
@Override
public boolean addAll(Collection<? extends E> collection) {
if (0 == collection.size() || this == collection) {
return false;
}
if (collection instanceof EnumSet) {
EnumSet set = (EnumSet) collection;
if (!isValidType(set.elementClass)) {
throw new ClassCastException();
}
HugeEnumSet hugeSet = (HugeEnumSet) set;
boolean addSuccessful = false;
for (int i = 0; i < bits.length; i++) {
oldBits = bits[i];
bits[i] |= hugeSet.bits[i];
if (oldBits != bits[i]) {
addSuccessful = true;
size = size - Long.bitCount(oldBits)
+ Long.bitCount(bits[i]);
}
}
return addSuccessful;
}
return super.addAll(collection);
}
@Override
public int size() {
return size;
}
@Override
public void clear() {
Arrays.fill(bits, 0);
size = 0;
}
@Override
protected void complement() {
if (0 != enums.length) {
bitsIndex = enums.length / BIT_IN_LONG;
size = 0;
int bitCount = 0;
for (int i = 0; i <= bitsIndex; i++) {
bits[i] = ~bits[i];
bitCount = Long.bitCount(bits[i]);
size += bitCount;
}
bits[bitsIndex] &= (-1l >>> (BIT_IN_LONG - enums.length
% BIT_IN_LONG));
size -= bitCount;
bitCount = Long.bitCount(bits[bitsIndex]);
size += bitCount;
}
}
@Override
public boolean contains(Object object) {
if (null == object) {
return false;
}
if (!isValidType(object.getClass())) {
return false;
}
calculateElementIndex((E)object);
return (bits[bitsIndex] & (1l << elementInBits)) != 0;
}
@Override
@SuppressWarnings("unchecked")
public HugeEnumSet<E> clone() {
Object set = super.clone();
if (null != set) {
((HugeEnumSet<E>) set).bits = bits.clone();
return (HugeEnumSet<E>) set;
}
return null;
}
@Override
public boolean containsAll(Collection<?> collection) {
if (collection.size() == 0) {
return true;
}
if (collection instanceof HugeEnumSet) {
HugeEnumSet set = (HugeEnumSet) collection;
if(isValidType(set.elementClass )) {
for(int i = 0; i < bits.length; i++) {
if((bits[i] & set.bits[i]) != set.bits[i]){
return false;
}
}
return true;
}
}
return !(collection instanceof EnumSet) && super.containsAll(collection);
}
@Override
public boolean equals(Object object) {
if (null == object) {
return false;
}
if (!isValidType(object.getClass())) {
return super.equals(object);
}
return Arrays.equals(bits, ((HugeEnumSet) object).bits);
}
@Override
public Iterator<E> iterator() {
return new HugeEnumSetIterator();
}
@Override
public boolean remove(Object object) {
if (!contains(object)) {
return false;
}
bits[bitsIndex] -= (1l << elementInBits);
size--;
return true;
}
@Override
public boolean removeAll(Collection<?> collection) {
if (0 == collection.size()) {
return false;
}
if (collection instanceof EnumSet) {
EnumSet<E> set = (EnumSet<E>) collection;
if (!isValidType(set.elementClass)) {
return false;
}
boolean removeSuccessful = false;
long mask = 0;
for (int i = 0; i < bits.length; i++) {
oldBits = bits[i];
mask = bits[i] & ((HugeEnumSet<E>) set).bits[i];
if (mask != 0) {
bits[i] -= mask;
size = (size - Long.bitCount(oldBits) + Long
.bitCount(bits[i]));
removeSuccessful = true;
}
}
return removeSuccessful;
}
return super.removeAll(collection);
}
@Override
public boolean retainAll(Collection<?> collection) {
if (collection instanceof EnumSet) {
EnumSet<E> set = (EnumSet<E>) collection;
if (!isValidType(set.elementClass)) {
clear();
return true;
}
boolean retainSuccessful = false;
oldBits = 0;
for (int i = 0; i < bits.length; i++) {
oldBits = bits[i];
bits[i] &= ((HugeEnumSet<E>) set).bits[i];
if (oldBits != bits[i]) {
size = size - Long.bitCount(oldBits)
+ Long.bitCount(bits[i]);
retainSuccessful = true;
}
}
return retainSuccessful;
}
return super.retainAll(collection);
}
@Override
void setRange(E start, E end) {
calculateElementIndex(start);
int startBitsIndex = bitsIndex;
int startElementInBits = elementInBits;
calculateElementIndex(end);
int endBitsIndex = bitsIndex;
int endElementInBits = elementInBits;
long range = 0;
if (startBitsIndex == endBitsIndex) {
range = (-1l >>> (BIT_IN_LONG -(endElementInBits - startElementInBits + 1))) << startElementInBits;
size -= Long.bitCount(bits[bitsIndex]);
bits[bitsIndex] |= range;
size += Long.bitCount(bits[bitsIndex]);
} else {
range = (-1l >>> startElementInBits) << startElementInBits;
size -= Long.bitCount(bits[startBitsIndex]);
bits[startBitsIndex] |= range;
size += Long.bitCount(bits[startBitsIndex]);
// endElementInBits + 1 is the number of consecutive ones.
// 63 - endElementInBits is the following zeros of the right most one.
range = -1l >>> (BIT_IN_LONG - (endElementInBits + 1)) << (63 - endElementInBits);
size -= Long.bitCount(bits[endBitsIndex]);
bits[endBitsIndex] |= range;
size += Long.bitCount(bits[endBitsIndex]);
for(int i = (startBitsIndex + 1); i <= (endBitsIndex - 1); i++) {
size -= Long.bitCount(bits[i]);
bits[i] = -1l;
size += Long.bitCount(bits[i]);
}
}
}
private void calculateElementIndex(E element) {
int elementOrdinal = element.ordinal();
bitsIndex = elementOrdinal / BIT_IN_LONG;
elementInBits = elementOrdinal % BIT_IN_LONG;
oldBits = bits[bitsIndex];
}
private int bitsIndex;
private int elementInBits;
private long oldBits;
}
|
