package ash.util;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Map;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.PrintStream;
import java.io.BufferedReader;

/**
 * グラフ構造を扱うクラス
 */
public class Graph<T> implements Iterable<GNode<T>> {
	private GNode<T> first = null;
	private GNode<T> last = null;
	private int nNode = 0;
	private int nArc = 0;
	private boolean arcAtLast = true;

	@SuppressWarnings("unchecked")
	public void makeFromPair(BufferedReader reader) throws IOException {
		String line;
		while((line = reader.readLine()) != null) {
			StringTokenizer st = new StringTokenizer(line);
			T s1 = null;
			T s2 = null;
			try {
				s1 = (T)st.nextToken();
				s2 = (T)st.nextToken();
			}
			catch(NoSuchElementException e) { }
			if(s1 != null) {
				if(s2 == null)
					this.store(s1);
				else
					this.storePair(s1, s2);
			}
		}
	}
	@SuppressWarnings("unchecked")
	public void makeFromHier(BufferedReader reader) throws IOException {
		//System.err.println("==>makeFromHier()");
		String parent = "????";
		String line;
		while((line = reader.readLine()) != null) {
			if(line.length() > 0) {
				if(line.charAt(0) != '\t') {
					this.store((T)line);
					parent = line;
				} else {
					line = line.substring(1);
					if(line.length() > 0)
						this.storePair((T)parent, (T)line);
				}
			}
		}
	}
	public void printPair(PrintStream rep) {
		//System.err.println("==>printPair()");
		for(GNode<T> n : this) {
			if(!n.hasOut() && !n.hasIn()) rep.println(n.data);
			for(GNode<T> to : n)
				rep.println(n.data + "\t" + to.data);
		}
	}
	public void printHier(PrintStream rep) {
		//System.err.println("==>printHier()");
		for(GNode<T> n : this) {
			if(n.hasOut() || !n.hasIn()) {
				rep.println(n.data);
				for(GNode<T> to : n) rep.println("\t" + to.data);
			}
		}
	}
	public void printTree(PrintStream rep) {
		PrintTree<GNode<T>> pt = new PrintTree<GNode<T>>(10, rep);
		for(GNode<T> n : this) n.flag = 0; // フラグの初期化
		for(GNode<T> n : this) { // 親を持たないノードの表示
			if(!n.hasIn()) pt.printTree(n);
		}
		for(GNode<T> n : this) { // 表示されていないノードの表示
			if(n.flag == 0) pt.printTree(n);
		}
	}
	/*
	static final int MAX_DEPTH = 10;
	public void printTree(PrintStream rep) {
		//System.err.println("==>printTree()");
		for(GNode<String> n : this) n.flag = 0; // フラグの初期化
		for(GNode<String> n : this) { // 親を持たないノードの表示
			if(!n.hasIn()) printTSub(rep, n, 0);
		}
		for(GNode<String> n : this) { // 表示されていないノードの表示
			if(n.flag == 0) printTSub(rep, n, 0);
		}
	}
	private void printTSub(PrintStream rep, GNode<String> n, int level) {
		//System.err.println("==>printTSub()");
		if(level >= MAX_DEPTH) return;
		for(int i = 0; i < level; i ++)	rep.print('\t');
		rep.println(n.data);
		if(n.flag == 0) {
			n.flag = 1;
			for(GNode<String> to : n) printTSub(rep, to, level + 1);
		}
	}
	*/

	public Iterator<GNode<T>> iterator() {
		return new Iterator<GNode<T>>() {
			GNode<T> cursor = first;
			public boolean hasNext() { return cursor != null;	}
			public GNode<T> next() {
				if(cursor == null) throw new NoSuchElementException();
				GNode<T> next = cursor;
				cursor = cursor.next;
				return next;
			}
			public void remove() { }
		};
	}

	public int nNode() { return nNode; }
	public int nArc() { return nArc; }

	public void initFlag(int flag) {
		//for(GNode<T> n : this)
		for(GNode<T> n = first; n != null; n = n.next)
			n.flag = flag;
	}
	public GNode<T> get(int idx) {
		if(idx < 0) return last;
		//for(GNode<T> n : this)
		for(GNode<T> n = first; n != null; n = n.next)
			if(idx-- == 0) return n;
		return null;
	}
	public GNode<T> find(T data) {
		//for(GNode<T> n : this) {
		for(GNode<T> n = first; n != null; n = n.next) {
			if (data.equals(n.data)) return n;
		}
		return null;
	}
	public GNode<T> store(T data) {
		GNode<T> n = find(data);
		if(n == null) {
			n = new GNode<T>(data);
			addNode(n, -1);		// リストの最後に追加する。
		}
		return n;
	}
	public void add(T data, int idx) {
		addNode(new GNode<T>(data), idx);
	}
	public void addNode(GNode<T> node, int idx) {
		if (first != null) {
			if (idx == 0) {		// link at the first
				node.next = first;
				first = node;
			} else {
				GNode<T> p = get(idx-1); // the previous node
				if (p == null) p = last;
				node.next = p.next;
				p.next = node;
				if (p == last) last = node;
			}
		} else {
			node.next = null;
			first = last = node;
		}
		nNode++;
		//System.err.println(nNode + ". " + node);
	}
	public void deleteNode(GNode<T> node) {
		deleteArcs(node);
		nNode--;
		if(first == node) {
			first = node.next;
			if(first == null) last = null;
		} else {
			GNode<T> p = first;
			while(p.next != node) p = p.next;
			p.next = node.next;
			if(node == last) last = p;
		}
	}

	void reset() {
		first = last = null;
		nNode = nArc = 0;
	}
	void compressArcs() {
		//for(GNode<T> n : this) {
		for(GNode<T> n = first; n != null; n = n.next) {
			for(GArc<T> a = n.firstA; a != null; a = a.nextA) {
				GNode<T> nodeB = a.nodeB;
				for(GArc<T> a1 = a.nextA; a1 != null; ) {
					GArc<T> a2 = a1;
					a1 = a1.nextA;
					if(a2.nodeB == nodeB ) deleteArc(a2);
				}
			}
		}
	}
	void deleteAllArcs() {
		//for(GNode<T> n : this)
		for(GNode<T> n = first; n != null; n = n.next)
			deleteArcs(n);
	}
	void deleteArcs(GNode<T> node) {
		while(node.firstA != null) deleteArc(node.firstA);
		while(node.firstB != null) deleteArc(node.firstB);
	}
	void unlinkAllArcA() {
		//for(GNode<T> n : this)
		for(GNode<T> n = first; n != null; n = n.next)
			for(GArc<T> a = n.firstB; a != null; a = a.nextB)
				unlinkArcA(a);
	}
	void unlinkAllArcB() {
		//for(GNode<T> n : this)
		for(GNode<T> n = first; n != null; n = n.next)
			for(GArc<T> a = n.firstA; a != null; a = a.nextA)
				unlinkArcB(a);
	}
	
	void storePair(T s1, T s2) {
		//System.err.println("==>storPair():" + s1 + ", " + s2);
		GNode<T> n1 = store(s1);
		GNode<T> n2 = store(s2);
		for(GArc<T> a = n1.firstA; a != null; a = a.nextA) {
			if(a.nodeB == n2) return;
		}
		addArc(new GArc<T>(), n1, n2);
	}
	void addArc(GArc<T> arc, GNode<T> nodeA, GNode<T> nodeB ) {
		linkArcA(arc, nodeA);
		linkArcB(arc, nodeB);
		nArc++;
		//System.err.println(nArc + ". " + arc);
	}
	void deleteArc(GArc<T> arc) {
		unlinkArcA(arc);
		unlinkArcB(arc);
		nArc--;
	}
	void changeArcA(GArc<T> arc, GNode<T> nodeA) {
		unlinkArcA(arc);
		linkArcA(arc, nodeA);
	}
	void changeArcB(GArc<T> arc, GNode<T> nodeB) {
		unlinkArcB(arc);
		linkArcB(arc, nodeB);
	}
	private void linkArcA(GArc<T> arc, GNode<T> nodeA) {
		arc.nodeA = nodeA;
		if(arcAtLast) {
			if(nodeA.firstA != null) {
				GArc<T> prevArc = nodeA.firstA;
				while(prevArc.nextA != null)
					prevArc = prevArc.nextA;
				prevArc.nextA = arc;
			} else {
				nodeA.firstA = arc;
			}
		} else {
			arc.nextA = nodeA.firstA;
			nodeA.firstA = arc;
		}
	}
	private void linkArcB(GArc<T> arc, GNode<T> nodeB) {
		arc.nodeB = nodeB;
		if(arcAtLast) {
			if(nodeB.firstB != null) {
				GArc<T> prevArc = nodeB.firstB;
				while(prevArc.nextB != null)
					prevArc = prevArc.nextB;
				prevArc.nextB = arc;
			} else {
				nodeB.firstB = arc;
			}
		} else {
			arc.nextB = nodeB.firstB;
			nodeB.firstB = arc;
		}
	}
	private void unlinkArcA(GArc<T> arc) {
		GArc<T> prevArc = arc.nodeA.firstA;
		if(prevArc == arc) {
			arc.nodeA.firstA = arc.nextA;
		} else {
			while(prevArc.nextA != arc ) {
				prevArc = prevArc.nextA;
				if(prevArc == null) return;
			}
			prevArc.nextA = arc.nextA;
		}
		arc.nextA = null;
		arc.nodeA = null;
	}
	private void unlinkArcB(GArc<T> arc) {
		GArc<T> prevArc = arc.nodeB.firstB;
		if(prevArc == arc) {
			arc.nodeB.firstB = arc.nextB;
		} else {
			while(prevArc.nextB != arc ) {
				prevArc = prevArc.nextB;
				if(prevArc == null) return;
			}
			prevArc.nextB = arc.nextB;
		}
		arc.nextB = null;
		arc.nodeB = null;
	}
	
	void copy(Graph<T> graph) {
		Map<GNode<T>,GNode<T>> map = new HashMap<GNode<T>,GNode<T>>();
		reset();
		//for(GNode<T> n : graph) {
		for(GNode<T> n = graph.first; n != null; n = n.next) {
			GNode<T> n1 = new GNode<T>(n.data);
			map.put(n, n1);
			addNode(n1, -1);
		}
		//for(GNode<T> n : graph) {
		for(GNode<T> n = graph.first; n != null; n = n.next) {
			GNode<T> n1 = map.get(n);
			for(GArc<T> a = n.firstA; a != null; a = a.nextA)
				addArc(new GArc<T>(a.data), n1, map.get(a.nodeB));
		}
		checkLink();
	}
	void merge(Graph<T> graph) {
		if(graph.first == null) return;
		if(first != null) {
			last.next = graph.first;
		} else {
			first = graph.first;
		}
		last = graph.last;
		nNode += graph.nNode;
		nArc += graph.nArc;
		graph.first = graph.last  = null;
		graph.nNode = graph.nArc = 0;
	}

	public void checkLink() {
		if (!assertLink())
			System.err.println("***** CheckLink Failed ! *****");
	}
	private boolean assertLink() {
		GNode<T> n1 = null;
		//for(GNode<T> n : this) {
		for(GNode<T> n = first; n != null; n = n.next) {
			for(GArc<T> a = n.firstA; a != null; a = a.nextA) {
				if(a.nodeA != n) return false;
			}
			for(GArc<T> a = n.firstB; a != null; a = a.nextB) {
				if(a.nodeB != n) return false;
			}
			n1 = n;
		}
		return (n1 == last);
	}
	public void printGraph() {
		System.err.println("==>printGraph():");
		//for(GNode<T> n : this) {
		for(GNode<T> n = first; n != null; n = n.next) {
			System.err.println(n);
			for(GArc<T> a = n.firstA; a != null; a = a.nextA) {
				System.err.println("\t" + a);
			}
			System.err.println("\t======");
			for(GArc<T> a = n.firstB; a != null; a = a.nextB) {
				System.err.println("\t" + a);
			}
		}
	}
}

class GNode<T> implements Iterable<GNode<T>>, PrintableTree<GNode<T>> {
	GNode<T> next = null;
	GArc<T> firstA = null;
	GArc<T> firstB = null;
	T data = null;
	int flag = 0;
	GNode() {}
	GNode(T data) { this.data = data; }
	boolean hasOut() { return firstA != null; }
	boolean hasIn() { return firstB != null; }
	public String toString() {
		return "GNode[" + data + ", " + flag + "]";
	}
	public Iterator<GNode<T>> iterator() {
		return new Iterator<GNode<T>>() {
			GArc<T> cursor = firstA;
			public boolean hasNext() { return cursor != null;	}
			public GNode<T> next() {
				if(cursor == null) throw new NoSuchElementException();
				GArc<T> next = cursor;
				cursor = cursor.nextA;
				return next.nodeB;
			}
			public void remove() { }
		};
	}
	public boolean hasMember() {
		return flag == 0 && hasOut();
	}
	public String getContent(int type) {
		String mark = (flag == 1) ? (hasOut() ? " ->" : " *") : "";
		flag = 1;
		return data.toString() + mark;
	}
}
class GArc<T> {
	GNode<T> nodeA;
	GNode<T> nodeB;
	GArc<T>  nextA;
	GArc<T>  nextB;
	T data;
	GArc() {}
	GArc(T data) { this.data = data; }
	public String toString() {
		String a = (nodeA == null) ? "?" : nodeA.data.toString();
		String b = (nodeB == null) ? "?" : nodeB.data.toString();
		return "GArc[" + data + ", nodeA=" + a + ", nodeB=" + b + "]";
	}
}
