/*
 * Copyright 2020 Advanced Software Technologies Lab at ETH Zurich, Switzerland
 *
 * 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 com.android.commands.monkey.ape.model;

import java.io.FileInputStream;
import java.io.ObjectInputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.android.commands.monkey.ape.Subsequence;
import com.android.commands.monkey.ape.SubsequenceFilter;
import com.android.commands.monkey.ape.naming.Name;
import com.android.commands.monkey.ape.naming.Naming;
import com.android.commands.monkey.ape.tree.GUITree;
import com.android.commands.monkey.ape.tree.GUITreeAction;
import com.android.commands.monkey.ape.tree.GUITreeTransition;
import com.android.commands.monkey.ape.utils.Logger;
import com.android.commands.monkey.ape.utils.Utils;

public class Graph implements Serializable {

    static abstract class GraphIterator<T> implements Iterator<T> {

        Iterator<StateTransition> iterator;

        GraphIterator(Iterator<StateTransition> iterator) {
            this.iterator = iterator;
        }

        protected StateTransition advance() {
            return iterator.next();
        }

        @Override
        public boolean hasNext() {
            return iterator.hasNext();
        }

    }

    public static Iterator<State> targets(Collection<StateTransition> edges) {
        return new GraphIterator<State>(edges.iterator()) {

            @Override
            public State next() {
                return advance().getTarget();
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException("remove");
            }

        };
    }

    public static Set<State> targetsSet(Collection<StateTransition> edges) {
        Set<State> states = new HashSet<>();
        Iterator<State> it = targets(edges);
        while (it.hasNext()) {
            states.add(it.next());
        }
        return states;
    }

    /**
     * 
     */
    private static final long serialVersionUID = -4227920009231281174L;

    protected Map<StateKey, State> keyToState = new HashMap<>();
    protected Map<String, State> idToState = new HashMap<>();

    private Map<String, ActivityNode> activities = new HashMap<String, ActivityNode>();
    private Map<StateTransition, StateTransition> edges = new HashMap<StateTransition, StateTransition>();
    private Map<State, Map<StateTransition, StateTransition>> stateToOutStateTransitions = new HashMap<>();
    private Map<State, Map<StateTransition, StateTransition>> stateToInStateTransitions = new HashMap<>();
    private Map<ModelAction, Map<StateTransition, StateTransition>> actionToOutStateTransitions = new HashMap<>();

    private Set<State> entryStates = new HashSet<State>();
    private Set<State> cleanEntryStates = new HashSet<State>();
    private Set<GUITree> entryGUITrees = new HashSet<GUITree>();
    private Set<GUITree> cleanEntryGUITrees = new HashSet<GUITree>();

    private Map<Naming, Set<State>> namingToStates = new HashMap<>();

    private /* transient */ Set<ModelAction> unvisitedActions = new HashSet<>();
    private /* transient */ Set<ModelAction> visitedActions = new HashSet<>();

    private transient List<StateTransition> stateTransitionHistory = new ArrayList<>();
    private List<GUITreeTransition> treeTransitionHistory = new ArrayList<>(100);

    private boolean fireEvents;
    private transient List<GraphListener> listeners;
    private int timestamp;

    private int stateCounter = 0;
    private ActionCounters actionCounters = new ActionCounters();

    private String graphId = "g0";

    private Map<String, Map<Name, Set<ModelAction>>> nameToActions = new HashMap<>();

    private boolean verbose = true;
    private transient GraphPathFinder pathFinder = new GraphPathFinder();
    private transient GraphDiagnostics diagnostics = new GraphDiagnostics();

    public int size() {
        return keyToState.size();
    }

    public Set<State> getEntryStates() {
        return this.entryStates;
    }

    public Set<State> getCleanEntryStates() {
        return this.cleanEntryStates;
    }

    public State getNameGlobalTarget(ModelAction action) {
        State state = action.getState();
        Name name = action.getTarget();
        if (name == null) {
            return null;
        }
        String activity = state.getActivity();
        Set<ModelAction> actions = Utils.getFromMapMap(nameToActions, activity, name);
        if (actions == null) {
            return null;
        }
        if (actions.size() <= 1) {
            return null;
        }
        Set<State> targets = new HashSet<>();
        for (ModelAction shared : actions) {
            if (!shared.getType().equals(action.getType())) {
                continue;
            }
            for (StateTransition st : getOutStateTransitions(shared)) {
                targets.add(st.getTarget());
            }
        }
        if (targets.size() == 1) {
            return targets.iterator().next();
        }
        return null;
    }

    public boolean isNameGlobalAction(ModelAction action) {
        return getNameGlobalTarget(action) != null;
    }

    public boolean isActionUnvisitedByName(ModelAction action) {
        if (!action.requireTarget()) {
            return action.isUnvisited();
        }
        State state = action.getState();
        String activity = state.getActivity();
        Set<ModelAction> actions = Utils.getFromMapMap(nameToActions, activity, action.getTarget());
        if (actions == null) {
            return action.isUnvisited();
        }
        for (ModelAction shared : actions) {
            if (shared.isVisited() && shared.getType().equals(action.getType())) {
                return false;
            }
        }
        return true;
    }

    public void setVerbose(boolean verbose) {
        this.verbose = verbose;
    }

    public void setVersion(int version) {
        graphId = "g" + version;
    }

    public ActivityNode getActivityNode(String activity) {
        ActivityNode node = activities.get(activity);
        return node;
    }

    public List<GraphListener> getListeners() {
        if (listeners == null) {
            return Collections.emptyList();
        }
        return listeners;
    }

    private boolean addActivity(State state) {
        String activity = state.getActivity();
        ActivityNode node = activities.get(activity);
        if (node == null) {
            node = new ActivityNode(activity);
            node.addState(state);
            activities.put(activity, node);
            return true;
        }
        node.addState(state);
        return false;
    }

    public void printStatistics() {
        Logger.format(
                "GSTG(%s): activities (%d), states (%d), edges (%d), unvisited actions (%d), visited actions (%d)",
                graphId, activities.size(), size(), edges.size(), unvisitedActions.size(), visitedActions.size());
        for (ActivityNode an : this.activities.values()) {
            Logger.iformat("- %5.2f %3d %s", an.getVisitedRate(), an.getStates().size(), an);
        }
    }


    static State[] EMPTY_TARGETS = new State[0];

    public void addListener(GraphListener listener) {
        if (listeners == null) {
            listeners = new ArrayList<>();
        }
        this.listeners.add(listener);
    }

    public State getOrCreateState(StateKey stateKey) {
        State state = keyToState.get(stateKey);
        if (state == null) {
            state = State.buildState(stateKey);
            state.setGraphId(graphId + "s" + stateCounter++);
            //Logger.dformat("Try to add state " + state.getGraphId() + " " + state.getStateKey());
            fireNewStateEvents(state);
            State check = keyToState.put(stateKey, state);
            if (check != null) {
                state.dumpState();
                check.dumpState();
                throw new IllegalStateException("Impossible: two state has the same key: " + state.getStateKey());
            }
            check = idToState.put(state.getGraphId(), state);
            if (check != null) {
                state.dumpState();
                check.dumpState();
                throw new IllegalStateException("Impossible: two state has the same id: " + state.getGraphId());
            }
            addActivity(state);
            addActions(state);
            Utils.addToMapSet(namingToStates, state.getCurrentNaming(), state);
        }
        return state;
    }

    private void addActions(State state) {
        Map<Name, Set<ModelAction>> actions = Utils.getMapFromMap(nameToActions, state.getActivity());
        for (ModelAction action : state.getActions()) {
            action.setGraphId(graphId + "a" + actionCounters.getTotal());
            actionCounters.logEvent(action.getType());
            unvisitedActions.add(action);
            if (action.requireTarget()) {
                Utils.addToMapSet(actions, action.getTarget(), action);
            }
        }
    }

    static Comparator<GraphElement> LAST_VISIT_COUNT_COMPARATOR = new Comparator<GraphElement>() {

        @Override
        public int compare(GraphElement o1, GraphElement o2) {
            return o1.getLastVisitedTimestamp() - o2.getLastVisitedTimestamp();
        }
    };

    public void disableGraphEvents() {
        this.fireEvents = false;
    }

    public void enableGraphEvents() {
        this.fireEvents = true;
    }

    private void fireNewStateEvents(State node) {
        if (fireEvents == false) {
            return;
        }
        for (GraphListener l : listeners) {
            l.onAddNode(node);
        }
    }

    private void fireStateTransitionEvents(StateTransition edge) {
        if (fireEvents == false) {
            return;
        }
        for (GraphListener l : listeners) {
            l.onVisitStateTransition(edge);
        }
    }

    public int getTimestamp() {
        return timestamp;
    }

    public Iterator<GUITree> getGUITrees() {
        return new Iterator<GUITree>() {
            Iterator<GUITree> treeIterator;
            Iterator<State> stateIterator;
            {
                stateIterator = keyToState.values().iterator();
                if (stateIterator.hasNext()) {
                    treeIterator = stateIterator.next().getGUITrees().iterator();
                } else {
                    treeIterator = null;
                }
            }

            @Override
            public boolean hasNext() {
                if (treeIterator == null) {
                    return false;
                }
                if (!treeIterator.hasNext()) {
                    if (stateIterator.hasNext()) {
                        treeIterator = stateIterator.next().getGUITrees().iterator();
                        return treeIterator.hasNext();
                    } else {
                        treeIterator = null;
                        return false;
                    }
                } else {
                    return true;
                }
            }

            @Override
            public GUITree next() {
                return treeIterator.next();
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException("remove");
            }
        };
    }

    public int getAverageVisitedCount() {
        int size = this.size();
        if (size == 0) {
            return 0;
        }
        return this.timestamp / size;
    }

    public StateTransition addTransition(State source, ModelAction action, State target, GUITree sourceTree,
            GUITreeAction treeAction, GUITree targetTree) {
        StateTransition edge = addStateTransition(source, action, target);
        if (edge == null) {
            return null;
        }
        GUITreeTransition treeTransition = new GUITreeTransition(sourceTree, treeAction, targetTree);
        treeTransition.setThrottle(action.getThrottle());
        edge.updateThrottle(treeTransition.getThrottle());
        stateTransitionHistory.add(edge);
        treeTransitionHistory.add(treeTransition);
        edge.append(treeTransition);

        edge.strengthen();
        markVisited(edge, timestamp);
        fireStateTransitionEvents(edge);
        if (this.entryGUITrees.contains(sourceTree)) {
            this.entryStates.add(source);
        }
        if (this.cleanEntryGUITrees.contains(sourceTree)) {
            this.cleanEntryStates.add(source);
        }
        return edge;
    }

    public StateTransition addTransition(State source, ModelAction action, State target, GUITreeTransition treeTransition) {
        StateTransition edge = addStateTransition(source, action, target);
        if (edge == null) {
            throw new IllegalStateException("Should not be null.");
        }
        if (this.entryGUITrees.contains(treeTransition.getSource())) {
            this.entryStates.add(source);
        }
        if (this.cleanEntryGUITrees.contains(treeTransition.getSource())) {
            this.cleanEntryStates.add(source);
        }
        edge.strengthen();
        stateTransitionHistory.add(edge);
        edge.updateThrottle(treeTransition.getThrottle());
        edge.append(treeTransition);
        int timestamp = treeTransition.getTimestamp();
        if (timestamp == -1) {
            throw new IllegalStateException("Untracked GUI tree transition..");
        }
        markVisited(source, timestamp);
        markVisited(action, timestamp);
        markVisited(edge, timestamp);
        return edge;
    }

    private StateTransition addStateTransition(State source, ModelAction action, State target) {
        boolean added = false;
        if (target == null) {
            throw new RuntimeException("Target state should never be null");
        }
        StateTransition edge = null;
        if (source != null) {
            edge = new StateTransition(source, action, target);
            added = Utils.addToMapMapIfAbsent(actionToOutStateTransitions, action, edge, edge);
            if (verbose) {
                Logger.println("=== Adding edge...");
                Logger.println("    Source: " + source);
                Logger.println("    Action: " + action);
                Logger.println("    Target: " + target);
                Logger.println("    Add target result: " + added);
            }
            if (added != Utils.addToMapMapIfAbsent(stateToOutStateTransitions, source, edge, edge)) {
                throw new IllegalStateException("Sanity check failed");
            }
            if (added != Utils.addToMapMapIfAbsent(stateToInStateTransitions, target, edge, edge)) {
                throw new IllegalStateException("Sanity check failed");
            }
            if (added) {
                edge.setGraphId(graphId + "e" + edges.size());
                Utils.putIfAbsent(edges, edge, edge);
                if (actionToOutStateTransitions.get(action).size() == 1) {
                    edge.setType(StateTransitionVisitType.NEW_ACTION);
                } else {
                    edge.setType(StateTransitionVisitType.NEW_ACTION_TARGET);
                }
            } else {
                StateTransition existing = edges.get(edge);
                if (existing == null || existing == edge) {
                    throw new IllegalStateException();
                }
                edge = existing;
                edge.setType(StateTransitionVisitType.EXISTING);
            }
        }
        timestamp++;
        if (verbose) {
            printStatistics();
            Logger.format("GSTG is %supdated.", (added ? "" : "NOT "));
            Logger.format("GSTG state is %schanged.", (target.equals(source) ? "NOT " : ""));
        }
        return edge;
    }

    public void weakenStateTransition(State source, ModelAction action, State target) {
        StateTransition edge = this.edges.get(new StateTransition(source, action, target));
        if (edge == null) {
            throw new IllegalArgumentException("Cannot update a non-existing edge");
        }
        edge.weaken();
    }

    public Set<StateTransition> getOutStateTransitions(State state) {
        Map<StateTransition, StateTransition> ret = stateToOutStateTransitions.get(state);
        if (ret == null) {
            return Collections.emptySet();
        }
        return ret.keySet();
    }

    public Collection<StateTransition> getOutStateTransitions(ModelAction action) {
        Map<StateTransition, StateTransition> ret = actionToOutStateTransitions.get(action);
        if (ret == null) {
            return Collections.emptySet();
        }
        return ret.keySet();
    }

    public Set<StateTransition> getInStateTransitions(State state) {
        Map<StateTransition, StateTransition> ret = stateToInStateTransitions.get(state);
        if (ret == null) {
            return Collections.emptySet();
        }
        return ret.keySet();
    }

    public Subsequence findShortestPath(SubsequenceFilter filter, State current) {
        return pathFinder.findShortestPath(this, filter, current);
    }

    public void markVisited(ModelAction action, int timestamp) {
        if (!action.getType().isModelAction()) {
            return;
        }
        if (action.isUnvisited()) {
            if (!this.unvisitedActions.remove(action)) {
                throw new RuntimeException("sanity check failed, action should be added " + action);
            }
            action.visitedAt(timestamp);
            this.visitedActions.add(action);
        } else if (visitedActions.contains(action)) {
            action.visitedAt(timestamp);
        } else {
            Logger.println("Untracked action: " + action);
            Logger.println("State is " + action.getState());
            if (this.unvisitedActions.contains(action)) {
                throw new RuntimeException("Unvisited actions should not be marked visited.");
            }
            throw new RuntimeException("sanity check failed");
        }
    }

    public void markVisited(State node, int timestamp) {
        node.visitedAt(timestamp);
        markVisited(node.getActivity(), timestamp);
    }

    private void markVisited(StateTransition edge, int timestamp) {
        if (!edges.containsKey(edge)) {
            throw new RuntimeException("Sanity check failed!");
        }
        edge.visitedAt(timestamp);
    }

    private void markVisited(String activity, int timestamp) {
        ActivityNode node = getActivityNode(activity);
        node.visitedAt(timestamp);
    }

    public int getWeakOutStateTransitions(State state, int threshold) {
        Map<StateTransition, StateTransition> ret = stateToOutStateTransitions.get(state);
        if (ret == null) {
            return 0;
        }
        int count = 0;
        for (StateTransition edge : ret.keySet()) {
            if (edge.getStrength() < threshold) {
                count++;
            }
        }
        return count;
    }

    public int getWeakOutStateTransitions(State state) {
        Map<StateTransition, StateTransition> ret = stateToOutStateTransitions.get(state);
        if (ret == null) {
            return 0;
        }
        int count = 0;
        for (StateTransition edge : ret.keySet()) {
            if (!edge.isStrong()) {
                count++;
            }
        }
        return count;
    }

    public Collection<State> getStates() {
        return this.keyToState.values();
    }

    // TODO: Use TreeSet
    public Collection<StateTransition> sortStateTransitionsByLastVisitedCount(Set<StateTransition> edges) {
        StateTransition[] results = new StateTransition[edges.size()];
        results = edges.toArray(results);
        Arrays.sort(results, LAST_VISIT_COUNT_COMPARATOR);
        return Arrays.asList(results);
    }

    public List<Subsequence> findShortestPaths(State current, SubsequenceFilter filter, int pathLength) {
        List<Subsequence> selectedPaths = new ArrayList<>();
        findShortestPaths(selectedPaths, current, filter, pathLength);
        return selectedPaths;
    }

    public void findShortestPaths(List<Subsequence> selectedPaths, State current, SubsequenceFilter filter,
            int pathLength) {
        pathFinder.findShortestPaths(this, selectedPaths, current, filter, pathLength);
    }


    public boolean isReachable(Collection<State> from, State to) {
        return pathFinder.isReachable(this, from, to);
    }

    public void moveToState(List<Subsequence> selectedPaths, State current, final State end, final boolean includeBack, int pathLength) {
        pathFinder.moveToState(this, selectedPaths, current, end, includeBack, pathLength);
    }

    /**
     * 
     * @param states,
     *            A*B
     * @return
     */
    public Subsequence fillTransitionsByHistory(final State[] states) {
        return pathFinder.fillTransitionsByHistory(stateTransitionHistory, states);
    }

    public void fillTransitions(List<Subsequence> selectedPaths, final State[] states) {
        pathFinder.fillTransitions(this, selectedPaths, states);
    }

    public boolean hasInStateTransitionFrom(State thisState, State other) {
        Set<StateTransition> edges = getInStateTransitions(thisState);
        if (edges.isEmpty()) {
            return false;
        }
        for (StateTransition e : edges) {
            if (e.source.equals(other)) {
                return true;
            }
        }
        return false;
    }

    public void printActivityNodes() {
        diagnostics.printActivityNodes(activities, nameToActions, entryStates, namingToStates);
    }

    /**
     * How many edges of a state
     * 
     * @param state
     * @return
     */
    public int getCountOfOutStateTransitions(State state) {
        Map<StateTransition, StateTransition> edges = this.stateToOutStateTransitions.get(state);
        if (edges == null) {
            return 0;
        }
        return edges.size();
    }

    /**
     * How many actions have been visited on a state
     * 
     * @param state
     * @return
     */
    public int getCountOfOutActions(State state) {
        int count = 0;
        for (ModelAction action : state.getActions()) {
            if (this.actionToOutStateTransitions.containsKey(action)) {
                count++;
            }
        }
        return count;
    }

    public StateTransition findStateTransition(State source, ModelAction action, State target) {
        return this.edges.get(new StateTransition(source, action, target));
    }

    public StateTransition getStateTransition(State source, ModelAction action, State target) {
        StateTransition edge = findStateTransition(source, action, target);
        if (edge == null) {
            throw new IllegalArgumentException("Cannot update a non-existing edge");
        }
        return edge;
    }

    public static Graph readGraph(String modelFile) {
        try (ObjectInputStream ois = new ObjectInputStream(new FileInputStream(modelFile))) {
            return (Graph) ois.readObject();
        } catch (Exception e) {
            e.printStackTrace();
            Logger.println("Fail to load graph from " + modelFile);
        }
        return new Graph();
    }

    public int getCountOfUnvisitedActions() {
        return this.unvisitedActions.size();
    }

    public void printStateTransitions() {
        diagnostics.printStateTransitions(edges.keySet());
    }

    public String formatStateTransition(StateTransition edge) {
        return diagnostics.formatStateTransition(edge);
    }

    public ActivityNode[] getActivityNodes() {
        return activities.values().toArray(new ActivityNode[0]);
    }

    public int getCountOfActivities() {
        return this.activities.size();
    }

    public StateTransition getStateTransition(GUITreeTransition tt) {
        StateTransition st = tt.getCurrentStateTransition();
        if (st == null) {
            throw new IllegalStateException("Invalid tree transition");
        }
        if (!edges.containsKey(st)) {
            throw new IllegalStateException("Dangling tree transition");
        }
        return st;
    }

    public boolean isLikeBack(ModelAction action) {
        if (action.isBack()) {
            return true;
        }
        if (!action.isClick()) {
            return false;
        }
        State state = action.getState();
        ModelAction back = state.getBackAction();
        if (!back.isVisited()) {
            return false;
        }
        throw new RuntimeException("Not implemented");
    }

    void remove(State state, Collection<StateTransition> removed) {
        Logger.dformat("> Removing state %s", state);
        {
            Map<StateTransition, StateTransition> inStateTransitions = this.stateToInStateTransitions.remove(state);
            if (inStateTransitions != null && inStateTransitions.size() > 0) {
                Collection<StateTransition> temp = inStateTransitions.values();
                removed.addAll(temp);
                for (StateTransition edge : temp) {
                    this.edges.remove(edge);
                    State source = edge.getSource();
                    ModelAction action = edge.getAction();
                    Utils.removeFromMapMap(this.actionToOutStateTransitions, action, edge);
                    Utils.removeFromMapMap(this.stateToOutStateTransitions, source, edge);
                    Utils.removeFromMapMap(this.stateToInStateTransitions, edge.getTarget(), edge);
                }
            }
        }
        {
            Map<StateTransition, StateTransition> outStateTransitions = this.stateToOutStateTransitions.remove(state);
            if (outStateTransitions != null && outStateTransitions.size() > 0) {
                Collection<StateTransition> temp = outStateTransitions.values();
                removed.addAll(temp);
                for (StateTransition edge : temp) {
                    this.edges.remove(edge);
                    State target = edge.getTarget();
                    ModelAction action = edge.getAction();
                    Utils.removeFromMapMap(this.actionToOutStateTransitions, action, edge);
                    Utils.removeFromMapMap(this.stateToInStateTransitions, target, edge);
                    Utils.removeFromMapMap(this.stateToOutStateTransitions, edge.getSource(), edge);
                }
            }
        }
        {
            ActivityNode an = this.getActivityNode(state.getActivity());
            an.removeState(state);
        }
        {
            Map<Name, Set<ModelAction>> actions = Utils.getMapFromMap(nameToActions, state.getActivity());
            for (ModelAction action : state.getActions()) {
                this.unvisitedActions.remove(action);
                this.visitedActions.remove(action);
                if (action.requireTarget()) {
                    Utils.removeFromMapSet(actions, action.getTarget(), action);
                    if (actions.get(action.getTarget()).isEmpty()) {
                        actions.remove(action.getTarget());
                    }
                }
            }
        }
        {
            this.entryStates.remove(state);
            this.cleanEntryStates.remove(state);
            this.keyToState.remove(state.getStateKey());
            this.idToState.remove(state.getGraphId());
        }
        {
            Utils.removeFromMapSet(namingToStates, state.getCurrentNaming(), state);
        }
    }

    public Set<State> getStates(Naming naming) {
        Set<State> states = this.namingToStates.get(naming);
        if (states == null) {
            return Collections.emptySet();
        }
        return states;
    }

    public Set<State> getAllStates(Naming naming) {
        Set<State> states = new HashSet<State>();
        getAllStates(states, naming);
        return states;
    }

    private void getAllStates(Set<State> states, Naming naming) {
        states.addAll(getStates(naming));
        for (Naming child : naming.getChildren()) {
            getAllStates(states, child);
        }
    }

    void rebuildHistory() {
        if (stateTransitionHistory == null) {
            stateTransitionHistory = new ArrayList<>(this.treeTransitionHistory.size() << 1);
        } else {
            stateTransitionHistory.clear();
        }
        for (GUITreeTransition tt : this.treeTransitionHistory) {
            StateTransition edge = (StateTransition) tt.getCurrentStateTransition();
            int fv = edge.getFirstVisitedTimestamp();
            int lv = edge.getLastVisitedTimestamp();
            if (fv == -1 || fv > tt.getTimestamp()) {
                edge.firstVisitTimestamp = fv;
            }
            if (lv == -1 || lv < tt.getTimestamp()) {
                edge.lastVisitTimestamp = lv;
            }
            edge.visitedCount++;
            stateTransitionHistory.add(edge);
        }
    }

    public List<GUITreeTransition> getTreeHistory() {
        return treeTransitionHistory;
    }

    public boolean contains(State state) {
        State check = this.keyToState.get(state.getStateKey());
        if (check == null) {
            return false;
        }
        if (check != state) {
            Logger.wprintln("==========================================");
            Logger.wprintln("Duplicated states with the same key");
            Logger.wprintln("   given: " + state);
            Logger.wprintln("existing: " + check);
            Logger.wprintln("------------------------------------------");
            state.dumpState();
            Logger.wprintln("------------------------------------------");
            check.dumpState();
            Logger.wprintln("==========================================");
            throw new RuntimeException("Sanity check failed!");
        }
        return check == state;
    }

    public void addEntryGUITree(GUITree tree) {
        this.entryGUITrees.add(tree);
    }

    public void addCleanEntryGUITree(GUITree tree) {
        this.cleanEntryGUITrees.add(tree);
    }

    public boolean isEntryState(State state) {
        return this.entryStates.contains(state);
    }

    public boolean isCleanEntryState(State state) {
        return this.cleanEntryStates.contains(state);
    }

    public List<Subsequence> moveToState(State from, State to, boolean includeBack, int maxLength) {
        List<Subsequence> selectedPaths = new ArrayList<>();
        moveToState(selectedPaths, from, to, includeBack, maxLength);
        return selectedPaths;
    }
    public List<Subsequence> moveToState(State from, State to, boolean includeBack) {
        List<Subsequence> selectedPaths = new ArrayList<>();
        moveToState(selectedPaths, from, to, includeBack, Integer.MAX_VALUE);
        return selectedPaths;
    }

    public List<Subsequence> moveToState(State from, State to, int pathLength) {
        List<Subsequence> selectedPaths = new ArrayList<>();
        moveToState(selectedPaths, from, to, true, pathLength);
        return selectedPaths;
    }

    public Set<StateTransition> remove(State state) {
        Set<StateTransition> removed = new HashSet<>();
        remove(state, removed);
        return removed;
    }

    public List<Collection<StateTransition>> getTransitionsByName(ModelAction action) {
        List<Collection<StateTransition>> results = new ArrayList<>();
        if (!action.requireTarget()) {
            return Collections.emptyList();
        }
        Set<ModelAction> actions = Utils.getFromMapMap(nameToActions, action.getState().getActivity(), action.getTarget());
        if (actions == null || actions.isEmpty()) {
            return Collections.emptyList();
        }
        for (ModelAction a : actions) {
            if (a.getType().equals(action.getType())) {
                results.add(getOutStateTransitions(a));
            }
        }
        return results;
    }


}