uimaj-core/src/main/java/org/apache/uima/cas/impl/LinearTypeOrderBuilderImpl.java - uima-uimaj - Git at Google

 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *   http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing,
  * software distributed under the License is distributed on an
  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  * KIND, either express or implied.  See the License for the
  * specific language governing permissions and limitations
  * under the License.
  */

 package org.apache.uima.cas.impl;

 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;

 import org.apache.uima.cas.CAS;
 import org.apache.uima.cas.CASException;
 import org.apache.uima.cas.FeatureStructure;
 import org.apache.uima.cas.Type;
 import org.apache.uima.cas.TypeSystem;
 import org.apache.uima.cas.admin.CASAdminException;
 import org.apache.uima.cas.admin.LinearTypeOrder;
 import org.apache.uima.cas.admin.LinearTypeOrderBuilder;
 import org.apache.uima.internal.util.GraphNode;

 /**
  * Implementation of the <code>LinearTypeOrderBuilder</code> interface.
  *
  *
  */

 public class LinearTypeOrderBuilderImpl implements LinearTypeOrderBuilder {

         /**
          * An implementation of the {@link LinearTypeOrder LinearTypeOrder}
          * interface.
          *
          *
          */
   private static class TotalTypeOrder implements LinearTypeOrder {

     // The explicit order. We keep this since we need to return it. It would
     // be awkward and inefficient to compute it from lt.
     // index = orderNumber, value = type-code
     // used by serialization routines
     final private int[] order;

     // index= typeCode, value = order number
     final private short[] typeCodeToOrder;

     private boolean hashCodeComputed = false;

     private int computedHashCode;

     private TotalTypeOrder(String[] typeList, TypeSystem ts) throws CASException {
       this(encodeTypeList(typeList, ts), ts);
     }

     private static int[] encodeTypeList(String[] typeList, TypeSystem ts) throws CASException {
       int[] a = new int[typeList.length];
       LowLevelTypeSystem llts = (LowLevelTypeSystem) ts;
       for (int i = 0; i < a.length; i++) {
         int t = llts.ll_getCodeForTypeName(typeList[i]);
         if (t == LowLevelTypeSystem.UNKNOWN_TYPE_CODE) {
           throw new CASException(CASException.TYPEORDER_UNKNOWN_TYPE, typeList[i]);
         }
         a[i] = t;
       }
       return a;
     }

     /**
      * The constructor for the total type order, called by the other constructor and also when doing a
      *   cas complete deserialization, or just deserializing the type system/index defs
      *   Create the order from an array of type codes in ascending order.
      * @param typeList the list of ordered types
      * @param ts the type system
      */
     private TotalTypeOrder(int[] typeList, TypeSystem ts) {
       super();
       TypeSystemImpl tsi = (TypeSystemImpl) ts;
       this.order = typeList;
       final int sz = this.order.length + tsi.getSmallestType();
       if (sz > 32767) {
         /** Total number of UIMA types, {0}, exceeds the maximum of 32766. **/
         throw new CASAdminException(CASAdminException.TOO_MANY_TYPES, sz - 1);
       }
       this.typeCodeToOrder = new short[this.order.length + tsi.getSmallestType()];
       for (int i = 0; i < this.order.length; i++) {
         this.typeCodeToOrder[this.order[i]] = (short)i;
       }
     }


     /* (non-Javadoc)
      * @see org.apache.uima.cas.admin.LinearTypeOrder#compare(org.apache.uima.cas.impl.FeatureStructureImplC, org.apache.uima.cas.impl.FeatureStructureImplC)
      */
     @Override
     public int compare(FeatureStructure fs1, FeatureStructure fs2) {
       TypeImpl t1 = ((FeatureStructureImplC)fs1)._getTypeImpl();
       TypeImpl t2 = ((FeatureStructureImplC)fs2)._getTypeImpl();
       if (t1 == t2) return 0;
       return Short.compare(this.typeCodeToOrder[t1.getCode()],
                            this.typeCodeToOrder[t2.getCode()]);
     }

     // Look-up.
     @Override
     public boolean lessThan(Type t1, Type t2) {
       return lessThan(((TypeImpl) t1).getCode(), ((TypeImpl) t2).getCode());
       // return this.lt[((TypeImpl) t1).getCode()].get(((TypeImpl) t2)
       // .getCode());
     }

     @Override
     public boolean lessThan(int t1, int t2) {
       return this.typeCodeToOrder[t1] < this.typeCodeToOrder[t2];

       // return this.lt[t1].get(t2);
     }

     @Override
     public int[] getOrder() {
       return this.order;
     }

     @Override
     public int hashCode() {
       if (!hashCodeComputed) {
         computedHashCode = Arrays.hashCode(order);
         hashCodeComputed = true;
       }
       return computedHashCode;
     }

     @Override
     public boolean equals(Object obj) {
       if (this == obj) {
         return true;
       }
       if (obj == null) {
         return false;
       }
       if (getClass() != obj.getClass()) {
         return false;
       }
       TotalTypeOrder other = (TotalTypeOrder) obj;
       if (hashCode() != other.hashCode()) {
         return false;
       }
       if (!Arrays.equals(order, other.order)) {
         return false;
       }
       return true;
     }

   }

   private class Node extends GraphNode {

     private Node(Object o) {
       super(o);
     }

     private void removeAncestor(Node node) {
       this.predecessors.remove(node);
     }

     private int outRank() {
       return getNbrSucc();
     }

     private int inRank() {
       return getNbrPred();
     }

     private ArrayList<GraphNode> getAllPredecessors() {
       return this.predecessors;
     }

     private ArrayList<GraphNode> getAllSuccessors() {
       return this.successors;
     }

     private void removeSuccessor(int i) {
       this.successors.remove(i);
     }

     private void addAllPredecessors(ArrayList<? extends GraphNode> pred) {
       for (Iterator<? extends GraphNode> it = pred.iterator(); it.hasNext();) {
         Node n = (Node) it.next();
         if (!LinearTypeOrderBuilderImpl.this.order.pathFromTo(this, n)) {
           n.connect(this);
         }
         // else {
         // System.out.println("Testing: add predec: found loop from " +
         // this.getElement() + " to " +
         // n.getElement());
         // }
       }
     }

     private void addAllSuccessors(ArrayList<? extends GraphNode> successors1) {
       for (Iterator<? extends GraphNode> it = successors1.iterator(); it.hasNext();) {
         Node n = (Node) it.next();
         if (!LinearTypeOrderBuilderImpl.this.order.pathFromTo(n, this)) {
           connect(n);
         }
         // else {
         // System.out.println("Testing: add succ: found loop from " +
         // this.getElement() + " to " +
         // n.getElement());
         // }
       }
     }
   }

   private class Graph {

     // Map type names to graph nodes.
     private final HashMap<String, Node> nodeMap = new HashMap<String, Node>();

     private int size() {
       return this.nodeMap.size();
     }

     private Node getNode(String name) {
       Node node = this.nodeMap.get(name);
       if (node == null) {
         node = new Node(name);
         this.nodeMap.put(name, node);
       }
       return node;
     }

     private Graph copy(Node inRank0nodes) {
       Graph copy = new Graph();
       Iterator<Map.Entry<String, Node>> it = this.nodeMap.entrySet().iterator();
       Map.Entry<String, Node> entry;
       String key;
       // Copy the nodes.
       while (it.hasNext()) {
         entry = it.next();
         key = entry.getKey();
         copy.nodeMap.put(key, copy.getNode(key)); // getNode makes a new
                                                   // node
       }
       // Set pred's and succ's for nodes.
       it = this.nodeMap.entrySet().iterator();
       Node origNode, copyNode;
       while (it.hasNext()) {
         entry = it.next();
         key = entry.getKey();
         origNode = entry.getValue();
         copyNode = copy.nodeMap.get(key);
         for (int i = 0; i < origNode.inRank(); i++) {
           key = (String) origNode.getPredecessor(i).getElement();
           copyNode.addPredecessor(copy.getNode(key));
         }
         for (int i = 0; i < origNode.outRank(); i++) {
           key = (String) origNode.getSuccessor(i).getElement();
           copyNode.addSuccessor(copy.getNode(key));
         }
         if (origNode.inRank() == 0) {
           inRank0nodes.addSuccessor(origNode);
         }
       }
       return copy;
     }

     private ArrayList<Node> removeNode(Node node) {
       // Removing a node means removing it from the map (set of nodes) as
       // well
       // as removing outgoing references. Since we only remove nodes with
       // an
       // in-degree of 0, we don't need to worry about in-arcs.
       // Node node = (Node) this.nodeMap.get(name);
       ArrayList<Node> rank0s = new ArrayList<Node>();
       // if (node == null) {
       // return ;
       // }
       this.nodeMap.remove(node.getElement());
       final int max = node.outRank();
       for (int i = 0; i < max; i++) {
         Node n = (Node) node.getSuccessor(i);
         n.removeAncestor(node);
         if (n.inRank() == 0) {
           rank0s.add(n);
         }
       }
       return rank0s;
     }

     private boolean pathFromTo(Node n1, Node n2) {
       final HashMap<Node, Node> map = new HashMap<Node, Node>();
       return pathFromTo(n1, n2, map);
     }

     private boolean pathFromTo(Node n1, Node n2, HashMap<Node, Node> map) {
       if (n1 == n2) {
 	return true;
       }
       if (map.containsKey(n1)) {
 	return false;
       }
       map.put(n1, n1);
       for (int i = 0; i < n1.outRank(); i++) {
 	if (pathFromTo((Node) n1.getSuccessor(i), n2, map)) {
 	  return true;
 	}
       }
       return false;
     }

   }

   private Graph order;

   private TypeSystem ts;


   public LinearTypeOrderBuilderImpl(TypeSystem ts) {
     super();
     this.order = new Graph();
     this.ts = ts;
   }

   /**
    * The constructor for the total type order, called by the other constructor and also when doing a
    *   cas complete deserialization, or just deserializing the type system/index defs
    * @param typeList -
    * @param ts -
    * @return -
    */
   public static LinearTypeOrder createTypeOrder(int[] typeList, TypeSystem ts) {
     return new TotalTypeOrder(typeList, ts);
   }

   @Override
   public void add(String[] types) throws CASException {
     final int max = types.length - 1;
     boolean rc;
     for (int i = 0; i < max; i++) {
       rc = add(types[i], types[i + 1]);
       if (!rc) {
 	      throw new CASException(CASException.CYCLE_IN_TYPE_ORDER, types[i], types[i + 1]);
       }
     }
   }

   private boolean add(String s1, String s2) {
     final Node n1 = this.order.getNode(s1);
     final Node n2 = this.order.getNode(s2);
     if (this.order.pathFromTo(n1, n2)) {
       return true;
     }
     if (this.order.pathFromTo(n2, n1)) {
       return false;
     }
     n1.connect(n2);
     return true;
   }

   private void addInheritanceTypes() {
     List<Type> typesToModify = new ArrayList<Type>();

     for (Iterator<Type> tsi = this.ts.getTypeIterator(); tsi.hasNext();) {
       Type bottomType = tsi.next();

       Type type = bottomType;
       Node nIn = null;
       Node nOut = null;
       typesToModify.clear();

       while (true) {
       	String typeName = type.getName();
       	final Node n = this.order.getNode(typeName);
       	if ((nIn == null) && (n.inRank() != 0)) {
       	  nIn = n;
       	}
       	if ((nOut == null) && (n.outRank() != 0)) {
       	  nOut = n;
       	}
       	if ((nIn != null) && (nOut != null)) {
       	  break;
       	}
       	if (typeName.equals(CAS.TYPE_NAME_TOP)) {
       	  break;
       	}
       	typesToModify.add(type);
       	type = this.ts.getParent(type);
       }
       boolean doIn = true;
       boolean doOut = true;
       for (Iterator<Type> ni = typesToModify.iterator(); ni.hasNext();) {
 	type = ni.next();
 	String typeName = type.getName();
 	final Node n = this.order.getNode(typeName);
 	if (doIn && (nIn != null)) {
 	  if (n.inRank() == 0) {
 	    n.addAllPredecessors(nIn.getAllPredecessors());
 	  } else {
 	    doIn = false; // when going up the tree, when you find one
                                 // filled in, stop
 	  }
 	}
 	if (doOut && (nOut != null)) {
 	  if (n.outRank() == 0) {
 	    n.addAllSuccessors(nOut.getAllSuccessors());
 	  } else {
 	    doOut = false;
 	  }
 	}
       }
     } // for all types
   }

   @Override
   public LinearTypeOrder getOrder() throws CASException {
     addInheritanceTypes();
     Node inRank0Nodes = new Node("");
     Graph g = this.order.copy(inRank0Nodes);

     String[] totalOrder = new String[g.size()];
     // String s;
     for (int i = 0; i < totalOrder.length; i++) {
       Node n = (Node) inRank0Nodes.getSuccessor(0);
       totalOrder[i] = (String) n.getElement();
       inRank0Nodes.removeSuccessor(0);
       ArrayList<Node> newRank0Nodes = g.removeNode(n);
       for (Iterator<Node> it = newRank0Nodes.iterator(); it.hasNext();) {
 	      inRank0Nodes.addSuccessor(it.next());
       }
     }

     // System.out.println("Printing total order of types:");
     // for (int i = 0; i < totalOrder.length; i++) {
     // System.out.println(" " + totalOrder[i]);
     // }
     return new TotalTypeOrder(totalOrder, this.ts);
   }

 }
	/*
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the
	* "License"); you may not use this file except in compliance
	* with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing,
	* software distributed under the License is distributed on an
	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
	* KIND, either express or implied. See the License for the
	* specific language governing permissions and limitations
	* under the License.
	*/

	package org.apache.uima.cas.impl;

	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.HashMap;
	import java.util.Iterator;
	import java.util.List;
	import java.util.Map;

	import org.apache.uima.cas.CAS;
	import org.apache.uima.cas.CASException;
	import org.apache.uima.cas.FeatureStructure;
	import org.apache.uima.cas.Type;
	import org.apache.uima.cas.TypeSystem;
	import org.apache.uima.cas.admin.CASAdminException;
	import org.apache.uima.cas.admin.LinearTypeOrder;
	import org.apache.uima.cas.admin.LinearTypeOrderBuilder;
	import org.apache.uima.internal.util.GraphNode;

	/**
	* Implementation of the <code>LinearTypeOrderBuilder</code> interface.
	*
	*
	*/

	public class LinearTypeOrderBuilderImpl implements LinearTypeOrderBuilder {

	/**
	* An implementation of the {@link LinearTypeOrder LinearTypeOrder}
	* interface.
	*
	*
	*/
	private static class TotalTypeOrder implements LinearTypeOrder {

	// The explicit order. We keep this since we need to return it. It would
	// be awkward and inefficient to compute it from lt.
	// index = orderNumber, value = type-code
	// used by serialization routines
	final private int[] order;

	// index= typeCode, value = order number
	final private short[] typeCodeToOrder;

	private boolean hashCodeComputed = false;

	private int computedHashCode;

	private TotalTypeOrder(String[] typeList, TypeSystem ts) throws CASException {
	this(encodeTypeList(typeList, ts), ts);
	}

	private static int[] encodeTypeList(String[] typeList, TypeSystem ts) throws CASException {
	int[] a = new int[typeList.length];
	LowLevelTypeSystem llts = (LowLevelTypeSystem) ts;
	for (int i = 0; i < a.length; i++) {
	int t = llts.ll_getCodeForTypeName(typeList[i]);
	if (t == LowLevelTypeSystem.UNKNOWN_TYPE_CODE) {
	throw new CASException(CASException.TYPEORDER_UNKNOWN_TYPE, typeList[i]);
	}
	a[i] = t;
	}
	return a;
	}

	/**
	* The constructor for the total type order, called by the other constructor and also when doing a
	* cas complete deserialization, or just deserializing the type system/index defs
	* Create the order from an array of type codes in ascending order.
	* @param typeList the list of ordered types
	* @param ts the type system
	*/
	private TotalTypeOrder(int[] typeList, TypeSystem ts) {
	super();
	TypeSystemImpl tsi = (TypeSystemImpl) ts;
	this.order = typeList;
	final int sz = this.order.length + tsi.getSmallestType();
	if (sz > 32767) {
	/ Total number of UIMA types, {0}, exceeds the maximum of 32766. /
	throw new CASAdminException(CASAdminException.TOO_MANY_TYPES, sz - 1);
	}
	this.typeCodeToOrder = new short[this.order.length + tsi.getSmallestType()];
	for (int i = 0; i < this.order.length; i++) {
	this.typeCodeToOrder[this.order[i]] = (short)i;
	}
	}



	/* (non-Javadoc)
	* @see org.apache.uima.cas.admin.LinearTypeOrder#compare(org.apache.uima.cas.impl.FeatureStructureImplC, org.apache.uima.cas.impl.FeatureStructureImplC)
	*/
	@Override
	public int compare(FeatureStructure fs1, FeatureStructure fs2) {
	TypeImpl t1 = ((FeatureStructureImplC)fs1)._getTypeImpl();
	TypeImpl t2 = ((FeatureStructureImplC)fs2)._getTypeImpl();
	if (t1 == t2) return 0;
	return Short.compare(this.typeCodeToOrder[t1.getCode()],
	this.typeCodeToOrder[t2.getCode()]);
	}

	// Look-up.
	@Override
	public boolean lessThan(Type t1, Type t2) {
	return lessThan(((TypeImpl) t1).getCode(), ((TypeImpl) t2).getCode());
	// return this.lt[((TypeImpl) t1).getCode()].get(((TypeImpl) t2)
	// .getCode());
	}

	@Override
	public boolean lessThan(int t1, int t2) {
	return this.typeCodeToOrder[t1] < this.typeCodeToOrder[t2];

	// return this.lt[t1].get(t2);
	}

	@Override
	public int[] getOrder() {
	return this.order;
	}

	@Override
	public int hashCode() {
	if (!hashCodeComputed) {
	computedHashCode = Arrays.hashCode(order);
	hashCodeComputed = true;
	}
	return computedHashCode;
	}

	@Override
	public boolean equals(Object obj) {
	if (this == obj) {
	return true;
	}
	if (obj == null) {
	return false;
	}
	if (getClass() != obj.getClass()) {
	return false;
	}
	TotalTypeOrder other = (TotalTypeOrder) obj;
	if (hashCode() != other.hashCode()) {
	return false;
	}
	if (!Arrays.equals(order, other.order)) {
	return false;
	}
	return true;
	}

	}

	private class Node extends GraphNode {

	private Node(Object o) {
	super(o);
	}

	private void removeAncestor(Node node) {
	this.predecessors.remove(node);
	}

	private int outRank() {
	return getNbrSucc();
	}

	private int inRank() {
	return getNbrPred();
	}

	private ArrayList<GraphNode> getAllPredecessors() {
	return this.predecessors;
	}

	private ArrayList<GraphNode> getAllSuccessors() {
	return this.successors;
	}

	private void removeSuccessor(int i) {
	this.successors.remove(i);
	}

	private void addAllPredecessors(ArrayList<? extends GraphNode> pred) {
	for (Iterator<? extends GraphNode> it = pred.iterator(); it.hasNext();) {
	Node n = (Node) it.next();
	if (!LinearTypeOrderBuilderImpl.this.order.pathFromTo(this, n)) {
	n.connect(this);
	}
	// else {
	// System.out.println("Testing: add predec: found loop from " +
	// this.getElement() + " to " +
	// n.getElement());
	// }
	}
	}

	private void addAllSuccessors(ArrayList<? extends GraphNode> successors1) {
	for (Iterator<? extends GraphNode> it = successors1.iterator(); it.hasNext();) {
	Node n = (Node) it.next();
	if (!LinearTypeOrderBuilderImpl.this.order.pathFromTo(n, this)) {
	connect(n);
	}
	// else {
	// System.out.println("Testing: add succ: found loop from " +
	// this.getElement() + " to " +
	// n.getElement());
	// }
	}
	}
	}

	private class Graph {

	// Map type names to graph nodes.
	private final HashMap<String, Node> nodeMap = new HashMap<String, Node>();

	private int size() {
	return this.nodeMap.size();
	}

	private Node getNode(String name) {
	Node node = this.nodeMap.get(name);
	if (node == null) {
	node = new Node(name);
	this.nodeMap.put(name, node);
	}
	return node;
	}

	private Graph copy(Node inRank0nodes) {
	Graph copy = new Graph();
	Iterator<Map.Entry<String, Node>> it = this.nodeMap.entrySet().iterator();
	Map.Entry<String, Node> entry;
	String key;
	// Copy the nodes.
	while (it.hasNext()) {
	entry = it.next();
	key = entry.getKey();
	copy.nodeMap.put(key, copy.getNode(key)); // getNode makes a new
	// node
	}
	// Set pred's and succ's for nodes.
	it = this.nodeMap.entrySet().iterator();
	Node origNode, copyNode;
	while (it.hasNext()) {
	entry = it.next();
	key = entry.getKey();
	origNode = entry.getValue();
	copyNode = copy.nodeMap.get(key);
	for (int i = 0; i < origNode.inRank(); i++) {
	key = (String) origNode.getPredecessor(i).getElement();
	copyNode.addPredecessor(copy.getNode(key));
	}
	for (int i = 0; i < origNode.outRank(); i++) {
	key = (String) origNode.getSuccessor(i).getElement();
	copyNode.addSuccessor(copy.getNode(key));
	}
	if (origNode.inRank() == 0) {
	inRank0nodes.addSuccessor(origNode);
	}
	}
	return copy;
	}

	private ArrayList<Node> removeNode(Node node) {
	// Removing a node means removing it from the map (set of nodes) as
	// well
	// as removing outgoing references. Since we only remove nodes with
	// an
	// in-degree of 0, we don't need to worry about in-arcs.
	// Node node = (Node) this.nodeMap.get(name);
	ArrayList<Node> rank0s = new ArrayList<Node>();
	// if (node == null) {
	// return ;
	// }
	this.nodeMap.remove(node.getElement());
	final int max = node.outRank();
	for (int i = 0; i < max; i++) {
	Node n = (Node) node.getSuccessor(i);
	n.removeAncestor(node);
	if (n.inRank() == 0) {
	rank0s.add(n);
	}
	}
	return rank0s;
	}

	private boolean pathFromTo(Node n1, Node n2) {
	final HashMap<Node, Node> map = new HashMap<Node, Node>();
	return pathFromTo(n1, n2, map);
	}

	private boolean pathFromTo(Node n1, Node n2, HashMap<Node, Node> map) {
	if (n1 == n2) {
	return true;
	}
	if (map.containsKey(n1)) {
	return false;
	}
	map.put(n1, n1);
	for (int i = 0; i < n1.outRank(); i++) {
	if (pathFromTo((Node) n1.getSuccessor(i), n2, map)) {
	return true;
	}
	}
	return false;
	}

	}

	private Graph order;

	private TypeSystem ts;


	public LinearTypeOrderBuilderImpl(TypeSystem ts) {
	super();
	this.order = new Graph();
	this.ts = ts;
	}

	/**
	* The constructor for the total type order, called by the other constructor and also when doing a
	* cas complete deserialization, or just deserializing the type system/index defs
	* @param typeList -
	* @param ts -
	* @return -
	*/
	public static LinearTypeOrder createTypeOrder(int[] typeList, TypeSystem ts) {
	return new TotalTypeOrder(typeList, ts);
	}

	@Override
	public void add(String[] types) throws CASException {
	final int max = types.length - 1;
	boolean rc;
	for (int i = 0; i < max; i++) {
	rc = add(types[i], types[i + 1]);
	if (!rc) {
	throw new CASException(CASException.CYCLE_IN_TYPE_ORDER, types[i], types[i + 1]);
	}
	}
	}

	private boolean add(String s1, String s2) {
	final Node n1 = this.order.getNode(s1);
	final Node n2 = this.order.getNode(s2);
	if (this.order.pathFromTo(n1, n2)) {
	return true;
	}
	if (this.order.pathFromTo(n2, n1)) {
	return false;
	}
	n1.connect(n2);
	return true;
	}

	private void addInheritanceTypes() {
	List<Type> typesToModify = new ArrayList<Type>();

	for (Iterator<Type> tsi = this.ts.getTypeIterator(); tsi.hasNext();) {
	Type bottomType = tsi.next();

	Type type = bottomType;
	Node nIn = null;
	Node nOut = null;
	typesToModify.clear();

	while (true) {
	String typeName = type.getName();
	final Node n = this.order.getNode(typeName);
	if ((nIn == null) && (n.inRank() != 0)) {
	nIn = n;
	}
	if ((nOut == null) && (n.outRank() != 0)) {
	nOut = n;
	}
	if ((nIn != null) && (nOut != null)) {
	break;
	}
	if (typeName.equals(CAS.TYPE_NAME_TOP)) {
	break;
	}
	typesToModify.add(type);
	type = this.ts.getParent(type);
	}
	boolean doIn = true;
	boolean doOut = true;
	for (Iterator<Type> ni = typesToModify.iterator(); ni.hasNext();) {
	type = ni.next();
	String typeName = type.getName();
	final Node n = this.order.getNode(typeName);
	if (doIn && (nIn != null)) {
	if (n.inRank() == 0) {
	n.addAllPredecessors(nIn.getAllPredecessors());
	} else {
	doIn = false; // when going up the tree, when you find one
	// filled in, stop
	}
	}
	if (doOut && (nOut != null)) {
	if (n.outRank() == 0) {
	n.addAllSuccessors(nOut.getAllSuccessors());
	} else {
	doOut = false;
	}
	}
	}
	} // for all types
	}

	@Override
	public LinearTypeOrder getOrder() throws CASException {
	addInheritanceTypes();
	Node inRank0Nodes = new Node("");
	Graph g = this.order.copy(inRank0Nodes);

	String[] totalOrder = new String[g.size()];
	// String s;
	for (int i = 0; i < totalOrder.length; i++) {
	Node n = (Node) inRank0Nodes.getSuccessor(0);
	totalOrder[i] = (String) n.getElement();
	inRank0Nodes.removeSuccessor(0);
	ArrayList<Node> newRank0Nodes = g.removeNode(n);
	for (Iterator<Node> it = newRank0Nodes.iterator(); it.hasNext();) {
	inRank0Nodes.addSuccessor(it.next());
	}
	}

	// System.out.println("Printing total order of types:");
	// for (int i = 0; i < totalOrder.length; i++) {
	// System.out.println(" " + totalOrder[i]);
	// }
	return new TotalTypeOrder(totalOrder, this.ts);
	}

	}