001: /* Licensed to the Apache Software Foundation (ASF) under one or more
002: * contributor license agreements. See the NOTICE file distributed with
003: * this work for additional information regarding copyright ownership.
004: * The ASF licenses this file to You under the Apache License, Version 2.0
005: * (the "License"); you may not use this file except in compliance with
006: * the License. You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016:
017: package java.util;
018:
019: /**
020: * This is a concrete subclass of EnumSet designed specifically for enum type
021: * with more than 64 elements.
022: *
023: */
024: @SuppressWarnings("serial")
025: final class HugeEnumSet<E extends Enum<E>> extends EnumSet<E> {
026:
027: final private E[] enums;
028:
029: private long[] bits;
030:
031: private int size;
032:
033: private static final int BIT_IN_LONG = 64;
034:
035: HugeEnumSet(Class<E> elementType) {
036: super (elementType);
037: enums = elementType.getEnumConstants();
038: bits = new long[(enums.length + BIT_IN_LONG - 1) / BIT_IN_LONG];
039: Arrays.fill(bits, 0);
040: }
041:
042: private class HugeEnumSetIterator implements Iterator<E> {
043:
044: private long[] unProcessedBits;
045:
046: private int bitsPosition = 0;
047:
048: /*
049: * Mask for current element.
050: */
051: private long currentElementMask = 0;
052:
053: boolean canProcess = true;
054:
055: private HugeEnumSetIterator() {
056: unProcessedBits = new long[bits.length];
057: System.arraycopy(bits, 0, unProcessedBits, 0, bits.length);
058: bitsPosition = unProcessedBits.length;
059: findNextNoneZeroPosition(0);
060: if (bitsPosition == unProcessedBits.length) {
061: canProcess = false;
062: }
063: }
064:
065: private void findNextNoneZeroPosition(int start) {
066: for (int i = start; i < unProcessedBits.length; i++) {
067: if (0 != bits[i]) {
068: bitsPosition = i;
069: break;
070: }
071: }
072: }
073:
074: public boolean hasNext() {
075: return canProcess;
076: }
077:
078: public E next() {
079: if (!canProcess) {
080: throw new NoSuchElementException();
081: }
082: currentElementMask = unProcessedBits[bitsPosition]
083: & (-unProcessedBits[bitsPosition]);
084: unProcessedBits[bitsPosition] -= currentElementMask;
085: int index = Long.numberOfTrailingZeros(currentElementMask)
086: + bitsPosition * BIT_IN_LONG;
087: if (0 == unProcessedBits[bitsPosition]) {
088: int oldBitsPosition = bitsPosition;
089: findNextNoneZeroPosition(bitsPosition + 1);
090: if (bitsPosition == oldBitsPosition) {
091: canProcess = false;
092: }
093: }
094: return enums[index];
095: }
096:
097: public void remove() {
098: if (currentElementMask == 0) {
099: throw new IllegalStateException();
100: }
101: bits[bitsPosition] &= ~currentElementMask;
102: size--;
103: currentElementMask = 0;
104: }
105: }
106:
107: @Override
108: public boolean add(E element) {
109: if (!isValidType(element.getDeclaringClass())) {
110: throw new ClassCastException();
111: }
112: calculateElementIndex(element);
113:
114: bits[bitsIndex] |= (1l << elementInBits);
115: if (oldBits == bits[bitsIndex]) {
116: return false;
117: }
118: size++;
119: return true;
120: }
121:
122: @Override
123: public boolean addAll(Collection<? extends E> collection) {
124: if (0 == collection.size() || this == collection) {
125: return false;
126: }
127: if (collection instanceof EnumSet) {
128: EnumSet set = (EnumSet) collection;
129: if (!isValidType(set.elementClass)) {
130: throw new ClassCastException();
131: }
132: HugeEnumSet hugeSet = (HugeEnumSet) set;
133: boolean addSuccessful = false;
134: for (int i = 0; i < bits.length; i++) {
135: oldBits = bits[i];
136: bits[i] |= hugeSet.bits[i];
137: if (oldBits != bits[i]) {
138: addSuccessful = true;
139: size = size - Long.bitCount(oldBits)
140: + Long.bitCount(bits[i]);
141: }
142: }
143: return addSuccessful;
144: }
145: return super .addAll(collection);
146: }
147:
148: @Override
149: public int size() {
150: return size;
151: }
152:
153: @Override
154: public void clear() {
155: Arrays.fill(bits, 0);
156: size = 0;
157: }
158:
159: @Override
160: protected void complement() {
161: if (0 != enums.length) {
162: bitsIndex = enums.length / BIT_IN_LONG;
163:
164: size = 0;
165: int bitCount = 0;
166: for (int i = 0; i <= bitsIndex; i++) {
167: bits[i] = ~bits[i];
168: bitCount = Long.bitCount(bits[i]);
169: size += bitCount;
170: }
171: bits[bitsIndex] &= (-1l >>> (BIT_IN_LONG - enums.length
172: % BIT_IN_LONG));
173: size -= bitCount;
174: bitCount = Long.bitCount(bits[bitsIndex]);
175: size += bitCount;
176: }
177: }
178:
179: @SuppressWarnings("unchecked")
180: @Override
181: public boolean contains(Object object) {
182: if (null == object) {
183: return false;
184: }
185: if (!isValidType(object.getClass())) {
186: return false;
187: }
188: calculateElementIndex((E) object);
189: return (bits[bitsIndex] & (1l << elementInBits)) != 0;
190: }
191:
192: @Override
193: @SuppressWarnings("unchecked")
194: public HugeEnumSet<E> clone() {
195: Object set = super .clone();
196: if (null != set) {
197: ((HugeEnumSet<E>) set).bits = bits.clone();
198: return (HugeEnumSet<E>) set;
199: }
200: return null;
201: }
202:
203: @Override
204: public boolean containsAll(Collection<?> collection) {
205: if (collection.size() == 0) {
206: return true;
207: }
208: if (collection instanceof HugeEnumSet) {
209: HugeEnumSet set = (HugeEnumSet) collection;
210: if (isValidType(set.elementClass)) {
211: for (int i = 0; i < bits.length; i++) {
212: if ((bits[i] & set.bits[i]) != set.bits[i]) {
213: return false;
214: }
215:
216: }
217: return true;
218: }
219: }
220: return !(collection instanceof EnumSet)
221: && super .containsAll(collection);
222: }
223:
224: @Override
225: public boolean equals(Object object) {
226: if (null == object) {
227: return false;
228: }
229: if (!isValidType(object.getClass())) {
230: return super .equals(object);
231: }
232: return Arrays.equals(bits, ((HugeEnumSet) object).bits);
233: }
234:
235: @Override
236: public Iterator<E> iterator() {
237: return new HugeEnumSetIterator();
238: }
239:
240: @Override
241: public boolean remove(Object object) {
242: if (!contains(object)) {
243: return false;
244: }
245: bits[bitsIndex] -= (1l << elementInBits);
246: size--;
247: return true;
248: }
249:
250: @Override
251: public boolean removeAll(Collection<?> collection) {
252: if (0 == collection.size()) {
253: return false;
254: }
255:
256: if (collection instanceof EnumSet) {
257: EnumSet<E> set = (EnumSet<E>) collection;
258: if (!isValidType(set.elementClass)) {
259: return false;
260: }
261: boolean removeSuccessful = false;
262: long mask = 0;
263: for (int i = 0; i < bits.length; i++) {
264: oldBits = bits[i];
265: mask = bits[i] & ((HugeEnumSet<E>) set).bits[i];
266: if (mask != 0) {
267: bits[i] -= mask;
268: size = (size - Long.bitCount(oldBits) + Long
269: .bitCount(bits[i]));
270: removeSuccessful = true;
271: }
272: }
273: return removeSuccessful;
274: }
275: return super .removeAll(collection);
276: }
277:
278: @Override
279: public boolean retainAll(Collection<?> collection) {
280: if (collection instanceof EnumSet) {
281: EnumSet<E> set = (EnumSet<E>) collection;
282: if (!isValidType(set.elementClass)) {
283: clear();
284: return true;
285: }
286:
287: boolean retainSuccessful = false;
288: oldBits = 0;
289: for (int i = 0; i < bits.length; i++) {
290: oldBits = bits[i];
291: bits[i] &= ((HugeEnumSet<E>) set).bits[i];
292: if (oldBits != bits[i]) {
293: size = size - Long.bitCount(oldBits)
294: + Long.bitCount(bits[i]);
295: retainSuccessful = true;
296: }
297: }
298: return retainSuccessful;
299: }
300: return super .retainAll(collection);
301: }
302:
303: @Override
304: void setRange(E start, E end) {
305: calculateElementIndex(start);
306: int startBitsIndex = bitsIndex;
307: int startElementInBits = elementInBits;
308: calculateElementIndex(end);
309: int endBitsIndex = bitsIndex;
310: int endElementInBits = elementInBits;
311: long range = 0;
312: if (startBitsIndex == endBitsIndex) {
313: range = (-1l >>> (BIT_IN_LONG - (endElementInBits
314: - startElementInBits + 1))) << startElementInBits;
315: size -= Long.bitCount(bits[bitsIndex]);
316: bits[bitsIndex] |= range;
317: size += Long.bitCount(bits[bitsIndex]);
318: } else {
319: range = (-1l >>> startElementInBits) << startElementInBits;
320: size -= Long.bitCount(bits[startBitsIndex]);
321: bits[startBitsIndex] |= range;
322: size += Long.bitCount(bits[startBitsIndex]);
323:
324: // endElementInBits + 1 is the number of consecutive ones.
325: // 63 - endElementInBits is the following zeros of the right most one.
326: range = -1l >>> (BIT_IN_LONG - (endElementInBits + 1)) << (63 - endElementInBits);
327: size -= Long.bitCount(bits[endBitsIndex]);
328: bits[endBitsIndex] |= range;
329: size += Long.bitCount(bits[endBitsIndex]);
330: for (int i = (startBitsIndex + 1); i <= (endBitsIndex - 1); i++) {
331: size -= Long.bitCount(bits[i]);
332: bits[i] = -1l;
333: size += Long.bitCount(bits[i]);
334: }
335: }
336: }
337:
338: private void calculateElementIndex(E element) {
339: int elementOrdinal = element.ordinal();
340: bitsIndex = elementOrdinal / BIT_IN_LONG;
341: elementInBits = elementOrdinal % BIT_IN_LONG;
342: oldBits = bits[bitsIndex];
343: }
344:
345: private int bitsIndex;
346:
347: private int elementInBits;
348:
349: private long oldBits;
350: }
|