Java 8 link chain functional style

Question

I have a Map<String , String> that points to links from A to B. I want to link all possible routes. eg:

 [A , B] [B , C] [C , D] [E , F] [F , G] [H , I] 

displays

 [A , B , C , D] [E , F , G] [H , I] 

I found a similar question here (but didn’t completely fulfill my requirement): https://stackoverflow.com/a/2128778

And here is my solution:

 public static <T> Set<List<T>> chainLinks(Map<T , T> map) { Set<List<T>> resultSet = new HashSet<>(); map.forEach((from, to) -> { if (!map.containsValue(from)) { List<T> list = new ArrayList<>(); list.add(from); list.addAll(inner(to, map)); resultSet.add(list); } }); return resultSet; } private static <T> List<T> inner(T from , Map<T , T> map) { if (map.containsKey(from)) { List<T> list = new ArrayList<>(); list.add(from); list.addAll(inner(map.get(from), map)); return list; } else { List<T> end = new ArrayList<>(); end.add(from); return end; } } 

and test case:

  @Test public void testChainLinks() { Map<String , String> map = new HashMap<String , String>() {{ put("A" , "B"); put("B" , "C"); put("C" , "D"); put("E" , "F"); put("F" , "G"); put("H" , "I"); }}; Utils.chainLinks(map).forEach(list -> { logger.info("list = {}" , list.stream().collect(Collectors.joining(" -> "))); }); } 

It works correctly:

 list = H -> I list = E -> F -> G list = A -> B -> C -> D 

But I do not like my decision. Because I feel that this can be solved in a more functional style. Here I smell stream.fold() . I tried, but in vain, to convert my code into a pure functional style: this means that there is no creation of intermediate objects ...

Is it possible? Any hints are appreciated!

Answer 1

There is an alternative solution using a custom collector with close to linear complexity. This is really faster than the previously proposed solutions, although it looks a bit uglier.

 public static <T> Collector<Entry<T, T>, ?, List<List<T>>> chaining() { BiConsumer<Map<T, ArrayDeque<T>>, Entry<T, T>> accumulator = ( m, entry) -> { ArrayDeque<T> k = m.remove(entry.getKey()); ArrayDeque<T> v = m.remove(entry.getValue()); if (k == null && v == null) { // new pair does not connect to existing chains // create a new chain with two elements k = new ArrayDeque<>(); k.addLast(entry.getKey()); k.addLast(entry.getValue()); m.put(entry.getKey(), k); m.put(entry.getValue(), k); } else if (k == null) { // new pair prepends an existing chain v.addFirst(entry.getKey()); m.put(entry.getKey(), v); } else if (v == null) { // new pair appends an existing chain k.addLast(entry.getValue()); m.put(entry.getValue(), k); } else { // new pair connects two existing chains together // reuse the first chain and update the tail marker // btw if k == v here, then we found a cycle k.addAll(v); m.put(k.getLast(), k); } }; BinaryOperator<Map<T, ArrayDeque<T>>> combiner = (m1, m2) -> { throw new UnsupportedOperationException(); }; // our map contains every chain twice: mapped to head and to tail // so in finisher we have to leave only half of them // (for example ones connected to the head). // The map step can be simplified to Entry::getValue if you fine with // List<Collection<T>> result. Function<Map<T, ArrayDeque<T>>, List<List<T>>> finisher = m -> m .entrySet().stream() .filter(e -> e.getValue().getFirst().equals(e.getKey())) .map(e -> new ArrayList<>(e.getValue())) .collect(Collectors.toList()); return Collector.of(HashMap::new, accumulator, combiner, finisher); } 

Using:

 List<List<String>> res = map.entrySet().stream().collect(chaining()); 

(I did not implement the combiner step, so it cannot be used for parallel threads, but it is also not difficult to add). The idea is simple: we track the partial chains so far found on the map, where the keys indicate the beginning and end of the chain, and the values ​​are ArrayDeque objects containing the found chains. Each new entry updates an existing deque (if it adds / adds it) or merges the two conventions together.

According to my tests, this version works 1000 times faster than @ saka1029 solution for an input array of 50,000 with 100 chains.

Answer 2

Non-recursive solution:

  Set<List<String>> result = map.keySet().stream() .filter(k -> !map.containsValue(k)) .map(e -> new ArrayList<String>() {{ String x = e; add(x); while (map.containsKey(x)) add(x = map.get(x)); }}) .collect(Collectors.toSet()); 

Answer 3

EDIT: An included filter from David Perez Cabrera's commentary to remove staging lists.

Well, you can easily recursively:

 private static Set<List<String>> chainLinks(Map<String, String> map) { return map.keySet().stream().filter(k -> !map.containsValue(k)).map( (key) -> calc(key, map, new LinkedList<>()) ).collect(Collectors.toSet()); } private static List<String> calc(String key,Map<String, String> map,List<String> list){ list.add(key); if (map.containsKey(key)) return calc(map.get(key),map,list); else return list; }