Tuesday, March 28, 2017

An indexOfSubList(...) to Find all Matching SubLists

Quick Tip

Java comes with 2 useful methods for finding a sublist in a list: Collections.indexOfSubList(List<?> source, List<?> target) Collections.lastIndexOfSubList(List<?> source, List<?> target).

These are useful methods, however, with these 2 methods I can only find the first matching sublist and the last matching sublist. What about all the other sublists in between? What if there are 3 matching sublists, or 10, or 100? Here is a quick example (Listing 1) of an new, overloaded indexOfSubList(List<?> source, List<?> target, int fromIndex) that has an extra parameter, int fromIndex. This extra parameter gives you the ability to go through and find every matching sublist.

NOTE This code comes directly from the source code of the existing Collections.indexOfSubList(List<?> source, List<?> target>) method.

Listing 1 - Find all Matching SubLists

public static int indexOfSubList(List<?> source, List<?> target, int fromIndex) {
    int sourceSize = source.size();
    int targetSize = target.size();
    int maxCandidate = sourceSize - targetSize;

    ListIterator<?> si = source.listIterator();
    if (fromIndex > 0) {
        for (int i=0; i<fromIndex; i++) {
            si.next();
        }
    }
    nextCand:
        for (int candidate = fromIndex; candidate <= maxCandidate; candidate++) {
            ListIterator<?> ti = target.listIterator();
            for (int i=0; i<targetSize; i++) {
                if (!eq(ti.next(), si.next())) {
                    // Back up source iterator to next candidate
                    for (int j=0; j<i; j++)
                        si.previous();
                    continue nextCand;
                }
            }
            return candidate;
        }

    return -1;  // No candidate matched the target
}

private static boolean eq(Object o1, Object o2) {
    return o1==null ? o2==null : o1.equals(o2);
}

No comments:

Post a Comment