java - 使用 ListIterator 且是唯一列表的集合

Question

这在最近的一个项目中一直困扰着我，我的 Google 呼呼声让我找不到合适的答案。

是否有一个集合可以访问 ListIterator 但也只允许集合内的唯一值？

为此，我有一个项目集合，在这个集合中，每个元素应该只有一个。我还希望能够在两个方向上遍历这个集合，同时也进行排序，或者允许我使用 Collections.Sort();

对其进行排序

我没有找到合适的东西，不得不使用以下代码编写我自己的类:

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();
            }
        }
    }
}

然而，这远非完美，因为我无法覆盖 ListIterator.set(); 因为 Collections.sort(); 使用它来移动项目在列表中。如果我试图阻止将非唯一项目添加到此处的列表中，则排序永远不会发生。

那么，有没有人有更好的方法或知道另一个遵守我想要的规则的集合？还是我只需要忍受这个相当恼人的问题？

[编辑]

这是 Collections.sort(); 方法:

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]);
    }
}

他们给出的理由是:

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

当您需要唯一值时，您应该尝试切换到集合。您可以将 TreeSet 与 Comparator 实例一起使用来对条目进行排序。 TreeSet 的 descendingSet() 方法将为您提供相反的顺序。如果您在某个时候确实需要 ListIterator，您可以从该集合创建一个临时列表。