001: /*
002: * $RCSfile: OperationGraph.java,v $
003: *
004: * Copyright (c) 2005 Sun Microsystems, Inc. All rights reserved.
005: *
006: * Use is subject to license terms.
007: *
008: * $Revision: 1.1 $
009: * $Date: 2005/02/11 04:57:13 $
010: * $State: Exp $
011: */
012: package javax.media.jai;
013:
014: import java.util.Enumeration;
015: import java.util.Vector;
016:
017: /**
018: * OperationGraph manages a list of <code>PartialOrderNode</code>s
019: * and pairwise preferences between them.
020: *
021: * The getOrderedOperationList method performs a topological sort.
022: * The topological sort follows the algorithm described in Horowitz
023: * and Sahni, <i>Fundamentals of Data Structures</i> (1976), p. 315.
024: *
025: * <p> Several minor changes are made to their implementation. First,
026: * nodes are represented as objects, not as integers. The count
027: * (in-degree) field is not used to link zero in-degree objects, but
028: * instead a separate zeroLink field is used. The neighbor lists are
029: * stored as Vectors, not linked lists, and enumerations are used
030: * to iterate over them.
031: *
032: * <p> This class is used by the implementation of the OperationRegistry
033: * class and is not intended to be part of the API.
034: *
035: * - what was OperationGraph pre-JAI 1.1 is now FactoryOperationGraph
036: *
037: */
038: class OperationGraph implements java.io.Serializable {
039:
040: /**
041: * A Vector of <code>PartialOrderNode</code>s, each
042: * <code>PartialOrderNode</code> contains the name of the operation
043: * and the <code>OperationGraph</code> that contains the image
044: * factories implementing that operation.
045: */
046: Vector operations = new Vector();
047:
048: /** A cached version of the ordered product list */
049: Vector orderedOperations;
050:
051: /** Signifies whether the cached copy is out of date. */
052: boolean isChanged = true;
053:
054: /**
055: * If true, use a case-insensitive compare of the name of the
056: * <code>PartialOrderNode</code> for lookups.
057: */
058: private boolean lookupByName = false;
059:
060: /**
061: * Constructs an <code>OperationGraph</code>.
062: * The default comparision for lookups is by object reference.
063: */
064: OperationGraph() {
065: }
066:
067: /**
068: * Specify the comparator used to compare the PartialOrderNode
069: * with an object (used for lookupOp)
070: *
071: * @param lookupByName if true lookup does a case-insensitive
072: * compare of the object being looked up with the
073: * <code>PartialOrderNode</code> name. Needless to say,
074: * this works only if the objects being looked
075: * up are <code>String</code>s.
076: */
077: OperationGraph(boolean lookupByName) {
078: this .lookupByName = lookupByName;
079: }
080:
081: /**
082: * The comparison used for lookups.
083: */
084: private boolean compare(PartialOrderNode poNode, Object op) {
085: if (lookupByName)
086: return poNode.getName().equalsIgnoreCase((String) op);
087: else
088: return poNode.getData() == op;
089: }
090:
091: /**
092: * Adds a PartialOrderNode to an <code>OperationGraph</code>.
093: */
094: void addOp(PartialOrderNode poNode) {
095:
096: operations.addElement(poNode);
097: isChanged = true;
098: }
099:
100: /**
101: * Removes the PartialOrderNode corresponding to the operation
102: * from an <code>OperationGraph</code>.
103: *
104: * Does a "lookupOp" of the PartialOrderNode corresponding to "op"
105: * and removes it.
106: */
107: synchronized boolean removeOp(Object op) {
108:
109: boolean retval = false;
110:
111: PartialOrderNode poNode = lookupOp(op);
112:
113: if (poNode != null) {
114: retval = operations.removeElement(poNode);
115:
116: if (retval)
117: isChanged = true;
118: }
119:
120: return retval;
121: }
122:
123: /**
124: * Locates an operation from within the vector of PartialOrderNodes
125: * using the object provided.
126: */
127: PartialOrderNode lookupOp(Object op) {
128:
129: int num = operations.size();
130:
131: for (int i = 0; i < num; i++) {
132: PartialOrderNode poNode = (PartialOrderNode) operations
133: .elementAt(i);
134:
135: if (compare(poNode, op)) {
136: PartialOrderNode tempNode = poNode;
137: return tempNode;
138: }
139: }
140:
141: return null;
142: }
143:
144: /** Sets a preference between two operations. */
145: synchronized boolean setPreference(Object preferred, Object other) {
146: boolean retval = false;
147:
148: if ((preferred == null) || (other == null)) {
149: throw new IllegalArgumentException(JaiI18N
150: .getString("Generic0"));
151: }
152:
153: if (preferred == other)
154: return retval;
155:
156: PartialOrderNode preferredPONode = lookupOp(preferred);
157: PartialOrderNode otherPONode = lookupOp(other);
158:
159: if ((preferredPONode != null) && (otherPONode != null)) {
160: preferredPONode.addEdge(otherPONode);
161:
162: retval = true;
163: isChanged = true;
164: }
165:
166: return retval;
167: }
168:
169: /** Removes a preference between two operations. */
170: synchronized boolean unsetPreference(Object preferred, Object other) {
171: boolean retval = false;
172:
173: if ((preferred == null) || (other == null)) {
174: throw new IllegalArgumentException(JaiI18N
175: .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: */
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
210: .elementAt(i);
211: pon.setCopyInDegree(pon.getInDegree());
212: }
213:
214: // Cache the ordered list in orderedOperations, and update the
215: // isChanged variable to reflect that this is a newly computed list.
216: orderedOperations = new Vector(num);
217: isChanged = false;
218:
219: // A linked list of nodes with zero in-degree
220: PartialOrderNode zeroList = null;
221: PartialOrderNode poNode;
222: int i;
223:
224: // Scan for elements with 0 in-degree
225: for (i = 0; i < num; i++) {
226: poNode = (PartialOrderNode) operations.elementAt(i);
227: if (poNode.getCopyInDegree() == 0) {
228: poNode.setZeroLink(zeroList);
229: zeroList = poNode;
230: }
231: }
232:
233: // Loop for each node
234: for (i = 0; i < num; i++) {
235: // No free vertices, must be a cycle somewhere
236: if (zeroList == null) {
237: orderedOperations = null;
238: return null; // Cycle exists
239: }
240:
241: // Set firstNode to a node from the free list
242: // and add it to the output.
243: PartialOrderNode firstNode = zeroList;
244:
245: orderedOperations.addElement(firstNode);
246:
247: // Bump the free list pointer
248: zeroList = zeroList.getZeroLink();
249: // For each neighbor of the output node, decrement its in-degree
250: Enumeration neighbors = firstNode.getNeighbors();
251: while (neighbors.hasMoreElements()) {
252: poNode = (PartialOrderNode) neighbors.nextElement();
253: poNode.decrementCopyInDegree();
254:
255: // If the in-degree has fallen to 0,
256: // place the node on the free list.
257: if (poNode.getCopyInDegree() == 0) {
258: poNode.setZeroLink(zeroList);
259: zeroList = poNode;
260: }
261: }
262: }
263:
264: Vector ordered = orderedOperations;
265: return ordered;
266: }
267: }
|