1 /*
2 * Copyright (C) 2016 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.graph;
18
19 import static com.google.common.base.Preconditions.checkNotNull;
20 import static com.google.common.graph.GraphConstants.NOT_AVAILABLE_ON_UNDIRECTED;
21
22 import com.google.common.annotations.Beta;
23 import com.google.common.base.Objects;
24 import com.google.common.collect.Iterators;
25 import com.google.common.collect.UnmodifiableIterator;
26 import com.google.errorprone.annotations.Immutable;
27 import javax.annotation.CheckForNull;
28
29 /**
30 * An immutable pair representing the two endpoints of an edge in a graph. The {@link EndpointPair}
31 * of a directed edge is an ordered pair of nodes ({@link #source()} and {@link #target()}). The
32 * {@link EndpointPair} of an undirected edge is an unordered pair of nodes ({@link #nodeU()} and
33 * {@link #nodeV()}).
34 *
35 * <p>The edge is a self-loop if, and only if, the two endpoints are equal.
36 *
37 * @author James Sexton
38 * @since 20.0
39 */
40 @Beta
41 @Immutable(containerOf = {"N"})
42 @ElementTypesAreNonnullByDefault
43 public abstract class EndpointPair<N> implements Iterable<N> {
44 private final N nodeU;
45 private final N nodeV;
46
47 private EndpointPair(N nodeU, N nodeV) {
48 this.nodeU = checkNotNull(nodeU);
49 this.nodeV = checkNotNull(nodeV);
50 }
51
52 /** Returns an {@link EndpointPair} representing the endpoints of a directed edge. */
53 public static <N> EndpointPair<N> ordered(N source, N target) {
54 return new Ordered<N>(source, target);
55 }
56
57 /** Returns an {@link EndpointPair} representing the endpoints of an undirected edge. */
58 public static <N> EndpointPair<N> unordered(N nodeU, N nodeV) {
59 // Swap nodes on purpose to prevent callers from relying on the "ordering" of an unordered pair.
60 return new Unordered<N>(nodeV, nodeU);
61 }
62
63 /** Returns an {@link EndpointPair} representing the endpoints of an edge in {@code graph}. */
64 static <N> EndpointPair<N> of(Graph<?> graph, N nodeU, N nodeV) {
65 return graph.isDirected() ? ordered(nodeU, nodeV) : unordered(nodeU, nodeV);
66 }
67
68 /** Returns an {@link EndpointPair} representing the endpoints of an edge in {@code network}. */
69 static <N> EndpointPair<N> of(Network<?, ?> network, N nodeU, N nodeV) {
70 return network.isDirected() ? ordered(nodeU, nodeV) : unordered(nodeU, nodeV);
71 }
72
73 /**
74 * If this {@link EndpointPair} {@link #isOrdered()}, returns the node which is the source.
75 *
76 * @throws UnsupportedOperationException if this {@link EndpointPair} is not ordered
77 */
78 public abstract N source();
79
80 /**
81 * If this {@link EndpointPair} {@link #isOrdered()}, returns the node which is the target.
82 *
83 * @throws UnsupportedOperationException if this {@link EndpointPair} is not ordered
84 */
85 public abstract N target();
86
87 /**
88 * If this {@link EndpointPair} {@link #isOrdered()} returns the {@link #source()}; otherwise,
89 * returns an arbitrary (but consistent) endpoint of the origin edge.
90 */
91 public final N nodeU() {
92 return nodeU;
93 }
94
95 /**
96 * Returns the node {@link #adjacentNode(Object) adjacent} to {@link #nodeU()} along the origin
97 * edge. If this {@link EndpointPair} {@link #isOrdered()}, this is equal to {@link #target()}.
98 */
99 public final N nodeV() {
100 return nodeV;
101 }
102
103 /**
104 * Returns the node that is adjacent to {@code node} along the origin edge.
105 *
106 * @throws IllegalArgumentException if this {@link EndpointPair} does not contain {@code node}
107 * @since 20.0 (but the argument type was changed from {@code Object} to {@code N} in 31.0)
108 */
109 public final N adjacentNode(N node) {
110 if (node.equals(nodeU)) {
111 return nodeV;
112 } else if (node.equals(nodeV)) {
113 return nodeU;
114 } else {
115 throw new IllegalArgumentException("EndpointPair " + this + " does not contain node " + node);
116 }
117 }
118
119 /**
120 * Returns {@code true} if this {@link EndpointPair} is an ordered pair (i.e. represents the
121 * endpoints of a directed edge).
122 */
123 public abstract boolean isOrdered();
124
125 /** Iterates in the order {@link #nodeU()}, {@link #nodeV()}. */
126 @Override
127 public final UnmodifiableIterator<N> iterator() {
128 return Iterators.forArray(nodeU, nodeV);
129 }
130
131 /**
132 * Two ordered {@link EndpointPair}s are equal if their {@link #source()} and {@link #target()}
133 * are equal. Two unordered {@link EndpointPair}s are equal if they contain the same nodes. An
134 * ordered {@link EndpointPair} is never equal to an unordered {@link EndpointPair}.
135 */
136 @Override
137 public abstract boolean equals(@CheckForNull Object obj);
138
139 /**
140 * The hashcode of an ordered {@link EndpointPair} is equal to {@code Objects.hashCode(source(),
141 * target())}. The hashcode of an unordered {@link EndpointPair} is equal to {@code
142 * nodeU().hashCode() + nodeV().hashCode()}.
143 */
144 @Override
145 public abstract int hashCode();
146
147 private static final class Ordered<N> extends EndpointPair<N> {
148 private Ordered(N source, N target) {
149 super(source, target);
150 }
151
152 @Override
153 public N source() {
154 return nodeU();
155 }
156
157 @Override
158 public N target() {
159 return nodeV();
160 }
161
162 @Override
163 public boolean isOrdered() {
164 return true;
165 }
166
167 @Override
168 public boolean equals(@CheckForNull Object obj) {
169 if (obj == this) {
170 return true;
171 }
172 if (!(obj instanceof EndpointPair)) {
173 return false;
174 }
175
176 EndpointPair<?> other = (EndpointPair<?>) obj;
177 if (isOrdered() != other.isOrdered()) {
178 return false;
179 }
180
181 return source().equals(other.source()) && target().equals(other.target());
182 }
183
184 @Override
185 public int hashCode() {
186 return Objects.hashCode(source(), target());
187 }
188
189 @Override
190 public String toString() {
191 return "<" + source() + " -> " + target() + ">";
192 }
193 }
194
195 private static final class Unordered<N> extends EndpointPair<N> {
196 private Unordered(N nodeU, N nodeV) {
197 super(nodeU, nodeV);
198 }
199
200 @Override
201 public N source() {
202 throw new UnsupportedOperationException(NOT_AVAILABLE_ON_UNDIRECTED);
203 }
204
205 @Override
206 public N target() {
207 throw new UnsupportedOperationException(NOT_AVAILABLE_ON_UNDIRECTED);
208 }
209
210 @Override
211 public boolean isOrdered() {
212 return false;
213 }
214
215 @Override
216 public boolean equals(@CheckForNull Object obj) {
217 if (obj == this) {
218 return true;
219 }
220 if (!(obj instanceof EndpointPair)) {
221 return false;
222 }
223
224 EndpointPair<?> other = (EndpointPair<?>) obj;
225 if (isOrdered() != other.isOrdered()) {
226 return false;
227 }
228
229 // Equivalent to the following simple implementation:
230 // boolean condition1 = nodeU().equals(other.nodeU()) && nodeV().equals(other.nodeV());
231 // boolean condition2 = nodeU().equals(other.nodeV()) && nodeV().equals(other.nodeU());
232 // return condition1 || condition2;
233 if (nodeU().equals(other.nodeU())) { // check condition1
234 // Here's the tricky bit. We don't have to explicitly check for condition2 in this case.
235 // Why? The second half of condition2 requires that nodeV equals other.nodeU.
236 // We already know that nodeU equals other.nodeU. Combined with the earlier statement,
237 // and the transitive property of equality, this implies that nodeU equals nodeV.
238 // If nodeU equals nodeV, condition1 == condition2, so checking condition1 is sufficient.
239 return nodeV().equals(other.nodeV());
240 }
241 return nodeU().equals(other.nodeV()) && nodeV().equals(other.nodeU()); // check condition2
242 }
243
244 @Override
245 public int hashCode() {
246 return nodeU().hashCode() + nodeV().hashCode();
247 }
248
249 @Override
250 public String toString() {
251 return "[" + nodeU() + ", " + nodeV() + "]";
252 }
253 }
254 }