/*
    *  XNap - A P2P framework and client.
    *
    *  See the file AUTHORS for copyright information.
    *
    *  This program is free software; you can redistribute it and/or modify
    *  it under the terms of the GNU General Public License as published by
    *  the Free Software Foundation.
    *
   *  This program is distributed in the hope that it will be useful,
   *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   *  GNU General Public License for more details.
   *
   *  You should have received a copy of the GNU General Public License
   *  along with this program; if not, write to the Free Software
   *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   */
  
  package org.xnap.pkg;
  
  import java.util.Arrays;
  import java.util.HashSet;
  import java.util.Hashtable;
  import java.util.Iterator;
  import java.util.LinkedList;
  import java.util.TreeMap;
  
  /***
   * 
   */
  public class DependencyGraph
  {
  
      //--- Constant(s) ---
  
      //--- Data field(s) ---
  	
  	private PackageManager manager;
  
  	private AndDependencyNode root;
  	private TreeMap nodeByPackage = new TreeMap();
  	private Hashtable nodeByToken = new Hashtable();
  	private LinkedList unparsedNodes = new LinkedList();
  
      //--- Constructor(s) ---
  
  	public DependencyGraph(PackageManager manager)
      {
  		this.manager = manager;
  		root = new AndDependencyNode("Root");
      }
  
      //--- Method(s) ---
  
  	public void add(PackageInfo info)
  	{
   		DependencyNode node	= addNode(info);
  		root.add(node);
  	}
  
  	public void buildDependencies(DependencyParser parser) throws ParseException
  	{
  		while (!unparsedNodes.isEmpty()) {
  			PackageDependencyNode node
  				= (PackageDependencyNode)unparsedNodes.removeFirst();
  
  			try {
  				// add depends
  				AbstractToken token = parser.parseDepends(node.getPackage());
  				if (token != null) {
  					node.setDepends(add(token));
  				}
  
  				// add conflicts
  				token = parser.parseConflicts(node.getPackage());
  				if (token != null) {
  					node.setConflicts(new ConflictsDependencyNode
  						("conflicts for " + node.getID(),
  						 add(token)));
  				}
  			}
  			catch (ParseException e) {
  				throw new ParseException("Invalid package description for " 
  										 + node.toString()
  										 + "(" + e.getMessage() + ")");
  			}
   		}
  	}
  
  	public DependencyNode getRoot()
  	{
  		return root;
  	}
  
  	public Iterator preorderIterator()
  	{
  		return new PreorderIterator(root);
  	}
 
  	private DependencyNode add(AbstractToken token)
  	{
 		DependencyNode node = (DependencyNode)nodeByToken.get(token.toString());
 		if (node != null) {
 			return node;
 		}
 		else if (token instanceof CommaToken) {
 			return add((CommaToken)token);
 		}
 		else if (token instanceof PipeToken) {
 			return add((PipeToken)token);
 		}
 		else if (token instanceof PackageToken) {
 			return add((PackageToken)token);
 		}
 
  		throw new RuntimeException("Unknown token: " + token);
  	}
 
 	private DependencyNode[] add(AbstractToken[] tokens)
 	{
 		DependencyNode[] nodes = new DependencyNode[tokens.length];
 		for (int i = 0; i < tokens.length; i++) {
 			DependencyNode node = (DependencyNode)nodeByToken.get(tokens[i]);
 			nodes[i] = (node != null) ? node : add(tokens[i]);
 		}
 		return nodes;
 	}
 
 	private DependencyNode add(CommaToken token)
 	{
 		LinkedList list = new LinkedList(Arrays.asList(add(token.depends)));
 		AndDependencyNode node = new AndDependencyNode(token.toString(), list);
 		return addNode(token.toString(), node);
 	}
 
 	private DependencyNode add(PipeToken token)
 	{
 		LinkedList list = new LinkedList(Arrays.asList(add(token.depends)));
 		OrDependencyNode node = new OrDependencyNode(token.toString(), list);
 		return addNode(token.toString(), node);
 	}
 
 	private DependencyNode add(PackageToken token)
 	{
 		LinkedList list = new LinkedList();
 
 		// packages
 		for (Iterator i = manager.tailSet(token.name).iterator(); i.hasNext();) {
 			PackageInfo info = (PackageInfo)i.next();
 			if (info.getPackage().equals(token.name)) {
 				if (token.compareMode == null
 					|| token.equalsVersion(info.compareToVersion
 										   (token.version))) {
 					// get package node
 					list.add(addNode(info));
 				}
 			}
 			else {
 				break;
 			}
 		}
 	
 		// provides
 		if (token.compareMode == null) {
 			PackageInfo[] providers = manager.getProviders(token.name);
 			if (providers != null) {
 				for (int i = 0; i < providers.length; i++) {
 					list.add(addNode(providers[i]));
 				}
 			}
 		}
 
 		if (list.size() == 0) {
 			return addNode(token.toString(), 
 						   new UnsatisfiedDependencyNode(token.toString()));
 		}
 		else if (list.size() == 1) {
 			return addNode(token.toString(), (DependencyNode)list.get(0));
 		}
 		else {
 			return addNode(token.toString(), 
 						   new OrDependencyNode(token.toString(), list));
 		}
 	}
 
 	private DependencyNode addNode(String token, DependencyNode node)
 	{
 		nodeByToken.put(token, node);
 		return node;
 	}
 
 	private DependencyNode addNode(PackageInfo info)
 	{
 		DependencyNode node = (DependencyNode)nodeByPackage.get(info);
 		if (node == null) {
 			node = new PackageDependencyNode(info);
 			nodeByPackage.put(info, node);
 			unparsedNodes.add(node);
 		}
 		return node;
 	}
 
 	//--- Inner Class(es) ---
 
 	public static class PreorderIterator implements Iterator 
 	{
 		private HashSet visited = new HashSet();
 		private LinkedList stack = new LinkedList();
 
 		public PreorderIterator(DependencyNode rootNode) 
 		{
 			for (Iterator i = rootNode.children(); i.hasNext();) {
 				DependencyNode node = (DependencyNode)i.next();
 				visited.add(node);
 				stack.addFirst(node);
 			}
 		}
 
 		public boolean hasNext() 
 		{
 			return !stack.isEmpty();
 		}
 
 		public Object next() 
 		{
 			DependencyNode parent = (DependencyNode)stack.removeFirst();
 
 			for (Iterator i = parent.children(); i.hasNext();) {
 				DependencyNode node = (DependencyNode)i.next();
 				
 				if (!visited.contains(node)) {
 					visited.add(node);
 					stack.addFirst(node);
 				}
 			}
 
 			return parent;
 		}
 
 		public void remove()
 		{
 			throw new UnsupportedOperationException();
 		}
 
     }
 
 }