Projektowanie iteratora w Javie

Question

Natrafiłem na wiele problemów, gdy wymagany jest iterator. Często są to proste rzeczy, w których masz już podstawową strukturę danych, którą możesz odłożyć. Innym razem staje się bardziej skomplikowany.

Przykładem może być iteracja po BST bez linków macierzystych przy użyciu przejścia w kolejności. Wymaga to zrobienia czegoś takiego:

• Utwórz stos w konstruktorze.
• Powoduje przejście do najdalszego od lewej strony węzła.
• Przechowuj, że jest więcej węzłów do odwiedzenia dla łatwego powrotu z hasNext().
• Przechowywać następny węzeł do odwiedzenia dla łatwego powrotu z następnego().

Możesz wykonać pracę, aby zlokalizować następny węzeł w hasNext() lub next(). Możesz także zlokalizować pierwszy węzeł w konstruktorze lub w pierwszym wywołaniu hasNext().

---

Moje pytanie

Czy istnieją normy i najlepsze praktyki, gdzie zrobić większość prac w implementacji iteratora? Czy sposób jest "czystszy" niż inny?

Answer 1

Po pierwsze, umowa Iterator wymaga hasNext powrót true jeśli jest więcej elementów, a next rzuci wyjątek, jeśli hasNext()==false.

Oznacza to, że istnieją dwa style korzystania z iteratora: while (it.hasNext()) it.next() i try { while (true) it.next(); } catch .... To ostatnie nie jest dobrą praktyką, ale musi być wspierane. Wspomniałem o tym, ponieważ nie można polegać na hasNext po wywołaniu przed next. Zauważyłem, że ten wymóg jest zwykle sprawcą niepotrzebnej złożoności implementacji iteratorów.

Do wyboru jest lokalna zmienna o wartości next. Jeśli next==null albo następna wartość jest nieznana (i musimy ją znaleźć), albo osiągnęliśmy koniec iteracji (hasNext() zwróci false, a next() zawiedzie). Należy również wziąć pod uwagę, że gdy następna wartość jest nieznana, możliwe, że jesteśmy na końcu iteracji, ale jeszcze jej nie zrealizowaliśmy.

Node next; 

public boolean hasNext() { 
    //if the next value already known, do nothing 
    if (next==null) {   
    //otherwise lookup the next value 
    next=findNext(); 
    } 
    //return true if the next value was found 
    return next!=null; 
} 

public Node next() { 
    if (next==null&&!hasNext()) { 
    //here we have reached the end of the iteration 
    throw new NoSuchElementException(); 
    } else { 
    //either we alredy knowed the next element 
    //or it was found by hasNext 
    Node result = next; 
    next=null; 
    return result; 
    } 
} 

private Node findNext() { 
    //the actual iteration 
} 

O wypadku na zamówienie przechodzenia, należy zachować stos (należy pamiętać, że realizacja Stack jest tablica oparte i zsynchronizowane, probebly lepiej jest użyć Dequeue takich jak LinkedList, który obsługuje także push i pop od wersji Java 6) oraz stan pomocniczy informujący o tym, jak wznowić iterację po każdym wywołaniu findNext.

Answer 2

Przenoszenie BST można zaimplementować za pomocą prostego systemu rekurencyjnego DFS (lewe dziecko -> węzeł -> prawe dziecko).

Odpowiedzi na twoje pytanie: ogólnie myślę, że nie ma "najlepszych praktyk" do projektowania iteratorów, ponieważ twoje struktury danych mogą być dowolnie złożone.Niektóre wspólne zasady:

• Twój iterator musi obsługiwać hasNext() i next() operacji w każdym przypadku. Jeśli twoja struktura danych jest niezmienna (lub usunięcie nie jest typowe), metodapowinna rzucić OperationNotSupportedException().
• next() metoda powinna sprawdzić wartość hasNext() na początku wdrożenia i wyrzucić NoSuchElementException, jeśli hasNext() zwraca false.
• Jeśli struktura danych zawiera iterator, należy wdrożyć interfejs Iterable<Type> i zaimplementować metodę public Iterator<Type> iterator().
• Jeśli więc zaimplementujesz interfejs Iterable, kod klienta może użyć operatora foreach do przetworzenia struktury danych. Jeśli takie zachowanie nie jest pożądane (na przykład użycie struktury dwudzielnego wykresu może spowodować wiele błędów klienta, ponieważ nie jest to oczywiste w przypadku iteracji dokładnie), prawdopodobnie powinieneś rozważyć inny sposób implementacji iteracji sekwencyjnych.
• Jeśli twoja struktura danych używa listy lub zestawu, twoja implementacja iteratora może korzystać z odpowiedniego iteratora kolekcji.

W każdym przypadku należy dokładnie zaprojektować swoje Iteratory. Każdy iterator jest głęboko związany z jego strukturą danych i powinien być zaprojektowany razem.