/*
 * Copyright 2009-2013 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.
 */
// Translated by Nina
package net.morilib.automata.nfa;

import java.io.IOException;
import java.io.Reader;
import java.util.Stack;
import net.morilib.automata.nfa.NFAAccept;
import net.morilib.automata.nfa.NFAAlternative;
import net.morilib.automata.nfa.NFAConcatenation;
import net.morilib.automata.nfa.NFAObject;
import net.morilib.automata.nfa.NFAOptional;
import net.morilib.automata.nfa.NFARepetition;
import net.morilib.automata.nfa.SingleSetNFA;
import net.morilib.range.CharSets;
import net.morilib.range.Interval;
import net.morilib.range.Range;

public class RegexpParser<T, A, B> {

	private int state;
	private int unread = -1;

	private Stack<NFAObject<T, A, B>> stk =
			new Stack<NFAObject<T, A, B>>();
	private Stack<Boolean> ors = new Stack<Boolean>();
	private StringBuffer chs = new StringBuffer();
	private NFAObject<T, A, B> nxt = null;
	private boolean orf = false;

	private NFAObject<T, A, B> mkor(NFAObject<T, A, B> b,
			NFAObject<T, A, B> a) {
		return NFAAlternative.newInstance(a, b);
	}

	private NFAObject<T, A, B> mkcat(NFAObject<T, A, B> a,
			NFAObject<T, A, B> b) {
		if(a == null) {
			return b;
		} else {
			return NFAConcatenation.newInstance(a, b);
		}
	}

	private NFAObject<T, A, B> mkcls(NFAObject<T, A, B> a,
			int c) {
		switch(c) {
		case '*':  return NFARepetition.newInstance(a, true);
		case '+':  return NFARepetition.newInstance(a, false);
		case '?':  return NFAOptional.newInstance(a);
		default:   throw new RuntimeException();
		}
	}

	private void doorf() {
		if(orf) {
			stk.push(mkor(stk.pop(), stk.pop()));
		}
	}

	private void donxt() {
		if(nxt != null) {
			stk.push(mkcat(stk.pop(), nxt));
			nxt = null;
		}
	}

	private void addor(int c) {
		donxt();
		if(c == '(') {
			stk.push(null);
			ors.push(orf);
		} else if(c == '|') {
			doorf();
			stk.push(null);
		}
		orf = c == '|';
	}

	private void addre(int c) {
		Range r;

		donxt();
		if(c == ')') {
			doorf();
			orf = ors.pop();
			nxt = stk.pop();
		} else if(c == ']') {
			r   = CharSets.parse(chs.substring(1));
			chs = new StringBuffer();
			nxt = SingleSetNFA.<T, A, B>newInstance(r);
		} else {
			r   = Interval.newPoint(Integer.valueOf(c));
			nxt = SingleSetNFA.<T, A, B>newInstance(r);
		}
	}

	private void addcl(int c) {
		if(nxt != null) {
			stk.push(mkcat(stk.pop(), mkcls(nxt, c)));
			nxt = null;
		} else {
			stk.push(mkcls(stk.pop(), c));
		}
	}

	private void addbuf(int c) {
		chs.appendCodePoint(c);
	}

	public static<T, A, B> NFAObject<T, A, B> parse(String rd,
			A tag) throws RegexParseException {
		RegexpParser<T, A, B> x;

		try {
			x = new RegexpParser<T, A, B>();
			x.stk.push(null);
			x._parse(new java.io.StringReader(rd));
			x.donxt();
			x.doorf();
			if(x.stk.size() != 1) {
				throw new RegexParseException();
			}
			return NFAAccept.newInstance(x.stk.pop(), tag);
		} catch(java.io.IOException e) {
			throw new RuntimeException(e);
		}
	}

	private int _read(java.io.Reader rd) throws java.io.IOException {
		int c;

		if(unread < 0) {
			return rd.read();
		} else {
			c = unread;
			unread = -1;
			return c;
		}
	}

	private boolean _step(int c) {
		switch(state) {
		case 0:
			if(c >= 0 && c <= 39) {
				state = 1;
				return true;
			} else if(c >= 40 && c <= 40) {
				state = 0;
				return true;
			} else if(c >= 41 && c <= 90) {
				state = 1;
				return true;
			} else if(c >= 91 && c <= 91) {
				state = 2;
				return true;
			} else if(c >= 92 && c <= 2147483647) {
				state = 1;
				return true;
			}
			return false;
		case 2:
			if(c >= 0 && c <= 91) {
				state = 3;
				return true;
			} else if(c >= 92 && c <= 92) {
				state = 4;
				return true;
			} else if(c >= 93 && c <= 93) {
				state = 1;
				return true;
			} else if(c >= 94 && c <= 2147483647) {
				state = 3;
				return true;
			}
			return false;
		case 4:
			if(c >= 0 && c <= 2147483647) {
				state = 2;
				return true;
			}
			return false;
		case 3:
			if(c >= 0 && c <= 44) {
				state = 3;
				return true;
			} else if(c >= 45 && c <= 45) {
				state = 5;
				return true;
			} else if(c >= 46 && c <= 92) {
				state = 3;
				return true;
			} else if(c >= 93 && c <= 93) {
				state = 1;
				return true;
			} else if(c >= 94 && c <= 2147483647) {
				state = 3;
				return true;
			}
			return false;
		case 5:
			if(c >= 0 && c <= 2147483647) {
				state = 2;
				return true;
			}
			return false;
		case 1:
			if(c >= 0 && c <= 39) {
				state = 1;
				return true;
			} else if(c >= 40 && c <= 40) {
				state = 0;
				return true;
			} else if(c >= 41 && c <= 41) {
				state = 1;
				return true;
			} else if(c >= 42 && c <= 42) {
				state = 6;
				return true;
			} else if(c >= 43 && c <= 43) {
				state = 6;
				return true;
			} else if(c >= 44 && c <= 62) {
				state = 1;
				return true;
			} else if(c >= 63 && c <= 63) {
				state = 6;
				return true;
			} else if(c >= 64 && c <= 90) {
				state = 1;
				return true;
			} else if(c >= 91 && c <= 91) {
				state = 2;
				return true;
			} else if(c >= 92 && c <= 123) {
				state = 1;
				return true;
			} else if(c >= 124 && c <= 124) {
				state = 0;
				return true;
			} else if(c >= 125 && c <= 2147483647) {
				state = 1;
				return true;
			}
			return false;
		case 6:
			if(c >= 0 && c <= 39) {
				state = 1;
				return true;
			} else if(c >= 40 && c <= 40) {
				state = 0;
				return true;
			} else if(c >= 41 && c <= 41) {
				state = 1;
				return true;
			} else if(c >= 44 && c <= 62) {
				state = 1;
				return true;
			} else if(c >= 64 && c <= 90) {
				state = 1;
				return true;
			} else if(c >= 91 && c <= 91) {
				state = 2;
				return true;
			} else if(c >= 92 && c <= 123) {
				state = 1;
				return true;
			} else if(c >= 124 && c <= 124) {
				state = 0;
				return true;
			} else if(c >= 125 && c <= 2147483647) {
				state = 1;
				return true;
			}
			return false;
		}
		return false;
	}

	private boolean _accepted() {
		return (state == 1 ||
				state == 6);
	}

	private void _execaction(int  $c) {
		switch(state) {
		case 5:
			addbuf($c);
			break;
		case 2:
			addbuf($c);
			break;
		case 0:
			addor($c);
			break;
		case 1:
			addre($c);
			break;
		case 3:
			addbuf($c);
			break;
		case 4:
			addbuf($c);
			break;
		case 6:
			addcl($c);
			break;
		}
	}

	private boolean _parse(
			Reader rd) throws IOException, RegexParseException {
		int p, c;

		for(p = -2; (c = _read(rd)) >= 0; p = c) {
			_execaction(p);
			if(!_step(c)) {
				throw new RegexParseException();
			}
		}
		_execaction(p);
		return _accepted();
	}

}
