Author: desruisseaux
Date: Tue Feb 26 17:02:14 2013
New Revision: 1450278
URL: http://svn.apache.org/r1450278
Log:
Support large CodeList (more than 64 elements).
Added:
sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/iso/LargeCodeList.java
(with props)
Modified:
sis/branches/JDK7/sis-utility/src/main/java/org/apache/sis/util/collection/CodeListSet.java
sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/collection/CodeListSetTest.java
Modified:
sis/branches/JDK7/sis-utility/src/main/java/org/apache/sis/util/collection/CodeListSet.java
URL:
http://svn.apache.org/viewvc/sis/branches/JDK7/sis-utility/src/main/java/org/apache/sis/util/collection/CodeListSet.java?rev=1450278&r1=1450277&r2=1450278&view=diff
==============================================================================
---
sis/branches/JDK7/sis-utility/src/main/java/org/apache/sis/util/collection/CodeListSet.java
[UTF-8] (original)
+++
sis/branches/JDK7/sis-utility/src/main/java/org/apache/sis/util/collection/CodeListSet.java
[UTF-8] Tue Feb 26 17:02:14 2013
@@ -17,6 +17,7 @@
package org.apache.sis.util.collection;
import java.util.AbstractSet;
+import java.util.BitSet;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
@@ -31,15 +32,6 @@ import org.apache.sis.util.resources.Err
* A specialized {@code Set} implementation for use with {@link CodeList}
values.
* This implementation uses a bit mask for efficient storage.
*
- * {@section Current limitation}
- * The current implementation is restricted to code list having a maximum of
64 values.
- * This restriction may be removed in a future Apache SIS version.
- *
- * {@note The standard <code>EnumSet</code> class uses different
implementations depending on
- * whether the enumeration contains more or less than 64 elements. We
can not apply the
- * same strategy for <code>CodeListSet</code>, because new code list
elements can be created
- * at runtime. Consequently this implementation needs to be able to
growth its capacity.}
- *
* @param <E> The type of code list elements in the set.
*
* @author Martin Desruisseaux (Geomatys)
@@ -48,7 +40,7 @@ import org.apache.sis.util.resources.Err
* @module
*/
public class CodeListSet<E extends CodeList<E>> extends AbstractSet<E>
- implements CheckedContainer<E>, Serializable
+ implements CheckedContainer<E>, Cloneable, Serializable
{
/**
* For cross-version compatibility.
@@ -57,20 +49,36 @@ public class CodeListSet<E extends CodeL
/**
* The type of code list elements.
+ *
+ * @see #getElementType()
*/
- final Class<E> elementType;
+ private final Class<E> elementType;
/**
* A bitmask of code list values present in this map.
*/
- long values;
+ private long values;
+
+ /**
+ * The bit set for supplementary values beyond the {@code values} mask, or
{@code null}
+ * if none. This is very rarely needed, but we need this field in case a
code list has
+ * more than 64 elements.
+ *
+ * {@note The standard <code>EnumSet</code> class uses different
implementations depending on
+ * whether the enumeration contains more or less than 64 elements.
We can not apply the
+ * same strategy for <code>CodeListSet</code>, because new code
list elements can be created
+ * at runtime. Consequently this implementation needs to be able to
growth its capacity.}
+ */
+ private BitSet supplementary;
/**
* All possible code list elements, fetched when first needed.
* Note that this array may need to be fetched more than once,
* because code list elements can be dynamically added.
+ *
+ * @see #valueOf(int)
*/
- transient E[] codes;
+ private transient E[] codes;
/**
* Creates an initially empty set for code lists of the given type.
@@ -97,11 +105,27 @@ public class CodeListSet<E extends CodeL
}
/**
+ * Returns the code list for the given ordinal value. This methods depends
+ * only on the code list type; it does not depend on the content of this
set.
+ */
+ final E valueOf(final int ordinal) {
+ E[] array = codes;
+ if (array == null || ordinal >= array.length) {
+ codes = array = Types.getCodeValues(elementType);
+ }
+ return array[ordinal];
+ }
+
+ /**
* Removes all elements from this set.
*/
@Override
public void clear() {
values = 0;
+ final BitSet s = supplementary;
+ if (s != null) {
+ s.clear();
+ }
}
/**
@@ -109,7 +133,8 @@ public class CodeListSet<E extends CodeL
*/
@Override
public boolean isEmpty() {
- return values == 0;
+ final BitSet s;
+ return values == 0 && ((s = supplementary) == null || s.isEmpty());
}
/**
@@ -119,22 +144,39 @@ public class CodeListSet<E extends CodeL
*/
@Override
public int size() {
- return Long.bitCount(values);
+ int n = Long.bitCount(values);
+ final BitSet s = supplementary;
+ if (s != null) {
+ n += s.cardinality();
+ }
+ return n;
}
/**
* Adds the specified code list element in this set.
*
- * @param e The code list element to add in this set.
+ * @param element The code list element to add in this set.
* @return {@code true} if this set has been modified as a consequence of
this method call.
*/
@Override
- public boolean add(final E e) {
- final long mask = 1L << e.ordinal();
- if (mask == 0) {
- throw new
IllegalArgumentException(Errors.format(Errors.Keys.IndexOutOfBounds_1,
"ordinal"));
+ public boolean add(final E element) {
+ int ordinal = element.ordinal();
+ if (ordinal < Long.SIZE) {
+ return values != (values |= (1L << ordinal));
+ }
+ /*
+ * The above code is suffisient in the vast majority of cases. In the
rare cases where
+ * there is more than 64 elements, create a BitSet for storing the
supplementary values.
+ */
+ BitSet s = supplementary;
+ if (s == null) {
+ supplementary = s = new BitSet();
+ }
+ if (s.get(ordinal -= Long.SIZE)) {
+ return false;
}
- return values != (values |= mask);
+ s.set(ordinal);
+ return true;
}
/**
@@ -148,7 +190,24 @@ public class CodeListSet<E extends CodeL
@Override
public boolean remove(final Object object) {
if (elementType.isInstance(object)) {
- return values != (values &= ~(1L << ((CodeList)
object).ordinal()));
+ return clear(((CodeList<?>) object).ordinal());
+ }
+ return false;
+ }
+
+ /**
+ * Clears the bit at the given ordinal value. This method is invoked by
+ * {@link #remove(Object)} or by {@link Iter#remove()}.
+ */
+ final boolean clear(int ordinal) {
+ if (ordinal < Long.SIZE) {
+ return values != (values &= ~(1L << ordinal));
+ }
+ // Rare cases where there is more than 64 elements.
+ final BitSet s = supplementary;
+ if (s != null && s.get(ordinal -= Long.SIZE)) {
+ s.clear(ordinal);
+ return true;
}
return false;
}
@@ -164,7 +223,15 @@ public class CodeListSet<E extends CodeL
@Override
public boolean contains(final Object object) {
if (elementType.isInstance(object)) {
- return (values & (1L << ((CodeList) object).ordinal())) != 0;
+ int ordinal = ((CodeList<?>) object).ordinal();
+ if (ordinal < Long.SIZE) {
+ return (values & (1L << ordinal)) != 0;
+ }
+ // Rare cases where there is more than 64 elements.
+ final BitSet s = supplementary;
+ if (s != null) {
+ return s.get(ordinal - Long.SIZE);
+ }
}
return false;
}
@@ -178,10 +245,28 @@ public class CodeListSet<E extends CodeL
@Override
public boolean containsAll(final Collection<?> c) {
if (c instanceof CodeListSet) {
- final CodeListSet<?> o = (CodeListSet) c;
+ final CodeListSet<?> o = (CodeListSet<?>) c;
if (elementType == o.elementType) {
- return values == (values | o.values);
+ if (values == (values | o.values)) {
+ /*
+ * Code below this point checks for the rare cases
+ * where there is more than 64 code list elements.
+ */
+ final BitSet s = supplementary;
+ final BitSet os = o.supplementary;
+ if (( s == null || s.isEmpty()) &&
+ (os == null || os.isEmpty()))
+ {
+ return true;
+ }
+ if (s != null && os != null) {
+ final BitSet tmp = (BitSet) os.clone();
+ tmp.andNot(s);
+ return tmp.isEmpty();
+ }
+ }
}
+ return false;
}
return super.containsAll(c);
}
@@ -195,9 +280,32 @@ public class CodeListSet<E extends CodeL
@Override
public boolean addAll(final Collection<? extends E> c) throws
IllegalArgumentException {
if (c instanceof CodeListSet) {
+ final CodeListSet<?> o = (CodeListSet<?>) c;
// Following assertion should be ensured by parameterized types.
- assert elementType.isAssignableFrom(((CodeListSet) c).elementType);
- return values != (values |= ((CodeListSet) c).values);
+ assert elementType.isAssignableFrom(o.elementType);
+ boolean changed = (values != (values |= o.values));
+ /*
+ * Code below this point is for the rare cases
+ * where there is more than 64 code list elements.
+ */
+ final BitSet os = o.supplementary;
+ if (os != null) {
+ final BitSet s = supplementary;
+ if (s == null) {
+ if (!os.isEmpty()) {
+ supplementary = (BitSet) os.clone();
+ changed = true;
+ }
+ } else if (changed) {
+ // Avoid the cost of computing cardinality.
+ s.or(os);
+ } else {
+ final int cardinality = s.cardinality();
+ s.or(os);
+ changed = (cardinality != s.cardinality());
+ }
+ }
+ return changed;
}
return super.addAll(c);
}
@@ -218,7 +326,26 @@ public class CodeListSet<E extends CodeL
@Override
public boolean removeAll(final Collection<?> c) {
if (c instanceof CodeListSet) {
- return values != (values &= ~mask((CodeListSet<?>) c));
+ boolean changed = (values != (values &= ~mask((CodeListSet<?>)
c)));
+ /*
+ * Code below this point is for the rare cases
+ * where there is more than 64 code list elements.
+ */
+ final BitSet s = supplementary;
+ if (s != null) {
+ final BitSet os = ((CodeListSet<?>) c).supplementary;
+ if (os != null) {
+ if (changed) {
+ // Avoid the cost of computing cardinality.
+ s.andNot(os);
+ } else {
+ final int cardinality = s.cardinality();
+ s.andNot(os);
+ changed = (cardinality != s.cardinality());
+ }
+ }
+ }
+ return changed;
}
return super.removeAll(c);
}
@@ -232,19 +359,43 @@ public class CodeListSet<E extends CodeL
@Override
public boolean retainAll(final Collection<?> c) {
if (c instanceof CodeListSet) {
- return values != (values &= mask((CodeListSet<?>) c));
+ boolean changed = (values != (values &= mask((CodeListSet<?>) c)));
+ /*
+ * Code below this point is for the rare cases
+ * where there is more than 64 code list elements.
+ */
+ final BitSet s = supplementary;
+ if (s != null) {
+ final BitSet os = ((CodeListSet<?>) c).supplementary;
+ if (os == null) {
+ changed |= !s.isEmpty();
+ s.clear();
+ } else if (changed) {
+ // Avoid the cost of computing cardinality.
+ s.and(os);
+ } else {
+ final int cardinality = s.cardinality();
+ s.and(os);
+ changed = (cardinality != s.cardinality());
+ }
+ }
+ return changed;
}
return super.retainAll(c);
}
/**
* Returns an iterator over the elements in this set.
+ * The instance returned by this implementation will iterate over a
snapshot of this
+ * {@code CodeListSet} content at the time this method has been invoked.
Changes in
+ * this {@code CodeListSet} made after this method call will not affect
the values
+ * returned by the iterator.
*
* @return An iterator over the elements in this set.
*/
@Override
public Iterator<E> iterator() {
- return new Iter();
+ return new Iter(values, supplementary);
}
/**
@@ -258,16 +409,23 @@ public class CodeListSet<E extends CodeL
private long remaining;
/**
- * Mask with all bits set to 1 except the bit for the last value
returned by {@link #next()}.
- * This mask is 0 if {@code next()} has not yet been invoked.
+ * Initialized to a clone of {@link CodeListSet#supplementary}, then
the bits are cleared
+ * as we progress in the iteration. The bit set become empty when the
iteration is done.
*/
- private long mask;
+ private final BitSet more;
/**
- * Creates a new iterator.
+ * Ordinal value of the last element returned by {@link #next()}, or
-1 if none.
*/
- Iter() {
+ private int last;
+
+ /**
+ * Creates a new iterator initialized to the given values.
+ */
+ Iter(final long values, final BitSet supplementary) {
remaining = values;
+ more = (supplementary != null) ? (BitSet) supplementary.clone() :
null;
+ last = -1;
}
/**
@@ -275,7 +433,7 @@ public class CodeListSet<E extends CodeL
*/
@Override
public boolean hasNext() {
- return remaining != 0;
+ return remaining != 0 || (more != null && !more.isEmpty());
}
/**
@@ -283,17 +441,18 @@ public class CodeListSet<E extends CodeL
*/
@Override
public E next() {
- final int index = Long.numberOfTrailingZeros(remaining);
- if (index >= Long.SIZE) {
- throw new NoSuchElementException();
- }
- mask = ~(1L << index);
- remaining &= mask;
- E[] array = codes;
- if (array == null || index >= array.length) {
- codes = array = Types.getCodeValues(elementType);
+ int ordinal = Long.numberOfTrailingZeros(remaining);
+ if (ordinal >= Long.SIZE) {
+ // Rare case when we have more than 64 elements.
+ if (more == null || (ordinal = more.nextSetBit(0)) < 0) {
+ throw new NoSuchElementException();
+ }
+ more.clear(ordinal);
+ ordinal += Long.SIZE;
}
- return array[index];
+ last = ordinal;
+ remaining &= ~(1L << ordinal);
+ return valueOf(ordinal);
}
/**
@@ -301,11 +460,31 @@ public class CodeListSet<E extends CodeL
*/
@Override
public void remove() {
- if (mask == 0) {
+ if (last < 0) {
throw new IllegalStateException();
}
- values &= mask;
- mask = 0;
+ clear(last);
+ last = -1;
+ }
+ }
+
+ /**
+ * Returns a clone of this set.
+ */
+ @Override
+ @SuppressWarnings("unchecked")
+ public CodeListSet<E> clone() {
+ @SuppressWarnings("unchecked")
+ final CodeListSet<E> clone;
+ try {
+ clone = (CodeListSet<E>) super.clone();
+ } catch (CloneNotSupportedException e) {
+ throw new AssertionError(e); // Should never happen, since we are
cloneable.
+ }
+ final BitSet s = supplementary;
+ if (s != null) {
+ clone.supplementary = (BitSet) s.clone();
}
+ return clone;
}
}
Modified:
sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/collection/CodeListSetTest.java
URL:
http://svn.apache.org/viewvc/sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/collection/CodeListSetTest.java?rev=1450278&r1=1450277&r2=1450278&view=diff
==============================================================================
---
sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/collection/CodeListSetTest.java
[UTF-8] (original)
+++
sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/collection/CodeListSetTest.java
[UTF-8] Tue Feb 26 17:02:14 2013
@@ -16,10 +16,17 @@
*/
package org.apache.sis.util.collection;
+import java.util.Set;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Random;
import org.opengis.referencing.cs.AxisDirection;
import org.opengis.metadata.spatial.PixelOrientation;
import org.apache.sis.test.TestCase;
import org.apache.sis.test.DependsOnMethod;
+import org.apache.sis.util.iso.LargeCodeList;
import org.junit.Test;
import static org.junit.Assert.*;
@@ -203,4 +210,69 @@ public final strictfp class CodeListSetT
assertArrayEquals(new Object[] {NORTH, NORTH_EAST, EAST, UP},
c.toArray());
assertFalse("Invoking a second time should not make any difference.",
c.addAll(o));
}
+
+ /**
+ * Tests the various methods with a code list containing more than 64
elements.
+ */
+ @Test
+ public void testLargeCodeList() {
+ final Set<LargeCodeList> master = new
HashSet<>(Arrays.asList(LargeCodeList.values()));
+ assertTrue("This test requires more than 64 elements.", master.size()
> Long.SIZE);
+ final CodeListSet<LargeCodeList> c = new
CodeListSet<>(LargeCodeList.class);
+ /*
+ * Copy all content from the master to the CodeListSet. This will
indirectly
+ * test CodeListSet.add(E), through the AbstractSet.addAll(Collection)
method.
+ */
+ assertTrue(c.addAll(master));
+ assertEquals(master.size(), c.size());
+ assertEquals(master, c);
+ assertFalse("Invoking a second time should not make any difference.",
c.addAll(master));
+ /*
+ * Keep a copy of the set before we modify it.
+ */
+ final CodeListSet<LargeCodeList> clone = c.clone();
+ assertNotSame("Clone shall be a new instance.", c, clone);
+ assertEquals("Clone shall be equal to the original.", master, clone);
+ /*
+ * Tests contains(Object) and remove(Object). We also remove elements
+ * from the master set, then we verify that the result is the same.
+ */
+ LargeCodeList lastRemoved = null;
+ final Random random = new Random();
+ do {
+ for (final Iterator<LargeCodeList> it=master.iterator();
it.hasNext();) {
+ final LargeCodeList code = it.next();
+ assertTrue(code.name(), c.contains(code));
+ if (random.nextBoolean()) {
+ assertTrue (code.name(), c.remove(code));
+ assertFalse(code.name(), c.contains(code));
+ it.remove();
+ lastRemoved = code;
+ if (master.size() == 1) {
+ // Very unlikely, but let be safe since the tests
+ // after the look require at least one element.
+ break;
+ }
+ }
+ }
+ } while (lastRemoved == null);
+ assertEquals(master, c);
+ assertFalse(c.isEmpty());
+ /*
+ * Test containsAll(Collection) and removeAll(Collection).
+ */
+ assertTrue ("The original set shall contain the decimated set.",
clone.containsAll(c));
+ assertFalse("The decimated set can not contain the original set.",
c.containsAll(clone));
+ assertTrue ("Original set minus one element.",
clone.remove(lastRemoved));
+ assertTrue ("Add an element to be ignored by removeAll(…).",
c.add(lastRemoved));
+ assertTrue ("Remove all elements found in the decimated set.",
clone.removeAll(c));
+ assertTrue ("Expect no common elements.", Collections.disjoint(master,
clone));
+ assertFalse("Invoking a second time should not make any difference.",
clone.removeAll(c));
+ /*
+ * Test retainAll(Collection).
+ */
+ assertTrue("Add the element to be retained.", clone.add(lastRemoved));
+ assertTrue(c.retainAll(clone));
+ assertEquals(Collections.singleton(lastRemoved), c);
+ }
}
Added:
sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/iso/LargeCodeList.java
URL:
http://svn.apache.org/viewvc/sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/iso/LargeCodeList.java?rev=1450278&view=auto
==============================================================================
---
sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/iso/LargeCodeList.java
(added)
+++
sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/iso/LargeCodeList.java
[UTF-8] Tue Feb 26 17:02:14 2013
@@ -0,0 +1,88 @@
+/*
+ * 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 org.apache.sis.util.iso;
+
+import java.util.List;
+import java.util.ArrayList;
+import org.opengis.util.CodeList;
+
+import static org.junit.Assert.*;
+
+
+/**
+ * A code list containing more than 64 elements. This implementation can be
used by tests
+ * that requires a large amount of code list elements.
+ *
+ * @author Martin Desruisseaux (Geomatys)
+ * @since 0.3
+ * @version 0.3
+ * @module
+ */
+@SuppressWarnings("serial")
+public final strictfp class LargeCodeList extends CodeList<LargeCodeList> {
+ /**
+ * List of all enumerations of this type.
+ */
+ private static final List<LargeCodeList> VALUES = new ArrayList<>(100);
+
+ /**
+ * Creates 100 code list elements.
+ */
+ static {
+ for (int i=0; i<100; i++) {
+ assertEquals(i, new LargeCodeList(i).ordinal());
+ }
+ }
+
+ /**
+ * Constructs an element. The new element is automatically
+ * added to the list to be returned by {@link #values}.
+ */
+ private LargeCodeList(final int i) {
+ super("LC#" + i, VALUES);
+ }
+
+ /**
+ * Returns the list of {@code LargeCodeList}s.
+ *
+ * @return The list of codes declared in the current JVM.
+ */
+ public static LargeCodeList[] values() {
+ synchronized (VALUES) {
+ return VALUES.toArray(new LargeCodeList[VALUES.size()]);
+ }
+ }
+
+ /**
+ * Returns the list of codes of the same kind than this code list element.
+ */
+ @Override
+ public LargeCodeList[] family() {
+ return values();
+ }
+
+ /**
+ * Returns the axis code that matches the given string,
+ * or returns a new one if none match it.
+ *
+ * @param code The name of the code list element to fetch or to create.
+ * @return A code list element matching the given name.
+ */
+ public static LargeCodeList valueOf(final String code) {
+ return valueOf(LargeCodeList.class, code);
+ }
+}
Propchange:
sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/iso/LargeCodeList.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange:
sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/iso/LargeCodeList.java
------------------------------------------------------------------------------
svn:mime-type = text/plain;charset=UTF-8
