--- src/main/java/org/apache/commons/collections4/NavigableSetValuedMap.java (revision 1760292) +++ src/main/java/org/apache/commons/collections4/NavigableSetValuedMap.java (working copy) @@ -16,36 +16,37 @@ */ package org.apache.commons.collections4; -import java.util.Set; +import java.util.NavigableSet; /** * Defines a map that holds a set of values against each key. *

- * A {@code SetValuedMap} is a Map with slightly different semantics: + * A {@code NavigableSetValuedMap} is a Map with slightly different semantics: *

+ * This map provides a sorted and navigable set interface to the values corresponding to each key. * - * @since 4.1 + * @since FIXME * @version $Id$ */ -public interface SetValuedMap extends MultiValuedMap { +public interface NavigableSetValuedMap extends SetValuedMap { /** * Gets the set of values associated with the specified key. *

- * Implementations typically return an empty {@code Set} if no values + * Implementations typically return an empty {@code NavigableSet} if no values * have been mapped to the key. *

* * @param key the key to retrieve - * @return the {@code Set} of values, implementations should return an - * empty {@code Set} for no mapping + * @return the {@code NavigableSet} of values, implementations should return an + * empty {@code NavigableSet} for no mapping rather than {@code null}. * @throws NullPointerException if the key is null and null keys are invalid */ @Override - Set get(K key); + NavigableSet get(K key); /** * Removes all values associated with the specified key. @@ -55,11 +56,11 @@ * specified key, an empty, unmodifiable set will be returned. * * @param key the key to remove values from - * @return the {@code Set} of values removed, implementations should + * @return the {@code NavigableSet} of values removed, implementations should * return null for no mapping found, but may return an empty collection * @throws UnsupportedOperationException if the map is unmodifiable * @throws NullPointerException if the key is null and null keys are invalid */ @Override - Set remove(Object key); + NavigableSet remove(Object key); } --- src/main/java/org/apache/commons/collections4/SetUtils.java (revision 1760323) +++ src/main/java/org/apache/commons/collections4/SetUtils.java (working copy) @@ -73,8 +73,28 @@ public static SortedSet emptySortedSet() { return EMPTY_SORTED_SET; } + + /** + * An empty unmodifiable navigable set. + * This is not provided in the JDK. + * @since FIXME + */ + @SuppressWarnings("rawtypes") + public static final NavigableSet EMPTY_NAVIGABLE_SET = + UnmodifiableNavigableSet.unmodifiableNavigableSet(new TreeSet()); /** + * Get a typed empty unmodifiable navigable set. + * @param the element type + * @return an empty sorted Set + * @since FIXME + */ + @SuppressWarnings("unchecked") // empty set is OK for any type + public static NavigableSet emptyNavigableSet() { + return EMPTY_NAVIGABLE_SET; + } + + /** * SetUtils should not normally be instantiated. */ private SetUtils() {} @@ -92,6 +112,19 @@ public static Set emptyIfNull(final Set set) { return set == null ? Collections.emptySet() : set; } + + /** + * Returns an immutable empty set if the argument is null, + * or the argument itself otherwise. + * + * @param the element type + * @param set the set, possibly null + * @return an empty set if the argument is null + * @since FIXME + */ + public static NavigableSet emptyIfNull(final NavigableSet set) { + return set == null ? SetUtils.emptyNavigableSet() : set; + } /** * Tests two sets for equality as per the equals() contract --- src/main/java/org/apache/commons/collections4/list/MappedList.java (revision 0) +++ src/main/java/org/apache/commons/collections4/list/MappedList.java (working copy) @@ -0,0 +1,318 @@ +/* + * 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.commons.collections4.list; + +import java.util.AbstractList; +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashSet; +import java.util.List; +import java.util.NavigableSet; +import java.util.Set; +import java.util.SortedSet; +import java.util.TreeSet; + +import org.apache.commons.collections4.NavigableSetValuedMap; +import org.apache.commons.collections4.SetUtils; +import org.apache.commons.collections4.multimap.HashSetValuedHashMap; +import org.apache.commons.collections4.multimap.TreeSetValuedHashMap; +import org.apache.commons.collections4.set.UnmodifiableNavigableSet; + +/** + * A List with fast {@link #indexOf(Object)} and {@link #contains(Object)} methods. + * A {@link HashSetValuedHashMap} is used to provide faster entry lookup at the + * expense of maintaining a second data structure (slight RAM and speed cost). + * + * @param + * @since FIXME + */ +public class MappedList extends AbstractList { + + private final List list; + private final NavigableSetValuedMap invertedMap; + + public MappedList() { + super(); + list = new ArrayList(); + invertedMap = new TreeSetValuedHashMap(); + } + + public MappedList(final Collection coll) { + this(); + addAll(coll); + } + + @Override + public E get(final int index) { + return list.get(index); + } + + @Override + public int size() { + return list.size(); + } + + @Override + public boolean isEmpty() { + return list.isEmpty(); + } + + @Override + public boolean contains(final Object o) { + /* try { + Collection values = invertedMap.get((E) o); + return values != null && !values.isEmpty(); + } catch (final ClassCastException e) { + return false; + }*/ + return invertedMap.containsKey(o); + } + + /*@Override + public Iterator iterator() { + // TODO Auto-generated method stub + return null; + }*/ + + /*@Override + public Object[] toArray() { + // TODO Auto-generated method stub + return null; + }*/ + + /*@Override + public T[] toArray(T[] a) { + // TODO Auto-generated method stub + return null; + }*/ + + @Override + public E set(final int index, final E element) { + checkRange(index); + final E previous = list.set(index, element); + invertedMap.removeMapping(previous, index); + invertedMap.put(element, index); + return previous; + } + + @Override + public boolean add(final E e) { + final boolean modified = list.add(e); + if (modified) { + invertedMap.put(e, list.size() - 1); + } + return modified; + } + + @Override + public void add(final int index, final E element) { + checkRange(index); + final boolean rebuild = isFasterToRebuildThanShift(index); + if (! rebuild) { + incrementMapIndices(index); + invertedMap.put(element, index); + } + list.add(index, element); + if (rebuild) { + rebuildMap(); + } + } + + @Override + public boolean remove(final Object o) { + if (!contains(o)) return false; + @SuppressWarnings("unchecked") + NavigableSet indices = invertedMap.get((E) o); + final int indexToRemove = indices.first(); + remove(indexToRemove); + return true; + } + @Override + public E remove(final int index) { + checkRange(index); + final E removed = list.get(index); + final boolean rebuild = isFasterToRebuildThanShift(index); + if (! rebuild) { + invertedMap.removeMapping(removed, index); + decrementMapIndices(index); + } + list.remove(index); + if (rebuild) { + rebuildMap(); + } + return removed; + } + + /*@Override + public boolean containsAll(Collection c) { + // TODO Auto-generated method stub + return false; + }*/ + + /*@Override + public boolean addAll(Collection c) { + // TODO Auto-generated method stub + return false; + }*/ + + /*@Override + public boolean addAll(int index, Collection c) { + // TODO Auto-generated method stub + return false; + }*/ + + /*@Override + public boolean removeAll(Collection c) { + // TODO Auto-generated method stub + return false; + }*/ + + /*@Override + public boolean retainAll(Collection c) { + // TODO Auto-generated method stub + return false; + }*/ + + @Override + public void clear() { + invertedMap.clear(); + list.clear(); + } + + + @SuppressWarnings("unchecked") + @Override + public int indexOf(final Object o) { + if (! contains(o)) return -1; + return invertedMap.get((E) o).first(); + //final NavigableSet indices = invertedMap.get((E) o); + //return (indices == null || indices.isEmpty()) ? -1 : indices.first(); + } + + @SuppressWarnings("unchecked") + @Override + public int lastIndexOf(final Object o) { + //if (! contains(o)) return -1; + //return invertedMap.get((E) o).last(); + final NavigableSet indices = invertedMap.get((E) o); + return (indices == null || indices.isEmpty()) ? -1 : indices.last(); + } + + + @SuppressWarnings("unchecked") + public NavigableSet getIndices(final Object o) { + if (! contains(o)) + return SetUtils.EMPTY_NAVIGABLE_SET; + final NavigableSet set = invertedMap.get((E) o); + return UnmodifiableNavigableSet.unmodifiableNavigableSet(set); + } + + /*@Override + public ListIterator listIterator() { + // TODO Auto-generated method stub + return null; + }*/ + + /*@Override + public ListIterator listIterator(int index) { + // TODO Auto-generated method stub + return null; + }*/ + + /*@Override + public List subList(int fromIndex, int toIndex) { + // TODO Auto-generated method stub + return null; + }*/ + + private void checkRange(final int index) { + if (index < 0 || index > size()) + throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); + } + + private String outOfBoundsMsg(final int index) { + return "Index: "+index+", Size: "+size(); + } + + private void incrementMapIndices(final int startIndex) { + shiftMapIndices(startIndex, 1); + } + private void decrementMapIndices(final int startIndex) { + shiftMapIndices(startIndex, -1); + } + /** + * this must be called BEFORE the list is modified. + * @param startIndex + * @param offset + */ + private void shiftMapIndices(final int startIndex, final int offset) { + final int stopIndex = list.size() - 1; + // if an element appears multiple times in the list, all indices in the + // inverted map must be shifted simultaneously. To avoid shifting the + // same index multiple times, the seen set is used + final Set seen = new HashSet(); + //for (int idx = startIndex; idx < stopIndex; idx++) { + // final E element = list.get(idx); + for (final E element : list.subList(startIndex, stopIndex+1)) { + if (seen.add(element)) { // Set.add(E) returns true if set does not contain element + // Depending on sign of offset, the indices either need to be + // incremented in descending order or decremented in ascending order + // This avoids index collision. (Consider offset=1 with two adjacent equal elements.) + // See descendingSet(). + /*final SortedSet indices = invertedMap.get(element).tailSet(startIndex); + for (final int i : indices) { + invertedMap.removeMapping(element, i); + invertedMap.put(element, i + offset); + }*/ + + // shift all of the indices >= startIndex for this element + final NavigableSet indices = invertedMap.get(element); + if (indices == null || indices.isEmpty()) + continue; + + // Re-adding the indices is the slowest part. This would be faster + // if indices supported replacing elements in the set, avoiding a bunch of tree re-linking. + final Collection upper; + //upper = new TreeSet(indices.tailSet(startIndex)); + //upper = new ArrayList(indices.tailSet(startIndex)); + upper = new ArrayList(indices.tailSet(startIndex)); + indices.removeAll(upper); + for (final Integer u : upper) { + indices.add(u + offset); + } + } + } + } + + private void rebuildMap() { + invertedMap.clear(); + int i = 0; + for (E e : list) { + invertedMap.put(e, i); + i++; + } + } + + private boolean isFasterToRebuildThanShift(final int index) { + //faster to modify the map. otherwise faster to rebuild the map from scratch + //final boolean fasterToRebuildThanShift = index < (list.size() * 3 / 4); + final boolean fasterToRebuildThanShift = true; + return fasterToRebuildThanShift; + } + +} +native +Author Id Revision HeadURL --- src/main/java/org/apache/commons/collections4/multimap/AbstractNavigableSetValuedMap.java (revision 1760292) +++ src/main/java/org/apache/commons/collections4/multimap/AbstractNavigableSetValuedMap.java (working copy) @@ -17,9 +17,14 @@ package org.apache.commons.collections4.multimap; import java.util.Collections; +import java.util.Comparator; +import java.util.Iterator; import java.util.Map; +import java.util.NavigableSet; import java.util.Set; +import java.util.SortedSet; +import org.apache.commons.collections4.NavigableSetValuedMap; import org.apache.commons.collections4.SetUtils; import org.apache.commons.collections4.SetValuedMap; @@ -30,16 +35,16 @@ * Subclasses specify a Map implementation to use as the internal storage and * the Set implementation to use as values. * - * @since 4.1 + * @since FIXME * @version $Id$ */ -public abstract class AbstractSetValuedMap extends AbstractMultiValuedMap - implements SetValuedMap { +public abstract class AbstractNavigableSetValuedMap extends AbstractSetValuedMap + implements NavigableSetValuedMap { /** * Constructor needed for subclass serialisation. */ - protected AbstractSetValuedMap() { + protected AbstractNavigableSetValuedMap() { super(); } @@ -49,7 +54,7 @@ * @param map the map to wrap, must not be null * @throws NullPointerException if the map is null */ - protected AbstractSetValuedMap(Map> map) { + protected AbstractNavigableSetValuedMap(Map> map) { super(map); } @@ -56,8 +61,8 @@ // ----------------------------------------------------------------------- @Override @SuppressWarnings("unchecked") - protected Map> getMap() { - return (Map>) super.getMap(); + protected Map> getMap() { + return (Map>) super.getMap(); } /** @@ -65,7 +70,7 @@ * @return a new list */ @Override - protected abstract Set createCollection(); + protected abstract NavigableSet createCollection(); // ----------------------------------------------------------------------- /** @@ -77,13 +82,13 @@ * Set for no mapping */ @Override - public Set get(final K key) { + public NavigableSet get(final K key) { return wrappedCollection(key); } @Override - Set wrappedCollection(final K key) { - return new WrappedSet(key); + NavigableSet wrappedCollection(final K key) { + return new WrappedNavigableSet(key); } /** @@ -96,7 +101,7 @@ * unmodifiable set for no mapping found. */ @Override - public Set remove(Object key) { + public NavigableSet remove(Object key) { return SetUtils.emptyIfNull(getMap().remove(key)); } @@ -105,15 +110,20 @@ * Wrapped set to handle add and remove on the collection returned by * {@code get(Object)}. */ - private class WrappedSet extends WrappedCollection implements Set { + private class WrappedNavigableSet extends WrappedCollection implements NavigableSet { - public WrappedSet(final K key) { + public WrappedNavigableSet(final K key) { super(key); } + + /** never null */ + private NavigableSet getSet() { + return SetUtils.emptyIfNull((NavigableSet) getMapping()); + } @Override public boolean equals(Object other) { - final Set set = (Set) getMapping(); + final NavigableSet set = getSet(); if (set == null) { return Collections.emptySet().equals(other); } @@ -120,16 +130,100 @@ if (!(other instanceof Set)) { return false; } - Set otherSet = (Set) other; + final Set otherSet = (Set) other; return SetUtils.isEqualSet(set, otherSet); } @Override public int hashCode() { - final Set set = (Set) getMapping(); - return SetUtils.hashCodeForSet(set); + return SetUtils.hashCodeForSet(getSet()); } + @Override + public Comparator comparator() { + return getSet().comparator(); + } + + @Override + public V first() { + return getSet().first(); + } + + @Override + public V last() { + return getSet().last(); + } + + @Override + public V lower(V e) { + return getSet().lower(e); + } + + @Override + public V floor(V e) { + return getSet().floor(e); + } + + @Override + public V ceiling(V e) { + return getSet().ceiling(e); + } + + @Override + public V higher(V e) { + return getSet().higher(e); + } + + @Override + public V pollFirst() { + return getSet().pollFirst(); + } + + @Override + public V pollLast() { + return getSet().pollLast(); + } + + @Override + public NavigableSet descendingSet() { + return getSet().descendingSet(); + } + + @Override + public Iterator descendingIterator() { + return getSet().descendingIterator(); + } + + @Override + public NavigableSet subSet(V fromElement, boolean fromInclusive, V toElement, boolean toInclusive) { + return getSet().subSet(fromElement, fromInclusive, toElement, toInclusive); + } + + @Override + public NavigableSet headSet(V toElement, boolean inclusive) { + return getSet().headSet(toElement, inclusive); + } + + @Override + public NavigableSet tailSet(V fromElement, boolean inclusive) { + return getSet().tailSet(fromElement, inclusive); + } + + @Override + public SortedSet subSet(V fromElement, V toElement) { + return getSet().subSet(fromElement, toElement); + } + + @Override + public SortedSet headSet(V toElement) { + return getSet().headSet(toElement); + } + + @Override + public SortedSet tailSet(V fromElement) { + return getSet().tailSet(fromElement); + } + } } --- src/main/java/org/apache/commons/collections4/multimap/AbstractSetValuedMap.java (revision 1760323) +++ src/main/java/org/apache/commons/collections4/multimap/AbstractSetValuedMap.java (working copy) @@ -30,7 +30,7 @@ * Subclasses specify a Map implementation to use as the internal storage and * the Set implementation to use as values. * - * @since 4.1 + * @since FIXME * @version $Id$ */ public abstract class AbstractSetValuedMap extends AbstractMultiValuedMap @@ -56,7 +56,7 @@ // ----------------------------------------------------------------------- @Override @SuppressWarnings("unchecked") - protected Map> getMap() { + protected Map> getMap() { return (Map>) super.getMap(); } --- src/main/java/org/apache/commons/collections4/multimap/TreeSetValuedHashMap.java (revision 1760292) +++ src/main/java/org/apache/commons/collections4/multimap/TreeSetValuedHashMap.java (working copy) @@ -21,29 +21,31 @@ import java.io.ObjectOutputStream; import java.io.Serializable; import java.util.HashMap; -import java.util.HashSet; import java.util.Map; +import java.util.TreeSet; import org.apache.commons.collections4.MultiValuedMap; /** * Implements a {@code SetValuedMap}, using a {@link HashMap} to provide data - * storage and {@link HashSet}s as value collections. This is the standard - * implementation of a SetValuedMap. + * storage and {@link TreeSet}s as value collections. This improves on the + * standard implementation of a SetValuedMap by providing total ordering on the + * value collections. This is the standard implementation of a + * SortedSetValuedMap and NavigableSetValuedMap. *

- * Note that HashSetValuedHashMap is not synchronized and is not + * Note that TreeSetValuedHashMap is not synchronized and is not * thread-safe. If you wish to use this map from multiple threads * concurrently, you must use appropriate synchronization. This class may throw * exceptions when accessed by concurrent threads without synchronization. * - * @since 4.1 + * @since FIXME * @version $Id$ */ -public class HashSetValuedHashMap extends AbstractSetValuedMap +public class TreeSetValuedHashMap extends AbstractNavigableSetValuedMap implements Serializable { /** Serialization Version */ - private static final long serialVersionUID = 20151118L; + private static final long serialVersionUID = 2675614644971970576L; /** * The initial map capacity used when none specified in constructor. @@ -51,69 +53,48 @@ private static final int DEFAULT_INITIAL_MAP_CAPACITY = 16; /** - * The initial set capacity when using none specified in constructor. - */ - private static final int DEFAULT_INITIAL_SET_CAPACITY = 3; - - /** - * The initial list capacity when creating a new value collection. - */ - private final int initialSetCapacity; - - /** - * Creates an empty HashSetValuedHashMap with the default initial + * Creates an empty TreeSetValuedHashMap with the default initial * map capacity (16) and the default initial set capacity (3). */ - public HashSetValuedHashMap() { - this(DEFAULT_INITIAL_MAP_CAPACITY, DEFAULT_INITIAL_SET_CAPACITY); + public TreeSetValuedHashMap() { + this(DEFAULT_INITIAL_MAP_CAPACITY); } /** - * Creates an empty HashSetValuedHashMap with the default initial - * map capacity (16) and the specified initial set capacity. - * - * @param initialSetCapacity the initial capacity used for value collections - */ - public HashSetValuedHashMap(int initialSetCapacity) { - this(DEFAULT_INITIAL_MAP_CAPACITY, initialSetCapacity); - } - - /** - * Creates an empty HashSetValuedHashMap with the specified initial + * Creates an empty TreeSetValuedHashMap with the specified initial * map and list capacities. * * @param initialMapCapacity the initial hashmap capacity * @param initialSetCapacity the initial capacity used for value collections */ - public HashSetValuedHashMap(int initialMapCapacity, int initialSetCapacity) { - super(new HashMap>(initialMapCapacity)); - this.initialSetCapacity = initialSetCapacity; + public TreeSetValuedHashMap(int initialMapCapacity) { + super(new HashMap>(initialMapCapacity)); } /** - * Creates an HashSetValuedHashMap copying all the mappings of the given map. + * Creates an TreeSetValuedHashMap copying all the mappings of the given map. * * @param map a MultiValuedMap to copy into this map */ - public HashSetValuedHashMap(final MultiValuedMap map) { - this(map.size(), DEFAULT_INITIAL_SET_CAPACITY); + public TreeSetValuedHashMap(final MultiValuedMap map) { + this(map.size()); super.putAll(map); } /** - * Creates an HashSetValuedHashMap copying all the mappings of the given map. + * Creates an TreeSetValuedHashMap copying all the mappings of the given map. * * @param map a Map to copy into this map */ - public HashSetValuedHashMap(final Map map) { - this(map.size(), DEFAULT_INITIAL_SET_CAPACITY); + public TreeSetValuedHashMap(final Map map) { + this(map.size()); super.putAll(map); } // ----------------------------------------------------------------------- @Override - protected HashSet createCollection() { - return new HashSet(initialSetCapacity); + protected TreeSet createCollection() { + return new TreeSet(); } // ----------------------------------------------------------------------- @@ -124,7 +105,7 @@ private void readObject(ObjectInputStream ois) throws IOException, ClassNotFoundException { ois.defaultReadObject(); - setMap(new HashMap>()); + setMap(new HashMap>()); doReadObject(ois); } --- src/test/java/org/apache/commons/collections4/list/MappedListTest.java (revision 1760292) +++ src/test/java/org/apache/commons/collections4/list/MappedListTest.java (working copy) @@ -17,57 +17,96 @@ package org.apache.commons.collections4.list; import java.util.ArrayList; +import java.util.Arrays; +import java.util.HashSet; import java.util.List; import java.util.ListIterator; +import java.util.Random; +import java.util.Set; +import org.apache.commons.collections4.BulkTest; + import junit.framework.Test; -import org.apache.commons.collections4.BulkTest; - /** * JUnit tests * - * @since 3.1 + * @since FIXME * @version $Id$ */ -public class TreeListTest extends AbstractListTest { +public class MappedListTest extends AbstractListTest { - public TreeListTest(final String name) { + public MappedListTest(final String name) { super(name); } + + public void testRunBenchmark() { + main(new String[] {}); + } -// public static void main(String[] args) { -// junit.textui.TestRunner.run(suite()); -// System.out.println(" add; toArray; iterator; insert; get; indexOf; remove"); -// System.out.print(" TreeList = "); -// benchmark(new TreeList()); -// System.out.print("\n ArrayList = "); -// benchmark(new java.util.ArrayList()); -// System.out.print("\n LinkedList = "); -// benchmark(new java.util.LinkedList()); -// System.out.print("\n NodeCachingLinkedList = "); -// benchmark(new NodeCachingLinkedList()); -// } + public static void main(String[] args) { + final int[] initialSize = new int[]{10, 100, 1000, 10000, 100000}; + final int[] count = new int[]{10, 100, 1000, 10000, 100000}; + + //junit.textui.TestRunner.run(suite()); + for (int sz : initialSize) { + for (int cnt : count) { + final long start = System.currentTimeMillis(); + System.out.print("\n" + sz + ", " + cnt + ":"); + System.out.print(" add; toArray; iterator; insert; get; indexOf; contains; remove"); + System.out.print("\n ArrayList = "); + benchmark(new java.util.ArrayList(), sz, cnt); + System.out.print("\n LinkedList = "); + benchmark(new java.util.LinkedList(), sz, cnt); + System.out.print("\n NodeCachingLinkedList = "); + benchmark(new NodeCachingLinkedList(), sz, cnt); + System.out.print("\n TreeList = "); + benchmark(new TreeList(), sz, cnt); + System.out.print("\n MappedList = "); + benchmark(new MappedList(), sz, cnt); + final long elapsed = (System.currentTimeMillis() - start) / 1000; + final long minutes = elapsed / 60; + final long seconds = elapsed % 60; + System.out.println("\n" + minutes + "m" + seconds + "s"); + } + } + } public static Test suite() { - return BulkTest.makeSuite(TreeListTest.class); + return BulkTest.makeSuite(MappedListTest.class); } - + public static void benchmark(final List l) { + final int initialSize = 100000; + final int count = 400; + benchmark(l, initialSize, count); + } + + public static void benchmark(final List l, final int initialSize, final int count) { + + final Random rand = new Random(0L); + + for (int i = 0; i < initialSize; i++) { + l.add(Integer.valueOf(i)); + } + + // add long start = System.currentTimeMillis(); - for (int i = 0; i < 100000; i++) { + for (int i = 0; i < count; i++) { l.add(Integer.valueOf(i)); } System.out.print(System.currentTimeMillis() - start + ";"); + // toArray start = System.currentTimeMillis(); - for (int i = 0; i < 200; i++) { + for (int i = 0; i < count; i++) { l.toArray(); } System.out.print(System.currentTimeMillis() - start + ";"); + // iterator start = System.currentTimeMillis(); - for (int i = 0; i < 100; i++) { + for (int i = 0; i < count; i++) { final java.util.Iterator it = l.iterator(); while (it.hasNext()) { it.next(); @@ -75,30 +114,42 @@ } System.out.print(System.currentTimeMillis() - start + ";"); + // insert start = System.currentTimeMillis(); - for (int i = 0; i < 10000; i++) { - final int j = (int) (Math.random() * 100000); + for (int i = 0; i < count; i++) { + final int j = rand.nextInt(initialSize); l.add(j, Integer.valueOf(-j)); } System.out.print(System.currentTimeMillis() - start + ";"); + // get start = System.currentTimeMillis(); - for (int i = 0; i < 50000; i++) { - final int j = (int) (Math.random() * 110000); + for (int i = 0; i < count; i++) { + final int j = rand.nextInt(initialSize); l.get(j); } System.out.print(System.currentTimeMillis() - start + ";"); + // indexOf start = System.currentTimeMillis(); - for (int i = 0; i < 200; i++) { - final int j = (int) (Math.random() * 100000); + for (int i = 0; i < count; i++) { + final int j = rand.nextInt(initialSize); l.indexOf(Integer.valueOf(j)); } System.out.print(System.currentTimeMillis() - start + ";"); + + // contains + start = System.currentTimeMillis(); + for (int i = 0; i < count; i++) { + final int j = rand.nextInt(initialSize); + l.contains(Integer.valueOf(j)); + } + System.out.print(System.currentTimeMillis() - start + ";"); + // remove start = System.currentTimeMillis(); - for (int i = 0; i < 10000; i++) { - final int j = (int) (Math.random() * 100000); + for (int i = 0; i < count; i++) { + final int j = rand.nextInt(initialSize); l.remove(j); } System.out.print(System.currentTimeMillis() - start + ";"); @@ -106,8 +157,8 @@ //----------------------------------------------------------------------- @Override - public TreeList makeObject() { - return new TreeList(); + public MappedList makeObject() { + return new MappedList(); } //----------------------------------------------------------------------- @@ -220,7 +271,7 @@ public void testBug35258() { final Object objectToRemove = Integer.valueOf(3); - final List treelist = new TreeList(); + final List treelist = new MappedList(); treelist.add(Integer.valueOf(0)); treelist.add(Integer.valueOf(1)); treelist.add(Integer.valueOf(2)); @@ -248,7 +299,7 @@ } public void testBugCollections447() { - final List treeList = new TreeList(); + final List treeList = new MappedList(); treeList.add("A"); treeList.add("B"); treeList.add("C"); @@ -271,7 +322,7 @@ public void testIterationOrder() { // COLLECTIONS-433: // ensure that the iteration order of elements is correct - // when initializing the TreeList with another collection + // when initializing the MappedList with another collection for (int size = 1; size < 1000; size++) { List other = new ArrayList(size); @@ -278,7 +329,7 @@ for (int i = 0; i < size; i++) { other.add(i); } - TreeList l = new TreeList(other); + MappedList l = new MappedList(other); ListIterator it = l.listIterator(); int i = 0; while (it.hasNext()) { @@ -297,7 +348,7 @@ public void testIterationOrderAfterAddAll() { // COLLECTIONS-433: // ensure that the iteration order of elements is correct - // when calling addAll on the TreeList + // when calling addAll on the MappedList // to simulate different cases in addAll, do different runs where // the number of elements already in the list and being added by addAll differ @@ -308,7 +359,7 @@ for (int j = i; j < size; j++) { other.add(j); } - TreeList l = new TreeList(); + MappedList l = new MappedList(); for (int j = 0; j < i; j++) { l.add(j); } @@ -328,5 +379,30 @@ } } } + + private static Set makeSet(E... values) { + Set set = new HashSet(); + for (E value : values) { + set.add(value); + } + return set; + } + + @SuppressWarnings("unchecked") + public void testGetIndices() { + final MappedList l = makeObject(); + l.add((E) "A"); //0 + l.add((E) "B"); //1 + l.add((E) "C"); //2 + l.add((E) "A"); //3 + l.add((E) "B"); //4 + l.add((E) "A"); //5 + l.add((E) "A"); //6 + + assertEquals(makeSet(0, 3, 5, 6), l.getIndices("A")); + assertEquals(makeSet(1, 4), l.getIndices("B")); + assertEquals(makeSet(2), l.getIndices("C")); + assertEquals(makeSet(), l.getIndices("D")); + } } --- src/test/java/org/apache/commons/collections4/multimap/TreeSetValuedHashMapTest.java (revision 1760292) +++ src/test/java/org/apache/commons/collections4/multimap/TreeSetValuedHashMapTest.java (working copy) @@ -26,30 +26,30 @@ import org.apache.commons.collections4.SetValuedMap; /** - * Test HashSetValuedHashMap + * Test TreeSetValuedHashMap * - * @since 4.1 + * @since FIXME * @version $Id$ */ -public class HashSetValuedHashMapTest extends AbstractMultiValuedMapTest { +public class TreeSetValuedHashMapTest extends AbstractMultiValuedMapTest { - public HashSetValuedHashMapTest(String testName) { + public TreeSetValuedHashMapTest(String testName) { super(testName); } public static Test suite() { - return BulkTest.makeSuite(HashSetValuedHashMapTest.class); + return BulkTest.makeSuite(TreeSetValuedHashMapTest.class); } // ----------------------------------------------------------------------- @Override public SetValuedMap makeObject() { - return new HashSetValuedHashMap(); + return new TreeSetValuedHashMap(); } @Override public MultiValuedMap makeConfirmedMap() { - return new HashSetValuedHashMap(); + return new TreeSetValuedHashMap(); } // ----------------------------------------------------------------------- @@ -126,11 +126,12 @@ assertNotSame(map1.hashCode(), map2.hashCode()); } -// public void testCreate() throws Exception { -// writeExternalFormToDisk((java.io.Serializable) makeObject(), -// "src/test/resources/data/test/HashSetValuedHashMap.emptyCollection.version4.1.obj"); -// writeExternalFormToDisk((java.io.Serializable) makeFullMap(), -// "src/test/resources/data/test/HashSetValuedHashMap.fullCollection.version4.1.obj"); -// } + + /*public void testCreate() throws Exception { + writeExternalFormToDisk((java.io.Serializable) makeObject(), + "src/test/resources/data/test/TreeSetValuedHashMap.emptyCollection.version4.1.obj"); + writeExternalFormToDisk((java.io.Serializable) makeFullMap(), + "src/test/resources/data/test/TreeSetValuedHashMap.fullCollection.version4.1.obj"); + }*/ }