source: trunk/autoquest-plugin-usability2/src/main/java/de/ugoe/cs/autoquest/plugin/usability2/rules/operator/wrapper/InstanceSequenceFinder.java @ 1326

//   Copyright 2012 Georg-August-Universität Göttingen, Germany
//
//   Licensed under the Apache License, Version 2.0 (the "License");
//   you may not use this file except in compliance with the License.
//   You may obtain a copy of the License at
//
//       http://www.apache.org/licenses/LICENSE-2.0
//
//   Unless required by applicable law or agreed to in writing, software
//   distributed under the License is distributed on an "AS IS" BASIS,
//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//   See the License for the specific language governing permissions and
//   limitations under the License.

package de.ugoe.cs.autoquest.plugin.usability2.rules.operator.wrapper;

import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.RandomAccess;

import de.ugoe.cs.autoquest.plugin.usability2.rules.operator.filter.EventTypeFilter;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance;

/**
 * <p>
 * TODO comment
 * </p>
 * 
 * @author Konni Hartmann
 */
public class InstanceSequenceFinder {

    // UtilityClass
    private InstanceSequenceFinder() {}

    private static class MatchesFilterComparator implements
        EqualComparator<IEventTaskInstance, EventTypeFilter>
    {

        /*
         * (non-Javadoc)
         * 
         * @see
         * de.ugoe.cs.autoquest.plugin.usability2.rules.operator.wrapper.EqualComparator#isEqual
         * (java.lang.Object, java.lang.Object)
         */
        @Override
        public boolean isEqual(IEventTaskInstance source, EventTypeFilter target) {
            return target.match(source.getTask()).isPresent();
        }

    }

    public static Collection<List<IEventTaskInstance>> containsSequence(Collection<List<IEventTaskInstance>> sequences,
                                                  List<EventTypeFilter> filters)
    {
        Collection<List<IEventTaskInstance>> result = new LinkedList<List<IEventTaskInstance>>();

        EqualComparator<IEventTaskInstance, EventTypeFilter> comparator =
            new MatchesFilterComparator();

        for (List<IEventTaskInstance> sequence : sequences) {
            if (indexOfSubList(sequence, filters, comparator) == -1)
                continue;
            result.add(sequence);
        }

        return result;
    }

    private static final int INDEXOFSUBLIST_THRESHOLD = 35;

    protected static <S, T> int indexOfSubList(List<S> source,
                                               List<T> target,
                                               EqualComparator<S, T> comp)
    {
        int sourceSize = source.size();
        int targetSize = target.size();
        int maxCandidate = sourceSize - targetSize;

        if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
            (source instanceof RandomAccess && target instanceof RandomAccess))
        {
            nextCand: for (int candidate = 0; candidate <= maxCandidate; candidate++) {
                for (int i = 0, j = candidate; i < targetSize; i++, j++)
                    if (!comp.isEqual(source.get(j), target.get(i)))
                        continue nextCand; // Element mismatch, try next cand
                return candidate; // All elements of candidate matched target
            }
        }
        else { // Iterator version of above algorithm
            ListIterator<S> si = source.listIterator();
            nextCand: for (int candidate = 0; candidate <= maxCandidate; candidate++) {
                ListIterator<T> ti = target.listIterator();
                for (int i = 0; i < targetSize; i++) {
                    if (!comp.isEqual(si.next(), ti.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
    }
}