// 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;
/**
*
* TODO comment
*
*
* @author Konni Hartmann
*/
public class InstanceSequenceFinder {
// UtilityClass
private InstanceSequenceFinder() {}
private static class MatchesFilterComparator implements
EqualComparator
{
/*
* (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> containsSequence(Collection> sequences,
List filters)
{
Collection> result = new LinkedList>();
EqualComparator comparator =
new MatchesFilterComparator();
for (List sequence : sequences) {
if (indexOfSubList(sequence, filters, comparator) == -1)
continue;
result.add(sequence);
}
return result;
}
private static final int INDEXOFSUBLIST_THRESHOLD = 35;
protected static int indexOfSubList(List source,
List target,
EqualComparator 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 si = source.listIterator();
nextCand: for (int candidate = 0; candidate <= maxCandidate; candidate++) {
ListIterator 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
}
}