/*
 * Copyright (C) 2008 Steve Ratcliffe
 * 
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License version 2 as
 *  published by the Free Software Foundation.
 * 
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 * 
 * 
 * Author: Steve Ratcliffe
 * Create date: 08-Nov-2008
 */
package uk.me.parabola.mkgmap.osmstyle;

import java.util.Arrays;
import java.util.BitSet;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Set;

import uk.me.parabola.log.Logger;
import uk.me.parabola.mkgmap.osmstyle.eval.AbstractBinaryOp;
import uk.me.parabola.mkgmap.osmstyle.eval.AbstractOp;
import uk.me.parabola.mkgmap.osmstyle.eval.LinkedBinaryOp;
import uk.me.parabola.mkgmap.osmstyle.eval.LinkedOp;
import uk.me.parabola.mkgmap.osmstyle.eval.Op;
import uk.me.parabola.mkgmap.reader.osm.Element;
import uk.me.parabola.mkgmap.reader.osm.Rule;
import uk.me.parabola.mkgmap.reader.osm.TagDict;
import uk.me.parabola.mkgmap.reader.osm.TypeResult;
import uk.me.parabola.mkgmap.reader.osm.WatchableTypeResult;

/**
 * A list of rules and the logic to select the correct one.
 *
 * A separate {@link RuleIndex} class is used to speed access to the rule list.
 *
 * @author Steve Ratcliffe
 */
public class RuleSet implements Rule, Iterable<Rule> {
	private static final Logger log = Logger.getLogger(RuleSet.class);
	private Rule[] rules;
	private Rule finalizeRule;

	// identifies cached values 
	int cacheId;
	boolean compiled = false;

	private final static short executeFinalizeRulesTagKey = TagDict.getInstance().xlate("mkgmap:execute_finalize_rules");

	private RuleIndex index = new RuleIndex();
	private final Set<String> usedTags = new HashSet<String>();
	
	@Override
	public void resolveType(Element el, TypeResult result) {
		cacheId = resolveType(cacheId, el, result);
	}
	
	
	/**
	 * Resolve the type for this element by running the rules in order.
	 *
	 * This is a very performance critical part of the style system as parts
	 * of the code are run for every tag in the input file.
	 *
	 * @param el The element as read from an OSM xml file in 'tag' format.
	 * @param result A GType describing the Garmin type of the first rule that
	 * matches is returned here.  If continue types are used then more than
	 * one type may be saved here.  If there are no matches then nothing will
	 * be saved.
	 */
	public int resolveType(int cacheId, Element el, TypeResult result) {
		WatchableTypeResult a = new WatchableTypeResult(result);
		if (!compiled || cacheId == Integer.MAX_VALUE)
			compile();
		// new element, invalidate all caches
		cacheId++;
		
		// Get all the rules that could match from the index.  
		BitSet candidates = new BitSet();
		for (Entry<Short, String> tagEntry : el.getFastTagEntryIterator()) {
			BitSet rules = index.getRulesForTag(tagEntry.getKey(), tagEntry.getValue());
			if (rules != null && !rules.isEmpty() )
				candidates.or(rules);
		}
		Rule lastRule = null;
		for (int i = candidates.nextSetBit(0); i >= 0; i = candidates.nextSetBit(i + 1)) {			
			a.reset();
			lastRule = rules[i];
			cacheId = lastRule.resolveType(cacheId, el, a);
			if (a.isResolved())
				return cacheId;
		}
		if (lastRule != null && lastRule.getFinalizeRule() != null){
			if ("true".equals(el.getTag(executeFinalizeRulesTagKey))){
				cacheId = lastRule.getFinalizeRule().resolveType(cacheId, el, a);
			}
		}
		return cacheId;
	}

	public Iterator<Rule> iterator() {
		if (rules == null)
			prepare();
		return Arrays.asList(rules).iterator();
	}

	/**
	 * Add a rule to this rule set.
	 * @param keystring The string form of the first term of the rule.  It will
	 * be A=B or A=*.  (In the future we may allow other forms).
	 * @param rule The actual rule.
	 * @param changeableTags The tags that may be changed by the rule.  This
	 * will be either a plain tag name A, or with a value A=B.
	 */
	public void add(String keystring, Rule rule, Set<String> changeableTags) {
		compiled = false;
		index.addRuleToIndex(new RuleDetails(keystring, rule, changeableTags));
	}

	/**
	 * Add all rules from the given rule set to this one.
	 * @param rs The other rule set.
	 */
	public void addAll(RuleSet rs) {
		for (RuleDetails rd : rs.index.getRuleDetails())
			add(rd.getKeystring(), rd.getRule(), rd.getChangingTags());
	}

	/**
	 * Format the rule set.  Warning: this doesn't produce a valid input
	 * rule file.
	 */
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (Rule rule : rules) {
			sb.append(rule.toString());
		}
		return sb.toString();
	}

	/**
	 * Merge the two rulesets together so that they appear to be one.
	 * @param rs The other rule set, it will have lower priority, that is the
	 * rules will be tried after the rules of this ruleset.
	 */
	public void merge(RuleSet rs) {
		// We have to basically rebuild the index and reset the rule list.
		RuleIndex newIndex = new RuleIndex();

		for (RuleDetails rd : index.getRuleDetails())
			newIndex.addRuleToIndex(rd);

		for (RuleDetails rd : rs.index.getRuleDetails())
			newIndex.addRuleToIndex(rd);

		index = newIndex;
		rules = newIndex.getRules();
		//System.out.println("Merging used tags: "
		//		   + getUsedTags().toString()
		//		   + " + "
		//		   + rs.getUsedTags());
		addUsedTags(rs.usedTags);
		//System.out.println("Result: " + getUsedTags().toString());
		compiled = false;
	}

	/**
	 * Prepare this rule set for use.  The index is built and and the rules
	 * are saved to an array for fast access.
	 */
	public void prepare() {
		index.prepare();
		rules = index.getRules();
		compile();
	}

	public Set<String> getUsedTags() {
		return usedTags;
	}

	public void addUsedTags(Collection<String> usedTags) {
		this.usedTags.addAll(usedTags);
	}

	/**
	 * Compile the rules and reset caches. Detect common sub-expressions and
	 * make sure that all rules use the same instance of these common
	 * sub-expressions.
	 */
	private void compile(){
		HashMap<String, Op> tests = new HashMap<String, Op>();

		for (Rule rule:rules){
			Op op;
			if (rule instanceof ExpressionRule)
				op = ((ExpressionRule)rule).getOp();
			else if (rule instanceof ActionRule)
				op = ((ActionRule) rule).getOp();
			else {
				log.error("unexpected rule instance");
				continue;
			}
			if (op instanceof AbstractBinaryOp){
				AbstractBinaryOp binOp = (AbstractBinaryOp) op;
				binOp.setFirst(compileOp(tests, binOp.getFirst()));
				binOp.setSecond(compileOp(tests, binOp.getSecond()));
				op = compileOp(tests, binOp);
			} else if (op instanceof AbstractOp){
				op = compileOp(tests, op);
			} else if (op instanceof LinkedBinaryOp){
				((LinkedBinaryOp) op).setFirst(compileOp(tests, ((LinkedBinaryOp) op).getFirst()));
				((LinkedBinaryOp) op).setSecond(compileOp(tests, ((LinkedBinaryOp) op).getSecond()));
			} else if (op instanceof LinkedOp) {
				Op wrappedOp = compileOp(tests, ((LinkedOp) op).getFirst());
				op.setFirst(wrappedOp);
			} else {
				log.error("unexpected op instance");
				continue;
			}
			if (rule instanceof ExpressionRule)
				((ExpressionRule)rule).setOp(op);
			else if (rule instanceof ActionRule)
				((ActionRule) rule).setOp(op);
			else {
				log.error("unexpected rule instance");
				continue;
			}
		}
		cacheId = 0;
		compiled = true;
	}
	
	private Op compileOp(HashMap<String, Op> tests, Op op){
		if (op instanceof AbstractBinaryOp){
			AbstractBinaryOp binOp = (AbstractBinaryOp) op;
			binOp.setFirst(compileOp(tests, binOp.getFirst()));
			binOp.setSecond(compileOp(tests, binOp.getSecond()));
		}
		if (op instanceof LinkedOp){
			// LinkedOp is referenced by other OPs, don't replace it 
			return op;
		}
		String test = op.toString();
		Op commonOp = tests.get(test);
		if (commonOp == null){
			if (op instanceof AbstractOp)
				((AbstractOp)op).resetCache();
			tests.put(test, op);
			commonOp = op;
		}
		
		return commonOp;
	}
	
	public void setFinalizeRule(Rule finalizeRule) {
		if (rules == null) {
			// this method must be called after prepare() is called so
			// that we have rules to which the finalize rules can be applied
			throw new IllegalStateException("First call prepare() before setting the finalize rules");
		}
		for (Rule rule : rules) 
			rule.setFinalizeRule(finalizeRule);
		
		compiled = false;
		this.finalizeRule = finalizeRule;  
	}

	@Override
	public Rule getFinalizeRule() {
		return finalizeRule;
	}

	@Override
	public void printStats(String header) {
		if (rules == null)
		  return;
		for (Rule rule : rules){ 
			rule.printStats(header);
		}
		if (finalizeRule != null)
			finalizeRule.printStats(header);
	}
	
	@Override
	public boolean containsExpression(String exp) {
		if (rules == null) {
			// this method must be called after prepare() is called so
			// that we have rules to which the finalize rules can be applied
			throw new IllegalStateException("First call prepare() before setting the finalize rules");
		}
		for (Rule rule : rules){
			if (rule.containsExpression(exp))
				return true;
		}
		if (finalizeRule != null){
			if (finalizeRule.containsExpression(exp))
				return true;
		}
		return false;
	}

	public BitSet getRules(Element el) {
		if (!compiled || cacheId == Integer.MAX_VALUE)
			compile();
		// new element, invalidate all caches
		cacheId++;

		// Get all the rules that could match from the index.  
		BitSet candidates = new BitSet();
		for (Entry<Short, String> tagEntry : el.getFastTagEntryIterator()) {
			BitSet rules = index.getRulesForTag(tagEntry.getKey(), tagEntry.getValue());
			if (rules != null && !rules.isEmpty() )
				candidates.or(rules);
		}
		return candidates;
	}
	
} 
