/*
 * Copyright 2009 Yuichiro Moriguchi
 *
 * 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 net.morilib.automata.lr;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

import net.morilib.deculture.misc.PrecedenceTerminal;

/**
 * 
 * 
 * @author MORIGUCHI, Yuichiro 2006/07/08
 */
public class LALR1Table implements LR1Table {

	//
	private LALR1Items goTo;

	//
	/*package*/ List<Map<GrammarSymbol, LRAction>> actionTable;
	/*package*/ List<Map<Nonterminal, Integer>>    goToTable;
	/*package*/ List<LRConflict> conflicts;
	private Map<Terminal, Integer> prior;
	private Map<Terminal, Associativity> assoc;

	/**
	 * 
	 * @param goTo
	 */
	public LALR1Table(LALR1Items goTo,
			Map<Terminal, Integer> priority,
			Map<Terminal, Associativity> assoc) {
		this.goTo  = goTo;
		this.prior = priority;
		this.assoc = assoc;
		computeTable();
	}

	//
	private<T, S> List<Map<T, S>> allocateMap(int size) {
		List<Map<T, S>> res = new ObjectArray<Map<T, S>>(size);

		for(int i = 0; i < size; i++) {
			res.set(i, new HashMap<T, S>());
		}
		return res;
	}

	//
	private void _addShiftReduce(Object k, ContextFreeRule r) {
		LRConflict cnf;

		cnf = LRConflict.newShiftReduce(k, r);
		conflicts.add(cnf);
	}

	//
	private void _addReduceReduce(ContextFreeRule k,
			ContextFreeRule r) {
		LRConflict cnf;

		cnf = LRConflict.newReduceReduce(k, r);
		conflicts.add(cnf);
	}

	//
	private Integer getprior(Terminal t) {
		Integer x;

		if(t instanceof PrecedenceTerminal) {
			x = prior.get(((PrecedenceTerminal)t).getPrecedence());
		} else {
			x = prior.get(t);
		}
		return x;
	}

	//
	private Integer getprior(ContextFreeRule r) {
		GrammarSymbol z;
		Integer x;

		if(r.getDerivedSymbolLength() == 3) {
			if(((z = r.getDerivedSymbol(1)) instanceof Terminal)) {
				x = getprior((Terminal)z);
			} else {
				x = null;
			}
		} else if(r.getDerivedSymbolLength() != 2) {
			x = null;
		} else if((z = r.getDerivedSymbol(0)) instanceof Terminal) {
			x = getprior((Terminal)z);
		} else if((z = r.getDerivedSymbol(1)) instanceof Terminal) {
			x = getprior((Terminal)z);
		} else {
			x = null;
		}
		return x;
	}

	//
	/*package*/ void computeTable() {
		ContextFreeGrammar grammar = goTo.getGrammar();
		conflicts = new ArrayList<LRConflict>();

		// numbering the states
		actionTable = allocateMap(goTo.getSizeOfStates());
		goToTable   = allocateMap(goTo.getSizeOfStates());

		//
		for(int i = 0; i < goTo.getSizeOfStates(); i++) {
			Set<LALR1Items.Item>  items  = goTo.getItems(i);
			Map<GrammarSymbol, LRAction> ctable = actionTable.get(i);

			// 
			for(LALR1Items.Item item : items) {
				if(item.isReduceState()) {
					//
					ContextFreeRule rule = item.getRule();

					if(rule.equals(grammar.getAugmentRule())) {
						// S' -> S*
						ctable.put(
								ContextFreeGrammar.ENDMARKER,
								LRAction.newAccept());
					} else {
						// reduce
						Set<Terminal> follow = item.getLookaheadSet();
						//System.out.println(item);

						for(Terminal k : follow) {
							LRAction act = (LRAction)ctable.get(k);
							Integer a, b;

							if(act == null) {
								ctable.put(k, LRAction.newReduce(k, rule));
							} else if(!act.isShift()) {
								_addReduceReduce(rule, act.getReduceRule());
							} else if((a = getprior(k)) == null) {
								_addShiftReduce(k, rule);
							} else if((b = getprior(rule)) == null) {
								_addShiftReduce(k, rule);
							} else if(a > b) {
								// terminal to be shifted has high priority
								// shift: do nothing
							} else if(a < b) {
								// terminal to be shifted has high priority
								// reduce
								ctable.put(k, LRAction.newReduce(k, rule));
							} else if(assoc.get(k) == Associativity.LEFT) {
								// left associativity
								// reduce
								ctable.put(k, LRAction.newReduce(k, rule));
							} else if(assoc.get(k) == Associativity.RIGHT) {
								// right associativity
								// shift: do nothing
							} else {
								_addShiftReduce(k, rule);
							}
						}
					}
				} else {
					GrammarSymbol symbol = item.getDirectedSymbol();
					Integer a, b;
					int nextid = goTo.goToID(i, symbol);
					//System.out.println(item);

					if(symbol instanceof Terminal) {
						// shift
						LRAction act = (LRAction)ctable.get(symbol);
						Terminal t = (Terminal)symbol;

						if(act == null) {
							ctable.put(t, LRAction.newShift(t, nextid));
						} else if(act.isShift()) {
							// do nothing
						} else if((a = getprior(t)) == null) {
							_addShiftReduce(t, act.getReduceRule());
						} else if((b = getprior(act.getReduceRule())) == null) {
							_addShiftReduce(t, act.getReduceRule());
						} else if(a > b) {
							// terminal to be shifted has high priority
							// shift
							ctable.put(t, LRAction.newShift(t, nextid));
						} else if(a < b) {
							// terminal to be shifted has high priority
							// reduce: do nothing
						} else if(assoc.get(act.getSymbol()) == Associativity.LEFT) {
							// left associativity
							// reduce: do nothing
						} else if(assoc.get(act.getSymbol()) == Associativity.RIGHT) {
							// right associativity
							// shift
							ctable.put(t, LRAction.newShift(t, nextid));
						} else {
							_addShiftReduce(t, act.getReduceRule());
						}
					} else if(symbol instanceof Nonterminal) {
						// goto
						goToTable.get(i).put(
								(Nonterminal)symbol,
								Integer.valueOf(nextid));
					}
				}
			}
		}
	}

	/**
	 * 
	 * @param g
	 * @return
	 */
	public static LALR1Table create(ContextFreeGrammar g,
			Map<Terminal, Integer> priority,
			Map<Terminal, Associativity> assoc) {
		LALR1Table t;
		LALR1Items m;

		m = LALR1Items.newLALR(g);
		t = new LALR1Table(m, priority, assoc);
		return t;
	}

	/* (non-Javadoc)
	 * @see net.morilib.automata.lr.LR1Table#getSizeOfStates()
	 */
	@Override
	public int getSizeOfStates() {
		return goTo.getSizeOfStates();
	}

	/* (non-Javadoc)
	 * @see org.usei.grammar.LR1Table#action(int, java.lang.Object)
	 */
	public LRAction action(int stateID, Terminal terminal) {
		//if(!goTo.getGrammar().isTerminal(terminal)) {
		//	throw new InvalidSymbolException(terminal.toString());
		//}
		return actionTable.get(stateID).get(terminal);
	}

	/* (non-Javadoc)
	 * @see net.morilib.automata.lr.LR1Table#actions(int)
	 */
	@Override
	public Map<GrammarSymbol, LRAction> actions(int stateID) {
		return Collections.unmodifiableMap(actionTable.get(stateID));
	}

	/* (non-Javadoc)
	 * @see org.usei.grammar.LR1Table#goTo(int, java.lang.Object)
	 */
	public int goTo(int stateID, Nonterminal nonterminal) {
		//if(!goTo.getGrammar().isNonterminal(nonterminal)) {
		//	throw new InvalidSymbolException(nonterminal.toString());
		//}
		return goToTable.get(stateID).get(nonterminal);
	}

	/* (non-Javadoc)
	 * @see net.morilib.automata.lr.LR1Table#goTos(int)
	 */
	@Override
	public Map<Nonterminal, Integer> goTos(int stateID) {
		return Collections.unmodifiableMap(goToTable.get(stateID));
	}

	/* (non-Javadoc)
	 * @see org.usei.grammar.LR1Table#getInitialStateID()
	 */
	public int getInitialStateID() {
		return goTo.getInitialStateID();
	}

	/* (non-Javadoc)
	 * @see org.usei.grammar.LR1Table#getConflicts()
	 */
	public Collection<LRConflict> getConflicts() {
		return Collections.unmodifiableCollection(conflicts);
	}

}
