001/* 002 * Copyright (C) 2016 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.graph; 018 019import static com.google.common.base.Preconditions.checkNotNull; 020import static com.google.common.graph.GraphConstants.NOT_AVAILABLE_ON_UNDIRECTED; 021 022import com.google.common.annotations.Beta; 023import com.google.common.base.Objects; 024import com.google.common.collect.Iterators; 025import com.google.common.collect.UnmodifiableIterator; 026import com.google.errorprone.annotations.Immutable; 027import org.checkerframework.checker.nullness.qual.Nullable; 028 029/** 030 * An immutable pair representing the two endpoints of an edge in a graph. The {@link EndpointPair} 031 * of a directed edge is an ordered pair of nodes ({@link #source()} and {@link #target()}). The 032 * {@link EndpointPair} of an undirected edge is an unordered pair of nodes ({@link #nodeU()} and 033 * {@link #nodeV()}). 034 * 035 * <p>The edge is a self-loop if, and only if, the two endpoints are equal. 036 * 037 * @author James Sexton 038 * @since 20.0 039 */ 040@Beta 041@Immutable(containerOf = {"N"}) 042public abstract class EndpointPair<N> implements Iterable<N> { 043 private final N nodeU; 044 private final N nodeV; 045 046 private EndpointPair(N nodeU, N nodeV) { 047 this.nodeU = checkNotNull(nodeU); 048 this.nodeV = checkNotNull(nodeV); 049 } 050 051 /** Returns an {@link EndpointPair} representing the endpoints of a directed edge. */ 052 public static <N> EndpointPair<N> ordered(N source, N target) { 053 return new Ordered<N>(source, target); 054 } 055 056 /** Returns an {@link EndpointPair} representing the endpoints of an undirected edge. */ 057 public static <N> EndpointPair<N> unordered(N nodeU, N nodeV) { 058 // Swap nodes on purpose to prevent callers from relying on the "ordering" of an unordered pair. 059 return new Unordered<N>(nodeV, nodeU); 060 } 061 062 /** Returns an {@link EndpointPair} representing the endpoints of an edge in {@code graph}. */ 063 static <N> EndpointPair<N> of(Graph<?> graph, N nodeU, N nodeV) { 064 return graph.isDirected() ? ordered(nodeU, nodeV) : unordered(nodeU, nodeV); 065 } 066 067 /** Returns an {@link EndpointPair} representing the endpoints of an edge in {@code network}. */ 068 static <N> EndpointPair<N> of(Network<?, ?> network, N nodeU, N nodeV) { 069 return network.isDirected() ? ordered(nodeU, nodeV) : unordered(nodeU, nodeV); 070 } 071 072 /** 073 * If this {@link EndpointPair} {@link #isOrdered()}, returns the node which is the source. 074 * 075 * @throws UnsupportedOperationException if this {@link EndpointPair} is not ordered 076 */ 077 public abstract N source(); 078 079 /** 080 * If this {@link EndpointPair} {@link #isOrdered()}, returns the node which is the target. 081 * 082 * @throws UnsupportedOperationException if this {@link EndpointPair} is not ordered 083 */ 084 public abstract N target(); 085 086 /** 087 * If this {@link EndpointPair} {@link #isOrdered()} returns the {@link #source()}; otherwise, 088 * returns an arbitrary (but consistent) endpoint of the origin edge. 089 */ 090 public final N nodeU() { 091 return nodeU; 092 } 093 094 /** 095 * Returns the node {@link #adjacentNode(Object) adjacent} to {@link #nodeU()} along the origin 096 * edge. If this {@link EndpointPair} {@link #isOrdered()}, this is equal to {@link #target()}. 097 */ 098 public final N nodeV() { 099 return nodeV; 100 } 101 102 /** 103 * Returns the node that is adjacent to {@code node} along the origin edge. 104 * 105 * @throws IllegalArgumentException if this {@link EndpointPair} does not contain {@code node} 106 */ 107 public final N adjacentNode(Object node) { 108 if (node.equals(nodeU)) { 109 return nodeV; 110 } else if (node.equals(nodeV)) { 111 return nodeU; 112 } else { 113 throw new IllegalArgumentException("EndpointPair " + this + " does not contain node " + node); 114 } 115 } 116 117 /** 118 * Returns {@code true} if this {@link EndpointPair} is an ordered pair (i.e. represents the 119 * endpoints of a directed edge). 120 */ 121 public abstract boolean isOrdered(); 122 123 /** Iterates in the order {@link #nodeU()}, {@link #nodeV()}. */ 124 @Override 125 public final UnmodifiableIterator<N> iterator() { 126 return Iterators.forArray(nodeU, nodeV); 127 } 128 129 /** 130 * Two ordered {@link EndpointPair}s are equal if their {@link #source()} and {@link #target()} 131 * are equal. Two unordered {@link EndpointPair}s are equal if they contain the same nodes. An 132 * ordered {@link EndpointPair} is never equal to an unordered {@link EndpointPair}. 133 */ 134 @Override 135 public abstract boolean equals(@Nullable Object obj); 136 137 /** 138 * The hashcode of an ordered {@link EndpointPair} is equal to {@code Objects.hashCode(source(), 139 * target())}. The hashcode of an unordered {@link EndpointPair} is equal to {@code 140 * nodeU().hashCode() + nodeV().hashCode()}. 141 */ 142 @Override 143 public abstract int hashCode(); 144 145 private static final class Ordered<N> extends EndpointPair<N> { 146 private Ordered(N source, N target) { 147 super(source, target); 148 } 149 150 @Override 151 public N source() { 152 return nodeU(); 153 } 154 155 @Override 156 public N target() { 157 return nodeV(); 158 } 159 160 @Override 161 public boolean isOrdered() { 162 return true; 163 } 164 165 @Override 166 public boolean equals(@Nullable Object obj) { 167 if (obj == this) { 168 return true; 169 } 170 if (!(obj instanceof EndpointPair)) { 171 return false; 172 } 173 174 EndpointPair<?> other = (EndpointPair<?>) obj; 175 if (isOrdered() != other.isOrdered()) { 176 return false; 177 } 178 179 return source().equals(other.source()) && target().equals(other.target()); 180 } 181 182 @Override 183 public int hashCode() { 184 return Objects.hashCode(source(), target()); 185 } 186 187 @Override 188 public String toString() { 189 return "<" + source() + " -> " + target() + ">"; 190 } 191 } 192 193 private static final class Unordered<N> extends EndpointPair<N> { 194 private Unordered(N nodeU, N nodeV) { 195 super(nodeU, nodeV); 196 } 197 198 @Override 199 public N source() { 200 throw new UnsupportedOperationException(NOT_AVAILABLE_ON_UNDIRECTED); 201 } 202 203 @Override 204 public N target() { 205 throw new UnsupportedOperationException(NOT_AVAILABLE_ON_UNDIRECTED); 206 } 207 208 @Override 209 public boolean isOrdered() { 210 return false; 211 } 212 213 @Override 214 public boolean equals(@Nullable Object obj) { 215 if (obj == this) { 216 return true; 217 } 218 if (!(obj instanceof EndpointPair)) { 219 return false; 220 } 221 222 EndpointPair<?> other = (EndpointPair<?>) obj; 223 if (isOrdered() != other.isOrdered()) { 224 return false; 225 } 226 227 // Equivalent to the following simple implementation: 228 // boolean condition1 = nodeU().equals(other.nodeU()) && nodeV().equals(other.nodeV()); 229 // boolean condition2 = nodeU().equals(other.nodeV()) && nodeV().equals(other.nodeU()); 230 // return condition1 || condition2; 231 if (nodeU().equals(other.nodeU())) { // check condition1 232 // Here's the tricky bit. We don't have to explicitly check for condition2 in this case. 233 // Why? The second half of condition2 requires that nodeV equals other.nodeU. 234 // We already know that nodeU equals other.nodeU. Combined with the earlier statement, 235 // and the transitive property of equality, this implies that nodeU equals nodeV. 236 // If nodeU equals nodeV, condition1 == condition2, so checking condition1 is sufficient. 237 return nodeV().equals(other.nodeV()); 238 } 239 return nodeU().equals(other.nodeV()) && nodeV().equals(other.nodeU()); // check condition2 240 } 241 242 @Override 243 public int hashCode() { 244 return nodeU().hashCode() + nodeV().hashCode(); 245 } 246 247 @Override 248 public String toString() { 249 return "[" + nodeU() + ", " + nodeV() + "]"; 250 } 251 } 252}