1 /* 2 * Copyright (c) 2000, 2014, 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 private static final long serialVersionUID = 5308261378582246841L; 44 45 /** The data associated with this node. */ 46 protected Object data; 47 48 /** 49 * A <code>Set</code> of neighboring nodes pointed to by this 50 * node. 51 */ 52 protected Set outNodes = new HashSet(); 53 54 /** The in-degree of the node. */ 55 protected int inDegree = 0; 56 57 /** 58 * A <code>Set</code> of neighboring nodes that point to this 59 * node. 60 */ 61 private Set inNodes = new HashSet(); 62 63 public DigraphNode(Object data) { 64 this.data = data; 65 } 66 67 /** Returns the <code>Object</code> referenced by this node. */ 68 public Object getData() { 69 return data; 70 } 71 72 /** 73 * Returns an <code>Iterator</code> containing the nodes pointed 74 * to by this node. 75 */ 76 public Iterator getOutNodes() { 77 return outNodes.iterator(); 78 } 79 80 /** 81 * Adds a directed edge to the graph. The outNodes list of this 82 * node is updated and the in-degree of the other node is incremented. 83 * 84 * @param node a <code>DigraphNode</code>. 85 * 86 * @return <code>true</code> if the node was not previously the 87 * target of an edge. 88 */ 89 public boolean addEdge(DigraphNode node) { 90 if (outNodes.contains(node)) { 91 return false; 92 } 93 94 outNodes.add(node); 95 node.inNodes.add(this); 96 node.incrementInDegree(); 97 return true; 98 } 99 100 /** 101 * Returns <code>true</code> if an edge exists between this node 102 * and the given node. 103 * 104 * @param node a <code>DigraphNode</code>. 105 * 106 * @return <code>true</code> if the node is the target of an edge. 107 */ 108 public boolean hasEdge(DigraphNode node) { 109 return outNodes.contains(node); 110 } 111 112 /** 113 * Removes a directed edge from the graph. The outNodes list of this 114 * node is updated and the in-degree of the other node is decremented. 115 * 116 * @return <code>true</code> if the node was previously the target 117 * of an edge. 118 */ 119 public boolean removeEdge(DigraphNode node) { 120 if (!outNodes.contains(node)) { 121 return false; 122 } 123 124 outNodes.remove(node); 125 node.inNodes.remove(this); 126 node.decrementInDegree(); 127 return true; 128 } 129 130 /** 131 * Removes this node from the graph, updating neighboring nodes 132 * appropriately. 133 */ 134 public void dispose() { 135 Object[] inNodesArray = inNodes.toArray(); 136 for(int i=0; i<inNodesArray.length; i++) { 137 DigraphNode node = (DigraphNode) inNodesArray[i]; 138 node.removeEdge(this); 139 } 140 141 Object[] outNodesArray = outNodes.toArray(); 142 for(int i=0; i<outNodesArray.length; i++) { 143 DigraphNode node = (DigraphNode) outNodesArray[i]; 144 removeEdge(node); 145 } 146 } 147 148 /** Returns the in-degree of this node. */ 149 public int getInDegree() { 150 return inDegree; 151 } 152 153 /** Increments the in-degree of this node. */ 154 private void incrementInDegree() { 155 ++inDegree; 156 } 157 158 /** Decrements the in-degree of this node. */ 159 private void decrementInDegree() { 160 --inDegree; 161 } 162 }