W aplikacji Grails staram się zapobiec tworzeniu cykli w grafie skierowanym. Użytkownik może przypisać rodzica do węzła, ale żaden węzeł nie powinien być przodkiem swojego rodzica. Napisałem prostą funkcję konfiguracji, która wywołuje checkLineageForTarget, czyli funkcję rekurencyjną, która wykonuje ciężkie podnoszenie:

boolean checkLineageForTarget(Integer target, Collection<Node>stillToProcess){
// true means that this is a safe addition
// false means that this addition creates a cycle

    boolean retVal = stillToProcess.each {
        Collection<Node> itsParents = getParentNodes(it)

        if (it.id == target){
            println("found a loop on " + target);
            return false; // loop detected!
        }
        if (itsParents.empty){ return true; } // end of the line

        return checkLineageForTarget(target, itsParents)
    }

    // at this point, retVal is always true, even when the "found a loop [...]" condition is met
    return retVal;
}

To „działa”, ponieważ wyświetla komunikat „znaleziono pętlę [...]”, ale poza zamknięciem retVal jest prawdziwe, funkcja wywołująca próbuje dodać nową relację nadrzędny/podrzędny, a mój stos przepełnia się .

Jakie jest moje nieporozumienie?

3
Alan Gilbert 22 luty 2012, 04:47

3 odpowiedzi

Najlepsza odpowiedź

each< Metoda /a> zwraca tę samą kolekcję, na której została wywołana, więc retVal prawdopodobnie nie jest wartością logiczną „prawda”, ale jest oceniana jako „prawda” (ponieważ jest to kolekcja, oznaczałoby to, że nie jest pusta).

Jeśli chcesz sprawdzić warunek dla każdego elementu w kolekcji, możesz użyć every.

boolean checkLineageForTarget(Integer target, Collection<Node>stillToProcess){
    stillToProcess.every { node ->
        node.id != target && checkLineageForTarget(target, getParentNodes(node))
    }
}

Zauważ, że nie musiałem sprawdzać warunku .empty w kolekcji węzłów nadrzędnych, ponieważ zostanie on przefiltrowany przez rekurencyjne wywołanie checkLineageForTarget (tj. wywołanie .every na pustej kolekcji zawsze zwraca true). Ponadto, z powodu zwarcia operatora &&, iteracja zatrzymuje się, gdy tylko node.id == target :)

3
epidemian 22 luty 2012, 17:36

.each wydaje się zwracać obiekt, który jest zapętlony po zakończeniu. Przypisujesz to do wartości logicznej i jest ona zmuszana do true. Prawdopodobnie chcesz użyć .every do swojego zadania. Zwraca true tylko wtedy, gdy każda iteracja zwraca true i przestanie zapętlać, gdy trafi w pierwszy false. Więcej informacji znajdziesz w fajnych dokumentach.

3
seth.miller 22 luty 2012, 05:10

Kiedy wracasz do zamknięcia, jest to jak powrót do wywołania metody w ramach metody — jest to działanie lokalne dla tego zakresu i nie ma wpływu na rzeczywistą metodę, w której wywoływane jest zamknięcie. W tym przypadku możesz użyć jednego z innych sugerowanych podejść (np. każdy) lub użyj zwykłej pętli for, ponieważ działa tak samo jak każdy Groovy (tj. jest bezpieczny dla null i obsługuje, ale nie wymaga typów), ale możesz wyjść z pętli lub powrócić, a ponieważ jesteś w prawdziwa pętla for zwróci z metody:

boolean checkLineageForTarget(Integer target, Collection<Node>stillToProcess){

   for (Node node in stillToProcess) {
      Collection<Node> itsParents = getParentNodes(node)
      ...
   }
   ...
}
2
Burt Beckwith 22 luty 2012, 05:40