Converti ramo e ciclo associato per utilizzare l'API Java Stream

Question

Ho un semplice algoritmo Branch and Bound che funziona su una variante del problema del Salesman e ho pensato che sarebbe stato divertente provare a convertirlo per utilizzare l'API Java 8 Stream . Sto avendo difficoltà a capire come farlo senza fare affidamento sugli effetti collaterali, comunque.

codice iniziale

int bound = Integer.MAX_VALUE; 
List<Location> bestPath = null; 

while(!queue.isEmpty()) { 
    Node curr = queue.poll(); 
    //bound exceeds best, bail 
    if (curr.getBound() >= bound) { 
     return bestPath; 
    } 
    //have a complete path, save it 
    if(curr.getPath().size() == locations.size()) { 
     bestPath = curr.getPath(); 
     bound = curr.getBound(); 
     continue; 
    } 
    //incomplete path - add all possible next steps 
    Set<Location> unvisited = new HashSet<>(locations); 
    unvisited.removeAll(curr.getPath()); 
    for (Location l : unvisited) { 
     List<Location> newPath = new ArrayList<>(curr.getPath()); 
     newPath.add(l); 
     Node newNode = new Node(newPath, getBoundForPath(newPath)); 
     if (newNode.getBound() <= bound){ 
      queue.add(newNode); 
     } 
    } 
} 

ho preso un primo colpo a convertire al API Stream e si avvicinò con la seguente:

Java 8 Versione

Consumer<Node> nodeConsumer = node -> { 
    if(node.getPath().size() == locations.size()) { 
     bestPath = node.getPath(); 
     bound = node.getBound(); 
    } else { 
     locations.stream() 
      .filter(l -> !node.getPath().contains(l)) 
      .map(l -> { 
       List<Location> newPath = new ArrayList<>(node.getPath()); 
       newPath.add(s); 
       return new Node(newPath, getBoundForPath(newPath)); 
      }) 
      .filter(newNode -> newNode.getBound() <= bound) 
      .forEach(queue::add); 
    } 
}; 

Stream.generate(() -> queue.poll()) 
    .peek(nodeConsumer) 
    .filter(s -> s.getBound() > bound) 
    .findFirst(); 

return bestPath; 

Il problema principale è che il nodeConsumer deve fare riferimento a bestPath e bound, che sono non le variabili finali. Potrei renderli variabili finali AtomicReference per aggirare questo problema, ma mi sento come se questo tipo di violazione violasse lo spirito dell'API del flusso. Qualcuno può aiutarmi a distillare l'algoritmo iniziale in un'implementazione più idiomatica?

Answer 1

Mi chiedo se l'utilizzo di reduce sia la soluzione ideale in quanto consente di tenere traccia dei valori senza la necessità di variabili esterne.

Qualcosa come il seguente (ho dovuto indovinare alcuni dei dettagli del codice precedente, ma spero di essere sulla strada giusta).

final BiFunction<Entry<Integer, List<Location>>, Node, Entry<Integer, List<Location>>> accumulator 
     = (identity, node) -> { 
      if (node.getPath().size() == locations.size()) { 
       return new SimpleEntry<>(node.getBound(), node.getPath()); 
      } else { 
       locations.stream() 
        .filter(l -> !node.getPath().contains(l)) 
        .map(l -> { 
         List<Location> newPath = new ArrayList<>(node.getPath()); 
         newPath.add(l); 
         return new Node(newPath, getBoundForPath(newPath)); 
        }) 
        .filter(newNode -> newNode.getBound() <= identity.getKey()) 
        .forEach(queue::add); 
       return identity; 
      } 
     }; 

    final BinaryOperator<Entry<Integer, List<Location>>> combiner 
     = (left, right) -> left.getKey() < right.getKey() ? left : right; 

    final Entry<Integer, List<Location>> identity 
     = new SimpleEntry<>(Integer.MAX_VALUE, null); 

    final List<Location> bestValue = Stream.generate(queue::poll) 
     .reduce(identity, accumulator, combiner) 
     .getValue(); 

In alternativa, si potrebbe guardare con Seq in jOOλ (un'estensione sequenziale a Streams), e utilizzare foldLeft invece.