Function style of Java 8 link

I have a map < < string, string >, which represents the link from a to B I want to link all possible routes For example:

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

Will output

[A,B,C,F,I]

I found similar problems here (but did not fully meet my requirements): https://stackoverflow.com/a/10176274/298430

This 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 cases:

@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 does work:

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

But I don't like my solution Because I think it can be solved in a more practical way I can feel the stream here The smell of fold () I tried to convert my code to pure function style, but in vain: this means that there is no intermediate object creation

Is it possible? Any tips are appreciated!

Solution

Alternative solutions using custom collectors have near linear complexity It is indeed faster than the previously proposed solution, but it looks a little ugly

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,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);
}

Usage:

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

I didn't implement the compositor step, so it can't be used for parallel streams, but it's not hard to add it The idea is simple: we track some chains found in the map so far, where the key points to the beginning and end of the chain, and the value is the arraydeque object containing the chain found so far Each new entry updates the existing deque (if it is attached / pre added) or merges the two deques together

According to my test, this version is 1000 times faster than the @ saka1029 solution with 50000 element input array with 100 chains