1 /* 2 * $RCSfile: OperationGraph.java,v $ 3 * 4 * Copyright (c) 2005 Sun Microsystems, Inc. All rights reserved. 5 * 6 * Use is subject to license terms. 7 * 8 * $Revision: 1.1 $ 9 * $Date: 2005/02/11 04:57:13 $ 10 * $State: Exp $ 11 */ 12 package com.lightcrafts.mediax.jai; 13 14 import java.util.Enumeration; 15 import java.util.Vector; 16 17 /** 18 * OperationGraph manages a list of <code>PartialOrderNode</code>s 19 * and pairwise preferences between them. 20 * 21 * The getOrderedOperationList method performs a topological sort. 22 * The topological sort follows the algorithm described in Horowitz 23 * and Sahni, <i>Fundamentals of Data Structures</i> (1976), p. 315. 24 * 25 * <p> Several minor changes are made to their implementation. First, 26 * nodes are represented as objects, not as integers. The count 27 * (in-degree) field is not used to link zero in-degree objects, but 28 * instead a separate zeroLink field is used. The neighbor lists are 29 * stored as Vectors, not linked lists, and enumerations are used 30 * to iterate over them. 31 * 32 * <p> This class is used by the implementation of the OperationRegistry 33 * class and is not intended to be part of the API. 34 * 35 * - what was OperationGraph pre-JAI 1.1 is now FactoryOperationGraph 36 * 37 */ 38 class OperationGraph implements java.io.Serializable { 39 40 /** 41 * A Vector of <code>PartialOrderNode</code>s, each 42 * <code>PartialOrderNode</code> contains the name of the operation 43 * and the <code>OperationGraph</code> that contains the image 44 * factories implementing that operation. 45 */ 46 Vector operations = new Vector(); 47 48 /** A cached version of the ordered product list */ 49 Vector orderedOperations; 50 51 /** Signifies whether the cached copy is out of date. */ 52 boolean isChanged = true; 53 54 /** 55 * If true, use a case-insensitive compare of the name of the 56 * <code>PartialOrderNode</code> for lookups. 57 */ 58 private boolean lookupByName = false; 59 60 /** 61 * Constructs an <code>OperationGraph</code>. 62 * The default comparision for lookups is by object reference. 63 */ OperationGraph()64 OperationGraph() {} 65 66 /** 67 * Specify the comparator used to compare the PartialOrderNode 68 * with an object (used for lookupOp) 69 * 70 * @param lookupByName if true lookup does a case-insensitive 71 * compare of the object being looked up with the 72 * <code>PartialOrderNode</code> name. Needless to say, 73 * this works only if the objects being looked 74 * up are <code>String</code>s. 75 */ OperationGraph(boolean lookupByName)76 OperationGraph(boolean lookupByName) { 77 this.lookupByName = lookupByName; 78 } 79 80 /** 81 * The comparison used for lookups. 82 */ compare(PartialOrderNode poNode, Object op)83 private boolean compare(PartialOrderNode poNode, Object op) { 84 if (lookupByName) 85 return poNode.getName().equalsIgnoreCase((String)op); 86 else 87 return poNode.getData() == op; 88 } 89 90 /** 91 * Adds a PartialOrderNode to an <code>OperationGraph</code>. 92 */ addOp(PartialOrderNode poNode)93 void addOp(PartialOrderNode poNode) { 94 95 operations.addElement(poNode); 96 isChanged = true; 97 } 98 99 /** 100 * Removes the PartialOrderNode corresponding to the operation 101 * from an <code>OperationGraph</code>. 102 * 103 * Does a "lookupOp" of the PartialOrderNode corresponding to "op" 104 * and removes it. 105 */ removeOp(Object op)106 synchronized boolean removeOp(Object op) { 107 108 boolean retval = false; 109 110 PartialOrderNode poNode = lookupOp(op); 111 112 if (poNode != null) { 113 retval = operations.removeElement(poNode); 114 115 if (retval) 116 isChanged = true; 117 } 118 119 return retval; 120 } 121 122 /** 123 * Locates an operation from within the vector of PartialOrderNodes 124 * using the object provided. 125 */ lookupOp(Object op)126 PartialOrderNode lookupOp(Object op) { 127 128 int num = operations.size(); 129 130 for (int i = 0; i < num; i++) { 131 PartialOrderNode poNode = (PartialOrderNode)operations.elementAt(i); 132 133 if (compare(poNode, op)) { 134 PartialOrderNode tempNode = poNode; 135 return tempNode; 136 } 137 } 138 139 return null; 140 } 141 142 /** Sets a preference between two operations. */ setPreference(Object preferred, Object other)143 synchronized boolean setPreference(Object preferred, 144 Object other) { 145 boolean retval = false; 146 147 if ((preferred == null) || (other == null)) { 148 throw new IllegalArgumentException( 149 JaiI18N.getString("Generic0")); 150 } 151 152 if (preferred == other) 153 return retval; 154 155 PartialOrderNode preferredPONode = lookupOp(preferred); 156 PartialOrderNode otherPONode = lookupOp(other); 157 158 if ((preferredPONode != null) && (otherPONode != null)) { 159 preferredPONode.addEdge(otherPONode); 160 161 retval = true; 162 isChanged = true; 163 } 164 165 return retval; 166 } 167 168 /** Removes a preference between two operations. */ unsetPreference(Object preferred, Object other)169 synchronized boolean unsetPreference(Object preferred, 170 Object other) { 171 boolean retval = false; 172 173 if ((preferred == null) || (other == null)) { 174 throw new IllegalArgumentException( 175 JaiI18N.getString("Generic0")); 176 } 177 178 if (preferred == other) 179 return retval; 180 181 PartialOrderNode preferredPONode = lookupOp(preferred); 182 PartialOrderNode otherPONode = lookupOp(other); 183 184 if ((preferredPONode != null) && (otherPONode != null)) { 185 preferredPONode.removeEdge(otherPONode); 186 187 retval = true; 188 isChanged = true; 189 } 190 191 return retval; 192 } 193 194 /** 195 * Performs a topological sort on the set of 196 * <code>PartialOrderNodes</code>. 197 */ getOrderedOperationList()198 public synchronized Vector getOrderedOperationList() { 199 200 // If the cached copy is still current, return it 201 if (isChanged == false) { 202 203 Vector ordered = orderedOperations; 204 return ordered; 205 } 206 207 int num = operations.size(); // The number of nodes in the digraph 208 for (int i=0; i<num; i++) { 209 PartialOrderNode pon = (PartialOrderNode)operations.elementAt(i); 210 pon.setCopyInDegree(pon.getInDegree()); 211 } 212 213 // Cache the ordered list in orderedOperations, and update the 214 // isChanged variable to reflect that this is a newly computed list. 215 orderedOperations = new Vector(num); 216 isChanged = false; 217 218 // A linked list of nodes with zero in-degree 219 PartialOrderNode zeroList = null; 220 PartialOrderNode poNode; 221 int i; 222 223 // Scan for elements with 0 in-degree 224 for (i = 0; i < num; i++) { 225 poNode = (PartialOrderNode)operations.elementAt(i); 226 if (poNode.getCopyInDegree() == 0) { 227 poNode.setZeroLink(zeroList); 228 zeroList = poNode; 229 } 230 } 231 232 // Loop for each node 233 for (i = 0; i < num; i++) { 234 // No free vertices, must be a cycle somewhere 235 if (zeroList == null) { 236 orderedOperations = null; 237 return null; // Cycle exists 238 } 239 240 // Set firstNode to a node from the free list 241 // and add it to the output. 242 PartialOrderNode firstNode = zeroList; 243 244 orderedOperations.addElement(firstNode); 245 246 // Bump the free list pointer 247 zeroList = zeroList.getZeroLink(); 248 // For each neighbor of the output node, decrement its in-degree 249 Enumeration neighbors = firstNode.getNeighbors(); 250 while (neighbors.hasMoreElements()) { 251 poNode = (PartialOrderNode)neighbors.nextElement(); 252 poNode.decrementCopyInDegree(); 253 254 // If the in-degree has fallen to 0, 255 // place the node on the free list. 256 if (poNode.getCopyInDegree() == 0) { 257 poNode.setZeroLink(zeroList); 258 zeroList = poNode; 259 } 260 } 261 } 262 263 Vector ordered = orderedOperations; 264 return ordered; 265 } 266 } 267