/*
 * 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;

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

	//
	private LR0Items goTo;

	//
	private Map<Set<LR0Items.Item>, Integer> stateIDMap =
		new HashMap<Set<LR0Items.Item>, Integer>();
	//private ArrayList rules;

	//
	/*package*/ List<Map<GrammarSymbol, LRAction>> actionTable;
	/*package*/ List<Map<Nonterminal,   Integer>>   goToTable;
	/*package*/ int initialStateID;
	/*package*/ List<LRConflict> conflicts;

	/**
	 * 
	 * @param goTo
	 */
	public SLR1Table(LR0Items goTo) {
		this.goTo = goTo;

		computeTable();
	}

	//
	private void numberingStates(
			Collection<Set<LR0Items.Item>> states) {
		int stateid = 0;

		for(Set<LR0Items.Item> o : states) {
			stateIDMap.put(o, Integer.valueOf(stateid++));
		}
	}

	//
	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;
	}

	//
	/*package*/ void computeTable() {
		Collection<Set<LR0Items.Item>> states = goTo.getAllStates();
		ContextFreeGrammar grammar = goTo.getGrammar();
		conflicts = new ArrayList<LRConflict>();

		// numbering the states
		numberingStates(states);
		actionTable = allocateMap(states.size());
		goToTable   = allocateMap(states.size());

		//
		for(Set<LR0Items.Item> items : states) {
			int stateid = stateIDMap.get(items);
			Map<GrammarSymbol, LRAction> ctable =
				actionTable.get(stateid);

			//
			if(goTo.isInitialState(items)) {
				initialStateID = stateid;
			}

			// 
			for(LR0Items.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 =
							grammar.follow(rule.getLeftSymbol());

						for(Terminal k : follow) {
							LRAction act = (LRAction)ctable.get(k);

							if(act == null) {
								ctable.put(k, LRAction.newReduce(k, rule));
							} else if(!act.isShift()) {
								// reduce/reduce conflict
								LRConflict cnf = LRConflict.newReduceReduce(
										rule,
										act.getReduceRule());

								conflicts.add(cnf);
							} else {
								// shift/reduce conflict
								LRConflict cnf = LRConflict.newShiftReduce(
										k, rule);

								conflicts.add(cnf);
							}
						}
					}
				} else {
					GrammarSymbol symbol = item.getDirectedSymbol();
					Set<LR0Items.Item> nextst =
						goTo.goTo(items, symbol);
					int nextid = stateIDMap.get(nextst);

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

						if(act == null) {
							ctable.put(symbol, LRAction.newShift(
									(Terminal)symbol, nextid));
						} else if(!act.isShift()) {
							// shift/reduce conflict
							LRConflict cnf = LRConflict.newShiftReduce(
									symbol,
									act.getReduceRule());

							conflicts.add(cnf);
						}
					} else if(symbol instanceof Nonterminal) {
						// goto
						goToTable.get(stateid).put(
								(Nonterminal)symbol,
								Integer.valueOf(nextid));
					}
				}
			}
		}
	}

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

	/* (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 initialStateID;
	}

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

}
