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 javax.annotation.Nullable;
027
028/**
029 * An immutable pair representing the two endpoints of an edge in a graph. The {@link EndpointPair}
030 * of a directed edge is an ordered pair of nodes ({@link #source()} and {@link #target()}). The
031 * {@link EndpointPair} of an undirected edge is an unordered pair of nodes ({@link #nodeU()} and
032 * {@link #nodeV()}).
033 *
034 * <p>The edge is a self-loop if, and only if, the two endpoints are equal.
035 *
036 * @author James Sexton
037 * @since 20.0
038 */
039@Beta
040public abstract class EndpointPair<N> implements Iterable<N> {
041  private final N nodeU;
042  private final N nodeV;
043
044  private EndpointPair(N nodeU, N nodeV) {
045    this.nodeU = checkNotNull(nodeU);
046    this.nodeV = checkNotNull(nodeV);
047  }
048
049  /** Returns an {@link EndpointPair} representing the endpoints of a directed edge. */
050  public static <N> EndpointPair<N> ordered(N source, N target) {
051    return new Ordered<N>(source, target);
052  }
053
054  /** Returns an {@link EndpointPair} representing the endpoints of an undirected edge. */
055  public static <N> EndpointPair<N> unordered(N nodeU, N nodeV) {
056    // Swap nodes on purpose to prevent callers from relying on the "ordering" of an unordered pair.
057    return new Unordered<N>(nodeV, nodeU);
058  }
059
060  /** Returns an {@link EndpointPair} representing the endpoints of an edge in {@code graph}. */
061  static <N> EndpointPair<N> of(Graph<?> graph, N nodeU, N nodeV) {
062    return graph.isDirected() ? ordered(nodeU, nodeV) : unordered(nodeU, nodeV);
063  }
064
065  /** Returns an {@link EndpointPair} representing the endpoints of an edge in {@code network}. */
066  static <N> EndpointPair<N> of(Network<?, ?> network, N nodeU, N nodeV) {
067    return network.isDirected() ? ordered(nodeU, nodeV) : unordered(nodeU, nodeV);
068  }
069
070  /**
071   * If this {@link EndpointPair} {@link #isOrdered()}, returns the node which is the source.
072   *
073   * @throws UnsupportedOperationException if this {@link EndpointPair} is not ordered
074   */
075  public abstract N source();
076
077  /**
078   * If this {@link EndpointPair} {@link #isOrdered()}, returns the node which is the target.
079   *
080   * @throws UnsupportedOperationException if this {@link EndpointPair} is not ordered
081   */
082  public abstract N target();
083
084  /**
085   * If this {@link EndpointPair} {@link #isOrdered()} returns the {@link #source()}; otherwise,
086   * returns an arbitrary (but consistent) endpoint of the origin edge.
087   */
088  public final N nodeU() {
089    return nodeU;
090  }
091
092  /**
093   * Returns the node {@link #adjacentNode(Object) adjacent} to {@link #nodeU()} along the origin
094   * edge. If this {@link EndpointPair} {@link #isOrdered()}, this is equal to {@link #target()}.
095   */
096  public final N nodeV() {
097    return nodeV;
098  }
099
100  /**
101   * Returns the node that is adjacent to {@code node} along the origin edge.
102   *
103   * @throws IllegalArgumentException if this {@link EndpointPair} does not contain {@code node}
104   */
105  public final N adjacentNode(Object node) {
106    if (node.equals(nodeU)) {
107      return nodeV;
108    } else if (node.equals(nodeV)) {
109      return nodeU;
110    } else {
111      throw new IllegalArgumentException(
112          String.format("EndpointPair %s does not contain node %s", this, node));
113    }
114  }
115
116  /**
117   * Returns {@code true} if this {@link EndpointPair} is an ordered pair (i.e. represents the
118   * endpoints of a directed edge).
119   */
120  public abstract boolean isOrdered();
121
122  /** Iterates in the order {@link #nodeU()}, {@link #nodeV()}. */
123  @Override
124  public final UnmodifiableIterator<N> iterator() {
125    return Iterators.forArray(nodeU, nodeV);
126  }
127
128  /**
129   * Two ordered {@link EndpointPair}s are equal if their {@link #source()} and {@link #target()}
130   * are equal. Two unordered {@link EndpointPair}s are equal if they contain the same nodes. An
131   * ordered {@link EndpointPair} is never equal to an unordered {@link EndpointPair}.
132   */
133  @Override
134  public abstract boolean equals(@Nullable Object obj);
135
136  /**
137   * The hashcode of an ordered {@link EndpointPair} is equal to {@code Objects.hashCode(source(),
138   * target())}. The hashcode of an unordered {@link EndpointPair} is equal to {@code
139   * nodeU().hashCode() + nodeV().hashCode()}.
140   */
141  @Override
142  public abstract int hashCode();
143
144  private static final class Ordered<N> extends EndpointPair<N> {
145    private Ordered(N source, N target) {
146      super(source, target);
147    }
148
149    @Override
150    public N source() {
151      return nodeU();
152    }
153
154    @Override
155    public N target() {
156      return nodeV();
157    }
158
159    @Override
160    public boolean isOrdered() {
161      return true;
162    }
163
164    @Override
165    public boolean equals(@Nullable Object obj) {
166      if (obj == this) {
167        return true;
168      }
169      if (!(obj instanceof EndpointPair)) {
170        return false;
171      }
172
173      EndpointPair<?> other = (EndpointPair<?>) obj;
174      if (isOrdered() != other.isOrdered()) {
175        return false;
176      }
177
178      return source().equals(other.source()) && target().equals(other.target());
179    }
180
181    @Override
182    public int hashCode() {
183      return Objects.hashCode(source(), target());
184    }
185
186    @Override
187    public String toString() {
188      return String.format("<%s -> %s>", source(), target());
189    }
190  }
191
192  private static final class Unordered<N> extends EndpointPair<N> {
193    private Unordered(N nodeU, N nodeV) {
194      super(nodeU, nodeV);
195    }
196
197    @Override
198    public N source() {
199      throw new UnsupportedOperationException(NOT_AVAILABLE_ON_UNDIRECTED);
200    }
201
202    @Override
203    public N target() {
204      throw new UnsupportedOperationException(NOT_AVAILABLE_ON_UNDIRECTED);
205    }
206
207    @Override
208    public boolean isOrdered() {
209      return false;
210    }
211
212    @Override
213    public boolean equals(@Nullable Object obj) {
214      if (obj == this) {
215        return true;
216      }
217      if (!(obj instanceof EndpointPair)) {
218        return false;
219      }
220
221      EndpointPair<?> other = (EndpointPair<?>) obj;
222      if (isOrdered() != other.isOrdered()) {
223        return false;
224      }
225
226      // Equivalent to the following simple implementation:
227      // boolean condition1 = nodeU().equals(other.nodeU()) && nodeV().equals(other.nodeV());
228      // boolean condition2 = nodeU().equals(other.nodeV()) && nodeV().equals(other.nodeU());
229      // return condition1 || condition2;
230      if (nodeU().equals(other.nodeU())) { // check condition1
231        // Here's the tricky bit. We don't have to explicitly check for condition2 in this case.
232        // Why? The second half of condition2 requires that nodeV equals other.nodeU.
233        // We already know that nodeU equals other.nodeU. Combined with the earlier statement,
234        // and the transitive property of equality, this implies that nodeU equals nodeV.
235        // If nodeU equals nodeV, condition1 == condition2, so checking condition1 is sufficient.
236        return nodeV().equals(other.nodeV());
237      }
238      return nodeU().equals(other.nodeV()) && nodeV().equals(other.nodeU()); // check condition2
239    }
240
241    @Override
242    public int hashCode() {
243      return nodeU().hashCode() + nodeV().hashCode();
244    }
245
246    @Override
247    public String toString() {
248      return String.format("[%s, %s]", nodeU(), nodeV());
249    }
250  }
251}