Połączona lista z wieloma głowicami w Javie

Question

Mam listę, w której chciałbym zachować kilka wskaźników. Próbowałem utworzyć wiele ListIteratorów na tej samej liście, ale to zabrania mi dodawać nowe elementy na mojej liście ... (zobacz Concurrent Modification exception).

mogę stworzyć własną klasę ale wolałbym użyć wbudowanego w realizacji;)

być bardziej szczegółowe, tutaj jest nieefektywna realizacja dwóch podstawowych operacji i tego, który nie działa:

class MyList <E> { 
    private int[] _heads; 
    private List<E> _l; 

    public MyList (int nbHeads) { 
     _heads = new int[nbHeads]; 
     _l = new LinkedList<E>(); 
    } 

    public void add (E e) { 
     _l.add(e); 
    } 

    public E next (int head) { 
     return _l.get(_heads[head++]); // ugly 
    } 
} 


class MyList <E> { 
    private Vector<ListIterator<E>> _iters; 
    private List<E> _l; 

    public MyList (int nbHeads) { 
     _iters = new Vector<ListIterator<E>>(nbHeads); 
     _l = new LinkedList<E>(); 

     for(ListIterator<E> iter : _iters) iter = _l.listIterator(); 
    } 

    public void add (E e) { 
     _l.add(e); 
    } 

    public E next (int head) { 
     // ConcurrentModificationException because of the add() 
     return _iters.get(head).next(); 
    } 
} 

Answer 1

Podejdę do tego, ukrywając wszystkie rzeczywiste iteratory na liście wewnątrz klasy opakowania i ukrywając samą listę w jej własnej opakowaniu. Okienko listy będzie wiedzieć o wszystkich opakowaniach iteracyjnych; na add(), musiałby wymusić na każdym opakowaniu iteratora, aby zapisać bieżącą pozycję, usunąć wewnętrzny iterator, a następnie wykonać faktyczne dodawanie (które mogłoby uniknąć wyjątku ConcurrentModificationException, ponieważ cały iterator został zniszczony), a następnie mieć wszystkie opakowania iteracyjne ponownie utworzyć swoje iteratory i ustawić je w odpowiedniej pozycji.Ponieważ wydajesz się dodawać tylko do końca listy, żadne wymyślne indeksowanie nie będzie konieczne, ale będziesz musiał dowiedzieć się, co dzieje się z iteratorami, które już przeszły do ​​końca - czy są na końcu, czy na ich oryginalnym pozycja na liście? Niektórzy z nich oczywiście mogli już powiedzieć swoim rozmówcom, że hasNext() jest fałszywa ... Jeszcze jedna rzecz: add() i get() powinienem uważać za synchronized.

Oto testowe rozwiązanie zgodne z tymi wytycznymi. PureListWrapper i PureIteratorWrapper, jak sugerują nazwy, po prostu przekazują wszystkie wywołania metod do elementu, który zawijają.

import java.util.ArrayList; 
import java.util.Collection; 
import java.util.HashSet; 
import java.util.Iterator; 
import java.util.List; 
import java.util.ListIterator; 
import java.util.Set; 

import junit.framework.TestCase; 

public class ConcurrentlyAddableListTest extends TestCase { 


    public void testAdd() throws Exception { 
     List<String> list = new ConcurrentlyAddableList<String>(); 
     list.add("apple"); 
     list.add("banana"); 
     Iterator<String> a = list.iterator(); 
     Iterator<String> b = list.iterator(); 
     b.next(); 
     Iterator<String> c = list.iterator(); 
     c.next(); 
     c.next(); 
     list.add("cherry"); 
     assertEquals("apple", a.next()); 
     assertEquals("banana", b.next()); 
     assertEquals("cherry", c.next()); 
    } 


    private static class ConcurrentlyAddableList<T> extends PureListWrapper<T> { 
     private final Set<WrappedIterator<T>> iterators = new HashSet<WrappedIterator<T>>(); 

     @Override 
     public Iterator<T> iterator() { 
      WrappedIterator<T> iterator = new WrappedIterator<T>(super.iterator()); 
      iterators.add(iterator); 
      return iterator; 
     } 

     @Override 
     public synchronized boolean add(T o) { 
      final HashSet<WrappedIterator<T>> set = new HashSet<WrappedIterator<T>>(iterators); 
      for (WrappedIterator<T> iterator : set) 
       iterator.rememberPosition(this); 
      boolean result = super.add(o); 
      for (WrappedIterator<T> iterator : set) 
       iterator.restorePosition(this); 
      return result; 
     } 
    } 

    private static class WrappedIterator<T> extends PureIteratorWrapper<T> { 
     private int index = 0; 

     public WrappedIterator(Iterator<T> iterator) { 
      super(iterator); 
     } 

     @Override 
     public T next() { 
      index++; 
      return super.next(); 
     } 

     public void restorePosition(List<T> list) { 
      setIterator(list.iterator()); 
      int prevIndex = index; 
      index = 0; 
      while (index < prevIndex) 
       next(); 
     } 

     public void rememberPosition(List<T> list) { 
      setIterator(null); 
     } 

    } 
} 

Answer 2

przyczyną wyjątkiem opisano w its javadoc:

na przykład, nie jest na ogół dopuszczalne jeden wątek zmodyfikować a Kolekcja, podczas gdy inny wątek jest nad nim powtarzany . Zasadniczo wyniki iteracji są w tych okolicznościach niezdefiniowane . Niektóre implementacje Iteratora (łącznie z ze wszystkich ogólnych implementacji kolekcji dostarczonych przez środowiska JRE) mogą zdecydować o odrzuceniu tego wyjątku , jeśli zostanie wykryte to zachowanie . Iteratory, które to robią to , znane jako fail-szybkie iteratory, ponieważ ulegają one niepowodzeniem szybko i bezbłędnie, zamiast tego, że ryzykują arbitralne, niedeterministyczne zachowanie w przyszłości w w nieokreślonym czasie.

Należy zauważyć, że ten wyjątek nie oznacza, że ​​obiekt ma został jednocześnie zmodyfikowany innym wątkiem niż jeden . Jeśli pojedynczy wątek wywołuje sekwencję wywołań, które naruszają kontrakt obiektu, obiekt może wyrzucić ten wyjątek. Na przykład, jeśli wątek modyfikuje kolekcję bezpośrednio podczas iterowania nad kolekcją za pomocą iteratora fail-fast, , iterator wyrzuci ten wyjątek .

Oznacza to, że dla wszystkich klas kolekcji w JDK zmiana kolekcji powoduje unieważnienie wszystkich jej iteratorów (z wyjątkiem tego, który dokonał zmiany).

Można obejść ten problem za pomocą indeksów, a nie iteratorów, ale wymaga to listy dostępu losowego, a listy połączone nie zapewniają efektywnego dostępu losowego.

Dlatego jeśli naprawdę potrzebujesz takiej struktury danych, będziesz musiał spojrzeć poza JDK lub wdrożyć ją samodzielnie.