How to determine if a list is subsequences of another with java8 thread?

Question

For example, I have a long list [1, 2, 3, ..., 10] and a short list [1, 2, 3, ..., 10] [1, 3, 6] , then I can say that short is a subsequence of another. On the other hand, the list [1 6 3] is not that it is against restriction of order.

Below is my java7 style code for this question:

 List<Integer> sequence = Arrays.asList(1, 3, 6); List<Integer> global = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10); Iterator<Integer> iterGlobal = global.iterator(); boolean allMatch = true; for(Integer itemSequence: sequence) { boolean match = false; while(iterGlobal.hasNext()) { if(itemSequence.equals(iterGlobal.next())) { match = true; break; } } if(!match) { allMatch = false; break; } } System.out.println(allMatch); //=> true 

And I want to find a java8 stream style to achieve the same result.

Answer 1

Real functional solutions, i.e. not containing a volatile state, hard to find. This is best illustrated by the fact that all answers still include mutable state.

In addition, there is no List.indexOf(T object, int startIndex) . To illustrate how useful this would be, define it using a helper method:

 public static int indexOf(List<?> list, int startIndex, Object o) { if(startIndex!=0) list=list.subList(startIndex, list.size()); int ix=list.indexOf(o); return ix<0? -1: ix+startIndex; } 

^{It would be easy to find an alternative implementation without a temporary object if this is a problem}

Now a simple solution using mutable state would be:

 boolean allMatch = sequence.stream().allMatch(new Predicate<Integer>() { int index = 0; public boolean test(Integer t) { return (index = indexOf(global, index, t)) >=0; } }); 

A functional solution without a mutable state requires that the value type contain two items in two lists. When we use the int[2] array for this, the solution will be:

 boolean allMatch = Stream.iterate( new int[]{ 0, global.indexOf(sequence.get(0)) }, a -> new int[] { a[0]+1, indexOf(global, a[1], sequence.get(a[0]+1)) } ) .limit(sequence.size()) .allMatch(a -> a[1]>=0); 

Answer 2

I ask, and I first answer the question for mark only:

 List<Integer> sequence = Arrays.asList(1, 3, 6); List<Integer> global = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10); Iterator<Integer> iter = global.iterator(); boolean subSequence = sequence.stream().allMatch(itemSequence -> { return Stream.generate(iter::next) .anyMatch(itemGlobal -> itemSequence.equals(itemGlobal)); }); System.out.println(subSequence); 

It works well for the sequence list [1, 3, 6], and for the sequence [1, 6, 3] it throws the java.util.NoSuchElementException error. This is not what I finally want to achieve.

Answer 3

I think that you came very close to the solution (I didn’t even think of Iterator like this, therefore, plus one for you). The problem is that Stream.generate is an infinite stream.

I changed the code a bit.

  Iterator<Integer> iter = global.iterator(); boolean subSequence = sequence.stream().allMatch(itemSequence -> { return StreamSupport.stream(Spliterators.spliteratorUnknownSize(iter, Spliterator.ORDERED), false) .anyMatch(itemGlobal -> itemSequence.equals(itemGlobal)); }); System.out.println(subSequence); 

Answer 4

A variant of @Eugene's @Run response would include calling Iterable :: spliterator on the global List <>, and then apply the result to StreamSupport :: stream:

 final Spliterator<Integer> spliterator = global.spliterator(); final boolean subSequence = sequence.stream().allMatch( itemSequence -> StreamSupport.stream( spliterator, false ).anyMatch(itemSequence::equals) ); System.out.println(subSequence); 

Answer 5

I will add another option when I see Holger's answer; but this will only work with jdk-9 Stream.iterate .

I defined the helper method in the same way, the little bit is different:

 private static int fits(List<Integer> global, int elementIndex, int element) { return global.indexOf(element) >= elementIndex ? global.indexOf(element) : -1; } 

And then just use int[2] :

 boolean allMatch = Stream.iterate(new int[] { 0, 0 }, array -> array[0] < sequence.size() && array[1] >= 0, array -> new int[] { array[0] + 1, fits(global, array[1], sequence.get(a[0])) }) .allMatch(array -> array[0] >= array[1]); 

EDIT Holger is right, this will only work for non-duplicates.

I can also write it for duplicates, but then it suffers from the fact that fits needs to be called twice.

  boolean allMatch = Stream.iterate(new int[] { 0, 0 }, a -> { return a[0] == sequence.size() ? false : fits(global, sequence.get(a[0])) >= a[1]; }, a -> { int nextFits = fits(global, sequence.get(a[0])); return new int[] { a[0] + 1, nextFits > a[1] ? nextFits + 1 : -1 }; }) .count() == sequence.size();