Collection that uses ListIterator and is a unique list

Question

This has been annoying me in a project recently and my Google phoo is failing me at finding a suitable answer.

Is there a collection, that has access to the ListIterator but also only allows for unique values inside the collection?

Reasoning for this, I have a collection of items, that in this collection, there should only ever be one of each element. I also want to be able to traverse this collection in both directions whilst also being sorted or allow me to sort it using Collections.Sort();

I've not found anything suitable and had to write my own class using the following code:

public class UniqueArrayList<E> extends ArrayList<E> {
    @Override
    public boolean add(E element){
        if (this.contains(element))
            return false;
        else
            return super.add(element);
    }

    @Override
    public void add(int index, E element){
        if (this.contains(element))
            return;
        else
            super.add(index, element);
    }

    @Override
    public boolean addAll(Collection<? extends E> c){
        if (new HashSet<E>(c).size() < c.size())
            return false;
        for(E element : c){
            if (this.contains(c))
                return false;
        }
        return super.addAll(c);
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        if (new HashSet<E>(c).size() < c.size())
            return false;
        for(E element : c){
            if (this.contains(c))
                return false;
        }
        return super.addAll(index, c);
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > this.size())
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }

    @Override
    public ListIterator<E> listIterator() {
        return new ListItr(0);
    }

    @Override
    public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size();
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size())
                throw new NoSuchElementException();
            Object[] elementData = UniqueArrayList.this.toArray();
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                UniqueArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }


    }

    private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = UniqueArrayList.this.toArray();
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            try {
                //Need to allow this for the collections sort to work!
                //if (!UniqueArrayList.this.contains(e))
                UniqueArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                UniqueArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }
}

However this is far from perfect, for one I can't override the ListIterator.set(); because Collections.sort(); uses it to move items in the list. If I try to prevent non unique items from being added to the list here, the sort never happens.

So, does anyone have a better method or know of another collection that abides by the rules that I would like? Or do I just need to live with this rather irritating issue?

[Edit]

This is the Collections.sort(); method:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray();
    Arrays.sort(a);
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);
    }
}

The reasoning they give for doing this is:

This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n² log(n) performance that would result from attempting to sort a linked list in place.

Answer 1

When you need unique values you should try to switch to a Set. You can use a TreeSet together with a Comparator instance to sort the entries. The descendingSet() method of TreeSet will give you the reverse order. If you really need a ListIterator at some point you could create a temporary list from the set.

Answer 2

As Thor Stan mentioned, a TreeSet gets you most of what you want. It ensures elements are unique, it keeps them sorted, and you can iterate it in either direction using iterator() or descendingIterator().

It's not entirely clear why you're asking for ListIterator though. Most things about a ListIterator are very positional: the notion of an index, or adding something at the current position, or setting the current element. These don't make sense for a sorted set.

One aspect of a ListIterator that you might be looking for, though, is the ability to reverse directions in the midst of iteration. You can't do this directly with a TreeSet iterator, since it offers access only via an ordinary Iterator instead of a ListIterator.

However, a TreeSet implements the NavigableSet interface, which lets you step through the elements in order, in either direction. The NavigableSet interface is a subinterface of SortedSet, which provides the first() and last() methods to get you started at one of the "ends" of the set. Once you have an element in the set, you can step in either direction using the lower(E) and higher(E) methods. Or, if you want to start somewhere in the middle, you can't start at a position by index, but you can start with a value (which needn't be a member of the set) and then call lower(E) or higher(E).

For example:

    TreeSet<String> set = new TreeSet<>(
        Arrays.asList("a", "z", "b", "y"));
    String cur;

    cur = set.first();     // a
    cur = set.higher(cur); // b
    cur = set.higher(cur); // y
    cur = set.higher(cur); // z
    cur = set.lower(cur);  // y
    cur = set.lower(cur);  // b
    cur = set.lower(cur);  // a
    cur = set.lower(cur);  // null