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.compatqual.NullableDecl;
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(@NullableDecl 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(@NullableDecl 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(@NullableDecl 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}