/* This software was developed within the context of the project Metaphor for Science
	Museums (Mesmuses) in the framework of the Information Society Technology
	Programme, part of the Fifth Research And Technological Development
	Framework Programme of the European Community, under the Consortium
	Agreement dated <June 30, 2001>, between INRIA, Finsiel Spa, IMSS,
	Valoris , CSI, ICS-FORTH, ENSTB, EDW International.
*/

/*
 *  CHANGE LOG:
 *
 *  Each entry starts with a date, who did the changed and what has been done.
 *  Separated by ':'.
 *
 *  12.11.2002 : Karsten Tolle : Changed so also Resources can be used to build up
 *                               a DAG.
 *  28.01.2003 : Sofia Alaxeki : Added getAllDescendants, getAllAncestors and
 *                                getRelatives. For distinct count of relatives.
 *
 *  28.01.2003 : Sofia Alaxeki : Added findRoots, getLeaves and getRoots
 */
// RDF_DAG.java

package gr.forth.ics.vrp.corevrp.model;

import java.util.*;

/**
 * RDF_DAG.java - DAG stands for Directed Acyclic Graph.
 *
 * This class has been generated to describe the Directed Acyclic Graph for classes
 * and properties in respect to the subClass and subProperty relations.
 * It consists of a HashMap containing the Objects as key and the corresponding
 * sub resources are in a HashSet as the value.
 * The graph might consist of several parts that are not connected. To enable an easy
 * traversal the roots are stored in a seperate ArrayList.
 *
 * @author Karsten Tolle & Sofia Alexaki
 * @version 2.5  (30 Januar 2003)
 */
public class RDF_DAG {


	// Creator
	/** Create a new RDF_DAG. We are creating an adjazenz list here.*/
	public RDF_DAG() {}

	// Variables
	/** Containing the elements of the adjazenz list.*/
	public HashMap dag = new HashMap();
	/** Containig the order of the graph (available after running loopcheck).*/
	private ArrayList order = new ArrayList(); // with a LinkedList it might can be improfed.
	/** Accessing the order. */
  public ArrayList getorder() { return order; }
	/** In case a loop occures during the method loopcheck it will be set to false.*/
	private boolean no_loop = true;
	/** In case of a loop the element causing the loop (not determistic) is saved here. (can be more than one) */
	private ArrayList loop_element = new ArrayList();

	private HashSet roots = new HashSet();
        /**
         *
         * @return The roots of the dag
         */
	public HashSet getroots() {
		return roots;
	}

	private HashSet leaves = new HashSet();

	public ArrayList getloop_element() { return loop_element; }

	public boolean getno_loop() {
		return no_loop;
	}

	public HashMap getdag() {
		return dag;
	}


  public void enter(String sub, String super_res) {
	 enter(sub, super_res, false);
  }

  public void enter(Resource sub, Resource super_res) {
		enter(sub,super_res,true);
  }

  public void enter(Object sub, Object super_res, boolean resource) {
	 if (!dag.containsKey(super_res)) {
		ArrayList new_al = new ArrayList();
		new_al.add(new HashSet());
		new_al.add(new HashSet());
		new_al.add(new Integer(0));
		new_al.add(new Integer(0));
		dag.put(super_res, new_al);
		roots.add(super_res);
	 }
	 if (roots.contains(sub)) roots.remove(sub); // remove the sub from the roots set
	 ArrayList al = (ArrayList)dag.get(super_res);
	 HashSet list = (HashSet)al.get(0);
	 String s;
	 if (resource) s = ((Resource)sub).getID(); else s = sub.toString();
	 if (list.contains(sub)) System.out.println("The class/property "+s+" is already a sub class/property for "+super_res);
	 else {
		  //Only in this case we need to add that the sub has a parent the super_res
		  list.add(sub);
		  if (!dag.containsKey(sub)) {
			  ArrayList new_al = new ArrayList();
			  new_al.add(new HashSet());
			  new_al.add(new HashSet());
			  new_al.add(new Integer(0));
			  new_al.add(new Integer(0));

				dag.put(sub, new_al);
		  }
		  al = (ArrayList)dag.get(sub);
		  list = (HashSet)al.get(1);
		  list.add(super_res);
	 }
  }

  public void enter(String s) {
	 if (!dag.containsKey(s)) {
		ArrayList al = new ArrayList();
		al.add(new HashSet());
		al.add(new HashSet());
		dag.put(s, al);
		roots.add(s);
	 }
  }

  public void enter(Resource s) {
	 if (!dag.containsKey(s)) {
		ArrayList al = new ArrayList();
		al.add(new HashSet());
		al.add(new HashSet());
		al.add(new Integer(0));
		al.add(new Integer(0));
		dag.put(s, al);
		roots.add(s);
	 }
  }

  /** Tries to remove the link from 'sub' to 'superResource' out of the DAG.*/
  public boolean remove(Resource sub, Resource super_res) {
		return remove(sub, super_res, true);
  }

  public boolean remove(String sub, String super_res) {
		return remove(sub, super_res, false);
  }

  public boolean remove(Resource res) {
    if (!dag.containsKey(res)) {
      return false;
    } else {
    	ArrayList al = (ArrayList)dag.get(res);
	HashSet list = (HashSet)al.get(0);
	HashSet list2 = (HashSet)al.get(1);
        if (list.size() == 0 && list2.size() == 0) {
          dag.remove(res);
          return true;
        }
    }
    return false;
  }


  public boolean remove(Object sub, Object super_res, boolean resource) {
		if (!dag.containsKey(super_res)) {
			 System.err.println("The class/property "+super_res+" is not entered jet.");
			 return false;
		} else {
			 ArrayList al = (ArrayList)dag.get(super_res);
			 HashSet list = (HashSet)al.get(0);
			 if (!list.contains(sub)) {
				  System.err.println("The class/property "+sub+" is not entered for "+super_res+" .");
				  return false;
			 } else {
				  list.remove(sub);
				  al = (ArrayList)dag.get(sub);
                                  /* Bug Fix 27-01-2002*/
                                  if ( dag.containsKey(sub) ) {
                                     ArrayList al2 = (ArrayList)dag.get(sub);
                        	     HashSet list2 = (HashSet)al2.get(1);
                        	     list2.remove(super_res);
                                  }
			 }
		}
		return true;
  }

  /**
	* Print the DAG-Graph to Std IO.
	*/
  public void enumerate() {
	 Collection keys = dag.keySet();
	 String s,v;
	 for (Iterator it1 = keys.iterator(); it1.hasNext(); ) {
	System.out.println();
		Object next = it1.next();
		ArrayList al = (ArrayList)dag.get(next);
		if (next instanceof Resource) s = ((Resource)next).getID();
		else s = next.toString();
		System.out.println("The sub resources of "+s+": ");
		HashSet values = (HashSet)al.get(0);
		for (Iterator it2 = values.iterator(); it2.hasNext(); ) {
			 Object value = it2.next();
			 if (value instanceof Resource) v = ((Resource)value).getID();
			 else v = value.toString();
			 System.out.println(v+" ");
		}
		/*System.out.println("#desc of "+s+": "+this.getdesc((Resource)next));
		System.out.println("The super resources of "+s+": ");
		values = (HashSet)al.get(1);
		for (Iterator it2 = values.iterator(); it2.hasNext(); ) {
			 Object value = it2.next();
			 if (value instanceof Resource) v = ((Resource)value).getID();
			 else v = value.toString();
			 System.out.println(v+" ");
		}*/
		//System.out.println("#ancs of "+s+": "+this.getancs((Resource)next));
	 }
  }

  /**
	* Checking the graph for loops and creating the topological order list. Returns true if there is no loop, otherwide it will return false
	*/
	public boolean loopcheck() {
		// Init
		// System.out.println("checking for loops in RDF_DAG");
		HashMap pred = new HashMap();
		HashMap color = new HashMap();
		order = new ArrayList();
		// painting all nodes white
		paint_white(color);
		Collection keys = color.keySet();
		for (Iterator it = keys.iterator(); it.hasNext(); ) {
			 Object next = it.next();
			 if (dag.containsKey(next)) { // if it is a sub class/property of a class/property
				  ArrayList al = (ArrayList)dag.get(next);
				  HashSet values = (HashSet)al.get(0);
				  if (color.get(next).equals("w")) {
						pred.put(next, null);
						visit(next, values, color, pred);
				  }
			 } else { // it is not a sub class/property
			 // changed on 18.08.2000
				  Object color_next = color.get(next.toString());
				  if (color_next.equals("w")) {
						color.put(next, "b");
						order.add(0,next);
				  }
			 }
		}
		// if (no_loop) System.out.println("no_loop is true"); else System.out.println("no_loop is false");
      if (no_loop) {
			 return true;
      }
		return false; // loop found
  }

  /** Make a deepsearch for the element <actual>. Will be called recursively.*/
  private void visit(Object actual, HashSet values, HashMap color, HashMap pred) {
		color.put(actual, "g");
		for (Iterator it = values.iterator(); it.hasNext(); ) {
			 Object next = it.next();
			 Object color_next = color.get(next);
			 if (color_next.equals("w")) {
				  pred.put(next, actual);
				  if (dag.containsKey(next)) {
						//put.out("in if!");
						ArrayList al = (ArrayList)dag.get(next);
						HashSet next_values = (HashSet)al.get(0);
						visit(next, next_values, color, pred);
				  } else {
						color.put(next, "b");
						order.add(0,next);
              }
          } else {
				  if (color_next.equals("g")) {
                  no_loop = false;
						loop_element.add(next);
				  }
          }
      }
      color.put(actual, "b");
      order.add(0,actual);
  }


	/** Return a string containing the topological order of the DAG.*/
	public String output() {
		StringBuffer bs = new StringBuffer();
		// bs.append("The graph in a topological order: \n");
		for (int i = 0; i < order.size(); ) {
								Object o = order.get(i++);
								String s;
								if (o instanceof Resource) s = ((Resource)o).getID();
								else s = o.toString();
			bs.append(s+", ");
		}
		return bs.toString();
	}

	/**
	 * Paint the whole graph white by entering the elements in the
	 * color hash map having the color "w".
	 */
	private void paint_white(HashMap color) {
		// painting all nodes white
		Collection keys = dag.keySet();
		for (Iterator it1 = keys.iterator(); it1.hasNext(); ) {
			Object next = it1.next();
			color.put(next,"w");
								ArrayList al = (ArrayList)dag.get(next);
								HashSet values = (HashSet)al.get(0);
			for (Iterator it2 = values.iterator(); it2.hasNext(); ) {
				Object value = it2.next();
				color.put(value, "w");
			}
		}
	}

	/**
	 * Find the leaves, i.e., the nodes without descendants based on the
	 * information
	 */
	public HashSet getLeaves() {
	  Collection keys = dag.keySet();
	  for (Iterator it1 = keys.iterator(); it1.hasNext(); ) {
	    Object next = it1.next();
	    ArrayList al = (ArrayList)dag.get(next);
	    HashSet desc = (HashSet)al.get(0);
	    if (desc.size() == 0) {
	      leaves.add(next);
	    }
	  }
          return leaves;
	}

	/**
	 * Recompute the roots, i.e., the nodes without ancestors based on the
	 * information
	 */
	public HashSet findRoots() {
	  Collection keys = dag.keySet();
          roots = new HashSet();
	  for (Iterator it1 = keys.iterator(); it1.hasNext(); ) {
	    Object next = it1.next();
	    ArrayList al = (ArrayList)dag.get(next);
	    HashSet anc = (HashSet)al.get(1);
	    if (anc.size() == 0) {
	      roots.add(next);
	    }
	  }
          return roots;
	}

  /**
    * Returns a HashSet containing all the distinct relatives of a node res
    * @param res the node reference
    * @param i When it is set to 0 it computes the distinct descendants of the
    * node. When it is set to 1 computes the distinct ancestors
    */
  public HashSet getRelatives(Resource res, int i) {
    HashSet rels = new HashSet();
    ArrayList al = (ArrayList)dag.get(res);
    if ( al == null) {
      return rels;
    }
    HashSet dRels = (HashSet)al.get(i);
    for (Iterator it1 = dRels.iterator(); it1.hasNext(); ) {
	Resource relNode = (Resource)it1.next();
	//If the ancNode is already an ancestor then we don't need to compute
	//its ancestors again
	if (!rels.contains(relNode) ) {
          rels.add(relNode);
	  rels.addAll((Collection)getRelatives(relNode, i));
	}
    }
    //Add the number of the distinct relatives in the dag
    Integer relsNum = new Integer(rels.size());
    if (i == 0) {
      al.add(2, relsNum);
    } else {
      al.add(3, relsNum);
    }
    //System.out.println(res.getID() +  rels.size());
    return rels;
  }

  /**
   * Computes the distinct descendants for all nodes under the <res> node
   * and put the number of the descendants in the dag
   */
  public void getAllDescendants(Resource res){
    getRelatives(res, 0);
  }

  /**
   * Computes the distinct ancestors for all nodes contained in the dag
   * and put the number of the descendants in the dag
   */
  public void getAllAncestors() {
    HashSet leaves = getLeaves();
    for (Iterator it1 = leaves.iterator(); it1.hasNext(); ) {
      Resource leaf = (Resource)it1.next();
      getRelatives(leaf , 1);
    }
  }

}
