/**********************************************************************
 * Copyright (c) 2018 Ericsson
 *
 * All rights reserved. This program and the accompanying materials are
 * made available under the terms of the Eclipse Public License v1.0 which
 * accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 **********************************************************************/

package org.eclipse.tracecompass.internal.analysis.graph.core.dataprovider;

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.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.atomic.AtomicLong;
import java.util.function.Predicate;

import org.eclipse.core.runtime.IProgressMonitor;
import org.eclipse.jdt.annotation.NonNull;
import org.eclipse.jdt.annotation.Nullable;
import org.eclipse.tracecompass.analysis.graph.core.base.IGraphWorker;
import org.eclipse.tracecompass.analysis.graph.core.base.TmfEdge;
import org.eclipse.tracecompass.analysis.graph.core.base.TmfEdge.EdgeType;
import org.eclipse.tracecompass.analysis.graph.core.base.TmfGraph;
import org.eclipse.tracecompass.analysis.graph.core.base.TmfVertex;
import org.eclipse.tracecompass.analysis.graph.core.criticalpath.CriticalPathModule;
import org.eclipse.tracecompass.internal.analysis.graph.core.base.TmfGraphStatistics;
import org.eclipse.tracecompass.internal.analysis.graph.core.base.TmfGraphVisitor;
import org.eclipse.tracecompass.internal.tmf.core.model.AbstractTmfTraceDataProvider;
import org.eclipse.tracecompass.internal.tmf.core.model.filters.TimeGraphStateQueryFilter;
import org.eclipse.tracecompass.tmf.core.model.CommonStatusMessage;
import org.eclipse.tracecompass.tmf.core.model.filters.SelectionTimeQueryFilter;
import org.eclipse.tracecompass.tmf.core.model.filters.TimeQueryFilter;
import org.eclipse.tracecompass.tmf.core.model.timegraph.ITimeGraphArrow;
import org.eclipse.tracecompass.tmf.core.model.timegraph.ITimeGraphDataProvider;
import org.eclipse.tracecompass.tmf.core.model.timegraph.ITimeGraphRowModel;
import org.eclipse.tracecompass.tmf.core.model.timegraph.ITimeGraphState;
import org.eclipse.tracecompass.tmf.core.model.timegraph.TimeGraphArrow;
import org.eclipse.tracecompass.tmf.core.model.timegraph.TimeGraphRowModel;
import org.eclipse.tracecompass.tmf.core.model.timegraph.TimeGraphState;
import org.eclipse.tracecompass.tmf.core.response.ITmfResponse.Status;
import org.eclipse.tracecompass.tmf.core.response.TmfModelResponse;
import org.eclipse.tracecompass.tmf.core.trace.ITmfTrace;

import com.google.common.cache.CacheBuilder;
import com.google.common.cache.CacheLoader;
import com.google.common.cache.LoadingCache;
import com.google.common.collect.BiMap;
import com.google.common.collect.HashBiMap;
import com.google.common.collect.Multimap;
import com.google.common.collect.TreeMultimap;

/**
 * Data Provider for the Critical Path.
 *
 * @author Loic Prieur-Drevon
 */
public class CriticalPathDataProvider extends AbstractTmfTraceDataProvider implements ITimeGraphDataProvider<@NonNull CriticalPathEntry> {

    /**
     * Extension point ID for the provider
     */
    public static final @NonNull String ID = "org.eclipse.tracecompass.analysis.graph.core.dataprovider.CriticalPathDataProvider"; //$NON-NLS-1$
    /**
     * Atomic long to assign each entry the same unique ID every time the data
     * provider is queried
     */
    private static final AtomicLong ATOMIC_LONG = new AtomicLong();

    private @NonNull CriticalPathModule fCriticalPathModule;

    /**
     * Remember the unique mappings from hosts to their entry IDs
     */
    private final Map<String, Long> fHostIdToEntryId = new HashMap<>();
    /**
     * Remember the unique mappings from workers to their entry IDs
     */
    private final BiMap<IGraphWorker, Long> fWorkerToEntryId = HashBiMap.create();

    private final LoadingCache<IGraphWorker, CriticalPathVisitor> fHorizontalVisitorCache = CacheBuilder.newBuilder()
            .maximumSize(10).build(new CacheLoader<IGraphWorker, CriticalPathVisitor>() {

                @Override
                public CriticalPathVisitor load(IGraphWorker key) throws Exception {
                    TmfGraph criticalPath = fCriticalPathModule.getCriticalPath();
                    return new CriticalPathVisitor(criticalPath, key);
                }
            });

    /**
     * FIXME when switching between traces, the current worker is set to null, do
     * this to remember the last arrows used.
     */
    private List<ITimeGraphArrow> fLinks;

    /**
     * Constructor
     *
     * @param trace
     *            The trace for which we will be providing the time graph models
     * @param criticalPathProvider
     *            the critical path module for this trace
     */
    public CriticalPathDataProvider(@NonNull ITmfTrace trace, @NonNull CriticalPathModule criticalPathProvider) {
        super(trace);
        fCriticalPathModule = criticalPathProvider;
    }

    @Override
    public synchronized @NonNull TmfModelResponse<@NonNull List<@NonNull CriticalPathEntry>> fetchTree(
            @NonNull TimeQueryFilter filter, @Nullable IProgressMonitor monitor) {
        TmfGraph graph = fCriticalPathModule.getCriticalPath();
        if (graph == null) {
            return new TmfModelResponse<>(null, Status.RUNNING, CommonStatusMessage.RUNNING);
        }

        IGraphWorker current = getCurrent();
        if (current == null) {
            return new TmfModelResponse<>(null, Status.COMPLETED, CommonStatusMessage.COMPLETED);
        }

        CriticalPathVisitor visitor = fHorizontalVisitorCache.getUnchecked(current);
        return new TmfModelResponse<>(visitor.getEntries(), Status.COMPLETED, CommonStatusMessage.COMPLETED);
    }

    /**
     * Get the current {@link IGraphWorker} from the {@link CriticalPathModule}
     *
     * @return the current graph worker if it is set, else null.
     */
    private @Nullable IGraphWorker getCurrent() {
        Object obj = fCriticalPathModule.getParameter(CriticalPathModule.PARAM_WORKER);
        if (obj == null) {
            return null;
        }
        if (!(obj instanceof IGraphWorker)) {
            throw new IllegalStateException("Wrong type for critical path module parameter " + //$NON-NLS-1$
                    CriticalPathModule.PARAM_WORKER +
                    " expected IGraphWorker got " + //$NON-NLS-1$
                    obj.getClass().getSimpleName());
        }
        return (IGraphWorker) obj;
    }

    @Override
    public @NonNull String getId() {
        return ID;
    }

    @Override
    public @NonNull TmfModelResponse<@NonNull List<@NonNull ITimeGraphRowModel>> fetchRowModel(@NonNull SelectionTimeQueryFilter filter, @Nullable IProgressMonitor monitor) {
        IGraphWorker graphWorker = getCurrent();
        if (graphWorker == null) {
            return new TmfModelResponse<>(null, Status.COMPLETED, CommonStatusMessage.COMPLETED);
        }
        CriticalPathVisitor visitor = fHorizontalVisitorCache.getIfPresent(graphWorker);
        if (visitor == null) {
            return new TmfModelResponse<>(null, Status.COMPLETED, CommonStatusMessage.COMPLETED);
        }

        Map<@NonNull Integer, @NonNull Predicate<@NonNull Multimap<@NonNull String, @NonNull String>>> predicates = new HashMap<>();
        if (filter instanceof TimeGraphStateQueryFilter) {
            TimeGraphStateQueryFilter timeEventFilter = (TimeGraphStateQueryFilter) filter;
            predicates.putAll(computeRegexPredicate(timeEventFilter));
        }

        List<@NonNull ITimeGraphRowModel> rowModels = new ArrayList<>();
        for (Long id : filter.getSelectedItems()) {
            /*
             * need to use asMap, so that we don't return a row for an ID that does not
             * belong to this provider, else fStates.get(id) might return an empty
             * collection for an id from another data provider.
             */
            Collection<ITimeGraphState> states = visitor.fStates.asMap().get(id);
            if (states != null) {
                List<ITimeGraphState> filteredStates = new ArrayList<>();
                for (ITimeGraphState state : states) {
                    if (overlaps(state.getStartTime(), state.getDuration(), filter.getTimesRequested())) {
                        // Reset the properties for this state before filtering
                        state.setActiveProperties(0);
                        applyFilterAndAddState(filteredStates, state, id, predicates, monitor);
                    }
                }
                rowModels.add(new TimeGraphRowModel(id, filteredStates));
            }
        }
        return new TmfModelResponse<>(rowModels, Status.COMPLETED, CommonStatusMessage.COMPLETED);
    }

    private static final boolean overlaps(long start, long duration, long[] times) {
        int pos = Arrays.binarySearch(times, start);
        if (pos >= 0) {
            // start is one of the times
            return true;
        }
        int ins = -pos - 1;
        if (ins >= times.length) {
            // start is larger than the last time
            return false;
        }
        /*
         * the first queried time which is larger than the state start time, is also
         * smaller than the state end time. I.e. at least one queried time is in the
         * state range
         */
        return times[ins] <= start + duration;
    }

    @Override
    public @NonNull TmfModelResponse<@NonNull List<@NonNull ITimeGraphArrow>> fetchArrows(@NonNull TimeQueryFilter filter, @Nullable IProgressMonitor monitor) {
        return new TmfModelResponse<>(getLinkList(filter.getStart(), filter.getEnd()), Status.COMPLETED, CommonStatusMessage.COMPLETED);
    }

    @Override
    public @NonNull TmfModelResponse<@NonNull Map<@NonNull String, @NonNull String>> fetchTooltip(@NonNull SelectionTimeQueryFilter filter, @Nullable IProgressMonitor monitor) {
        IGraphWorker worker = fWorkerToEntryId.inverse().get(filter.getSelectedItems().iterator().next());
        if (worker == null) {
            return new TmfModelResponse<>(null, Status.COMPLETED, CommonStatusMessage.COMPLETED);
        }
        Map<@NonNull String, @NonNull String> info = worker.getWorkerInformation(filter.getStart());
        return new TmfModelResponse<>(info, Status.COMPLETED, CommonStatusMessage.COMPLETED);
    }

    private final class CriticalPathVisitor extends TmfGraphVisitor {
        private final TmfGraph fGraph;
        /**
         * The {@link IGraphWorker} for which the view (tree / states) are computed
         */
        private final Map<String, CriticalPathEntry> fHostEntries = new HashMap<>();
        private final Map<IGraphWorker, CriticalPathEntry> fWorkers = new LinkedHashMap<>();
        private final TmfGraphStatistics fStatistics = new TmfGraphStatistics();

        /**
         * Store the states in a {@link TreeMultimap} so that they are grouped by entry
         * and sorted by start time.
         */
        private final TreeMultimap<Long, ITimeGraphState> fStates = TreeMultimap.create(Comparator.naturalOrder(),
                Comparator.comparingLong(ITimeGraphState::getStartTime));
        private long fStart;
        private long fEnd;
        private List<@NonNull CriticalPathEntry> fCached;
        /**
         * Cache the links once the graph has been traversed.
         */
        private @Nullable List<ITimeGraphArrow> fGraphLinks;

        private CriticalPathVisitor(TmfGraph graph, IGraphWorker worker) {
            fGraph = graph;
            fStart = getTrace().getStartTime().toNanos();
            fEnd = getTrace().getEndTime().toNanos();

            TmfVertex head = graph.getHead();
            if (head != null) {
                fStart = Long.min(fStart, head.getTs());
                for (IGraphWorker w : graph.getWorkers()) {
                    TmfVertex tail = graph.getTail(w);
                    if (tail != null) {
                        fEnd = Long.max(fEnd, tail.getTs());
                    }
                }
            }
            fStatistics.computeGraphStatistics(graph, worker);
        }

        @Override
        public void visitHead(TmfVertex node) {
            IGraphWorker owner = fGraph.getParentOf(node);
            if (owner == null) {
                return;
            }
            if (fWorkers.containsKey(owner)) {
                return;
            }
            TmfVertex first = fGraph.getHead(owner);
            TmfVertex last = fGraph.getTail(owner);
            if (first == null || last == null) {
                return;
            }
            fStart = Long.min(getTrace().getStartTime().toNanos(), first.getTs());
            fEnd = Long.max(getTrace().getEndTime().toNanos(), last.getTs());
            Long sum = fStatistics.getSum(owner);
            Double percent = fStatistics.getPercent(owner);

            // create host entry
            String host = owner.getHostId();
            long parentId = fHostIdToEntryId.computeIfAbsent(host, h -> ATOMIC_LONG.getAndIncrement());
            fHostEntries.computeIfAbsent(host, h -> new CriticalPathEntry(parentId, -1L, host, fStart, fEnd, sum, percent));

            long entryId = fWorkerToEntryId.computeIfAbsent(owner, w -> ATOMIC_LONG.getAndIncrement());
            CriticalPathEntry entry = new CriticalPathEntry(entryId, parentId, owner, fStart, fEnd, sum, percent);

            fWorkers.put(owner, entry);
        }

        @Override
        public void visit(TmfEdge link, boolean horizontal) {
            if (horizontal) {
                IGraphWorker parent = fGraph.getParentOf(link.getVertexFrom());
                Long id = fWorkerToEntryId.get(parent);
                if (id != null) {
                    String linkQualifier = link.getLinkQualifier();
                    ITimeGraphState ev = (linkQualifier == null) ? new TimeGraphState(link.getVertexFrom().getTs(), link.getDuration(), getMatchingState(link.getType())) :
                        new TimeGraphState(link.getVertexFrom().getTs(), link.getDuration(), getMatchingState(link.getType()), linkQualifier);
                    fStates.put(id, ev);
                }
            } else {
                IGraphWorker parentFrom = fGraph.getParentOf(link.getVertexFrom());
                IGraphWorker parentTo = fGraph.getParentOf(link.getVertexTo());
                CriticalPathEntry entryFrom = fWorkers.get(parentFrom);
                CriticalPathEntry entryTo = fWorkers.get(parentTo);
                List<ITimeGraphArrow> graphLinks = fGraphLinks;
                if (graphLinks != null && entryFrom != null && entryTo != null) {
                    ITimeGraphArrow lk = new TimeGraphArrow(entryFrom.getId(), entryTo.getId(), link.getVertexFrom().getTs(),
                            link.getVertexTo().getTs() - link.getVertexFrom().getTs(), getMatchingState(link.getType()));
                    graphLinks.add(lk);
                }
            }
        }

        public @NonNull List<@NonNull CriticalPathEntry> getEntries() {
            if (fCached != null) {
                return fCached;
            }

            fGraph.scanLineTraverse(fGraph.getHead(), this);
            List<@NonNull CriticalPathEntry> list = new ArrayList<>(fHostEntries.values());
            list.addAll(fWorkers.values());
            fCached = list;
            return list;
        }

        public synchronized List<ITimeGraphArrow> getGraphLinks() {
            if (fGraphLinks == null) {
                // the graph has not been traversed yet
                fGraphLinks = new ArrayList<>();
                fGraph.scanLineTraverse(fGraph.getHead(), this);
            }
            return fGraphLinks;
        }
    }

    /**
     * Critical path typically has relatively few links, so we calculate and save
     * them all, but just return those in range
     */
    private @Nullable List<@NonNull ITimeGraphArrow> getLinkList(long startTime, long endTime) {
        IGraphWorker current = getCurrent();
        List<ITimeGraphArrow> graphLinks = fLinks;
        if (current == null) {
            if (graphLinks != null) {
                return graphLinks;
            }
            return Collections.emptyList();
        }
        CriticalPathVisitor visitor = fHorizontalVisitorCache.getIfPresent(current);
        if (visitor == null) {
            return Collections.emptyList();
        }
        graphLinks = visitor.getGraphLinks();
        fLinks = graphLinks;
        return getLinksInRange(graphLinks, startTime, endTime);
    }

    private static List<@NonNull ITimeGraphArrow> getLinksInRange(List<ITimeGraphArrow> allLinks, long startTime, long endTime) {
        List<@NonNull ITimeGraphArrow> linksInRange = new ArrayList<>();
        for (ITimeGraphArrow link : allLinks) {
            if (link.getStartTime() <= endTime &&
                    link.getStartTime() + link.getDuration() >= startTime) {
                linksInRange.add(link);
            }
        }
        return linksInRange;
    }

    private static int getMatchingState(EdgeType type) {
        switch (type) {
        case RUNNING:
            return 0;
        case INTERRUPTED:
            return 1;
        case PREEMPTED:
            return 2;
        case TIMER:
            return 3;
        case BLOCK_DEVICE:
            return 4;
        case USER_INPUT:
            return 5;
        case NETWORK:
            return 6;
        case IPI:
            return 7;
        case EPS:
        case UNKNOWN:
        case DEFAULT:
        case BLOCKED:
            break;
        default:
            break;
        }
        return 8;
    }

}