package de.renew.engine.searcher;

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

import org.apache.log4j.Logger;

import de.renew.engine.thread.SimulationThreadPool;
import de.renew.unify.CalculationChecker;
import de.renew.unify.ICalculationChecker;
import de.renew.unify.IStateRecorder;
import de.renew.unify.Impossible;
import de.renew.unify.StateRecorder;
import de.renew.unify.Variable;

/**
 * This class implements the search algorithm that is used
 * to find bindings for occurrences.
 * <p>
 * A search is initiated by calling {@link #searchAndRecover}
 * or {@link #initiatedSearch}.
 * <p>
 * The searcher maintains a set of {@link Occurrence} objects
 * that are currently considered for binding.
 * Each occurrence can generate a set of {@link Binder} objects
 * that are currently considered for binding.
 * The searcher repeatedly selects one binder with the best
 * binding badness and tries to bind it.
 * If the binding is successful, the searcher continues
 * with the next binder.
 * If the binding fails, the searcher restores the state
 * to before the binding was attempted and tries the next
 * binder.
 * <p>
 * If all binders have been tried and there are no more
 * binders left, but all calculations are consistent,
 * a binding has been found and is reported to the
 * {@link Finder} object that was given when starting
 * the search.
 * <p>
 * After each attempt to bind a binder, successful or not,
 * the state is restored to before the attempt. This ensures
 * that no side effects of failed attempts remain.
 */
public class Searcher implements ISearcher {
    private static final Logger LOGGER = Logger.getLogger(Searcher.class);

    /**
     * The object that is informed about every
     * successfully detected binding.
     */
    private Finder _finder;

    /**
     * the set of current unprocessed {@link Binder}s
     */
    private final Set<Binder> _binders;

    /**
     * the set of {@link Occurrence} object (normally
     * transition occurrences) that participate
     * in this search and in the subsequent execution.
     */
    private final Set<Occurrence> _occurrences;

    /**
     * the object which is informed about
     */
    private Triggerable _primaryTriggerable;
    private double _earliestTime;

    /**
     * The calculation checker.
     */
    private final ICalculationChecker _calcChecker;

    /**
     * The state recorder.
     */
    private final IStateRecorder _stateRecorder;
    private final Map<String, DeltaSet> _deltaSets;

    /**
     * Construct a cleanly initialized instance.
     */
    public Searcher() {
        this(new HashSet<>(), new HashMap<>());
    }

    /**
     * Constructor setting the primary triggerable and the finder to the given values.
     * <p>
     * This constructor is used by the Distribute plug-in
     * ({@literal @link de.renew.distribute.DistributePlugin})
     * to search a local target net instance
     * for another Renew simulation.
     * If another local target is already involved in the distributed search,
     * {@link #Searcher(Searcher, Finder)} is used instead.
     * <p>
     * This constructor is called in
     * {@literal @link DistributeSearcher#DistributeSearcher(SearchDistributor, Triggerable, Finder)}
     * to prepare a call to {@literal @link DistributeSearcher#searchFirstCall}.
     * That sequence is used in {@literal @link SearcherAccessorImpl#searchCall}.
     *
     * @param primaryTriggerable the object which is informed about
     * @param finder the object that is informed about every successfully detected binding
     */
    protected Searcher(Triggerable primaryTriggerable, Finder finder) {
        this();
        _primaryTriggerable = primaryTriggerable;
        _finder = finder;
    }

    /**
     * Constructor initializing this searcher to a state similar to {@code parent}'s.
     * This searcher's state will not be completely equal.
     * Especially {@link #_calcChecker}, {@link #_stateRecorder}
     * and the internal set of {@link Binder} objects are not copied.
     * <p>
     * This constructor is used by the Distribute plug-in
     * ({@literal @link de.renew.distribute.DistributePlugin})
     * to search an additional local target net instance
     * for another Renew simulation.
     * It is called in {@literal @link DistributeSearcher#searchAdditionalCall}
     * and this in turn is called in {@literal @link SearcherAccessorImpl#searchCall}.
     *
     * @param parent the {@link Searcher} that gets assigned
     * @param finder the {@link Finder} that gets assigned
     */
    protected Searcher(Searcher parent, Finder finder) {
        this(parent._occurrences, parent._deltaSets);
        _primaryTriggerable = parent._primaryTriggerable;
        _finder = finder;
    }

    private Searcher(Set<Occurrence> occurrences, Map<String, DeltaSet> deltaSets) {
        assert SimulationThreadPool.isSimulationThread() : "is not in a simulation thread";
        _binders = new HashSet<>();
        _occurrences = occurrences;

        _calcChecker = new CalculationChecker();
        _stateRecorder = new StateRecorder();

        _deltaSets = deltaSets;
    }

    @Override
    public ICalculationChecker getCalculationChecker() {
        return _calcChecker;
    }

    @Override
    public IStateRecorder getStateRecorder() {
        return _stateRecorder;
    }

    @Override
    public boolean isCompleted() {
        assert SimulationThreadPool.isSimulationThread() : "is not in a simulation thread";
        return _finder.isCompleted();
    }

    private void setPrimaryTriggerable(Triggerable triggerable) {
        // Clear all triggers previously associated to the triggerable.
        if (triggerable != null) {
            triggerable.triggers().clear();
        }

        _primaryTriggerable = triggerable;
    }

    /**
     * Returns the primary triggerable that is informed about changes
     * in this searcher.
     *
     * @return the primary triggerable
     */
    protected Triggerable getPrimaryTriggerable() {
        return _primaryTriggerable;
    }

    @Override
    public void insertTriggerable(TriggerableCollection triggerables) {
        assert SimulationThreadPool.isSimulationThread() : "is not in a simulation thread";
        // If there is a primary triggerable, we register it
        // at the given collection of triggerables.
        if (_primaryTriggerable != null) {
            triggerables.include(_primaryTriggerable);
        }
    }

    @Override
    public void addOccurrence(Occurrence occurrence) {
        assert SimulationThreadPool.isSimulationThread() : "is not in a simulation thread";
        _occurrences.add(occurrence);
    }

    @Override
    public void removeOccurrence(Occurrence occurrence) {
        assert SimulationThreadPool.isSimulationThread() : "is not in a simulation thread";
        _occurrences.remove(occurrence);
    }

    @Override
    public Collection<Occurrence> getOccurrences() {
        assert SimulationThreadPool.isSimulationThread() : "is not in a simulation thread";
        return _occurrences;
    }

    @Override
    public DeltaSet getDeltaSet(DeltaSetFactory factory) {
        assert SimulationThreadPool.isSimulationThread() : "is not in a simulation thread";
        String category = factory.getCategory();
        DeltaSet result = _deltaSets.get(category);
        if (result == null) {
            result = factory.createDeltaSet();
            _deltaSets.put(category, result);
        }
        return result;
    }

    @Override
    public double getEarliestTime() {
        assert SimulationThreadPool.isSimulationThread() : "is not in a simulation thread";
        return _earliestTime;
    }

    /**
     * Remember the earliest possible time for
     * the currently found binding to be enacted.
     * This value can later on be queried by
     * See also: {@link #getEarliestTime}.
     *
     * @param time the time
     */
    private void setEarliestTime(double time) {
        _earliestTime = time;
    }

    /**
     * Find the binder with the minimum binding badness
     * Return null, if no binder wants to try.
     */
    private Binder selectBestBinder() {
        Binder bestBinder = null;
        int bestBadness = BindingBadness.MAX;
        Iterator<Binder> iterator = _binders.iterator();
        while (iterator.hasNext() && !isCompleted()) {
            Binder binder = iterator.next();
            int badness = binder.bindingBadness(this);
            if (badness < bestBadness) {
                bestBinder = binder;
                bestBadness = badness;
            }
        }
        return bestBinder;
    }

    @Override
    public void search() {
        assert SimulationThreadPool.isSimulationThread() : "is not in a simulation thread";
        int checkpoint = _stateRecorder.checkpoint();
        if (!_binders.isEmpty()) {
            Binder binder = selectBestBinder();
            if (binder != null && !isCompleted()) {
                removeBinder(binder);
                binder.bind(this);
                addBinder(binder);
            }
        } else if (_calcChecker.isConsistent()) {
            // Make sure not to fire before all tokens are available.
            double time = 0;
            for (DeltaSet deltaSet : _deltaSets.values()) {
                time = Math.max(time, deltaSet.computeEarliestTime());
            }
            setEarliestTime(time);

            // Notify the finder, even if the binding is not yet
            // activated. The finder might want to store the
            // binding for a later time or find out the earliest possible
            // binding.
            _finder.found(this);
        }
        _stateRecorder.restore(checkpoint);
    }

    @Override
    public void search(Occurrence occurrence) {
        assert SimulationThreadPool.isSimulationThread() : "is not in a simulation thread";
        int checkpoint = _stateRecorder.checkpoint();
        try {
            Collection<Binder> binders = occurrence.makeBinders(this);
            addOccurrence(occurrence);
            addBinders(binders);
            search();
            removeBinders(binders);
            removeOccurrence(occurrence);
        } catch (Impossible e) {
            // When getting the binders, an exception was thrown.
            // The occurrence cannot be enabled.
            LOGGER.error(e.getMessage(), e);
        } finally {
            _stateRecorder.restore(checkpoint);
        }
    }

    @Override
    public void addBinder(Binder binder) {
        assert SimulationThreadPool.isSimulationThread() : "is not in a simulation thread";
        _binders.add(binder);
    }

    @Override
    public void removeBinder(Binder binder) {
        assert SimulationThreadPool.isSimulationThread() : "is not in a simulation thread";
        _binders.remove(binder);
    }

    @Override
    public void addBinders(Collection<Binder> binders) {
        assert SimulationThreadPool.isSimulationThread() : "is not in a simulation thread";
        _binders.addAll(binders);
    }

    @Override
    public void removeBinders(Collection<Binder> binders) {
        assert SimulationThreadPool.isSimulationThread() : "is not in a simulation thread";
        _binders.removeAll(binders);
    }

    /**
     * Make sure to clean up before a search.
     */
    private void startSearch() {
        // Make sure that the current state recorder does not waste
        // space with now obsolete bindings.
        _stateRecorder.restore();

        // Ensure that the temporary containers are initially empty.
        // If they are not, something went wrong previously,
        // so we report en error.
        if (!_occurrences.isEmpty() || !_binders.isEmpty()) {
            throw new RuntimeException("Searcher was not in idle state at the start of a search.");
        }
    }

    @Override
    public void searchAndRecover(Finder finder, Searchable searchable, Triggerable triggerable) {
        assert SimulationThreadPool.isSimulationThread() : "is not in a simulation thread";
        // Prepare a new search that starts from scratch.
        startSearch();

        // Remember the finder.
        _finder = finder;

        // Remember the triggerable that is interested in changes
        // of this search result.
        setPrimaryTriggerable(triggerable);

        // Unless we find any further restriction,
        // the next firing can happen immediately.
        _earliestTime = 0;

        try {
            // Is this searchable object activated?
            searchable.startSearch(this);
        } catch (Exception e) {
            LOGGER.error(e.getMessage(), e);

            // We reinsert this searchable only when a binding was found,
            // because otherwise there is no real chance that we
            // could have more luck next time.
        }

        // Reset state to allow garbage collection.
        _binders.clear();
        _occurrences.clear();

        _calcChecker.reset();
        _stateRecorder.restore();
        _deltaSets.clear();

        setPrimaryTriggerable(null);

        _finder = null;
    }

    @Override
    public void initiatedSearch(
        ChannelTarget channelTarget, String name, Variable params, boolean isOptional,
        Finder finder, Triggerable triggerable)
    {
        assert SimulationThreadPool.isSimulationThread() : "is not in a simulation thread";
        // Prepare a new search that starts from scratch.
        startSearch();

        // Remember the finder.
        _finder = finder;

        // Possible register for state change notifications.
        setPrimaryTriggerable(triggerable);

        try {
            // We want to find a transition within the specified
            // net instance that can fire. This method is
            // usually called to generate the very first tokens
            // in a net. In a sense, this resembles the main(args)
            // call of the runtime environment.
            //
            // If the argument isOptional is true, the invoked net
            // need not provide an appropriate channel at all. But if it does,
            // the synchronisation must succeed.
            Variable targetVariable = new Variable(channelTarget, _stateRecorder);
            Binder initialBinder = new ChannelBinder(targetVariable, name, params, isOptional);
            addBinder(initialBinder);
            search();
            removeBinder(initialBinder);
            _stateRecorder.restore();
        } catch (Exception e) {
            LOGGER.error(e.getMessage(), e);

            // We reinsert this searchable only when a binding was found,
            // because otherwise there is no real chance that we
            // could have more luck next time.
        }

        // Reset state to allow garbage collection.
        _binders.clear();
        _occurrences.clear();

        _calcChecker.reset();
        _stateRecorder.restore();
        _deltaSets.clear();

        setPrimaryTriggerable(null);
        _finder = null;
    }
}