/*
 * File:     ElanSearchEngine.java
 * Project:  MPI Linguistic Application
 * Date:     03 April 2006
 *
 * Copyright (C) 2001-2006  Max Planck Institute for Psycholinguistics
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

package mpi.eudico.client.annotator.search.model;

import mpi.eudico.client.annotator.search.result.model.ElanMatch;

import mpi.eudico.server.corpora.clom.Annotation;
import mpi.eudico.server.corpora.clom.Transcription;

import mpi.eudico.server.corpora.clomimpl.abstr.TierImpl;

import mpi.eudico.util.TimeRelation;

import mpi.search.SearchLocale;

import mpi.search.content.query.model.*;

import mpi.search.model.Query;
import mpi.search.model.SearchEngine;
import mpi.search.model.SearchListener;

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;
import java.util.logging.*;
import java.util.regex.*;


/**
 * The SearchEngine performs the actual search in ELAN
 *
 * @author Alexander Klassmann
 * @version November 2004
 * @version Aug 2005 Identity removed
 */
public class ElanSearchEngine implements SearchEngine {
    private static final Logger logger = Logger.getLogger(ElanSearchEngine.class.getName());
    private Hashtable patternHash = new Hashtable();
    private Hashtable annotationHash = new Hashtable();
    private Hashtable unitTierHash = new Hashtable();
    private Hashtable relationshipHash = new Hashtable();
    private Transcription transcription;

    /**
     *
     * @param theTranscription
     */
    public ElanSearchEngine(SearchListener searchTool,
        Transcription transcription) {
        //super(searchTool);
        this.transcription = transcription;
        logger.setLevel(Level.ALL);
    }

    /**
     *
     * @throws QueryFormulationException
     * @throws PatternSyntaxException
     */
    private void initHashtables(ContentQuery query)
        throws QueryFormulationException, PatternSyntaxException {
        patternHash.clear();
        annotationHash.clear();
        unitTierHash.clear();
        relationshipHash.clear();

        AnchorConstraint anchorConstraint = query.getAnchorConstraint();
        String[] tierNames = anchorConstraint.getTierNames();

        for (int i = 0; i < tierNames.length; i++) {
            TierImpl tier = (TierImpl) transcription.getTierWithId(tierNames[i]);

            if (tier == null) {
                throw new QueryFormulationException(SearchLocale.getString(
                        "Search.Exception.CannotFindTier") + " '" +
                    tierNames[i] + "'");
            }

            List annotations = tier.getAnnotations();
            annotationHash.put(tierNames[i], annotations);
        }

        patternHash.put(anchorConstraint,
            Utilities.getPattern(anchorConstraint, query.getType()));

        for (int i = 1; i <= (query.size() - 1); i++) {
            DependentConstraint constraint = query.getDependentConstraint(i);

            String tierName = constraint.getTierName();
            TierImpl tier = (TierImpl) transcription.getTierWithId(tierName);

            if (tier == null) {
                throw new QueryFormulationException(SearchLocale.getString(
                        "Search.Exception.CannotFindTier") + " '" + tierName +
                    "'");
            }

            if (!annotationHash.containsKey(tierName)) {
                List annotations = tier.getAnnotations();
                annotationHash.put(tierName, annotations);
            }

            if (Constraint.STRUCTURAL.equals(constraint.getMode())) {
                tierName = constraint.getUnit().substring(0,
                        constraint.getUnit().lastIndexOf(' '));

                TierImpl unitTier = (TierImpl) transcription.getTierWithId(tierName);

                if (unitTier == null) {
                    throw new QueryFormulationException(SearchLocale.getString(
                            "Search.Exception.CannotFindTier") + " '" +
                        tierName + "'");
                }

                unitTierHash.put(constraint, unitTier);
                relationshipHash.put(constraint, getRelationship(unitTier, tier));

                if (!annotationHash.containsKey(tierName)) {
                    List annotations = unitTier.getAnnotations();
                    annotationHash.put(tierName, annotations);
                }
            }

            patternHash.put(constraint,
                Utilities.getPattern(constraint, query.getType()));
        }
    }

    public void performSearch(Query query) throws Exception {
        executeThread((ContentQuery) query);
    }

    /**
     * Performs search
     * @param query
     *
     * @return Vector
     */
    public void executeThread(ContentQuery query)
        throws PatternSyntaxException, QueryFormulationException, 
            NullPointerException {
        //set unlimited size since search is done only within one transcription
        query.getResult().setChunkSize(Integer.MAX_VALUE);
        initHashtables(query);

        AnchorConstraint anchorConstraint = query.getAnchorConstraint();

        String[] tierNames = anchorConstraint.getTierNames();

        for (int i = 0; i < tierNames.length; i++) {
            List anchorAnnotations = (List) annotationHash.get(tierNames[i]);
            List anchorMatches;

            if (!(anchorConstraint instanceof RestrictedAnchorConstraint)) {
                int[] range = getAnnotationIndicesInScope(anchorAnnotations,
                        anchorConstraint.getLowerBoundary(),
                        anchorConstraint.getUpperBoundary(),
                        anchorConstraint.getUnit());

                anchorMatches = getMatches(Utilities.getPattern(
                            anchorConstraint, query.getType()),
                        anchorAnnotations, range);
            } else {
                anchorMatches = ((RestrictedAnchorConstraint) anchorConstraint).getResult()
                                 .getMatches(tierNames[i]);
            }

            filterDependentConstraints(query, anchorMatches,
                anchorConstraint.getNr());

            for (int j = 0; j < anchorMatches.size(); j++) {
                query.getResult().addMatch((ElanMatch) anchorMatches.get(j));
            }
        }
    }

    private void filterDependentConstraints(ContentQuery query,
        List startingMatches, int startingConstraintNr)
        throws NullPointerException {
        for (int i = 1; i <= (query.size() - 1); i++) {
            if (query.getDependentConstraint(i).getRefConstraintNr() == startingConstraintNr) {
                int j = 0;

                while (j < startingMatches.size()) {
                    Object o = startingMatches.get(j);
                    Annotation annotation = (o instanceof ElanMatch)
                        ? ((ElanMatch) o).getAnnotation() : (Annotation) o;

                    if (constraintFulfilled(query,
                                query.getDependentConstraint(i), annotation)) {
                        j++;
                    } else {
                        startingMatches.remove(j);
                    }
                }
            }
        }
    }

    /**
     *
     * @param constraint
     * @param anchorAnnotations
     * @param matchInfos
     */
    private boolean constraintFulfilled(ContentQuery query,
        DependentConstraint constraint, Annotation annotation)
        throws NullPointerException {
        TierImpl unitTier = null;
        List unitAnnotations = null;
        List constraintAnnotations = null;
        TierImpl[] relShip = null;

        long lowerBoundary = constraint.getLowerBoundary();
        long upperBoundary = constraint.getUpperBoundary();
        Pattern pattern = (Pattern) patternHash.get(constraint);

        constraintAnnotations = (List) annotationHash.get(constraint.getTierName());

        if (Constraint.STRUCTURAL.equals(constraint.getMode())) {
            unitTier = (TierImpl) unitTierHash.get(constraint);

            unitAnnotations = (List) annotationHash.get(unitTier.getName());

            relShip = (TierImpl[]) relationshipHash.get(constraint);
        }

        List annotationsInScope;
        int[] annotationIndicesInScope;

        if (Constraint.TEMPORAL.equals(constraint.getMode())) {
            annotationIndicesInScope = getAnnotationIndicesInScope(constraintAnnotations,
                    annotation.getBeginTimeBoundary(),
                    annotation.getEndTimeBoundary(), upperBoundary,
                    constraint.getUnit());
        } else {
            annotationsInScope = getAnnotationsInScope(lowerBoundary,
                    upperBoundary, unitTier, unitAnnotations, relShip,
                    annotation);

            annotationIndicesInScope = new int[annotationsInScope.size()];

            for (int j = 0; j < annotationsInScope.size(); j++) {
                annotationIndicesInScope[j] = constraintAnnotations.indexOf(annotationsInScope.get(
                            j));
                logger.log(Level.FINE,
                    "Constraint annotation: " +
                    ((Annotation) annotationsInScope.get(j)).getValue());
            }
        }

        List matchedAnnotations = getMatchedAnnotations(pattern,
                constraintAnnotations, annotationIndicesInScope);

        filterDependentConstraints(query, matchedAnnotations, constraint.getNr());

        return (((constraint.getQuantifier() == Constraint.ANY) &&
        (matchedAnnotations.size() > 0)) ||
        ((constraint.getQuantifier() == Constraint.NONE) &&
        (matchedAnnotations.size() == 0)));
    }

    /**
     * Returns list with the annotations (not their indices!) in constraint tier
     * within specified range
     *
     * @param lowerBoundary
     * @param upperBoundary
     * @param unitTier
     * @param unitAnnotations
     * @param relationship
     * @param anchorAnnotation
     * @return List
     */
    static private List getAnnotationsInScope(long lowerBoundary,
        long upperBoundary, TierImpl unitTier, List unitAnnotations,
        TierImpl[] relationship, Annotation centralAnnotation)
        throws NullPointerException {
        List annotationsInScope = new ArrayList();
        Annotation centralUnitAnnotation = centralAnnotation;

        while ((centralUnitAnnotation.getTier() != unitTier) &&
                (centralUnitAnnotation != null)) {
            centralUnitAnnotation = centralUnitAnnotation.getParentAnnotation();
        }

        if (centralUnitAnnotation == null) {
            throw new NullPointerException();
        }

        int unitAnnotationIndex = unitAnnotations.indexOf(centralUnitAnnotation);

        int[] unitAnnotationIndicesInScope = getRangeForTier(unitTier,
                lowerBoundary, upperBoundary, unitAnnotationIndex);

        Annotation rootOfCentralAnnotation = centralUnitAnnotation;

        while (rootOfCentralAnnotation.hasParentAnnotation()) {
            rootOfCentralAnnotation = rootOfCentralAnnotation.getParentAnnotation();
        }

        logger.log(Level.FINE,
            "Unit annotation " + centralUnitAnnotation.getValue());

        Annotation unitAnnotation;

        for (int k = 0; k < unitAnnotationIndicesInScope.length; k++) {
            unitAnnotation = (Annotation) unitAnnotations.get(unitAnnotationIndicesInScope[k]);

            boolean haveSameRoot = true;

            if (unitAnnotation.hasParentAnnotation()) {
                Annotation rootOfUnitAnnotation = unitAnnotation;

                while (rootOfUnitAnnotation.hasParentAnnotation()) {
                    rootOfUnitAnnotation = rootOfUnitAnnotation.getParentAnnotation();
                }

                haveSameRoot = rootOfUnitAnnotation == rootOfCentralAnnotation;
            }

            if (haveSameRoot) {
                annotationsInScope.addAll(getDescAnnotations(unitAnnotation,
                        relationship));
            }
        }

        return annotationsInScope;
    }

    /**
     * same as getAnnotationIndicesInScope(...) with distance 0
     *
     * @param annotationList
     * @param intervalBegin
     * @param intervalEnd
     * @param timeComparisonMode
     * @return int[]
     */
    static private int[] getAnnotationIndicesInScope(List annotationList,
        long intervalBegin, long intervalEnd, String timeComparisonMode) {
        return getAnnotationIndicesInScope(annotationList, intervalBegin,
            intervalEnd, 0L, timeComparisonMode);
    }

    /**
     * returns indices of annotations that fulfull the time constraint the
     * parameter "distance" is used only for particular timeComparisonModes
     *
     * @param annotationList
     * @param intervalBegin
     * @param intervalEnd
     * @param distance
     * @param timeComparisonMode
     * @return int[]
     */
    static private int[] getAnnotationIndicesInScope(List annotationList,
        long intervalBegin, long intervalEnd, long distance,
        String timeComparisonMode) {
        int[] annotationsInInterval = new int[annotationList.size()];
        int index = 0;

        for (int i = 0; i < annotationList.size(); i++) {
            Annotation annotation = (Annotation) annotationList.get(i);
            boolean constraintFulfilled = false;

            if (Constraint.OVERLAP.equals(timeComparisonMode)) {
                constraintFulfilled = TimeRelation.overlaps(annotation,
                        intervalBegin, intervalEnd);
            } else if (Constraint.IS_INSIDE.equals(timeComparisonMode)) {
                constraintFulfilled = TimeRelation.isInside(annotation,
                        intervalBegin, intervalEnd);
            } else if (Constraint.NO_OVERLAP.equals(timeComparisonMode)) {
                constraintFulfilled = TimeRelation.doesNotOverlap(annotation,
                        intervalBegin, intervalEnd);
            } else if (Constraint.NOT_INSIDE.equals(timeComparisonMode)) {
                constraintFulfilled = TimeRelation.isNotInside(annotation,
                        intervalBegin, intervalEnd);
            } else if (Constraint.LEFT_OVERLAP.equals(timeComparisonMode)) {
                constraintFulfilled = TimeRelation.overlapsOnLeftSide(annotation,
                        intervalBegin, intervalEnd);
            } else if (Constraint.RIGHT_OVERLAP.equals(timeComparisonMode)) {
                constraintFulfilled = TimeRelation.overlapsOnRightSide(annotation,
                        intervalBegin, intervalEnd);
            } else if (Constraint.WITHIN_OVERALL_DISTANCE.equals(
                        timeComparisonMode)) {
                constraintFulfilled = TimeRelation.isWithinDistance(annotation,
                        intervalBegin, intervalEnd, distance);
            } else if (Constraint.WITHIN_DISTANCE_TO_LEFT_BOUNDARY.equals(
                        timeComparisonMode)) {
                constraintFulfilled = TimeRelation.isWithinLeftDistance(annotation,
                        intervalBegin, distance);
            } else if (Constraint.WITHIN_DISTANCE_TO_RIGHT_BOUNDARY.equals(
                        timeComparisonMode)) {
                constraintFulfilled = TimeRelation.isWithinRightDistance(annotation,
                        intervalEnd, distance);
            } else if (Constraint.BEFORE_LEFT_DISTANCE.equals(
                        timeComparisonMode)) {
                constraintFulfilled = TimeRelation.isBeforeLeftDistance(annotation,
                        intervalBegin, distance);
            } else if (Constraint.AFTER_RIGHT_DISTANCE.equals(
                        timeComparisonMode)) {
                constraintFulfilled = TimeRelation.isAfterRightDistance(annotation,
                        intervalEnd, distance);
            }

            if (constraintFulfilled) {
                annotationsInInterval[index++] = i;
            }
        }

        int[] range = new int[index];
        System.arraycopy(annotationsInInterval, 0, range, 0, index);

        return range;
    }

    /**
     * search only on specified subindices of tier
     *
     * @param pattern
     * @param annotationList
     * @param range
     *            subindices
     * @return int[]
     */
    static private List getMatches(Pattern pattern, List annotationList,
        int[] range) {
        List matchList = new ArrayList();

        for (int i = 0; i < range.length; i++) {
            Annotation annotation = (Annotation) annotationList.get(range[i]);
            Matcher matcher = pattern.matcher(annotation.getValue());

            if (matcher.find()) {
                List substringIndices = new ArrayList();

                do {
                    substringIndices.add(new int[] {
                            matcher.start(0), matcher.end(0)
                        });
                } while (matcher.find());

                ElanMatch match = new ElanMatch(annotation, range[i],
                        (int[][]) substringIndices.toArray(new int[0][0]));

                if (range[i] > 0) {
                    match.setLeftContext(((Annotation) annotationList.get(range[i] -
                            1)).getValue());
                }

                if ((match.getIndex() + 1) < annotationList.size()) {
                    match.setRightContext(((Annotation) annotationList.get(range[i] +
                            1)).getValue());
                }

                matchList.add(match);
            }
        }

        return matchList;
    }

    /**
     * search only on specified subindices of tier
     *
     * @param pattern
     * @param annotationList
     * @param range
     *            subindices
     * @return int[]
     */
    static private List getMatchedAnnotations(Pattern pattern,
        List annotationList, int[] range) {
        List matchedAnnotationList = new ArrayList();

        for (int i = 0; i < range.length; i++) {
            Annotation annotation = (Annotation) annotationList.get(range[i]);
            Matcher matcher = pattern.matcher(annotation.getValue());

            if (matcher.find()) {
                matchedAnnotationList.add(annotation);
            }
        }

        return matchedAnnotationList;
    }

    /**
     * computes intersection of range and [0..tier.size] returns array of the
     * integers in this intersection
     *
     * @param tier
     * @param lowerBoundary
     * @param upperBoundary
     * @param center
     * @return int[]
     */
    static private int[] getRangeForTier(TierImpl tier, long lowerBoundary,
        long upperBoundary, int center) {
        int newLowerBoundary = (lowerBoundary == Long.MIN_VALUE) ? 0
                                                                 : (int) Math.max(0,
                center + lowerBoundary);
        int newUpperBoundary = (upperBoundary == Long.MAX_VALUE)
            ? (tier.getNumberOfAnnotations() - 1)
            : (int) Math.min(tier.getNumberOfAnnotations() - 1,
                center + upperBoundary);

        int[] range = new int[-newLowerBoundary + newUpperBoundary + 1];

        for (int i = 0; i < range.length; i++) {
            range[i] = i + newLowerBoundary;
        }

        return range;
    }

    /**
     * gets all descendant annotations (e.g. children of children etc.)
     *
     * @param ancestorAnnotation
     * @param relationship
     * @return Vector
     */
    static private List getDescAnnotations(Annotation ancestorAnnotation,
        TierImpl[] relationship) {
        List childAnnotations = new ArrayList();
        List parentAnnotations = new ArrayList();
        parentAnnotations.add(ancestorAnnotation);

        for (int r = relationship.length - 1; r >= 0; r--) {
            childAnnotations = new ArrayList();

            try {
                for (int i = 0; i < parentAnnotations.size(); i++) {
                    childAnnotations.addAll(((Annotation) parentAnnotations.get(
                            i)).getChildrenOnTier(relationship[r]));
                }
            } catch (Exception re) {
                re.printStackTrace();

                return new ArrayList();
            }

            parentAnnotations = childAnnotations;
        }

        return parentAnnotations;
    }

    /**
     * returns array of all Tiers between ancester and descendant tier,
     * including descendTier, excluding ancestorTier; empty, if ancestorTier ==
     * descendTier
     *
     * @param ancesterTier
     * @param descendTier
     * @return TierImpl[]
     */
    static private TierImpl[] getRelationship(TierImpl ancesterTier,
        TierImpl descendTier) {
        List relationship = new ArrayList();
        TierImpl parentTier = descendTier;

        try {
            if (descendTier.hasAncestor(ancesterTier)) {
                while (!ancesterTier.equals(parentTier)) {
                    relationship.add(parentTier);
                    parentTier = (TierImpl) parentTier.getParentTier();
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }

        return (TierImpl[]) relationship.toArray(new TierImpl[0]);
    }
}
