/**
 * Copyright (c) 2016-2018, the Alpha Team.
 * All rights reserved.
 *
 * Additional changes made by Siemens.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1) Redistributions of source code must retain the above copyright notice, this
 *    list of conditions and the following disclaimer.
 *
 * 2) Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package at.ac.tuwien.kr.alpha.core.grounder;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import at.ac.tuwien.kr.alpha.api.programs.Predicate;
import at.ac.tuwien.kr.alpha.api.programs.atoms.Atom;
import at.ac.tuwien.kr.alpha.api.programs.terms.Term;
import at.ac.tuwien.kr.alpha.commons.substitutions.Instance;

/**
 * A storage for instances with a certain arity, where each position of the instance can be indexed.
 * This aids in matching and joining instances. An index can be added or removed at any time for a desired position of
 * all instances.
 * Copyright (c) 2016-2020, the Alpha Team.
 */
public class IndexedInstanceStorage {
	private final Predicate predicate;
	private final boolean positive;

	/**
	 * A collection of all instances currently stored in this storage.
	 */
	private final LinkedHashSet<Instance> instances = new LinkedHashSet<>();

	/**
	 * For each position, a mapping of termIds to list of instances with this termId at the corresponding position
	 */
	private final ArrayList<HashMap<Term, ArrayList<Instance>>> indices = new ArrayList<>();

	private final ArrayList<Instance> recentlyAddedInstances = new ArrayList<>();

	public IndexedInstanceStorage(Predicate predicate, boolean positive) {
		this.predicate = predicate;
		this.positive = positive;

		// Create list of mappings, initialize to null.
		while (indices.size() < predicate.getArity()) {
			indices.add(null);
		}
	}

	public Predicate getPredicate() {
		return predicate;
	}

	public void markRecentlyAddedInstancesDone() {
		recentlyAddedInstances.clear();
	}

	public void addIndexPosition(int position) {
		if (position < 0 || position > predicate.getArity() - 1) {
			throw new RuntimeException("Requested to create indices for attribute out of range." +
					"IndexedInstanceStorage: " + this + "  requested indices position: " + position);
		}
		// Add index
		indices.set(position, new LinkedHashMap<>());

		// Initialize index with all instances currently used.
		for (Instance instance : instances) {
			indices.get(position).putIfAbsent(instance.terms.get(position), new ArrayList<>());
			ArrayList<Instance> instancesAtPosition = indices.get(position).get(instance.terms.get(position));
			instancesAtPosition.add(instance);
		}
	}

	public void removeIndexPosition(int position) {
		if (position < 0 || position > predicate.getArity() - 1) {
			throw new RuntimeException("Requested to create indices for attribute out of range." +
					"IndexedInstanceStorage: " + this + "  requested indices position: " + position);
		}
		indices.set(position, null);
	}

	/**
	 * Returns whether an instance is already contained in the storage.
	 * 
	 * @param instance the instance to check for containment.
	 * @return true if the instance is already contained in the storage.
	 */
	public boolean containsInstance(Instance instance) {
		return instances.contains(instance);
	}

	public void addInstance(Instance instance) {
		if (instance.terms.size() != predicate.getArity()) {
			throw new RuntimeException("Instance length does not match arity of IndexedInstanceStorage: " +
					"instance size: " + instance.terms.size()
					+ " IndexedInstanceStorage: " + this);
		}
		instances.add(instance);
		recentlyAddedInstances.add(instance);
		// Add instance to all indices.
		for (int i = 0; i < indices.size(); i++) {
			HashMap<Term, ArrayList<Instance>> posIndex = indices.get(i);
			if (posIndex == null) {
				continue;
			}
			posIndex.putIfAbsent(instance.terms.get(i), new ArrayList<>());
			ArrayList<Instance> matchingInstancesAtPos = posIndex.get(instance.terms.get(i));
			matchingInstancesAtPos.add(instance); // Add instance
		}
	}

	public void removeInstance(Instance instance) {
		if (recentlyAddedInstances.size() != 0) {
			// Hint: exception may be replaced by removing the instance also from the list of recentlyAddedInstances.
			throw new RuntimeException("Instance is removed while there are unprocessed new instances; Result dubious.");
		}
		// Remove from all indices
		for (int i = 0; i < indices.size(); i++) {
			HashMap<Term, ArrayList<Instance>> posIndex = indices.get(i);
			if (posIndex == null) {
				continue;
			}
			ArrayList<Instance> matchingInstancesAtPos = posIndex.get(instance.terms.get(i));
			matchingInstancesAtPos.remove(instance); // Remove instance

			// If there are no more instances having the term at the current position,
			// remove the entry from the hash.
			if (matchingInstancesAtPos.size() == 0) {
				posIndex.remove(instance.terms.get(i));
			}
		}
		instances.remove(instance);
	}

	public List<Instance> getRecentlyAddedInstances() {
		return recentlyAddedInstances;
	}

	/**
	 * Returns a list of all instances having the given term at the given position. Returns null if no such
	 * instances exist.
	 * 
	 * @param term
	 * @param position
	 * @return
	 */
	public List<Instance> getInstancesMatchingAtPosition(Term term, int position) {
		Map<Term, ArrayList<Instance>> indexForPosition = indices.get(position);
		if (indexForPosition == null) {
			throw new RuntimeException("IndexedInstanceStorage queried for position " + position + " which is not indexed.");
		}
		ArrayList<Instance> matchingInstances = indexForPosition.get(term);
		return matchingInstances == null ? Collections.emptyList() : matchingInstances;
	}

	private int getMostSelectiveGroundTermPosition(Atom atom) {
		int smallestNumberOfInstances = Integer.MAX_VALUE;
		int mostSelectiveTermPosition = -1;
		for (int i = 0; i < atom.getTerms().size(); i++) {
			Term testTerm = atom.getTerms().get(i);
			if (testTerm.isGround()) {
				ArrayList<Instance> instancesMatchingTest = indices.get(i).get(testTerm);
				if (instancesMatchingTest == null) {
					// Ground term at i matches zero instances, it is most selective.
					return i;
				}
				int numInstancesTestTerm = instancesMatchingTest.size();
				if (numInstancesTestTerm < smallestNumberOfInstances) {
					smallestNumberOfInstances = numInstancesTestTerm;
					mostSelectiveTermPosition = i;
				}
			}
		}
		return mostSelectiveTermPosition;
	}

	public List<Instance> getInstancesFromPartiallyGroundAtom(Atom substitute) {
		// For selection of the instances, find ground term on which to select.
		int firstGroundTermPosition = getMostSelectiveGroundTermPosition(substitute);
		// Select matching instances, select all if no ground term was found.
		if (firstGroundTermPosition != -1) {
			Term firstGroundTerm = substitute.getTerms().get(firstGroundTermPosition);
			return getInstancesMatchingAtPosition(firstGroundTerm, firstGroundTermPosition);
		} else {
			return new ArrayList<>(getAllInstances());
		}
	}

	public Set<Instance> getAllInstances() {
		return instances;
	}

	@Override
	public String toString() {
		return (positive ? "+" : "-") + predicate;
	}
}
