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 javax.annotation.CheckForNull;
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"})
042@ElementTypesAreNonnullByDefault
043public abstract class EndpointPair<N> implements Iterable<N> {
044  private final N nodeU;
045  private final N nodeV;
046
047  private EndpointPair(N nodeU, N nodeV) {
048    this.nodeU = checkNotNull(nodeU);
049    this.nodeV = checkNotNull(nodeV);
050  }
051
052  /** Returns an {@link EndpointPair} representing the endpoints of a directed edge. */
053  public static <N> EndpointPair<N> ordered(N source, N target) {
054    return new Ordered<N>(source, target);
055  }
056
057  /** Returns an {@link EndpointPair} representing the endpoints of an undirected edge. */
058  public static <N> EndpointPair<N> unordered(N nodeU, N nodeV) {
059    // Swap nodes on purpose to prevent callers from relying on the "ordering" of an unordered pair.
060    return new Unordered<N>(nodeV, nodeU);
061  }
062
063  /** Returns an {@link EndpointPair} representing the endpoints of an edge in {@code graph}. */
064  static <N> EndpointPair<N> of(Graph<?> graph, N nodeU, N nodeV) {
065    return graph.isDirected() ? ordered(nodeU, nodeV) : unordered(nodeU, nodeV);
066  }
067
068  /** Returns an {@link EndpointPair} representing the endpoints of an edge in {@code network}. */
069  static <N> EndpointPair<N> of(Network<?, ?> network, N nodeU, N nodeV) {
070    return network.isDirected() ? ordered(nodeU, nodeV) : unordered(nodeU, nodeV);
071  }
072
073  /**
074   * If this {@link EndpointPair} {@link #isOrdered()}, returns the node which is the source.
075   *
076   * @throws UnsupportedOperationException if this {@link EndpointPair} is not ordered
077   */
078  public abstract N source();
079
080  /**
081   * If this {@link EndpointPair} {@link #isOrdered()}, returns the node which is the target.
082   *
083   * @throws UnsupportedOperationException if this {@link EndpointPair} is not ordered
084   */
085  public abstract N target();
086
087  /**
088   * If this {@link EndpointPair} {@link #isOrdered()} returns the {@link #source()}; otherwise,
089   * returns an arbitrary (but consistent) endpoint of the origin edge.
090   */
091  public final N nodeU() {
092    return nodeU;
093  }
094
095  /**
096   * Returns the node {@link #adjacentNode(Object) adjacent} to {@link #nodeU()} along the origin
097   * edge. If this {@link EndpointPair} {@link #isOrdered()}, this is equal to {@link #target()}.
098   */
099  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}