Attachment #34241 for bug #58740

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





import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;

import org.apache.commons.collections4.ListUtils;


/**
 * Decorates a <code>List</code> to ensure that no duplicates are present much
 * like a <code>Map</code>.
 * <p>
 * The <code>List</code> interface makes certain assumptions/requirements. This
 * implementation breaks these in certain ways, but this is merely the result of
 * rejecting duplicates. Each violation is explained in the method, but it
 * should not affect you. Bear in mind that Maps require immutable objects to
 * function correctly.
 * <p>
 * The {@link org.apache.commons.collections4.set.ListOrderedMap ListOrderedMap}
 * class provides an alternative approach, by wrapping an existing Map and
 * retaining insertion order in the iterator.
 * <p>
 * This class is Serializable from Commons Collections 3.1.

 * @since 3.0
 * @version $Id$
 */
public class MapUniqueList<E> extends AbstractSerializableListDecorator<E> {

    /** Serialization version. */
    private static final long serialVersionUID = 5539814519665417789L;

    /** Internal Map to maintain uniqueness. */
    private final Map<E, Integer> map;

    /**
     * Factory method to create a MapList using the supplied list to retain order.
     * <p>
     * If the list contains duplicates, these are removed (first indexed one
     * kept). A <code>HashMap</code> is used for the set behaviour. The map
     * also gives better performance for indexOf, contains(E), and get(E).
     *
     * @param <E>  the element type
     * @param list  the list to decorate, must not be null
     * @return a new {@link MapUniqueList}
     * @throws NullPointerException if list is null
     * @since FIXME
     */
    public static <E> MapUniqueList<E> mapUniqueList(final List<E> list) {
        if (list == null) {
            throw new NullPointerException("List must not be null");
        }
        final Map<E, Integer> map = new HashMap<E, Integer>();
        if (list.isEmpty()) {
            return new MapUniqueList<E>(list, map);
        }
        final List<E> temp = new ArrayList<E>(list);
        list.clear();
        final MapUniqueList<E> maplist = new MapUniqueList<E>(list, map);
        maplist.addAll(temp);
        return maplist;
    }

    // -----------------------------------------------------------------------
    /**
     * Constructor that wraps (not copies) the List and specifies the map to use.
     * <p>
     * The map and list must both be correctly initialised to the same elements.
     *
     * @param map  the map to decorate, must not be null
     * @param list  the list to decorate, must not be null
     * @throws NullPointerException if map or list is null
     */
    protected MapUniqueList(final List<E> list, final Map<E, Integer> map) {
        super(list);
        if (map == null) {
            throw new NullPointerException("Map must not be null");
        }
        this.map = map;
    }

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

     * @return an unmodifiable set view
     */
    public Set<E> asSet() {
        return UnmodifiableSet.unmodifiableSet(map.keySet());
    }

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

     * <p>
     * <i>(Violation)</i> The <code>List</code> interface requires that this
     * method returns <code>true</code> always. However this class may return
     * <code>false</code> because of the uniqueness criteria.
     *
     * @param object  the object to add
     * @return true if object was added

    @Override
    public void add(final int index, final E object) {
        // adds element if it is not contained already
        if (map.containsKey(object) == false) {
            super.add(index, object);
            map.put(object, index);
        }
    }


     */
    @Override
    public boolean addAll(final Collection<? extends E> coll) {
        //return addAll(size(), coll);
        boolean changed = false;
        for (E e : coll) {
            changed |= add(e);
        }
        return changed;
    }

    /**

     */
    @Override
    public boolean addAll(final int index, final Collection<? extends E> coll) {
        /*final List<E> temp = new ArrayList<E>();
        for (final E e : coll) {
            if (map.add(e)) {
                temp.add(e);
            }
        }
        return super.addAll(index, temp);*/
        boolean changed = false;
        int i = index;
        for (E e : coll) {
            if (!map.containsKey(e)) {
                add(i, e);
                i++;
                changed = true;
            }
        }
        return changed;
    }

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

            super.remove(pos); // remove the duplicate by index
        }

        map.remove(removed); // remove the item deleted by the map
        map.put(object, index); // add the new item to the unique map

        return removed; // return the item deleted by the map
    }

    @Override
    public boolean remove(final Object object) {
        final boolean result = map.remove(object) != null;
        if (result) {
            super.remove(object);
        }

    @Override
    public E remove(final int index) {
        final E result = super.remove(index);
        map.remove(result);
        return result;
    }


     */
    @Override
    public boolean retainAll(final Collection<?> coll) {
        final Set<E> set = map.keySet();
        boolean result = set.retainAll(coll);
        if (result == false) {
            return false;

        if (set.size() == 0) {
            super.clear();
        } else {
            // use the map as parameter for the call to retainAll to improve performance
            super.retainAll(set);
        }
        return result;

    @Override
    public void clear() {
        super.clear();
        map.clear();
    }

    @Override
    public boolean contains(final Object object) {
        return map.containsKey(object);
    }

    @Override
    public boolean containsAll(final Collection<?> coll) {
        return map.keySet().containsAll(coll);
    }

    @Override
    public Iterator<E> iterator() {
        return new MapListIterator<E>(super.iterator(), map);
    }

    @Override
    public ListIterator<E> listIterator() {
        return new MapListListIterator<E>(super.listIterator(), map);
    }

    @Override
    public ListIterator<E> listIterator(final int index) {
        return new MapListListIterator<E>(super.listIterator(index), map);
    }

    /**

    @Override
    public List<E> subList(final int fromIndex, final int toIndex) {
        final List<E> superSubList = super.subList(fromIndex, toIndex);
        final Map<E, Integer> subMap = createMapBasedOnList(map, superSubList);
        return ListUtils.unmodifiableList(new MapUniqueList<E>(superSubList, subMap));
    }

    /**
     * Create a new {@link Map} with the same type as the provided {@code map}
     * and populate it with all elements of {@code list}.
     *
     * @param map  the {@link Map} to be used as return type, must not be null
     * @param list  the {@link List} to populate the {@link Map}
     * @return a new {@link Map} populated with all elements of the provided
     *   {@link List}
     */
    @SuppressWarnings("unchecked")
    protected Map<E, Integer> createMapBasedOnList(final Map<E, Integer> map, final List<E> list) {
        Map<E, Integer> subMap;
        if (map.getClass().equals(HashMap.class)) {
            subMap = new HashMap<E, Integer>(list.size());
        } else {
            try {
                subMap = map.getClass().newInstance();
            } catch (final InstantiationException ie) {
                subMap = new HashMap<E, Integer>();
            } catch (final IllegalAccessException iae) {
                subMap = new HashMap<E, Integer>();
            }
        }
        assert subMap.isEmpty();
        for (E e : list) {
            if (! subMap.containsKey(e)) {
                subMap.put(e, subMap.size());
            }
        }
        return subMap;
    }

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

    /**
     * Inner class iterator.
     */
    static class MapListIterator<E> extends AbstractIteratorDecorator<E> {

        private final Map<E, Integer> map;
        private E last = null;

        protected MapListIterator(final Iterator<E> it, final Map<E, Integer> map) {
            super(it);
            this.map = map;
        }

        @Override

        @Override
        public void remove() {
            super.remove();
            map.remove(last);
            last = null;
        }
    }

    /**
     * Inner class iterator.
     */
    static class MapListListIterator<E> extends
            AbstractListIteratorDecorator<E> {

        private final Map<E, Integer> map;
        private E last = null;

        protected MapListListIterator(final ListIterator<E> it, final Map<E, Integer> map) {
            super(it);
            this.map = map;
        }

        @Override

        @Override
        public void remove() {
            super.remove();
            map.remove(last);
            last = null;
        }

        @Override
        public void add(final E object) {
            if (map.containsKey(object) == false) {
                super.add(object);
                map.put(object, map.size());
            }
        }





import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;

/**
 * JUnit tests.
 *
 * @since FIXME
 * @version $Id$
 */
public class MapUniqueListTest<E> extends AbstractListTest<E> {

    public MapUniqueListTest(final String testName) {
        super(testName);
    }


    //-----------------------------------------------------------------------
    @Override
    public List<E> makeObject() {
        return new MapUniqueList<E>(new ArrayList<E>(), new HashMap<E, Integer>());
    }

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


    @Override
    public void testListIteratorAdd() {
        // override to cope with Map behaviour
        resetEmpty();
        final List<E> list1 = getCollection();
        final List<E> list2 = getConfirmed();


    @Override
    public void testCollectionAddAll() {
        // override for map behaviour
        resetEmpty();
        E[] elements = getFullElements();
        boolean r = getCollection().addAll(Arrays.asList(elements));

    }

    public void testIntCollectionAddAll() {
      // make a MapUniqueList with one element
      final List<Integer> alist = new ArrayList<Integer>();
      final Map<Integer, Integer> map = new HashMap<Integer, Integer>();
      final List<Integer> list = new MapUniqueList<Integer>(alist, map);
      final Integer existingElement = Integer.valueOf(1);
      list.add(existingElement);


    @Override
    @SuppressWarnings("unchecked")
    public void testListSetByIndex() {
        // override for map behaviour
        resetFull();
        final int size = getCollection().size();
        getCollection().set(0, (E) new Long(1000));


        getCollection().set(2, (E) new Long(1000));
        assertEquals(size - 1, getCollection().size());
        assertEquals(new Long(1000), getCollection().get(1));  // map into 2, but shifted down to 1
    }

    boolean extraVerify = true;

    public void testFactory() {
        final Integer[] array = new Integer[] { Integer.valueOf(1), Integer.valueOf(2), Integer.valueOf(1) };
        final ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(array));
        final MapUniqueList<Integer> lmap = MapUniqueList.mapUniqueList(list);

        assertEquals("Duplicate element was added.", 2, lmap.size());
        assertEquals(Integer.valueOf(1), lmap.get(0));
        assertEquals(Integer.valueOf(2), lmap.get(1));
        assertEquals(Integer.valueOf(1), list.get(0));
        assertEquals(Integer.valueOf(2), list.get(1));
    }


    @SuppressWarnings("unchecked")
    public void testAdd() {
        final MapUniqueList<E> lmap = new MapUniqueList<E>(new ArrayList<E>(), new HashMap<E, Integer>());

        // Duplicate element
        final E obj = (E) Integer.valueOf(1);
        lmap.add(obj);
        lmap.add(obj);
        assertEquals("Duplicate element was added.", 1, lmap.size());

        // Unique element
        lmap.add((E) Integer.valueOf(2));
        assertEquals("Unique element was not added.", 2, lmap.size());
    }

    @SuppressWarnings("unchecked")
    public void testAddAll() {
        final MapUniqueList<E> lmap = new MapUniqueList<E>(new ArrayList<E>(), new HashMap<E, Integer>());

        lmap.addAll(
            Arrays.asList((E[]) new Integer[] { Integer.valueOf(1), Integer.valueOf(1)}));

        assertEquals("Duplicate element was added.", 1, lmap.size());
    }

    @SuppressWarnings("unchecked")
    public void testMap() {
        final MapUniqueList<E> lmap = new MapUniqueList<E>(new ArrayList<E>(), new HashMap<E, Integer>());

        // Duplicate element
        final E obj1 = (E) Integer.valueOf(1);

        final E obj2 = (E) Integer.valueOf(2);
        final E obj3 = (E) Integer.valueOf(3);

        lmap.add(obj1);
        lmap.add(obj2);
        lmap.set(0, obj1);
        assertEquals(2, lmap.size());
        assertSame(obj1, lmap.get(0));
        assertSame(obj2, lmap.get(1));

        lmap.clear();
        lmap.add(obj1);
        lmap.add(obj2);
        lmap.set(0, obj2);
        assertEquals(1, lmap.size());
        assertSame(obj2, lmap.get(0));

        lmap.clear();
        lmap.add(obj1);
        lmap.add(obj2);
        lmap.set(0, obj3);
        assertEquals(2, lmap.size());
        assertSame(obj3, lmap.get(0));
        assertSame(obj2, lmap.get(1));

        lmap.clear();
        lmap.add(obj1);
        lmap.add(obj2);
        lmap.set(1, obj1);
        assertEquals(1, lmap.size());
        assertSame(obj1, lmap.get(0));
    }

    @SuppressWarnings("unchecked")
    public void testListIterator() {
        final MapUniqueList<E> lmap = new MapUniqueList<E>(new ArrayList<E>(), new HashMap<E, Integer>());

        final E obj1 = (E) Integer.valueOf(1);
        final E obj2 = (E) Integer.valueOf(2);
        lmap.add(obj1);
        lmap.add(obj2);

        // Attempts to add a duplicate object
        for (final ListIterator<E> it = lmap.listIterator(); it.hasNext();) {
            it.next();

            if (!it.hasNext()) {

            }
        }

        assertEquals("Duplicate element was added", 2, lmap.size());
    }

    @SuppressWarnings("unchecked")
    public void testUniqueListReInsert() {
        final List<E> l = MapUniqueList.mapUniqueList(new LinkedList<E>());
        l.add((E) new Object());
        l.add((E) new Object());



    @SuppressWarnings("unchecked")
    public void testUniqueListDoubleInsert() {
        final List<E> l = MapUniqueList.mapUniqueList(new LinkedList<E>());
        l.add((E) new Object());
        l.add((E) new Object());


    }

    @SuppressWarnings("unchecked")
    public void testMapDownwardsInList() {
        /*
         * Checks the following semantics
         * [a,b]
         * map(0,b): [b]->a
         * So UniqList contains [b] and a is returned
         */
        final ArrayList<E> l = new ArrayList<E>();
        final HashMap<E, Integer> m = new HashMap<E, Integer>();
        final MapUniqueList<E> ul = new MapUniqueList<E>(l, m);

        final E a = (E) new Object();
        final E b = (E) new Object();

        ul.add(b);
        assertEquals(a, l.get(0));
        assertEquals(b, l.get(1));
        assertTrue(m.containsKey(a));
        assertTrue(m.containsKey(b));

        assertEquals(a, ul.set(0, b));
        assertEquals(1, m.size());
        assertEquals(1, l.size());
        assertEquals(b, l.get(0));
        assertTrue(m.containsKey(b));
        assertFalse(m.containsKey(a));
    }

    @SuppressWarnings("unchecked")
    public void testMapInBiggerList() {
        /*
         * Checks the following semantics
         * [a,b,c]
         * map(0,b): [b,c]->a
         * So UniqList contains [b,c] and a is returned
         */
        final ArrayList<E> l = new ArrayList<E>();
        final HashMap<E, Integer> m = new HashMap<E, Integer>();
        final MapUniqueList<E> ul = new MapUniqueList<E>(l, m);

        final E a = (E) new Object();
        final E b = (E) new Object();

        assertEquals(a, l.get(0));
        assertEquals(b, l.get(1));
        assertEquals(c, l.get(2));
        assertTrue(m.containsKey(a));
        assertTrue(m.containsKey(b));
        assertTrue(m.containsKey(c));

        assertEquals(a, ul.set(0, b));
        assertEquals(2, m.size());
        assertEquals(2, l.size());
        assertEquals(b, l.get(0));
        assertEquals(c, l.get(1));
        assertFalse(m.containsKey(a));
        assertTrue(m.containsKey(b));
        assertTrue(m.containsKey(c));
    }

    @SuppressWarnings("unchecked")
    public void testMapUpwardsInList() {
        /*
         * Checks the following semantics
         * [a,b,c]
         * map(1,a): [a,c]->b
         * So UniqList contains [a,c] and b is returned
         */
        final ArrayList<E> l = new ArrayList<E>();
        final HashMap<E, Integer> s = new HashMap<E, Integer>();
        final MapUniqueList<E> ul = new MapUniqueList<E>(l, s);

        final E a = (E) new String("A");
        final E b = (E) new String("B");

        assertEquals(a, l.get(0));
        assertEquals(b, l.get(1));
        assertEquals(c, l.get(2));
        assertTrue(s.containsKey(a));
        assertTrue(s.containsKey(b));
        assertTrue(s.containsKey(c));

        assertEquals(b, ul.set(1, a));
        assertEquals(2, s.size());

        assertEquals(2, l.size());
        assertEquals(a, l.get(0));
        assertEquals(c, l.get(1));
        assertTrue(s.containsKey(a));
        assertFalse(s.containsKey(b));
        assertTrue(s.containsKey(c));
    }

    public void testCollections304() {
        final List<String> list = new LinkedList<String>();
        final MapUniqueList<String> decoratedList = MapUniqueList.mapUniqueList(list);
        final String s1 = "Apple";
        final String s2 = "Lemon";
        final String s3 = "Orange";

    @SuppressWarnings("unchecked")
    public void testCollections307() {
        List<E> list = new ArrayList<E>();
        List<E> uniqueList = MapUniqueList.mapUniqueList(list);

        final String hello = "Hello";
        final String world = "World";

        assertFalse(subList.contains("World")); // passes
        assertFalse(subUniqueList.contains("World")); // fails

        // repeat the test with a different class than HashMap;
        // which means subclassing MapUniqueList below
        list = new ArrayList<E>();
        uniqueList = new MapUniqueList307(list, new java.util.TreeMap<E, Integer>());

        uniqueList.add((E) hello);
        uniqueList.add((E) world);

    @SuppressWarnings("unchecked")
    public void testRetainAll() {
        final List<E> list = new ArrayList<E>(10);
        final MapUniqueList<E> uniqueList = MapUniqueList.mapUniqueList(list);
        for (int i = 0; i < 10; ++i) {
            uniqueList.add((E)Integer.valueOf(i));
        }

        for (int i = 0; i < 5; ++i) {
            list.add((E)Integer.valueOf(i));
        }
        final MapUniqueList<E> uniqueList = MapUniqueList.mapUniqueList(list);
        for (int i = 5; i < 10; ++i) {
            uniqueList.add((E)Integer.valueOf(i));
        }

        assertTrue(uniqueList.contains(Integer.valueOf(8)));
    }

    public void testMapCollections444() {
        final List<Integer> list = new ArrayList<Integer>();
        final Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        final MapUniqueList<Integer> lmap = new MapUniqueList<Integer>(list, map);

        // Duplicate element
        final Integer obj1 = Integer.valueOf(1);
        final Integer obj2 = Integer.valueOf(2);

        lmap.add(obj1);
        lmap.add(obj2);
        lmap.set(0, obj1);
        assertEquals(2, lmap.size());
        assertSame(obj1, lmap.get(0));
        assertSame(obj2, lmap.get(1));

        assertTrue(lmap.contains(obj1));
        assertTrue(lmap.contains(obj2));
    }

    class MapUniqueList307 extends MapUniqueList<E> {
        /**
         * Generated serial version ID.
         */
        private static final long serialVersionUID = 1415013031022962158L;

        public MapUniqueList307(final List<E> list, final Map<E, Integer> map) {
            super(list, map);
        }
    }


    //-----------------------------------------------------------------------
    @Override
    public String getCompatibilityVersion() {
        return "4.FIXME";
    }

    public void testCreate() throws Exception {
        resetEmpty();
        writeExternalFormToDisk((java.io.Serializable) getCollection(), "src/test/resources/data/test/MapUniqueList.emptyCollection.version4.FIXME.obj");
        resetFull();
        writeExternalFormToDisk((java.io.Serializable) getCollection(), "src/test/resources/data/test/MapUniqueList.fullCollection.version4.FIXME.obj");
    }

}

Return to bug 58740

Lines 18-27 Link Here

(-)src/main/java/org/apache/commons/collections4/list/MapUniqueList.java (-73 / +97 lines)
18		18
19	import java.util.ArrayList;	19	import java.util.ArrayList;
20	import java.util.Collection;	20	import java.util.Collection;
21	import java.util.HashSet;	21	import java.util.HashMap;
22	import java.util.Iterator;	22	import java.util.Iterator;
23	import java.util.List;	23	import java.util.List;
24	import java.util.ListIterator;	24	import java.util.ListIterator;
		25	import java.util.Map;
25	import java.util.Set;	26	import java.util.Set;
26		27
27	import org.apache.commons.collections4.ListUtils;	28	import org.apache.commons.collections4.ListUtils;
Lines 31-46 Link Here
31		32
32	/**	33	/**
33	* Decorates a <code>List</code> to ensure that no duplicates are present much	34	* Decorates a <code>List</code> to ensure that no duplicates are present much
34	* like a <code>Set</code>.	35	* like a <code>Map</code>.
35	* <p>	36	* <p>
36	* The <code>List</code> interface makes certain assumptions/requirements. This	37	* The <code>List</code> interface makes certain assumptions/requirements. This
37	* implementation breaks these in certain ways, but this is merely the result of	38	* implementation breaks these in certain ways, but this is merely the result of
38	* rejecting duplicates. Each violation is explained in the method, but it	39	* rejecting duplicates. Each violation is explained in the method, but it
39	* should not affect you. Bear in mind that Sets require immutable objects to	40	* should not affect you. Bear in mind that Maps require immutable objects to
40	* function correctly.	41	* function correctly.
41	* <p>	42	* <p>
42	* The {@link org.apache.commons.collections4.set.ListOrderedSet ListOrderedSet}	43	* The {@link org.apache.commons.collections4.set.ListOrderedMap ListOrderedMap}
43	* class provides an alternative approach, by wrapping an existing Set and	44	* class provides an alternative approach, by wrapping an existing Map and
44	* retaining insertion order in the iterator.	45	* retaining insertion order in the iterator.
45	* <p>	46	* <p>
46	* This class is Serializable from Commons Collections 3.1.	47	* This class is Serializable from Commons Collections 3.1.
Lines 48-103 Link Here
48	* @since 3.0	49	* @since 3.0
49	* @version $Id$	50	* @version $Id$
50	*/	51	*/
51	public class SetUniqueList<E> extends AbstractSerializableListDecorator<E> {	52	public class MapUniqueList<E> extends AbstractSerializableListDecorator<E> {
52		53
53	/** Serialization version. */	54	/** Serialization version. */
54	private static final long serialVersionUID = 7196982186153478694L;	55	private static final long serialVersionUID = 5539814519665417789L;
55		56
56	/** Internal Set to maintain uniqueness. */	57	/** Internal Map to maintain uniqueness. */
57	private final Set<E> set;	58	private final Map<E, Integer> map;
58		59
59	/**	60	/**
60	* Factory method to create a SetList using the supplied list to retain order.	61	* Factory method to create a MapList using the supplied list to retain order.
61	* <p>	62	* <p>
62	* If the list contains duplicates, these are removed (first indexed one	63	* If the list contains duplicates, these are removed (first indexed one
63	* kept). A <code>HashSet</code> is used for the set behaviour.	64	* kept). A <code>HashMap</code> is used for the set behaviour. The map
		65	* also gives better performance for indexOf, contains(E), and get(E).
64	*	66	*
65	* @param <E> the element type	67	* @param <E> the element type
66	* @param list the list to decorate, must not be null	68	* @param list the list to decorate, must not be null
67	* @return a new {@link SetUniqueList}	69	* @return a new {@link MapUniqueList}
68	* @throws NullPointerException if list is null	70	* @throws NullPointerException if list is null
69	* @since 4.0	71	* @since FIXME
70	*/	72	*/
71	public static <E> SetUniqueList<E> setUniqueList(final List<E> list) {	73	public static <E> MapUniqueList<E> mapUniqueList(final List<E> list) {
72	if (list == null) {	74	if (list == null) {
73	throw new NullPointerException("List must not be null");	75	throw new NullPointerException("List must not be null");
74	}	76	}
		77	final Map<E, Integer> map = new HashMap<E, Integer>();
75	if (list.isEmpty()) {	78	if (list.isEmpty()) {
76	return new SetUniqueList<E>(list, new HashSet<E>());	79	return new MapUniqueList<E>(list, map);
77	}	80	}
78	final List<E> temp = new ArrayList<E>(list);	81	final List<E> temp = new ArrayList<E>(list);
79	list.clear();	82	list.clear();
80	final SetUniqueList<E> sl = new SetUniqueList<E>(list, new HashSet<E>());	83	final MapUniqueList<E> maplist = new MapUniqueList<E>(list, map);
81	sl.addAll(temp);	84	maplist.addAll(temp);
82	return sl;	85	return maplist;
83	}	86	}
84		87
85	// -----------------------------------------------------------------------	88	// -----------------------------------------------------------------------
86	/**	89	/**
87	* Constructor that wraps (not copies) the List and specifies the set to use.	90	* Constructor that wraps (not copies) the List and specifies the map to use.
88	* <p>	91	* <p>
89	* The set and list must both be correctly initialised to the same elements.	92	* The map and list must both be correctly initialised to the same elements.
90	*	93	*
91	* @param set the set to decorate, must not be null	94	* @param map the map to decorate, must not be null
92	* @param list the list to decorate, must not be null	95	* @param list the list to decorate, must not be null
93	* @throws NullPointerException if set or list is null	96	* @throws NullPointerException if map or list is null
94	*/	97	*/
95	protected SetUniqueList(final List<E> list, final Set<E> set) {	98	protected MapUniqueList(final List<E> list, final Map<E, Integer> map) {
96	super(list);	99	super(list);
97	if (set == null) {	100	if (map == null) {
98	throw new NullPointerException("Set must not be null");	101	throw new NullPointerException("Map must not be null");
99	}	102	}
100	this.set = set;	103	this.map = map;
101	}	104	}
102		105
103	// -----------------------------------------------------------------------	106	// -----------------------------------------------------------------------
Lines 107-113 Link Here
107	* @return an unmodifiable set view	110	* @return an unmodifiable set view
108	*/	111	*/
109	public Set<E> asSet() {	112	public Set<E> asSet() {
110	return UnmodifiableSet.unmodifiableSet(set);	113	return UnmodifiableSet.unmodifiableSet(map.keySet());
111	}	114	}
112		115
113	// -----------------------------------------------------------------------	116	// -----------------------------------------------------------------------
Lines 116-122 Link Here
116	* <p>	119	* <p>
117	* <i>(Violation)</i> The <code>List</code> interface requires that this	120	* <i>(Violation)</i> The <code>List</code> interface requires that this
118	* method returns <code>true</code> always. However this class may return	121	* method returns <code>true</code> always. However this class may return
119	* <code>false</code> because of the <code>Set</code> behaviour.	122	* <code>false</code> because of the uniqueness criteria.
120	*	123	*
121	* @param object the object to add	124	* @param object the object to add
122	* @return true if object was added	125	* @return true if object was added
Lines 147-155 Link Here
147	@Override	150	@Override
148	public void add(final int index, final E object) {	151	public void add(final int index, final E object) {
149	// adds element if it is not contained already	152	// adds element if it is not contained already
150	if (set.contains(object) == false) {	153	if (map.containsKey(object) == false) {
151	super.add(index, object);	154	super.add(index, object);
152	set.add(object);	155	map.put(object, index);
153	}	156	}
154	}	157	}
155		158
Lines 168-174 Link Here
168	*/	171	*/
169	@Override	172	@Override
170	public boolean addAll(final Collection<? extends E> coll) {	173	public boolean addAll(final Collection<? extends E> coll) {
171	return addAll(size(), coll);	174	//return addAll(size(), coll);
		175	boolean changed = false;
		176	for (E e : coll) {
		177	changed \|= add(e);
		178	}
		179	return changed;
172	}	180	}
173		181
174	/**	182	/**
Lines 188-200 Link Here
188	*/	196	*/
189	@Override	197	@Override
190	public boolean addAll(final int index, final Collection<? extends E> coll) {	198	public boolean addAll(final int index, final Collection<? extends E> coll) {
191	final List<E> temp = new ArrayList<E>();	199	/*final List<E> temp = new ArrayList<E>();
192	for (final E e : coll) {	200	for (final E e : coll) {
193	if (set.add(e)) {	201	if (map.add(e)) {
194	temp.add(e);	202	temp.add(e);
195	}	203	}
196	}	204	}
197	return super.addAll(index, temp);	205	return super.addAll(index, temp);*/
		206	boolean changed = false;
		207	int i = index;
		208	for (E e : coll) {
		209	if (!map.containsKey(e)) {
		210	add(i, e);
		211	i++;
		212	changed = true;
		213	}
		214	}
		215	return changed;
198	}	216	}
199		217
200	// -----------------------------------------------------------------------	218	// -----------------------------------------------------------------------
Lines 220-234 Link Here
220	super.remove(pos); // remove the duplicate by index	238	super.remove(pos); // remove the duplicate by index
221	}	239	}
222		240
223	set.remove(removed); // remove the item deleted by the set	241	map.remove(removed); // remove the item deleted by the map
224	set.add(object); // add the new item to the unique set	242	map.put(object, index); // add the new item to the unique map
225		243
226	return removed; // return the item deleted by the set	244	return removed; // return the item deleted by the map
227	}	245	}
228		246
229	@Override	247	@Override
230	public boolean remove(final Object object) {	248	public boolean remove(final Object object) {
231	final boolean result = set.remove(object);	249	final boolean result = map.remove(object) != null;
232	if (result) {	250	if (result) {
233	super.remove(object);	251	super.remove(object);
234	}	252	}
Lines 238-244 Link Here
238	@Override	256	@Override
239	public E remove(final int index) {	257	public E remove(final int index) {
240	final E result = super.remove(index);	258	final E result = super.remove(index);
241	set.remove(result);	259	map.remove(result);
242	return result;	260	return result;
243	}	261	}
244		262
Lines 262-267 Link Here
262	*/	280	*/
263	@Override	281	@Override
264	public boolean retainAll(final Collection<?> coll) {	282	public boolean retainAll(final Collection<?> coll) {
		283	final Set<E> set = map.keySet();
265	boolean result = set.retainAll(coll);	284	boolean result = set.retainAll(coll);
266	if (result == false) {	285	if (result == false) {
267	return false;	286	return false;
Lines 269-275 Link Here
269	if (set.size() == 0) {	288	if (set.size() == 0) {
270	super.clear();	289	super.clear();
271	} else {	290	} else {
272	// use the set as parameter for the call to retainAll to improve performance	291	// use the map as parameter for the call to retainAll to improve performance
273	super.retainAll(set);	292	super.retainAll(set);
274	}	293	}
275	return result;	294	return result;
Lines 278-309 Link Here
278	@Override	297	@Override
279	public void clear() {	298	public void clear() {
280	super.clear();	299	super.clear();
281	set.clear();	300	map.clear();
282	}	301	}
283		302
284	@Override	303	@Override
285	public boolean contains(final Object object) {	304	public boolean contains(final Object object) {
286	return set.contains(object);	305	return map.containsKey(object);
287	}	306	}
288		307
289	@Override	308	@Override
290	public boolean containsAll(final Collection<?> coll) {	309	public boolean containsAll(final Collection<?> coll) {
291	return set.containsAll(coll);	310	return map.keySet().containsAll(coll);
292	}	311	}
293		312
294	@Override	313	@Override
295	public Iterator<E> iterator() {	314	public Iterator<E> iterator() {
296	return new SetListIterator<E>(super.iterator(), set);	315	return new MapListIterator<E>(super.iterator(), map);
297	}	316	}
298		317
299	@Override	318	@Override
300	public ListIterator<E> listIterator() {	319	public ListIterator<E> listIterator() {
301	return new SetListListIterator<E>(super.listIterator(), set);	320	return new MapListListIterator<E>(super.listIterator(), map);
302	}	321	}
303		322
304	@Override	323	@Override
305	public ListIterator<E> listIterator(final int index) {	324	public ListIterator<E> listIterator(final int index) {
306	return new SetListListIterator<E>(super.listIterator(index), set);	325	return new MapListListIterator<E>(super.listIterator(index), map);
307	}	326	}
308		327
309	/**	328	/**
Lines 315-349 Link Here
315	@Override	334	@Override
316	public List<E> subList(final int fromIndex, final int toIndex) {	335	public List<E> subList(final int fromIndex, final int toIndex) {
317	final List<E> superSubList = super.subList(fromIndex, toIndex);	336	final List<E> superSubList = super.subList(fromIndex, toIndex);
318	final Set<E> subSet = createSetBasedOnList(set, superSubList);	337	final Map<E, Integer> subMap = createMapBasedOnList(map, superSubList);
319	return ListUtils.unmodifiableList(new SetUniqueList<E>(superSubList, subSet));	338	return ListUtils.unmodifiableList(new MapUniqueList<E>(superSubList, subMap));
320	}	339	}
321		340
322	/**	341	/**
323	* Create a new {@link Set} with the same type as the provided {@code set}	342	* Create a new {@link Map} with the same type as the provided {@code map}
324	* and populate it with all elements of {@code list}.	343	* and populate it with all elements of {@code list}.
325	*	344	*
326	* @param set the {@link Set} to be used as return type, must not be null	345	* @param map the {@link Map} to be used as return type, must not be null
327	* @param list the {@link List} to populate the {@link Set}	346	* @param list the {@link List} to populate the {@link Map}
328	* @return a new {@link Set} populated with all elements of the provided	347	* @return a new {@link Map} populated with all elements of the provided
329	* {@link List}	348	* {@link List}
330	*/	349	*/
331	@SuppressWarnings("unchecked")	350	@SuppressWarnings("unchecked")
332	protected Set<E> createSetBasedOnList(final Set<E> set, final List<E> list) {	351	protected Map<E, Integer> createMapBasedOnList(final Map<E, Integer> map, final List<E> list) {
333	Set<E> subSet;	352	Map<E, Integer> subMap;
334	if (set.getClass().equals(HashSet.class)) {	353	if (map.getClass().equals(HashMap.class)) {
335	subSet = new HashSet<E>(list.size());	354	subMap = new HashMap<E, Integer>(list.size());
336	} else {	355	} else {
337	try {	356	try {
338	subSet = set.getClass().newInstance();	357	subMap = map.getClass().newInstance();
339	} catch (final InstantiationException ie) {	358	} catch (final InstantiationException ie) {
340	subSet = new HashSet<E>();	359	subMap = new HashMap<E, Integer>();
341	} catch (final IllegalAccessException iae) {	360	} catch (final IllegalAccessException iae) {
342	subSet = new HashSet<E>();	361	subMap = new HashMap<E, Integer>();
343	}	362	}
344	}	363	}
345	subSet.addAll(list);	364	assert subMap.isEmpty();
346	return subSet;	365	for (E e : list) {
		366	if (! subMap.containsKey(e)) {
		367	subMap.put(e, subMap.size());
		368	}
		369	}
		370	return subMap;
347	}	371	}
348		372
349	// -----------------------------------------------------------------------	373	// -----------------------------------------------------------------------
Lines 350-363 Link Here
350	/**	374	/**
351	* Inner class iterator.	375	* Inner class iterator.
352	*/	376	*/
353	static class SetListIterator<E> extends AbstractIteratorDecorator<E> {	377	static class MapListIterator<E> extends AbstractIteratorDecorator<E> {
354		378
355	private final Set<E> set;	379	private final Map<E, Integer> map;
356	private E last = null;	380	private E last = null;
357		381
358	protected SetListIterator(final Iterator<E> it, final Set<E> set) {	382	protected MapListIterator(final Iterator<E> it, final Map<E, Integer> map) {
359	super(it);	383	super(it);
360	this.set = set;	384	this.map = map;
361	}	385	}
362		386
363	@Override	387	@Override
Lines 369-375 Link Here
369	@Override	393	@Override
370	public void remove() {	394	public void remove() {
371	super.remove();	395	super.remove();
372	set.remove(last);	396	map.remove(last);
373	last = null;	397	last = null;
374	}	398	}
375	}	399	}
Lines 377-391 Link Here
377	/**	401	/**
378	* Inner class iterator.	402	* Inner class iterator.
379	*/	403	*/
380	static class SetListListIterator<E> extends	404	static class MapListListIterator<E> extends
381	AbstractListIteratorDecorator<E> {	405	AbstractListIteratorDecorator<E> {
382		406
383	private final Set<E> set;	407	private final Map<E, Integer> map;
384	private E last = null;	408	private E last = null;
385		409
386	protected SetListListIterator(final ListIterator<E> it, final Set<E> set) {	410	protected MapListListIterator(final ListIterator<E> it, final Map<E, Integer> map) {
387	super(it);	411	super(it);
388	this.set = set;	412	this.map = map;
389	}	413	}
390		414
391	@Override	415	@Override
Lines 403-417 Link Here
403	@Override	427	@Override
404	public void remove() {	428	public void remove() {
405	super.remove();	429	super.remove();
406	set.remove(last);	430	map.remove(last);
407	last = null;	431	last = null;
408	}	432	}
409		433
410	@Override	434	@Override
411	public void add(final E object) {	435	public void add(final E object) {
412	if (set.contains(object) == false) {	436	if (map.containsKey(object) == false) {
413	super.add(object);	437	super.add(object);
414	set.add(object);	438	map.put(object, map.size());
415	}	439	}
416	}	440	}
417		441