// Path: core/src/main/java/edu/tuberlin/dima/textmining/jedi/core/model/FoundFeature.java
// public class FoundFeature<T> {
// 
//     T entity1;
//     T entity2;
// 
//     String pattern;
//     String relation;
// 
//     public FoundFeature(T entity1, T entity2, String pattern) {
//         this.entity1 = entity1;
//         this.entity2 = entity2;
//         this.pattern = pattern;
//     }
// 
// 
//     public String getRelation() {
//         return relation;
//     }
// 
//     public void setRelation(String relation) {
//         this.relation = relation;
//     }
// 
//     public T getEntity1() {
//         return entity1;
//     }
// 
// 	public void setEntity1(T entity1) {
// 		this.entity1 = entity1;
// 	}
// 
// 	public T getEntity2() {
//         return entity2;
//     }
// 
// 	public void setEntity2(T entity2) {
// 		this.entity2 = entity2;
// 	}
// 
// 	public String getPattern() {
//         return pattern;
//     }
// 
// 	public void setPattern(String pattern) {
// 		this.pattern = pattern;
// 	}
// 
// 	@Override
//     public String toString() {
//         return "FoundFeature{" +
//                 "entity1=" + transformToString(entity1) +
//                 ", entity2=" + transformToString(entity2) +
//                 ", pattern='" + pattern + '\'' +
//                 ", relation='" + relation + '\'' +
//                 '}';
//     }
// 
//     private static <T> String transformToString(T input) {
//         if(input instanceof Annotation) {
//             return ((Annotation) input).getCoveredText();
//         } else {
//             return input.toString();
//         }
//     }
// }
// 
// Path: core/src/main/java/edu/tuberlin/dima/textmining/jedi/core/util/StringComparision.java
// public class StringComparision {
// 
//     public static boolean determineSimilar(String left, String right) {
// 
//         final String commonPrefix = StringUtils.getCommonPrefix(new String[]{left, right});
//         final String commonSuffix = StringUtils.getCommonPrefix(new String[]{StringUtils.reverse(left), StringUtils.reverse(right)});
// 
//         final int commonLength = commonPrefix.length() + commonSuffix.length();
//         final double weightedSimilar = Math.sqrt((commonLength / (float) left.length()) * (commonLength / (float) right.length()));
//         int distance = LevenshteinDistance.computeLevenshteinDistance(right, commonPrefix + StringUtils.reverse(commonSuffix));
//         return weightedSimilar >= 0.85 || (distance < 3 && (commonPrefix.length() > 0) && (commonSuffix.length() > 0));
//     }
// }


import com.google.common.base.Function;
import com.google.common.base.Joiner;
import com.google.common.base.Optional;
import com.google.common.base.Predicate;
import com.google.common.collect.*;
import com.google.common.primitives.Ints;
import de.tudarmstadt.ukp.dkpro.core.api.coref.type.CoreferenceChain;
import de.tudarmstadt.ukp.dkpro.core.api.coref.type.CoreferenceLink;
import de.tudarmstadt.ukp.dkpro.core.api.lexmorph.type.pos.*;
import de.tudarmstadt.ukp.dkpro.core.api.ner.type.NamedEntity;
import de.tudarmstadt.ukp.dkpro.core.api.segmentation.type.Token;
import edu.tuberlin.dima.textmining.jedi.core.model.FoundFeature;
import edu.tuberlin.dima.textmining.jedi.core.util.StringComparision;
import org.apache.commons.lang.StringUtils;
import org.apache.uima.UIMAException;
import org.apache.uima.fit.util.JCasUtil;
import org.apache.uima.jcas.tcas.Annotation;
import org.jgrapht.DirectedGraph;
import org.jgrapht.GraphPath;
import org.jgrapht.Graphs;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.alg.DijkstraShortestPath;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleDirectedGraph;
import javax.annotation.Nullable;
import java.util.*;
import java.util.regex.Pattern;
package edu.tuberlin.dima.textmining.jedi.core.features.detector;



/**
 * A Function that takes a JCas as input and extracts
 * its annotations in terms of the shortest path between
 * all recognized entities.
 */

public class FindShortestPathFeatureExtractor extends AbstractShortestPathFeatureExtractor {


	public FindShortestPathFeatureExtractor(String options) throws UIMAException {
		super(options);
	}

	public FindShortestPathFeatureExtractor(String options, DetectorType detectorType) throws UIMAException {
		super(options);
		setName(detectorType.name());
	}


	private static class EntityPair {

		private Annotation entity1;
		private Annotation entity2;

		public Annotation getEntity1() {
			return entity1;
		}

		public Annotation getEntity2() {
			return entity2;
		}

		private EntityPair(Annotation entity1, Annotation entity2) {
			this.entity1 = entity1;
			this.entity2 = entity2;
		}
	}

	/**
	 * Extract the shortest paths along the dependency parse
	 * between every two named entities recognized.
	 *
	 * @param graph the dependency graph
	 * @return list of found features with entity_pair and pattern
	 * with the shortest path as pattern
	 */
	@Override
// Path: core/src/main/java/edu/tuberlin/dima/textmining/jedi/core/model/FoundFeature.java
// public class FoundFeature<T> {
// 
//     T entity1;
//     T entity2;
// 
//     String pattern;
//     String relation;
// 
//     public FoundFeature(T entity1, T entity2, String pattern) {
//         this.entity1 = entity1;
//         this.entity2 = entity2;
//         this.pattern = pattern;
//     }
// 
// 
//     public String getRelation() {
//         return relation;
//     }
// 
//     public void setRelation(String relation) {
//         this.relation = relation;
//     }
// 
//     public T getEntity1() {
//         return entity1;
//     }
// 
// 	public void setEntity1(T entity1) {
// 		this.entity1 = entity1;
// 	}
// 
// 	public T getEntity2() {
//         return entity2;
//     }
// 
// 	public void setEntity2(T entity2) {
// 		this.entity2 = entity2;
// 	}
// 
// 	public String getPattern() {
//         return pattern;
//     }
// 
// 	public void setPattern(String pattern) {
// 		this.pattern = pattern;
// 	}
// 
// 	@Override
//     public String toString() {
//         return "FoundFeature{" +
//                 "entity1=" + transformToString(entity1) +
//                 ", entity2=" + transformToString(entity2) +
//                 ", pattern='" + pattern + '\'' +
//                 ", relation='" + relation + '\'' +
//                 '}';
//     }
// 
//     private static <T> String transformToString(T input) {
//         if(input instanceof Annotation) {
//             return ((Annotation) input).getCoveredText();
//         } else {
//             return input.toString();
//         }
//     }
// }
// 
// Path: core/src/main/java/edu/tuberlin/dima/textmining/jedi/core/util/StringComparision.java
// public class StringComparision {
// 
//     public static boolean determineSimilar(String left, String right) {
// 
//         final String commonPrefix = StringUtils.getCommonPrefix(new String[]{left, right});
//         final String commonSuffix = StringUtils.getCommonPrefix(new String[]{StringUtils.reverse(left), StringUtils.reverse(right)});
// 
//         final int commonLength = commonPrefix.length() + commonSuffix.length();
//         final double weightedSimilar = Math.sqrt((commonLength / (float) left.length()) * (commonLength / (float) right.length()));
//         int distance = LevenshteinDistance.computeLevenshteinDistance(right, commonPrefix + StringUtils.reverse(commonSuffix));
//         return weightedSimilar >= 0.85 || (distance < 3 && (commonPrefix.length() > 0) && (commonSuffix.length() > 0));
//     }
// }


// Path: core/src/main/java/edu/tuberlin/dima/textmining/jedi/core/features/detector/FindShortestPathFeatureExtractor.java
import com.google.common.base.Function;
import com.google.common.base.Joiner;
import com.google.common.base.Optional;
import com.google.common.base.Predicate;
import com.google.common.collect.*;
import com.google.common.primitives.Ints;
import de.tudarmstadt.ukp.dkpro.core.api.coref.type.CoreferenceChain;
import de.tudarmstadt.ukp.dkpro.core.api.coref.type.CoreferenceLink;
import de.tudarmstadt.ukp.dkpro.core.api.lexmorph.type.pos.*;
import de.tudarmstadt.ukp.dkpro.core.api.ner.type.NamedEntity;
import de.tudarmstadt.ukp.dkpro.core.api.segmentation.type.Token;
import edu.tuberlin.dima.textmining.jedi.core.model.FoundFeature;
import edu.tuberlin.dima.textmining.jedi.core.util.StringComparision;
import org.apache.commons.lang.StringUtils;
import org.apache.uima.UIMAException;
import org.apache.uima.fit.util.JCasUtil;
import org.apache.uima.jcas.tcas.Annotation;
import org.jgrapht.DirectedGraph;
import org.jgrapht.GraphPath;
import org.jgrapht.Graphs;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.alg.DijkstraShortestPath;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleDirectedGraph;
import javax.annotation.Nullable;
import java.util.*;
import java.util.regex.Pattern;

package edu.tuberlin.dima.textmining.jedi.core.features.detector;



/**
 * A Function that takes a JCas as input and extracts
 * its annotations in terms of the shortest path between
 * all recognized entities.
 */

public class FindShortestPathFeatureExtractor extends AbstractShortestPathFeatureExtractor {


	public FindShortestPathFeatureExtractor(String options) throws UIMAException {
		super(options);
	}

	public FindShortestPathFeatureExtractor(String options, DetectorType detectorType) throws UIMAException {
		super(options);
		setName(detectorType.name());
	}


	private static class EntityPair {

		private Annotation entity1;
		private Annotation entity2;

		public Annotation getEntity1() {
			return entity1;
		}

		public Annotation getEntity2() {
			return entity2;
		}

		private EntityPair(Annotation entity1, Annotation entity2) {
			this.entity1 = entity1;
			this.entity2 = entity2;
		}
	}

	/**
	 * Extract the shortest paths along the dependency parse
	 * between every two named entities recognized.
	 *
	 * @param graph the dependency graph
	 * @return list of found features with entity_pair and pattern
	 * with the shortest path as pattern
	 */
	@Override
	public List<FoundFeature<Annotation>> getShortestPaths(final UndirectedGraph<Token, DependencyEdge> graph) {