Attachment #34239 for bug #58740

View | Details | Raw Unified | Return to bug 58740
Collapse All | Expand All




 */
package org.apache.commons.collections4;

import java.util.NavigableSet;

/**
 * Defines a map that holds a set of values against each key.
 * <p>
 * A {@code NavigableSetValuedMap} is a Map with slightly different semantics:
 * <ul>
 *   <li>Putting a value into the map will add the value to a {@link NavigableSet} at that key.</li>
 *   <li>Getting a value will return a {@link NavigableSet}, holding all the values put to that key.</li>
 * </ul>
 * This map provides a sorted and navigable set interface to the values corresponding to each key.
 *
 * @since FIXME
 * @version $Id$
 */
public interface NavigableSetValuedMap<K, V> extends SetValuedMap<K, V> {

    /**
     * Gets the set of values associated with the specified key.
     * <p>
     * Implementations typically return an empty {@code NavigableSet} if no values
     * have been mapped to the key.
     * <p>
     *
     * @param key  the key to retrieve
     * @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
    NavigableSet<V> get(K key);

    /**
     * Removes all values associated with the specified key.

     * specified key, an empty, unmodifiable set will be returned.
     *
     * @param key  the key to remove values from
     * @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
    NavigableSet<V> remove(Object key);
}




    public static <E> SortedSet<E> 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<Object>());

    /**
     * Get a typed empty unmodifiable navigable set.
     * @param <E> the element type
     * @return an empty sorted Set
     * @since FIXME
     */
    @SuppressWarnings("unchecked") // empty set is OK for any type
    public static <E> NavigableSet<E> emptyNavigableSet() {
        return EMPTY_NAVIGABLE_SET;
    }

    /**
     * <code>SetUtils</code> should not normally be instantiated.
     */
    private SetUtils() {}

    public static <T> Set<T> emptyIfNull(final Set<T> set) {
        return set == null ? Collections.<T>emptySet() : set;
    }
    
    /**
     * Returns an immutable empty set if the argument is <code>null</code>,
     * or the argument itself otherwise.
     *
     * @param <T> the element type
     * @param set the set, possibly <code>null</code>
     * @return an empty set if the argument is <code>null</code>
     * @since FIXME
     */
    public static <T> NavigableSet<T> emptyIfNull(final NavigableSet<T> set) {
        return set == null ? SetUtils.<T>emptyNavigableSet() : set;
    }

    /**
     * Tests two sets for equality as per the <code>equals()</code> contract




/*
 * 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 <E>
 * @since FIXME
 */
public class MappedList<E> extends AbstractList<E> {
    
    private final List<E> list;
    private final NavigableSetValuedMap<E, Integer> invertedMap;
    
    public MappedList() {
        super();
        list = new ArrayList<E>();
        invertedMap  = new TreeSetValuedHashMap<E, Integer>();
    }
    
    public MappedList(final Collection<? extends E> 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<Integer> values = invertedMap.get((E) o);
            return values != null && !values.isEmpty();
        } catch (final ClassCastException e) {
            return false;
        }*/
        return invertedMap.containsKey(o);
    }

    /*@Override
    public Iterator<E> iterator() {
        // TODO Auto-generated method stub
        return null;
    }*/

    /*@Override
    public Object[] toArray() {
        // TODO Auto-generated method stub
        return null;
    }*/

    /*@Override
    public <T> 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<Integer> 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<? extends E> c) {
        // TODO Auto-generated method stub
        return false;
    }*/

    /*@Override
    public boolean addAll(int index, Collection<? extends E> 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<Integer> 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<Integer> indices = invertedMap.get((E) o);
        return (indices == null || indices.isEmpty()) ? -1 : indices.last();
    }
    
    
    @SuppressWarnings("unchecked")
    public NavigableSet<Integer> getIndices(final Object o) {
        if (! contains(o))
            return SetUtils.EMPTY_NAVIGABLE_SET;
        final NavigableSet<Integer> set = invertedMap.get((E) o);
        return UnmodifiableNavigableSet.unmodifiableNavigableSet(set);
    }

    /*@Override
    public ListIterator<E> listIterator() {
        // TODO Auto-generated method stub
        return null;
    }*/

    /*@Override
    public ListIterator<E> listIterator(int index) {
        // TODO Auto-generated method stub
        return null;
    }*/

    /*@Override
    public List<E> 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<E> seen = new HashSet<E>();
        //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<Integer> 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<Integer> 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<Integer> upper;
                //upper = new TreeSet<Integer>(indices.tailSet(startIndex));
                //upper = new ArrayList<Integer>(indices.tailSet(startIndex));
                upper = new ArrayList<Integer>(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




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;


 * Subclasses specify a Map implementation to use as the internal storage and
 * the Set implementation to use as values.
 *
 * @since FIXME
 * @version $Id$
 */
public abstract class AbstractNavigableSetValuedMap<K, V> extends AbstractSetValuedMap<K, V>
    implements NavigableSetValuedMap<K, V> {

    /**
     * Constructor needed for subclass serialisation.
     */
    protected AbstractNavigableSetValuedMap() {
        super();
    }


     * @param map  the map to wrap, must not be null
     * @throws NullPointerException if the map is null
     */
    protected AbstractNavigableSetValuedMap(Map<K, ? extends NavigableSet<V>> map) {
        super(map);
    }


    // -----------------------------------------------------------------------
    @Override
    @SuppressWarnings("unchecked")
    protected Map<K, NavigableSet<V>> getMap() {
        return (Map<K, NavigableSet<V>>) super.getMap();
    }

    /**

     * @return a new list
     */
    @Override
    protected abstract NavigableSet<V> createCollection();

    // -----------------------------------------------------------------------
    /**

     *   <code>Set</code> for no mapping
     */
    @Override
    public NavigableSet<V> get(final K key) {
        return wrappedCollection(key);
    }

    @Override
    NavigableSet<V> wrappedCollection(final K key) {
        return new WrappedNavigableSet(key);
    }

    /**

     *   unmodifiable set for no mapping found.
     */
    @Override
    public NavigableSet<V> remove(Object key) {
        return SetUtils.emptyIfNull(getMap().remove(key));
    }


     * Wrapped set to handle add and remove on the collection returned by
     * {@code get(Object)}.
     */
    private class WrappedNavigableSet extends WrappedCollection implements NavigableSet<V> {

        public WrappedNavigableSet(final K key) {
            super(key);
        }
        
        /** never null */
        private NavigableSet<V> getSet() {
            return SetUtils.emptyIfNull((NavigableSet<V>) getMapping());
        }

        @Override
        public boolean equals(Object other) {
            final NavigableSet<V> set = getSet();
            if (set == null) {
                return Collections.emptySet().equals(other);
            }

            if (!(other instanceof Set)) {
                return false;
            }
            final Set<?> otherSet = (Set<?>) other;
            return SetUtils.isEqualSet(set, otherSet);
        }

        @Override
        public int hashCode() {
            return SetUtils.hashCodeForSet(getSet());
            return SetUtils.hashCodeForSet(set);
        }

        @Override
        public Comparator<? super V> 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<V> descendingSet() {
            return getSet().descendingSet();
        }

        @Override
        public Iterator<V> descendingIterator() {
            return getSet().descendingIterator();
        }

        @Override
        public NavigableSet<V> subSet(V fromElement, boolean fromInclusive, V toElement, boolean toInclusive) {
            return getSet().subSet(fromElement, fromInclusive, toElement, toInclusive);
        }

        @Override
        public NavigableSet<V> headSet(V toElement, boolean inclusive) {
            return getSet().headSet(toElement, inclusive);
        }

        @Override
        public NavigableSet<V> tailSet(V fromElement, boolean inclusive) {
            return getSet().tailSet(fromElement, inclusive);
        }

        @Override
        public SortedSet<V> subSet(V fromElement, V toElement) {
            return getSet().subSet(fromElement, toElement);
        }

        @Override
        public SortedSet<V> headSet(V toElement) {
            return getSet().headSet(toElement);
        }

        @Override
        public SortedSet<V> tailSet(V fromElement) {
            return getSet().tailSet(fromElement);
        }

    }

}

Lines 30-36 Link Here

(-)src/main/java/org/apache/commons/collections4/multimap/AbstractSetValuedMap.java (-2 / +2 lines)
30	* Subclasses specify a Map implementation to use as the internal storage and	30	* Subclasses specify a Map implementation to use as the internal storage and
31	* the Set implementation to use as values.	31	* the Set implementation to use as values.
32	*	32	*
33	* @since 4.1	33	* @since FIXME
34	* @version $Id$	34	* @version $Id$
35	*/	35	*/
36	public abstract class AbstractSetValuedMap<K, V> extends AbstractMultiValuedMap<K, V>	36	public abstract class AbstractSetValuedMap<K, V> extends AbstractMultiValuedMap<K, V>
Lines 56-62 Link Here
56	// -----------------------------------------------------------------------	56	// -----------------------------------------------------------------------
57	@Override	57	@Override
58	@SuppressWarnings("unchecked")	58	@SuppressWarnings("unchecked")
59	protected Map<K, Set<V>> getMap() {	59	protected Map<K, ? extends Set<V>> getMap() {
60	return (Map<K, Set<V>>) super.getMap();	60	return (Map<K, Set<V>>) super.getMap();
61	}	61	}
62		62




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 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.
 * <p>
 * <strong>Note that TreeSetValuedHashMap is not synchronized and is not
 * thread-safe.</strong> 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 FIXME
 * @version $Id$
 */
public class TreeSetValuedHashMap<K, V> extends AbstractNavigableSetValuedMap<K, V>
    implements Serializable {

    /** Serialization Version */
    private static final long serialVersionUID = 2675614644971970576L;

    /**
     * The initial map capacity used when none specified in constructor.

    private static final int DEFAULT_INITIAL_MAP_CAPACITY = 16;

    /**
     * Creates an empty TreeSetValuedHashMap with the default initial
     */
    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
     * map capacity (16) and the default initial set capacity (3).
     */
    public TreeSetValuedHashMap() {
        this(DEFAULT_INITIAL_MAP_CAPACITY);
    }

    /**
     * Creates an empty TreeSetValuedHashMap with the specified 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
     * map and list capacities.
     *
     * @param initialMapCapacity  the initial hashmap capacity
     * @param initialSetCapacity  the initial capacity used for value collections
     */
    public TreeSetValuedHashMap(int initialMapCapacity) {
        super(new HashMap<K, TreeSet<V>>(initialMapCapacity));
        this.initialSetCapacity = initialSetCapacity;
    }

    /**
     * Creates an TreeSetValuedHashMap copying all the mappings of the given map.
     *
     * @param map a <code>MultiValuedMap</code> to copy into this map
     */
    public TreeSetValuedHashMap(final MultiValuedMap<? extends K, ? extends V> map) {
        this(map.size());
        super.putAll(map);
    }

    /**
     * Creates an TreeSetValuedHashMap copying all the mappings of the given map.
     *
     * @param map a <code>Map</code> to copy into this map
     */
    public TreeSetValuedHashMap(final Map<? extends K, ? extends V> map) {
        this(map.size());
        super.putAll(map);
    }

    // -----------------------------------------------------------------------
    @Override
    protected TreeSet<V> createCollection() {
        return new TreeSet<V>();
    }

    // -----------------------------------------------------------------------


    private void readObject(ObjectInputStream ois) throws IOException, ClassNotFoundException {
        ois.defaultReadObject();
        setMap(new HashMap<K, TreeSet<V>>());
        doReadObject(ois);
    }


Lines 17-73 Link Here

(-)src/test/java/org/apache/commons/collections4/list/MappedListTest.java (-38 / +114 lines)
17	package org.apache.commons.collections4.list;	17	package org.apache.commons.collections4.list;
18		18
19	import java.util.ArrayList;	19	import java.util.ArrayList;
		20	import java.util.Arrays;
		21	import java.util.HashSet;
20	import java.util.List;	22	import java.util.List;
21	import java.util.ListIterator;	23	import java.util.ListIterator;
		24	import java.util.Random;
		25	import java.util.Set;
22		26
		27	import org.apache.commons.collections4.BulkTest;
		28
23	import junit.framework.Test;	29	import junit.framework.Test;
24		30
25	import org.apache.commons.collections4.BulkTest;
26
27	/**	31	/**
28	* JUnit tests	32	* JUnit tests
29	*	33	*
30	* @since 3.1	34	* @since FIXME
31	* @version $Id$	35	* @version $Id$
32	*/	36	*/
33	public class TreeListTest<E> extends AbstractListTest<E> {	37	public class MappedListTest<E> extends AbstractListTest<E> {
34		38
35	public TreeListTest(final String name) {	39	public MappedListTest(final String name) {
36	super(name);	40	super(name);
37	}	41	}
		42
		43	public void testRunBenchmark() {
		44	main(new String[] {});
		45	}
38		46
39	// public static void main(String[] args) {	47	public static void main(String[] args) {
40	// junit.textui.TestRunner.run(suite());	48	final int[] initialSize = new int[]{10, 100, 1000, 10000, 100000};
41	// System.out.println(" add; toArray; iterator; insert; get; indexOf; remove");	49	final int[] count = new int[]{10, 100, 1000, 10000, 100000};
42	// System.out.print(" TreeList = ");	50
43	// benchmark(new TreeList());	51	//junit.textui.TestRunner.run(suite());
44	// System.out.print("\n ArrayList = ");	52	for (int sz : initialSize) {
45	// benchmark(new java.util.ArrayList());	53	for (int cnt : count) {
46	// System.out.print("\n LinkedList = ");	54	final long start = System.currentTimeMillis();
47	// benchmark(new java.util.LinkedList());	55	System.out.print("\n" + sz + ", " + cnt + ":");
48	// System.out.print("\n NodeCachingLinkedList = ");	56	System.out.print(" add; toArray; iterator; insert; get; indexOf; contains; remove");
49	// benchmark(new NodeCachingLinkedList());	57	System.out.print("\n ArrayList = ");
50	// }	58	benchmark(new java.util.ArrayList(), sz, cnt);
		59	System.out.print("\n LinkedList = ");
		60	benchmark(new java.util.LinkedList(), sz, cnt);
		61	System.out.print("\n NodeCachingLinkedList = ");
		62	benchmark(new NodeCachingLinkedList(), sz, cnt);
		63	System.out.print("\n TreeList = ");
		64	benchmark(new TreeList(), sz, cnt);
		65	System.out.print("\n MappedList = ");
		66	benchmark(new MappedList(), sz, cnt);
		67	final long elapsed = (System.currentTimeMillis() - start) / 1000;
		68	final long minutes = elapsed / 60;
		69	final long seconds = elapsed % 60;
		70	System.out.println("\n" + minutes + "m" + seconds + "s");
		71	}
		72	}
		73	}
51		74
52	public static Test suite() {	75	public static Test suite() {
53	return BulkTest.makeSuite(TreeListTest.class);	76	return BulkTest.makeSuite(MappedListTest.class);
54	}	77	}
55		78
56	public static void benchmark(final List<? super Integer> l) {	79	public static void benchmark(final List<? super Integer> l) {
		80	final int initialSize = 100000;
		81	final int count = 400;
		82	benchmark(l, initialSize, count);
		83	}
		84
		85	public static void benchmark(final List<? super Integer> l, final int initialSize, final int count) {
		86
		87	final Random rand = new Random(0L);
		88
		89	for (int i = 0; i < initialSize; i++) {
		90	l.add(Integer.valueOf(i));
		91	}
		92
		93	// add
57	long start = System.currentTimeMillis();	94	long start = System.currentTimeMillis();
58	for (int i = 0; i < 100000; i++) {	95	for (int i = 0; i < count; i++) {
59	l.add(Integer.valueOf(i));	96	l.add(Integer.valueOf(i));
60	}	97	}
61	System.out.print(System.currentTimeMillis() - start + ";");	98	System.out.print(System.currentTimeMillis() - start + ";");
62		99
		100	// toArray
63	start = System.currentTimeMillis();	101	start = System.currentTimeMillis();
64	for (int i = 0; i < 200; i++) {	102	for (int i = 0; i < count; i++) {
65	l.toArray();	103	l.toArray();
66	}	104	}
67	System.out.print(System.currentTimeMillis() - start + ";");	105	System.out.print(System.currentTimeMillis() - start + ";");
68		106
		107	// iterator
69	start = System.currentTimeMillis();	108	start = System.currentTimeMillis();
70	for (int i = 0; i < 100; i++) {	109	for (int i = 0; i < count; i++) {
71	final java.util.Iterator<? super Integer> it = l.iterator();	110	final java.util.Iterator<? super Integer> it = l.iterator();
72	while (it.hasNext()) {	111	while (it.hasNext()) {
73	it.next();	112	it.next();
Lines 75-104 Link Here
75	}	114	}
76	System.out.print(System.currentTimeMillis() - start + ";");	115	System.out.print(System.currentTimeMillis() - start + ";");
77		116
		117	// insert
78	start = System.currentTimeMillis();	118	start = System.currentTimeMillis();
79	for (int i = 0; i < 10000; i++) {	119	for (int i = 0; i < count; i++) {
80	final int j = (int) (Math.random() * 100000);	120	final int j = rand.nextInt(initialSize);
81	l.add(j, Integer.valueOf(-j));	121	l.add(j, Integer.valueOf(-j));
82	}	122	}
83	System.out.print(System.currentTimeMillis() - start + ";");	123	System.out.print(System.currentTimeMillis() - start + ";");
84		124
		125	// get
85	start = System.currentTimeMillis();	126	start = System.currentTimeMillis();
86	for (int i = 0; i < 50000; i++) {	127	for (int i = 0; i < count; i++) {
87	final int j = (int) (Math.random() * 110000);	128	final int j = rand.nextInt(initialSize);
88	l.get(j);	129	l.get(j);
89	}	130	}
90	System.out.print(System.currentTimeMillis() - start + ";");	131	System.out.print(System.currentTimeMillis() - start + ";");
91		132
		133	// indexOf
92	start = System.currentTimeMillis();	134	start = System.currentTimeMillis();
93	for (int i = 0; i < 200; i++) {	135	for (int i = 0; i < count; i++) {
94	final int j = (int) (Math.random() * 100000);	136	final int j = rand.nextInt(initialSize);
95	l.indexOf(Integer.valueOf(j));	137	l.indexOf(Integer.valueOf(j));
96	}	138	}
97	System.out.print(System.currentTimeMillis() - start + ";");	139	System.out.print(System.currentTimeMillis() - start + ";");
		140
		141	// contains
		142	start = System.currentTimeMillis();
		143	for (int i = 0; i < count; i++) {
		144	final int j = rand.nextInt(initialSize);
		145	l.contains(Integer.valueOf(j));
		146	}
		147	System.out.print(System.currentTimeMillis() - start + ";");
98		148
		149	// remove
99	start = System.currentTimeMillis();	150	start = System.currentTimeMillis();
100	for (int i = 0; i < 10000; i++) {	151	for (int i = 0; i < count; i++) {
101	final int j = (int) (Math.random() * 100000);	152	final int j = rand.nextInt(initialSize);
102	l.remove(j);	153	l.remove(j);
103	}	154	}
104	System.out.print(System.currentTimeMillis() - start + ";");	155	System.out.print(System.currentTimeMillis() - start + ";");
Lines 106-113 Link Here
106		157
107	//-----------------------------------------------------------------------	158	//-----------------------------------------------------------------------
108	@Override	159	@Override
109	public TreeList<E> makeObject() {	160	public MappedList<E> makeObject() {
110	return new TreeList<E>();	161	return new MappedList<E>();
111	}	162	}
112		163
113	//-----------------------------------------------------------------------	164	//-----------------------------------------------------------------------
Lines 220-226 Link Here
220	public void testBug35258() {	271	public void testBug35258() {
221	final Object objectToRemove = Integer.valueOf(3);	272	final Object objectToRemove = Integer.valueOf(3);
222		273
223	final List<Integer> treelist = new TreeList<Integer>();	274	final List<Integer> treelist = new MappedList<Integer>();
224	treelist.add(Integer.valueOf(0));	275	treelist.add(Integer.valueOf(0));
225	treelist.add(Integer.valueOf(1));	276	treelist.add(Integer.valueOf(1));
226	treelist.add(Integer.valueOf(2));	277	treelist.add(Integer.valueOf(2));
Lines 248-254 Link Here
248	}	299	}
249		300
250	public void testBugCollections447() {	301	public void testBugCollections447() {
251	final List<String> treeList = new TreeList<String>();	302	final List<String> treeList = new MappedList<String>();
252	treeList.add("A");	303	treeList.add("A");
253	treeList.add("B");	304	treeList.add("B");
254	treeList.add("C");	305	treeList.add("C");
Lines 271-277 Link Here
271	public void testIterationOrder() {	322	public void testIterationOrder() {
272	// COLLECTIONS-433:	323	// COLLECTIONS-433:
273	// ensure that the iteration order of elements is correct	324	// ensure that the iteration order of elements is correct
274	// when initializing the TreeList with another collection	325	// when initializing the MappedList with another collection
275		326
276	for (int size = 1; size < 1000; size++) {	327	for (int size = 1; size < 1000; size++) {
277	List<Integer> other = new ArrayList<Integer>(size);	328	List<Integer> other = new ArrayList<Integer>(size);
Lines 278-284 Link Here
278	for (int i = 0; i < size; i++) {	329	for (int i = 0; i < size; i++) {
279	other.add(i);	330	other.add(i);
280	}	331	}
281	TreeList<Integer> l = new TreeList<Integer>(other);	332	MappedList<Integer> l = new MappedList<Integer>(other);
282	ListIterator<Integer> it = l.listIterator();	333	ListIterator<Integer> it = l.listIterator();
283	int i = 0;	334	int i = 0;
284	while (it.hasNext()) {	335	while (it.hasNext()) {
Lines 297-303 Link Here
297	public void testIterationOrderAfterAddAll() {	348	public void testIterationOrderAfterAddAll() {
298	// COLLECTIONS-433:	349	// COLLECTIONS-433:
299	// ensure that the iteration order of elements is correct	350	// ensure that the iteration order of elements is correct
300	// when calling addAll on the TreeList	351	// when calling addAll on the MappedList
301		352
302	// to simulate different cases in addAll, do different runs where	353	// to simulate different cases in addAll, do different runs where
303	// the number of elements already in the list and being added by addAll differ	354	// the number of elements already in the list and being added by addAll differ
Lines 308-314 Link Here
308	for (int j = i; j < size; j++) {	359	for (int j = i; j < size; j++) {
309	other.add(j);	360	other.add(j);
310	}	361	}
311	TreeList<Integer> l = new TreeList<Integer>();	362	MappedList<Integer> l = new MappedList<Integer>();
312	for (int j = 0; j < i; j++) {	363	for (int j = 0; j < i; j++) {
313	l.add(j);	364	l.add(j);
314	}	365	}
Lines 328-332 Link Here
328	}	379	}
329	}	380	}
330	}	381	}
		382
		383	private static <E> Set<E> makeSet(E... values) {
		384	Set<E> set = new HashSet<E>();
		385	for (E value : values) {
		386	set.add(value);
		387	}
		388	return set;
		389	}
		390
		391	@SuppressWarnings("unchecked")
		392	public void testGetIndices() {
		393	final MappedList<E> l = makeObject();
		394	l.add((E) "A"); //0
		395	l.add((E) "B"); //1
		396	l.add((E) "C"); //2
		397	l.add((E) "A"); //3
		398	l.add((E) "B"); //4
		399	l.add((E) "A"); //5
		400	l.add((E) "A"); //6
		401
		402	assertEquals(makeSet(0, 3, 5, 6), l.getIndices("A"));
		403	assertEquals(makeSet(1, 4), l.getIndices("B"));
		404	assertEquals(makeSet(2), l.getIndices("C"));
		405	assertEquals(makeSet(), l.getIndices("D"));
		406	}
331		407
332	}	408	}




import org.apache.commons.collections4.SetValuedMap;

/**
 * Test TreeSetValuedHashMap
 *
 * @since FIXME
 * @version $Id$
 */
public class TreeSetValuedHashMapTest<K, V> extends AbstractMultiValuedMapTest<K, V> {

    public TreeSetValuedHashMapTest(String testName) {
        super(testName);
    }

    public static Test suite() {
        return BulkTest.makeSuite(TreeSetValuedHashMapTest.class);
    }

    // -----------------------------------------------------------------------
    @Override
    public SetValuedMap<K, V> makeObject() {
        return new TreeSetValuedHashMap<K, V>();
    }

    @Override
    public MultiValuedMap<K, V> makeConfirmedMap() {
        return new TreeSetValuedHashMap<K, V>();
    }

    // -----------------------------------------------------------------------

        assertNotSame(map1.hashCode(), map2.hashCode());
    }

    
    /*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");
    }*/

}

Return to bug 58740

Lines 16-51 Link Here

(-)src/main/java/org/apache/commons/collections4/NavigableSetValuedMap.java (-12 / +13 lines)
16	*/	16	*/
17	package org.apache.commons.collections4;	17	package org.apache.commons.collections4;
18		18
19	import java.util.Set;	19	import java.util.NavigableSet;
20		20
21	/**	21	/**
22	* Defines a map that holds a set of values against each key.	22	* Defines a map that holds a set of values against each key.
23	* <p>	23	* <p>
24	* A {@code SetValuedMap} is a Map with slightly different semantics:	24	* A {@code NavigableSetValuedMap} is a Map with slightly different semantics:
25	* <ul>	25	* <ul>
26	* <li>Putting a value into the map will add the value to a {@link Set} at that key.</li>	26	* <li>Putting a value into the map will add the value to a {@link NavigableSet} at that key.</li>
27	* <li>Getting a value will return a {@link Set}, holding all the values put to that key.</li>	27	* <li>Getting a value will return a {@link NavigableSet}, holding all the values put to that key.</li>
28	* </ul>	28	* </ul>
		29	* This map provides a sorted and navigable set interface to the values corresponding to each key.
29	*	30	*
30	* @since 4.1	31	* @since FIXME
31	* @version $Id$	32	* @version $Id$
32	*/	33	*/
33	public interface SetValuedMap<K, V> extends MultiValuedMap<K, V> {	34	public interface NavigableSetValuedMap<K, V> extends SetValuedMap<K, V> {
34		35
35	/**	36	/**
36	* Gets the set of values associated with the specified key.	37	* Gets the set of values associated with the specified key.
37	* <p>	38	* <p>
38	* Implementations typically return an empty {@code Set} if no values	39	* Implementations typically return an empty {@code NavigableSet} if no values
39	* have been mapped to the key.	40	* have been mapped to the key.
40	* <p>	41	* <p>
41	*	42	*
42	* @param key the key to retrieve	43	* @param key the key to retrieve
43	* @return the {@code Set} of values, implementations should return an	44	* @return the {@code NavigableSet} of values, implementations should return an
44	* empty {@code Set} for no mapping	45	* empty {@code NavigableSet} for no mapping rather than {@code null}.
45	* @throws NullPointerException if the key is null and null keys are invalid	46	* @throws NullPointerException if the key is null and null keys are invalid
46	*/	47	*/
47	@Override	48	@Override
48	Set<V> get(K key);	49	NavigableSet<V> get(K key);
49		50
50	/**	51	/**
51	* Removes all values associated with the specified key.	52	* Removes all values associated with the specified key.
Lines 55-65 Link Here
55	* specified key, an empty, unmodifiable set will be returned.	56	* specified key, an empty, unmodifiable set will be returned.
56	*	57	*
57	* @param key the key to remove values from	58	* @param key the key to remove values from
58	* @return the {@code Set} of values removed, implementations should	59	* @return the {@code NavigableSet} of values removed, implementations should
59	* return null for no mapping found, but may return an empty collection	60	* return null for no mapping found, but may return an empty collection
60	* @throws UnsupportedOperationException if the map is unmodifiable	61	* @throws UnsupportedOperationException if the map is unmodifiable
61	* @throws NullPointerException if the key is null and null keys are invalid	62	* @throws NullPointerException if the key is null and null keys are invalid
62	*/	63	*/
63	@Override	64	@Override
64	Set<V> remove(Object key);	65	NavigableSet<V> remove(Object key);
65	}	66	}

Lines 73-80 Link Here

(-)src/main/java/org/apache/commons/collections4/SetUtils.java (+33 lines)
73	public static <E> SortedSet<E> emptySortedSet() {	73	public static <E> SortedSet<E> emptySortedSet() {
74	return EMPTY_SORTED_SET;	74	return EMPTY_SORTED_SET;
75	}	75	}
		76
		77	/**
		78	* An empty unmodifiable navigable set.
		79	* This is not provided in the JDK.
		80	* @since FIXME
		81	*/
		82	@SuppressWarnings("rawtypes")
		83	public static final NavigableSet EMPTY_NAVIGABLE_SET =
		84	UnmodifiableNavigableSet.unmodifiableNavigableSet(new TreeSet<Object>());
76		85
77	/**	86	/**
		87	* Get a typed empty unmodifiable navigable set.
		88	* @param <E> the element type
		89	* @return an empty sorted Set
		90	* @since FIXME
		91	*/
		92	@SuppressWarnings("unchecked") // empty set is OK for any type
		93	public static <E> NavigableSet<E> emptyNavigableSet() {
		94	return EMPTY_NAVIGABLE_SET;
		95	}
		96
		97	/**
78	* <code>SetUtils</code> should not normally be instantiated.	98	* <code>SetUtils</code> should not normally be instantiated.
79	*/	99	*/
80	private SetUtils() {}	100	private SetUtils() {}
Lines 92-97 Link Here
92	public static <T> Set<T> emptyIfNull(final Set<T> set) {	112	public static <T> Set<T> emptyIfNull(final Set<T> set) {
93	return set == null ? Collections.<T>emptySet() : set;	113	return set == null ? Collections.<T>emptySet() : set;
94	}	114	}
		115
		116	/**
		117	* Returns an immutable empty set if the argument is <code>null</code>,
		118	* or the argument itself otherwise.
		119	*
		120	* @param <T> the element type
		121	* @param set the set, possibly <code>null</code>
		122	* @return an empty set if the argument is <code>null</code>
		123	* @since FIXME
		124	*/
		125	public static <T> NavigableSet<T> emptyIfNull(final NavigableSet<T> set) {
		126	return set == null ? SetUtils.<T>emptyNavigableSet() : set;
		127	}
95		128
96	/**	129	/**
97	* Tests two sets for equality as per the <code>equals()</code> contract	130	* Tests two sets for equality as per the <code>equals()</code> contract

Line 0 Link Here

(-)src/main/java/org/apache/commons/collections4/list/MappedList.java (+320 lines)
		1	/*
		2	* Licensed to the Apache Software Foundation (ASF) under one or more
		3	* contributor license agreements. See the NOTICE file distributed with
		4	* this work for additional information regarding copyright ownership.
		5	* The ASF licenses this file to You under the Apache License, Version 2.0
		6	* (the "License"); you may not use this file except in compliance with
		7	* the License. You may obtain a copy of the License at
		8	*
		9	* http://www.apache.org/licenses/LICENSE-2.0
		10	*
		11	* Unless required by applicable law or agreed to in writing, software
		12	* distributed under the License is distributed on an "AS IS" BASIS,
		13	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
		14	* See the License for the specific language governing permissions and
		15	* limitations under the License.
		16	*/
		17
		18	package org.apache.commons.collections4.list;
		19
		20	import java.util.AbstractList;
		21	import java.util.ArrayList;
		22	import java.util.Collection;
		23	import java.util.HashSet;
		24	import java.util.List;
		25	import java.util.NavigableSet;
		26	import java.util.Set;
		27	import java.util.SortedSet;
		28	import java.util.TreeSet;
		29
		30	import org.apache.commons.collections4.NavigableSetValuedMap;
		31	import org.apache.commons.collections4.SetUtils;
		32	import org.apache.commons.collections4.multimap.HashSetValuedHashMap;
		33	import org.apache.commons.collections4.multimap.TreeSetValuedHashMap;
		34	import org.apache.commons.collections4.set.UnmodifiableNavigableSet;
		35
		36	/**
		37	* A List with fast {@link #indexOf(Object)} and {@link #contains(Object)} methods.
		38	* A {@link HashSetValuedHashMap} is used to provide faster entry lookup at the
		39	* expense of maintaining a second data structure (slight RAM and speed cost).
		40	*
		41	* @param <E>
		42	* @since FIXME
		43	*/
		44	public class MappedList<E> extends AbstractList<E> {
		45
		46	private final List<E> list;
		47	private final NavigableSetValuedMap<E, Integer> invertedMap;
		48
		49	public MappedList() {
		50	super();
		51	list = new ArrayList<E>();
		52	invertedMap = new TreeSetValuedHashMap<E, Integer>();
		53	}
		54
		55	public MappedList(final Collection<? extends E> coll) {
		56	this();
		57	addAll(coll);
		58	}
		59
		60	@Override
		61	public E get(final int index) {
		62	return list.get(index);
		63	}
		64
65	@Override
66	public int size() {
67	return list.size();
68	}
69
70	@Override
71	public boolean isEmpty() {
72	return list.isEmpty();
73	}
74
75	@Override
76	public boolean contains(final Object o) {
77	/* try {
78	Collection<Integer> values = invertedMap.get((E) o);
79	return values != null && !values.isEmpty();
80	} catch (final ClassCastException e) {
81	return false;
82	}*/
83	return invertedMap.containsKey(o);
84	}
85
86	/*@Override
87	public Iterator<E> iterator() {
88	// TODO Auto-generated method stub
89	return null;
90	}*/
91
92	/*@Override
93	public Object[] toArray() {
94	// TODO Auto-generated method stub
95	return null;
96	}*/
97
98	/*@Override
99	public <T> T[] toArray(T[] a) {
100	// TODO Auto-generated method stub
101	return null;
102	}*/
103
104	@Override
105	public E set(final int index, final E element) {
106	checkRange(index);
107	final E previous = list.set(index, element);
108	invertedMap.removeMapping(previous, index);
109	invertedMap.put(element, index);
110	return previous;
111	}
112
113	@Override
114	public boolean add(final E e) {
115	final boolean modified = list.add(e);
116	if (modified) {
117	invertedMap.put(e, list.size() - 1);
118	}
119	return modified;
120	}
121
122	@Override
123	public void add(final int index, final E element) {
124	checkRange(index);
125	final boolean rebuild = isFasterToRebuildThanShift(index);
126	if (! rebuild) {
127	incrementMapIndices(index);
128	invertedMap.put(element, index);
129	}
130	list.add(index, element);
131	if (rebuild) {
132	rebuildMap();
133	}
134	}
135
136	@Override
137	public boolean remove(final Object o) {
138	if (!contains(o)) return false;
139	@SuppressWarnings("unchecked")
140	NavigableSet<Integer> indices = invertedMap.get((E) o);
141	final int indexToRemove = indices.first();
142	remove(indexToRemove);
143	return true;
144	}
145	@Override
146	public E remove(final int index) {
147	checkRange(index);
148	final E removed = list.get(index);
149	final boolean rebuild = isFasterToRebuildThanShift(index);
150	if (! rebuild) {
151	invertedMap.removeMapping(removed, index);
152	decrementMapIndices(index);
153	}
154	list.remove(index);
155	if (rebuild) {
156	rebuildMap();
157	}
158	return removed;
159	}
160
161	/*@Override
162	public boolean containsAll(Collection<?> c) {
163	// TODO Auto-generated method stub
164	return false;
165	}*/
166
167	/*@Override
168	public boolean addAll(Collection<? extends E> c) {
169	// TODO Auto-generated method stub
170	return false;
171	}*/
172
173	/*@Override
174	public boolean addAll(int index, Collection<? extends E> c) {
175	// TODO Auto-generated method stub
176	return false;
177	}*/
178
179	/*@Override
180	public boolean removeAll(Collection<?> c) {
181	// TODO Auto-generated method stub
182	return false;
183	}*/
184
185	/*@Override
186	public boolean retainAll(Collection<?> c) {
187	// TODO Auto-generated method stub
188	return false;
189	}*/
190
191	@Override
192	public void clear() {
193	invertedMap.clear();
194	list.clear();
195	}
196
197
198	@SuppressWarnings("unchecked")
199	@Override
200	public int indexOf(final Object o) {
201	if (! contains(o)) return -1;
202	return invertedMap.get((E) o).first();
203	//final NavigableSet<Integer> indices = invertedMap.get((E) o);
204	//return (indices == null \|\| indices.isEmpty()) ? -1 : indices.first();
205	}
206
207	@SuppressWarnings("unchecked")
208	@Override
209	public int lastIndexOf(final Object o) {
210	//if (! contains(o)) return -1;
211	//return invertedMap.get((E) o).last();
212	final NavigableSet<Integer> indices = invertedMap.get((E) o);
213	return (indices == null \|\| indices.isEmpty()) ? -1 : indices.last();
214	}
215
216
217	@SuppressWarnings("unchecked")
218	public NavigableSet<Integer> getIndices(final Object o) {
219	if (! contains(o))
220	return SetUtils.EMPTY_NAVIGABLE_SET;
221	final NavigableSet<Integer> set = invertedMap.get((E) o);
222	return UnmodifiableNavigableSet.unmodifiableNavigableSet(set);
223	}
224
225	/*@Override
226	public ListIterator<E> listIterator() {
227	// TODO Auto-generated method stub
228	return null;
229	}*/
230
231	/*@Override
232	public ListIterator<E> listIterator(int index) {
233	// TODO Auto-generated method stub
234	return null;
235	}*/
236
237	/*@Override
238	public List<E> subList(int fromIndex, int toIndex) {
239	// TODO Auto-generated method stub
240	return null;
241	}*/
242
243	private void checkRange(final int index) {
244	if (index < 0 \|\| index > size())
245	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
246	}
247
248	private String outOfBoundsMsg(final int index) {
249	return "Index: "+index+", Size: "+size();
250	}
251
252	private void incrementMapIndices(final int startIndex) {
253	shiftMapIndices(startIndex, 1);
254	}
255	private void decrementMapIndices(final int startIndex) {
256	shiftMapIndices(startIndex, -1);
257	}
258	/**
259	* this must be called BEFORE the list is modified.
260	* @param startIndex
261	* @param offset
262	*/
263	private void shiftMapIndices(final int startIndex, final int offset) {
264	final int stopIndex = list.size() - 1;
265	// if an element appears multiple times in the list, all indices in the
266	// inverted map must be shifted simultaneously. To avoid shifting the
267	// same index multiple times, the seen set is used
268	final Set<E> seen = new HashSet<E>();
269	//for (int idx = startIndex; idx < stopIndex; idx++) {
270	// final E element = list.get(idx);
271	for (final E element : list.subList(startIndex, stopIndex+1)) {
272	if (seen.add(element)) { // Set.add(E) returns true if set does not contain element
273	// Depending on sign of offset, the indices either need to be
274	// incremented in descending order or decremented in ascending order
275	// This avoids index collision. (Consider offset=1 with two adjacent equal elements.)
276	// See descendingSet().
277	/*final SortedSet<Integer> indices = invertedMap.get(element).tailSet(startIndex);
278	for (final int i : indices) {
279	invertedMap.removeMapping(element, i);
280	invertedMap.put(element, i + offset);
281	}*/
282
283	// shift all of the indices >= startIndex for this element
284	final NavigableSet<Integer> indices = invertedMap.get(element);
285	if (indices == null \|\| indices.isEmpty())
286	continue;
287
288	// Re-adding the indices is the slowest part. This would be faster
289	// if indices supported replacing elements in the set, avoiding a bunch of tree re-linking.
290	final Collection<Integer> upper;
291	//upper = new TreeSet<Integer>(indices.tailSet(startIndex));
292	//upper = new ArrayList<Integer>(indices.tailSet(startIndex));
293	upper = new ArrayList<Integer>(indices.tailSet(startIndex));
294	indices.removeAll(upper);
295	for (final Integer u : upper) {
296	indices.add(u + offset);
297	}
298	}
299	}
300	}
301
302	private void rebuildMap() {
303	invertedMap.clear();
304	int i = 0;
305	for (E e : list) {
306	invertedMap.put(e, i);
307	i++;
308	}
309	}
310
311	private boolean isFasterToRebuildThanShift(final int index) {
312	//faster to modify the map. otherwise faster to rebuild the map from scratch
313	//final boolean fasterToRebuildThanShift = index < (list.size() * 3 / 4);
314	final boolean fasterToRebuildThanShift = true;
315	return fasterToRebuildThanShift;
316	}
317
318	}
319	native
320	Author Id Revision HeadURL

Lines 21-49 Link Here

(-)src/main/java/org/apache/commons/collections4/multimap/TreeSetValuedHashMap.java (-43 / +24 lines)
21	import java.io.ObjectOutputStream;	21	import java.io.ObjectOutputStream;
22	import java.io.Serializable;	22	import java.io.Serializable;
23	import java.util.HashMap;	23	import java.util.HashMap;
24	import java.util.HashSet;
25	import java.util.Map;	24	import java.util.Map;
		25	import java.util.TreeSet;
26		26
27	import org.apache.commons.collections4.MultiValuedMap;	27	import org.apache.commons.collections4.MultiValuedMap;
28		28
29	/**	29	/**
30	* Implements a {@code SetValuedMap}, using a {@link HashMap} to provide data	30	* Implements a {@code SetValuedMap}, using a {@link HashMap} to provide data
31	* storage and {@link HashSet}s as value collections. This is the standard	31	* storage and {@link TreeSet}s as value collections. This improves on the
32	* implementation of a SetValuedMap.	32	* standard implementation of a SetValuedMap by providing total ordering on the
		33	* value collections. This is the standard implementation of a
		34	* SortedSetValuedMap and NavigableSetValuedMap.
33	* <p>	35	* <p>
34	* <strong>Note that HashSetValuedHashMap is not synchronized and is not	36	* <strong>Note that TreeSetValuedHashMap is not synchronized and is not
35	* thread-safe.</strong> If you wish to use this map from multiple threads	37	* thread-safe.</strong> If you wish to use this map from multiple threads
36	* concurrently, you must use appropriate synchronization. This class may throw	38	* concurrently, you must use appropriate synchronization. This class may throw
37	* exceptions when accessed by concurrent threads without synchronization.	39	* exceptions when accessed by concurrent threads without synchronization.
38	*	40	*
39	* @since 4.1	41	* @since FIXME
40	* @version $Id$	42	* @version $Id$
41	*/	43	*/
42	public class HashSetValuedHashMap<K, V> extends AbstractSetValuedMap<K, V>	44	public class TreeSetValuedHashMap<K, V> extends AbstractNavigableSetValuedMap<K, V>
43	implements Serializable {	45	implements Serializable {
44		46
45	/** Serialization Version */	47	/** Serialization Version */
46	private static final long serialVersionUID = 20151118L;	48	private static final long serialVersionUID = 2675614644971970576L;
47		49
48	/**	50	/**
49	* The initial map capacity used when none specified in constructor.	51	* The initial map capacity used when none specified in constructor.
Lines 51-119 Link Here
51	private static final int DEFAULT_INITIAL_MAP_CAPACITY = 16;	53	private static final int DEFAULT_INITIAL_MAP_CAPACITY = 16;
52		54
53	/**	55	/**
54	* The initial set capacity when using none specified in constructor.	56	* Creates an empty TreeSetValuedHashMap with the default initial
55	*/
56	private static final int DEFAULT_INITIAL_SET_CAPACITY = 3;
57
58	/**
59	* The initial list capacity when creating a new value collection.
60	*/
61	private final int initialSetCapacity;
62
63	/**
64	* Creates an empty HashSetValuedHashMap with the default initial
65	* map capacity (16) and the default initial set capacity (3).	57	* map capacity (16) and the default initial set capacity (3).
66	*/	58	*/
67	public HashSetValuedHashMap() {	59	public TreeSetValuedHashMap() {
68	this(DEFAULT_INITIAL_MAP_CAPACITY, DEFAULT_INITIAL_SET_CAPACITY);	60	this(DEFAULT_INITIAL_MAP_CAPACITY);
69	}	61	}
70		62
71	/**	63	/**
72	* Creates an empty HashSetValuedHashMap with the default initial	64	* Creates an empty TreeSetValuedHashMap with the specified initial
73	* map capacity (16) and the specified initial set capacity.
74	*
75	* @param initialSetCapacity the initial capacity used for value collections
76	*/
77	public HashSetValuedHashMap(int initialSetCapacity) {
78	this(DEFAULT_INITIAL_MAP_CAPACITY, initialSetCapacity);
79	}
80
81	/**
82	* Creates an empty HashSetValuedHashMap with the specified initial
83	* map and list capacities.	65	* map and list capacities.
84	*	66	*
85	* @param initialMapCapacity the initial hashmap capacity	67	* @param initialMapCapacity the initial hashmap capacity
86	* @param initialSetCapacity the initial capacity used for value collections	68	* @param initialSetCapacity the initial capacity used for value collections
87	*/	69	*/
88	public HashSetValuedHashMap(int initialMapCapacity, int initialSetCapacity) {	70	public TreeSetValuedHashMap(int initialMapCapacity) {
89	super(new HashMap<K, HashSet<V>>(initialMapCapacity));	71	super(new HashMap<K, TreeSet<V>>(initialMapCapacity));
90	this.initialSetCapacity = initialSetCapacity;
91	}	72	}
92		73
93	/**	74	/**
94	* Creates an HashSetValuedHashMap copying all the mappings of the given map.	75	* Creates an TreeSetValuedHashMap copying all the mappings of the given map.
95	*	76	*
96	* @param map a <code>MultiValuedMap</code> to copy into this map	77	* @param map a <code>MultiValuedMap</code> to copy into this map
97	*/	78	*/
98	public HashSetValuedHashMap(final MultiValuedMap<? extends K, ? extends V> map) {	79	public TreeSetValuedHashMap(final MultiValuedMap<? extends K, ? extends V> map) {
99	this(map.size(), DEFAULT_INITIAL_SET_CAPACITY);	80	this(map.size());
100	super.putAll(map);	81	super.putAll(map);
101	}	82	}
102		83
103	/**	84	/**
104	* Creates an HashSetValuedHashMap copying all the mappings of the given map.	85	* Creates an TreeSetValuedHashMap copying all the mappings of the given map.
105	*	86	*
106	* @param map a <code>Map</code> to copy into this map	87	* @param map a <code>Map</code> to copy into this map
107	*/	88	*/
108	public HashSetValuedHashMap(final Map<? extends K, ? extends V> map) {	89	public TreeSetValuedHashMap(final Map<? extends K, ? extends V> map) {
109	this(map.size(), DEFAULT_INITIAL_SET_CAPACITY);	90	this(map.size());
110	super.putAll(map);	91	super.putAll(map);
111	}	92	}
112		93
113	// -----------------------------------------------------------------------	94	// -----------------------------------------------------------------------
114	@Override	95	@Override
115	protected HashSet<V> createCollection() {	96	protected TreeSet<V> createCollection() {
116	return new HashSet<V>(initialSetCapacity);	97	return new TreeSet<V>();
117	}	98	}
118		99
119	// -----------------------------------------------------------------------	100	// -----------------------------------------------------------------------
Lines 124-130 Link Here
124		105
125	private void readObject(ObjectInputStream ois) throws IOException, ClassNotFoundException {	106	private void readObject(ObjectInputStream ois) throws IOException, ClassNotFoundException {
126	ois.defaultReadObject();	107	ois.defaultReadObject();
127	setMap(new HashMap<K, HashSet<V>>());	108	setMap(new HashMap<K, TreeSet<V>>());
128	doReadObject(ois);	109	doReadObject(ois);
129	}	110	}
130		111