Finden Sie den Stamm einer Hierarchie, mit Optional

Question

Ich habe eine Baumhierarchie von Typen, die ihre Kinder, aber nicht ihre Eltern kennen. Jetzt bin die Schaffung ich eine externe Registrierung, die den entgegengesetzten Weg bietet, von außen:

public interface Registry<X>{ 
    Optional<X> parent(X node); 
} 

Nun würde Ich mag ein Verfahren in dieser Schnittstelle implementieren, die den Grundton dieser Hierarchie von einem bestimmten Knoten wird (der Wurzelknoten kann der übergebene Knoten oder ein Vorgänger sein).

bekam ich so weit:

default X root(X node) { 

    X current = node; 

    for (Optional<X> opt = Optional.of(current); 
     opt.isPresent(); 
     opt = opt.flatMap(this::parent)) { 

     if (opt.isPresent()) { 
      current = opt.get(); 
     } 
    } 

    return current; 

} 

Während dies funktioniert, ist es ein bisschen unbeholfen fühlt. Optional.isPresent() wird zweimal aufgerufen und die Variable current wird neu zugewiesen. Kann ich das irgendwie eleganter und funktioneller machen?

Answer 1

Guava und JDK Stream-Versionen unten, aber der absolute Gewinner ist JavaSlang. Ich liebe es!

import javaslang.collection.Stream; 
import java.util.Optional; 
// ... 
default X root(X node) { 
    return Stream.iterate(Optional.of(node), 
           t -> t.flatMap(this::parent) 
         ).takeWhile(Optional::isPresent) 
          .last() 
          .orElseThrow(NoSuchElementException::new); 
} 

Die Stream.iterate() Methode ist genau das, was ich in den beiden anderen Versionen bin fehlt.

---

Guava:

Zuerst werden wir eine Hilfsklasse Optionals genannt erstellen:

// to avoid misunderstandings: 
import java.util.Optional; 
import java.util.function.Function; 

import com.google.common.collect.AbstractIterator; 

public final class Optionals { 

    private Optionals(){} 

    /** 
    * Given an instance of type T and a function from T to Optional<T>, 
    * return an Iterable<T>. This Iterable will keep returning values 
    * by repeatedly applying the supplied function until the returned Optional 
    * is not present. 
    */ 
    public static <T> Iterable<T> stream(
     final T start, final Function<T, Optional<T>> increment) { 

     return() -> new AbstractIterator<T>() { 
      Optional<T> current = Optional.of(start); 

      @Override 
      protected T computeNext() { 
       if (!current.isPresent()) return endOfData(); 
       final T data = current.get(); 
       current = current.flatMap(increment); 
       return data; 
      } 
     }; 
    } 
} 

Das ist natürlich noch mehr Textvorschlag, aber das ist wiederverwendbar, und jetzt sind wir kann die Schnittstellenmethode übersichtlich schreiben:

default X root(final X node) { 
    return Iterables.getLast(Optionals.stream(node, this::parent)); 
} 

Offensichtlich wäre es möglich, dies ohne Guava zu implementieren, aber es wäre viel unordentlicher.

---

Java 8 Stream-Version:

public final class Streams { 
    private Streams(){} 

/** 
* Given an instance of type T and a function from T to Optional<T>, 
* return a Stream<T>. This Stream will keep returning values by 
* repeatedly applying the supplied function until the returned Optional 
* is not present. 
*/ 
public static <X> Stream<X> stream(
     final X start, final Function<X, Optional<X>> increment) { 

    return StreamSupport.stream(
      new Spliterator<X>() { 

       Optional<X> next = Optional.ofNullable(start); 

       @Override 
       public boolean tryAdvance(final Consumer<? super X> action) { 
        final boolean present = next.isPresent(); 
        if (present) action.accept(next.get()); 
        next = next.flatMap(increment); 
        return present; 
       } 

       @Override 
       public Spliterator<X> trySplit() { return null; } 

       @Override 
       public long estimateSize() { return Long.MAX_VALUE; } 

       @Override 
       public int characteristics() { return Spliterator.ORDERED; } 
      }, false 
    ); 
} 

, die zu diesem Code führt:

default X root(final X node) { 
    return Streams.stream(node, this::parent) 
        .reduce((left, right) -> right) 
        .orElseThrow(NoSuchElementException::new); 
} 

Answer 2

Ich denke an

default X root(X node) { 
    X root = node; 

    for (Optional<X> parentOpt = parent(root); parentOpt.isPresent(); root = parentOpt.get()) 
     ; 

    return root; 
} 

ich nicht wie der Handel mit null Argumente. Wir verschieben also auf die Implementierung parent, die Sie wahrscheinlich als eine leere Optional auf null Argument zurückgeben dokumentieren. Wenn das Argument null ist, geben wir auch null zurück. Wenn das Argument nicht null ist, speichern wir seinen Wert in root und starten die Schleifenbildung. Wir bekommen seine potenziellen Eltern. Wenn es vorhanden ist, aktualisieren wir root und versuchen es erneut. Andernfalls brechen wir und geben den letzten gespeicherten Wert in root zurück, da das soweit ist.

Das plump Gefühl, denke ich, kommt aus der ursprünglichen Optional um node. Ich glaube nicht, dass du das brauchst.

Answer 3

Die Antwort von @Sotirios ist prägnant und mehr als gut genug.

Sie haben eine Iterator in Ihrem Versuch einer Lösung implementiert und meine Lösung ist, es als Spliterator/Stream zu implementieren. Es ist wahrscheinlich zu kompliziert für Ihre spezielle Frage, aber es könnte für Ihre Bibliothek anderswo nützlich sein, oder es könnte für jemand anderen nützlich sein, der stackoverflow durchsucht.

public class ParentSpliterator<T> implements Spliterator<T> { 
    private final Registry<T> registry; 
    private Optional<T> currentNodeOpt; 

    public ParentSpliterator(Registry<T> registry, T startNode) { 
     this.registry = registry; 
     this.currentNodeOpt = Optional.of(startNode); 
    } 

    @Override 
    public boolean tryAdvance(Consumer<? super T> action) { 
     if (!currentNodeOpt.isPresent()) { 
      return false; // stream is empty 
     } else { 
      T currentNode = currentNodeOpt.get(); 
      action.accept(currentNode); 
      currentNodeOpt = registry.parent(currentNode); 
      return true; 
     } 

//  // Alternative implementation (more Stream-ish):   
//  return currentNodeOpt.map(node -> { 
//   action.accept(node); 
//   currentNodeOpt = registry.parent(node); 
//   return node; 
//  }).isPresent(); 
    } 

    @Override 
    public Spliterator<T> trySplit() { 
     return null; // Cannot be split. 
    } 

    @Override 
    public long estimateSize() { 
     return Long.MAX_VALUE; // No quick way to estimate size. 
    } 

    @Override 
    public int characteristics() { 
     return Spliterator.ORDERED; // maybe others? 
    } 

    public static void main(String[] args) { 
     Registry.CountDownRegistry cdr = new Registry.CountDownRegistry(); 
     ParentSpliterator<Integer> parentSpliterator = new ParentSpliterator<>(cdr, 3); 
     Stream<Integer> stream = StreamSupport.stream(parentSpliterator, false); 
     //stream.forEach(System.out::println); 

     // Using a reduce to pick the last element of the Stream: 
     Integer root = stream.reduce((node, nextNode) -> nextNode).get(); 
     System.out.println(root); 
    } 
} 

Und Sie müssen dieses Dienstprogramm Klasse das Beispiel an die Arbeit:

public interface Registry<X> { 
    Optional<X> parent(X node); 

    public static class CountDownRegistry implements Registry<Integer> { 

     @Override 
     public Optional<Integer> parent(Integer node) { 
      if (node > 0) { 
       return Optional.of(node - 1); 
      } else { 
       return Optional.empty(); 
      } 
     } 
    } 
} 

Answer 4

Ich glaube, Sie ziemlich nah sind bereits mit der Schleife Sie versucht. Es kann ein wenig vereinfacht werden, da der Schleifenkörper nur ausgeführt wird, wenn die Schleifenbedingung wahr ist, so dass Sie innerhalb der Schleife opt.isPresent nicht erneut testen müssen. Sie können eine Variable speichern, wenn Sie den Parameter node wiederverwenden. (Ich weiß, es ist eine Stilsache.) Der flatMap Anruf im Inkrementteil kauft Sie nicht viel, weil Sie wissen, dass opt an diesem Punkt anwesend ist; Sie können auch parent auf das Ergebnis opt.get während der Zuweisung node anrufen, während Sie gerade dabei sind. Dies ergibt:

default X root(X node) { 
    for (Optional<X> opt = Optional.of(node); opt.isPresent(); opt = parent(node = opt.get())) 
     ; 
    return node; 
} 

Sie haben ziemlich viel davon ausgehen, dass node nicht null ist, so dass Sie den parent Anruf in die Schleife Zustand bewegen kann, die Dinge ein wenig zu vereinfachen:

default X root(X node) { 
    for (Optional<X> opt; (opt = parent(node)).isPresent(); node = opt.get()) 
     ; 
    return node; 
} 

Java 9 wird haben Sie einen neuen three-arg Stream.iterate factory, mit dem Sie einen Leaf-to-Root-Stream von Knoten ganz einfach erstellen können. Die drei Argumente sind genau wie die drei Anweisungen einer for-Schleife, außer dass sie keine Nebenwirkungen haben können. Sie können Ihre ursprüngliche for-Schleife in einen Strom transkribieren wie folgt:

default Stream<X> stream(X node) { 
    return Stream.iterate(Optional.of(node), 
          Optional::isPresent, 
          op -> op.flatMap(this::parent)) 
       .map(Optional::get); 
} 

Schließlich gibt es das:

default X root(X node) { 
    return Optional.of(node).flatMap(this::parent).map(this::root).orElse(node); 
} 

Es gibt mehrere Dinge, von Hinweis zu dieser Technik.

• Es verletzt eines der Stilregeln für Optional, die ich espousing habe, insbesondere diese: „# 4: Es ist generell eine schlechte Idee, ein Optional für den spezifischen Zweck der Verkettungsverfahren von ihm zu schaffen bekomme einen Wert. " (link)
• Es ist rekursiv, was bedeutet, dass es Ihren Stapel blasen kann, wenn Ihre Hierarchie zu tief ist.
• Ihre Mitarbeiter werden Sie meiden, wenn Sie diese Technik verwenden.

Ich empfehle nicht, Code wie diesen zu schreiben, aber ich wollte es vor jemand anderem veröffentlichen. :-)