/*********************** Author: J. Steensgaard-Madsen *************
 * 
 * A partial ordering is a transitive and asymmetric relation.
 * A total ordering in addition relates any two values.
 *
 * Problem: 
 *   find a total ordering which reduces to a given partial
 *   ordering by removal of some pairs.
 *
 * Topological sorting is one method to solve the problem.
 *
 * The class below provides means to state and solve particular 
 * problems of this kind.
 *
 *******************************************************************/

interface Printable {
    public void print();
}

public class POset implements Printable {

    /***************************************************************
     * POset provides means to define a partially ordered set
     *
     * public class POset 
     *    extends java.lang.Object implements Printable 
     * {
     *    public POset.POitems first;
     *    public POset();
     *    public void print();
     *    public class POset. POitems extends java.lang.Object {
     *        public Printable contents;
     *        public void precedes(POset.POitems);
     *        public POset.POitems next() throws java.lang.Exception;
     *        public POset.POitems(POset,Printable);
     *    }
     * }
     *
     * Users may generate elements and indicate a required order of
     * given pairs.  A list of all elements that does not violate 
     * the required one can be accessed.
     *
     ***************************************************************/

    public POitems 
	first;      // The first element of the list of all

    private boolean
	modified;   // Set to true with a new order requirement

    private class Succ {

	/* A class of objects for a list of required successors    */

	Succ next;      // the next in the list of successors
	POitems item;   // the element required to follow
    }


    public void print() {
	/** 
	 * Format:
	 *   { x_1 {y_1_1,y_1_2,y_1_3,...}, 
	 *     x_2 {y_2_1,y_2_2,y_2_3,...},
	 *     ...
	 *   }
	 *
	 * where (x_i,y_k) corresponds to u.precedes(v) with
	 * x_i corresponding to u.print() and y_k to v.print()
	 *
	 ***********************************************************/

	POitems temp = first;  // to traverse the list of all
	Succ    aux;           // to traverse the successor list

	System.out.print("{");
	while (temp != null) {
	    temp.contents.print();
	    aux = temp.successor;
	    System.out.print(" {");
	    while (aux != null) {
		aux.item.contents.print();
		aux = aux.next;
		if (aux != null) System.out.print(",");
	    }
	    System.out.print("}");
	    temp = temp.next_item;
	    if (temp != null) System.out.print(",\n");
	}
	System.out.print("}\n");
    }
	


    public class POitems {

	/***********************************************************
	 * Objects of type POitems represents elements of POset.
	 * Member functions:
	 *
	 *   a.prededes(POitems b)   requires b to succeed a
	 *   a.next()                a's successor in the list of all
	 *
	 ***********************************************************/

	private Succ 
	    successor;    // A list of required successor POitems

	private POitems 
	    next_item;    // The next element in the list of all

	public Printable 
	    contents;     // Provided by users

	private int 
	    predecessors; // The number of required predecessors

	public void precedes(POitems x) {

	    /* Enters x in a new element in the list of 
	     * required successors of this 
	     ********************************************************/

	    Succ y = new Succ();  // the new element

	    y.item = x;
	    y.next = successor;
	    successor = y;
	    modified = true;
	}

	public POitems next() throws Exception  {

	    /* returns the next element in the list of all, provided
	     * no new element or no new required order.
	     ********************************************************/

	    Exception bad = new Exception("Untimely modification"); 

	    if (modified) {
		if (first != this) 
		    throw bad;
		topsort();
	    }

	    return next_item;
	}


	private void count_predecessors() {

            /* An element with no required predecessors may be first
	     * in the list of all.  Later one can then simulate the
	     * removal of that element so that the next may be found
	     * likewise
	     ********************************************************/

	    POitems 
		item = first;  // to traverse the list of all
	    Succ 
		temp;          // to traverse the successors list

	    while (item != null) {
		temp = item.successor;
		while (temp != null) {
		    temp.item.predecessors += 1;
		    temp = temp.next;
		}
		item = item.next_item;
	    }
	}

	private POitems get_entry() throws Exception  {

	    /* Finds and removes an element for which no
	     * required predecessor remains.
	     ********************************************************/

	    POitems 
		entry = first, // to traverse the list of all
		pred = null;   // the predecessor of entry
	    Succ 
		temp;          // to traverse the successors list
	    Exception bad 
		= new Exception("No partial ordering");

	    while (entry != null && entry.predecessors != 0) {
		pred = entry;
		entry = entry.next_item;
	    }

	    // No such element exists: no partial ordering
	    if (entry == null) throw bad;

	    // Remove the element
	    if (pred == null) first = entry.next_item;
	    else pred.next_item = entry.next_item;
	    entry.next_item = null;

	    // Reduce the counts of predessors correspondingly
	    temp = entry.successor;
	    while (temp != null) {
		temp.item.predecessors -= 1;
		temp = temp.next;
	    }

	    return entry;
	}


	private void topsort() throws Exception {

	    /* Topological sort is an algorithm to find a total
	     * ordering that agrees with a given partial ordering
	     * Let solution(first) denote an ordering corresponding
	     * to the current value of first.
	     *******************************************************/

	    POitems 
		entry,          // a possible first
		temp = null;    // a list of previous, possible firsts

	    count_predecessors();

	    // extract a possible first and put in on the temp-list
	    while (first != null) { 
		/*
		 * INV: length(temp) + length(first)
		 * INV: reverse(temp) ++ solution(first)
		 *  -- where ++ denotes list concatenation
		 */
		entry = get_entry();
		entry.next_item = temp;
		temp = entry;
	    }

	    // the new total ordering is the reverse of temp
	    while (temp != null) {
		/* 
		 * INV: reverse(temp) ++ first
		 */
		entry = temp; 
		temp  = temp.next_item;
		entry.next_item = first;
		first = entry;
	    }

	    modified = false;
	}

	public POitems(Printable x) {

	    /* Instantiate a POitems object and let its contents be x */

	    successor = null;
	    next_item = first; 
	    first = this;
	    predecessors = 0;
	    contents = x;
	    modified = true;
	}

	/****************** End of class POitems **********************/

    }

    /********************** End of class POset   **********************/

}