package search.graph;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class BFS {
	
	public static void main(String[] args) {
		Graph<String> fortran = new Graph<String>("Fortran");
		Graph<String> algol = new Graph<String>("Algol");
		Graph<String> pli = new Graph<String>("PL/I");
		Graph<String> scheme = new Graph<String>("Scheme");
		Graph<String> c = new Graph<String>("C");
		Graph<String> cpp = new Graph<String>("C++");
		Graph<String> perl = new Graph<String>("Perl");
		Graph<String> tcl = new Graph<String>("Tcl");
		Graph<String> smalltalk = new Graph<String>("Smalltalk");
		Graph<String> pascal = new Graph<String>("Pascal");
		Graph<String> commonlisp = new Graph<String>("Common Lisp");
		Graph<String> java = new Graph<String>("Java");
		Graph<String> python = new Graph<String>("Python");
		Graph<String> csharp = new Graph<String>("C#");
		Graph<String> javascript = new Graph<String>("JavaScript");
		Graph<String> ruby = new Graph<String>("Ruby");
		Graph<String> ada = new Graph<String>("Ada");
		Graph<String> eiffel = new Graph<String>("Eiffel");
		
		fortran.addChild(algol);
		fortran.addChild(pli);
		algol.addChild(scheme);
		algol.addChild(pascal);
		algol.addChild(c);
		algol.addChild(cpp);
		algol.addChild(perl);
		algol.addChild(tcl);
		scheme.addChild(commonlisp);
		cpp.addChild(java);
		java.addChild(javascript);
		java.addChild(csharp);
		cpp.addChild(csharp);
		cpp.addChild(python);
		c.addChild(cpp);
		c.addChild(python);
		algol.addChild(perl);
		perl.addChild(ruby);
		python.addChild(ruby);
		smalltalk.addChild(ruby);
		pli.addChild(pascal);
		pascal.addChild(python);
		pascal.addChild(ada);
		ada.addChild(eiffel);
		
		for (String lang : fortran)
			System.out.println(lang);
	}
	
	public static class Graph<E> implements Iterable<E> {
		
		private E value;
		private List<Graph<E>> children;
		
		public Graph(E value) {
			this.value = value;
			this.children = new ArrayList<Graph<E>>();
		}

		public void addChild(Graph<E> child) {
			children.add(child);
		}

		@Override
		public Iterator<E> iterator() {
			return new GraphIterator<E>(this);
		}
		
		private static class GraphIterator<E> implements Iterator<E> {
			
			private Queue<Graph<E>> open;
			private Set<Graph<E>> closed;

			public GraphIterator(Graph<E> tree) {
				open = new LinkedList<Graph<E>>();
				open.offer(tree);
				closed = new HashSet<Graph<E>>();
			}
			
			@Override
			public boolean hasNext() {
				return !open.isEmpty();
			}

			@Override
			public E next() {
				Graph<E> t = open.poll();
				closed.add(t);
				for (Graph<E> v : t.children)
					if (closed.add(v))
						open.offer(v);
				return t.value;
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();
				
			}
			
		}

	}

}