1 /* 2 * Copyright (c) 2000, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package javax.imageio.spi; 27 28 import java.io.Serializable; 29 import java.util.HashSet; 30 import java.util.Iterator; 31 import java.util.Set; 32 33 /** 34 * A node in a directed graph. In addition to an arbitrary 35 * <code>Object</code> containing user data associated with the node, 36 * each node maintains a <code>Set</code>s of nodes which are pointed 37 * to by the current node (available from <code>getOutNodes</code>). 38 * The in-degree of the node (that is, number of nodes that point to 39 * the current node) may be queried. 40 * 41 */ 42 class DigraphNode implements Cloneable, Serializable { 43 44 /** The data associated with this node. */ 45 protected Object data; 46 47 /** 48 * A <code>Set</code> of neighboring nodes pointed to by this 49 * node. 50 */ 51 protected Set outNodes = new HashSet(); 52 53 /** The in-degree of the node. */ 54 protected int inDegree = 0; 55 56 /** 57 * A <code>Set</code> of neighboring nodes that point to this 58 * node. 59 */ 60 private Set inNodes = new HashSet(); 61 62 public DigraphNode(Object data) { 63 this.data = data; 64 } 65 66 /** Returns the <code>Object</code> referenced by this node. */ 67 public Object getData() { 68 return data; 69 } 70 71 /** 72 * Returns an <code>Iterator</code> containing the nodes pointed 73 * to by this node. 74 */ 75 public Iterator getOutNodes() { 76 return outNodes.iterator(); 77 } 78 79 /** 80 * Adds a directed edge to the graph. The outNodes list of this 81 * node is updated and the in-degree of the other node is incremented. 82 * 83 * @param node a <code>DigraphNode</code>. 84 * 85 * @return <code>true</code> if the node was not previously the 86 * target of an edge. 87 */ 88 public boolean addEdge(DigraphNode node) { 89 if (outNodes.contains(node)) { 90 return false; 91 } 92 93 outNodes.add(node); 94 node.inNodes.add(this); 95 node.incrementInDegree(); 96 return true; 97 } 98 99 /** 100 * Returns <code>true</code> if an edge exists between this node 101 * and the given node. 102 * 103 * @param node a <code>DigraphNode</code>. 104 * 105 * @return <code>true</code> if the node is the target of an edge. 106 */ 107 public boolean hasEdge(DigraphNode node) { 108 return outNodes.contains(node); 109 } 110 111 /** 112 * Removes a directed edge from the graph. The outNodes list of this 113 * node is updated and the in-degree of the other node is decremented. 114 * 115 * @return <code>true</code> if the node was previously the target 116 * of an edge. 117 */ 118 public boolean removeEdge(DigraphNode node) { 119 if (!outNodes.contains(node)) { 120 return false; 121 } 122 123 outNodes.remove(node); 124 node.inNodes.remove(this); 125 node.decrementInDegree(); 126 return true; 127 } 128 129 /** 130 * Removes this node from the graph, updating neighboring nodes 131 * appropriately. 132 */ 133 public void dispose() { 134 Object[] inNodesArray = inNodes.toArray(); 135 for(int i=0; i<inNodesArray.length; i++) { 136 DigraphNode node = (DigraphNode) inNodesArray[i]; 137 node.removeEdge(this); 138 } 139 140 Object[] outNodesArray = outNodes.toArray(); 141 for(int i=0; i<outNodesArray.length; i++) { 142 DigraphNode node = (DigraphNode) outNodesArray[i]; 143 removeEdge(node); 144 } 145 } 146 147 /** Returns the in-degree of this node. */ 148 public int getInDegree() { 149 return inDegree; 150 } 151 152 /** Increments the in-degree of this node. */ 153 private void incrementInDegree() { 154 ++inDegree; 155 } 156 157 /** Decrements the in-degree of this node. */ 158 private void decrementInDegree() { 159 --inDegree; 160 } 161 }