//   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.tasktrees.temporalrelation.utils;

import java.io.PrintStream;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskTraversingVisitor;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IMarkingTemporalRelationship;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
import de.ugoe.cs.autoquest.tasktrees.treeifc.TaskPath;

/**
 * <p>
 * A task traversal represents a list of task paths through a task tree. Traversal may represent all
 * possible task paths. In this case, all paths start with the root node and end with the leaf
 * nodes. It is also possible to exclude the traversal of a certain parent node. In this case, the
 * traversal does not contain paths to the children of this parent but only a single path to the
 * parent itself. For selections, this is always the case. I.e., a traversal never contains paths
 * were a selection is contained and where it is not the last element of the path. In addition,
 * if the only child of a marking temporal relationship is an event task, then the marking
 * temporal relationship is not added to the paths. The reason is, that from a task path point of
 * view, this information is inherently present. Task traversals offer a good way to derive easily
 * comparable task tree representations. This allows for efficient detection of similar tasks. 
 * </p>
 * 
 * @author Patrick Harms
 */
public class TaskTraversal {
    
    /** */
    private List<TaskPath> traversalPaths = new LinkedList<TaskPath>();
    
    /** */
    private TaskPath[] traversalPathArray = null;
    
    /** */
    private ITask task = null;
    
    /**
     *
     */
    public static TaskTraversal getTraversal(ITask                task,
                                             final List<TaskPath> untraversedPaths)
    {
        final TaskTraversal result = new TaskTraversal();
        final TaskPath currentPath = new TaskPath();
        final int[] currentIndex = new int[1];
        currentIndex[0] = 0;
        
        task.accept(new DefaultTaskTraversingVisitor() {
            @Override
            public void visit(IEventTask eventTask) {
                currentPath.add(eventTask, currentIndex[0]);
                result.add(new TaskPath(currentPath));
                currentPath.removeLast();
            }

            @Override
            public void visit(ISequence relationship) {
                currentPath.add(relationship, currentIndex[0]);
                
                if (pathIsInList(currentPath, untraversedPaths)) {
                    result.add(new TaskPath(currentPath));
                }
                else {
                    int indexBuffer = currentIndex[0];
                    
                    List<ITask> children = relationship.getChildren();
                    for (int i = 0; i < children.size(); i++) {
                        currentIndex[0] = i;
                        super.visit(children.get(i));
                    }
                    
                    currentIndex[0] = indexBuffer;
                }
                
                currentPath.removeLast();
            }

            @Override
            public void visit(ISelection relationship) {
                // selections are never traversed as a traversal can have different orders
                // for semantically identical selections
                currentPath.add(relationship, currentIndex[0]);
                result.add(new TaskPath(currentPath));
                currentPath.removeLast();
            }

            @Override
            public void visit(IMarkingTemporalRelationship relationship) {
                ITask markedTask = relationship.getMarkedTask();
                
                while (markedTask instanceof IMarkingTemporalRelationship) {
                    markedTask = ((IMarkingTemporalRelationship) markedTask).getMarkedTask();
                }
                
                currentPath.add(relationship, currentIndex[0]);
                
                if (pathIsInList(currentPath, untraversedPaths)) {
                    result.add(new TaskPath(currentPath));
                }
                // if the child is an event task we do not traverse this marking temporal
                // relationship
                else if (markedTask instanceof IEventTask) {
                    result.add(new TaskPath(currentPath));
                }
                else {
                    int indexBuffer = currentIndex[0];
                    currentIndex[0] = 0;
                    super.visit(relationship);
                    currentIndex[0] = indexBuffer;
                }
                
                currentPath.removeLast();
            }
        });
        
        result.setComplete();

        return result;
    }

    /**
     *
     */
    public int[] getIndexesRootedBy(TaskPath pathToRoot) {
        int[] indexes = new int[] { -1, -1 };
        
        for (int i = 0; i < traversalPathArray.length; i++) {
            TaskPath path = traversalPathArray[i];
            
            // check if the path starts with the path to the root
            if (path.size() >= pathToRoot.size()) {
                boolean startsWithPathToRoot = true;
            
                for (int j = 0; (j < pathToRoot.size()) && (j < path.size()); j++) {
                    if (!pathToRoot.get(j).equals(path.get(j))) {
                        startsWithPathToRoot = false;
                        break;
                    }
                }
                
                if (startsWithPathToRoot) {
                    if (indexes[0] < 0) {
                        indexes[0] = i;
                    }
                    indexes[1] = i;
                }
            }
        }
        
        return indexes;
        
    }

    /**
     *
     */
    public TaskPath[] subList(int fromIndex, int toIndex) {
        return Arrays.copyOfRange(traversalPathArray, fromIndex, toIndex);
    }

    /**
     *
     */
    public ITask getTask() {
        return task;
    }

    /**
     *
     */
    public ITask get(int i) {
        return traversalPathArray[i].getLast();
    }

    /**
     *
     */
    public int size() {
        return traversalPathArray.length;
    }

    /**
     * @return the traversalPaths
     */
    public TaskPath[] getTraversalPaths() {
        return traversalPathArray;
    }

    /**
     *
     */
    public void dump(PrintStream out) {
        for (TaskPath path : traversalPathArray) {
            out.print(path.getLast().getId());
            out.print('\t');
        }
        
        out.println();
    }

    /**
     *
     */
    private void add(TaskPath taskPath) {
        traversalPaths.add(taskPath);
    }
    
    /**
     *
     */
    private void setComplete() {
        traversalPathArray = traversalPaths.toArray(new TaskPath[traversalPaths.size()]);
        traversalPaths = null;
        task = traversalPathArray[0].getTask(0);
    }

    /**
     *
     */
    private static boolean pathIsInList(TaskPath path, List<TaskPath> pathList) {
        if (pathList != null) {
            for (TaskPath candidate : pathList) {
                if (path.equals(candidate)) {
                    return true;
                }
            }
        }
        
        return false;
    }
}
