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} containing user data associated with the node, 36 * each node maintains a {@code Set}s of nodes which are pointed 37 * to by the current node (available from {@code getOutNodes}). 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<E> implements Cloneable, Serializable { 43 private static final long serialVersionUID = 5308261378582246841L; 44 45 /** The data associated with this node. */ 46 protected E data; 47 48 /** 49 * A {@code Set} of neighboring nodes pointed to by this 50 * node. 51 */ 52 protected Set<DigraphNode<E>> outNodes = new HashSet<>(); 53 54 /** The in-degree of the node. */ 55 protected int inDegree = 0; 56 57 /** 58 * A {@code Set} of neighboring nodes that point to this 59 * node. 60 */ 61 private Set<DigraphNode<E>> inNodes = new HashSet<>(); 62 63 public DigraphNode(E data) { 64 this.data = data; 65 } 66 67 /** Returns the {@code Object} referenced by this node. */ 68 public E getData() { 69 return data; 70 } 71 72 /** 73 * Returns an {@code Iterator} containing the nodes pointed 74 * to by this node. 75 */ 76 public Iterator<DigraphNode<E>> 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}. 85 * 86 * @return {@code true} if the node was not previously the 87 * target of an edge. 88 */ 89 public boolean addEdge(DigraphNode<E> 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} if an edge exists between this node 102 * and the given node. 103 * 104 * @param node a {@code DigraphNode}. 105 * 106 * @return {@code true} if the node is the target of an edge. 107 */ 108 public boolean hasEdge(DigraphNode<E> 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} if the node was previously the target 117 * of an edge. 118 */ 119 public boolean removeEdge(DigraphNode<E> 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 @SuppressWarnings("unchecked") 138 DigraphNode<E> node = (DigraphNode<E>)inNodesArray[i]; 139 node.removeEdge(this); 140 } 141 142 Object[] outNodesArray = outNodes.toArray(); 143 for(int i=0; i<outNodesArray.length; i++) { 144 @SuppressWarnings("unchecked") 145 DigraphNode<E> node = (DigraphNode<E>)outNodesArray[i]; 146 removeEdge(node); 147 } 148 } 149 150 /** Returns the in-degree of this node. */ 151 public int getInDegree() { 152 return inDegree; 153 } 154 155 /** Increments the in-degree of this node. */ 156 private void incrementInDegree() { 157 ++inDegree; 158 } 159 160 /** Decrements the in-degree of this node. */ 161 private void decrementInDegree() { 162 --inDegree; 163 } 164 }