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