Коллекция, которая использует ListIterator и является уникальным списком
Это недавно раздражало меня в проекте, и мой Google phoo не может найти подходящий ответ.
Есть ли коллекция, которая имеет доступ к 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]);
}
}
Причины, по которым они приводят это:
Эта реализация сбрасывает указанный список в массив, сортирует массив и перебирает список, сбрасывая каждый элемент из соответствующая позиция в массиве. Это позволяет избежать 2 log (n) производительность, которая может возникнуть в результате сортировки связанных список на месте.
Ответы
Ответ 1
Как сказал Thor Stan, TreeSet доставит вам больше всего того, чего вы хотите. Он гарантирует уникальность элементов, он держит их отсортированными, и вы можете перебирать их в любом направлении с помощью iterator() или descendingIterator().
Не совсем понятно, почему вы просите ListIterator. Большинство вещей о ListIterator очень позиционные: понятие индекса или добавление чего-то в текущую позицию или установка текущего элемента. Это не имеет смысла для сортированного набора.
Один аспект ListIterator, который вы, возможно, ищете, - это способность обратного направления в середине итерации. Вы не можете сделать это напрямую с помощью итератора TreeSet, поскольку он предлагает доступ только через обычный Iterator вместо ListIterator.
Однако, TreeSet реализует интерфейс NavigableSet, который позволяет вам последовательно перемещать элементы в любом направлении. Интерфейс NavigableSet является вспомогательным интерфейсом SortedSet, который предоставляет методы first() и last(), чтобы вы начали с одного из "концов" набора. Когда у вас есть элемент в наборе, вы можете шагнуть в любом направлении, используя методы lower(E) и higher(E). Или, если вы хотите начать где-то посередине, вы не можете начать с позиции по индексу, но вы можете начать со значения (которое не должно быть членом набора), а затем вызвать lower(E) или higher(E).
Например:
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
Ответ 2
Когда вам нужны уникальные значения, вы должны попытаться переключиться на Set.
Вы можете использовать TreeSet вместе со экземпляром Comparator для сортировки записей. Метод descendingSet() TreeSet даст вам обратный порядок.
Если вам действительно нужен ListIterator, в какой-то момент вы можете создать временный список из набора.
Ответ 3
Java считает, что List позволяет нестандартным элементам и Set не указывать. Наборы явно не поддерживают ListIterators, и поэтому код, который использует ListIterator, может предположить, что базовая коллекция не является Set.
Java 8 больше не использует ListIterator для сортировки, но если вы застряли в Java 7, который вам действительно не поможет. В основном зависит от вашего контекста и использования, может быть полезно использовать либо Set, как сказал Тор, в своем ответе, создав List по требованию, когда это необходимо.
Другой вариант - просто предоставить свой собственный ListIterator, который обращается к списку с помощью метода, который не проверяет наличие дубликатов. Преимущество этого заключалось бы в том, чтобы не создавать посторонние объекты, но опция Set скорее всего приведет к сокращению кода и вряд ли будет значительной по производительности.
Возможно, есть и другие варианты, но я не могу придумать никаких изящных.
Ответ 4
Это проблема без простых ответов.
Проблема в том, что вы нарушили контракт для add(int, E). Этот метод должен либо добавить элемент, либо вызвать исключение - ему не разрешено возвращать без добавления элемента.
Если вы переопределите set(int, E), чтобы иногда он не устанавливал элемент, он также нарушил бы контракт для этого метода. это предотвратило бы работу Collections.sort() от того, как вы идентифицировали.
Я бы не рекомендовал нарушать эти контракты - это может привести к тому, что другие методы, которые действуют в списках, будут вести себя непредсказуемыми способами.
Другие испытывали эти трудности - например, см. java docs для SetUniqueList.
Другая проблема с вашей реализацией заключается в том, что она будет чрезвычайно медленной, потому что ArrayList.contains() - это линейный поиск.
Одним из решений было бы написать класс, который использует как ArrayList, так и HashSet, и написать собственные версии add и set, а не разорвать контракты для обычных версий. Это не проверено, но вы получаете эту идею.
public final class MyList<E extends Comparable<? super E>> extends AbstractList<E> {
private final List<E> list = new ArrayList<>();
private final Set<E> set = new HashSet<>();
public E get(int i) {
return list.get(i);
}
public int size() {
return list.size();
}
public boolean tryAdd(E e) {
return set.add(e) && list.add(e);
}
public boolean tryAdd(int i, E e) {
if (set.add(e)) {
list.add(i, e);
return true;
}
return false;
}
public boolean trySet(int i, E e) {
return set.add(e) && set.remove(list.set(i, e));
}
public boolean remove(Object o) {
return set.remove(o) && list.remove(o);
}
public void sort() {
Collections.sort(list);
}
// One bonus of this approach is that contains() is now O(1)
public boolean contains(Object o) {
return set.contains(o);
}
// rest omitted.
}
Что-то вроде этого не нарушит контракт для List. Обратите внимание, что в этой версии add и set введите UnsupportedOperationException, потому что это поведение, унаследованное от AbstractList. Вы можете sort вызвать myList.sort(). Кроме того, метод listIterator будет работать, но вы не сможете использовать его для set или add (хотя remove будет работать).
Если вам нужны элементы add или set, итерации по этому List, вам нужно будет использовать явный индекс, а не listIterator. Лично я не считаю это серьезной проблемой. listIterator необходим для списков типа LinkedList, у которых нет метода времени get, но для ArrayList он приятный, но не существенный.
