View Javadoc
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.Nullable;
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  public abstract class EndpointPair<N> implements Iterable<N> {
43    private final N nodeU;
44    private final N nodeV;
45  
46    private EndpointPair(N nodeU, N nodeV) {
47      this.nodeU = checkNotNull(nodeU);
48      this.nodeV = checkNotNull(nodeV);
49    }
50  
51    /** Returns an {@link EndpointPair} representing the endpoints of a directed edge. */
52    public static <N> EndpointPair<N> ordered(N source, N target) {
53      return new Ordered<N>(source, target);
54    }
55  
56    /** Returns an {@link EndpointPair} representing the endpoints of an undirected edge. */
57    public static <N> EndpointPair<N> unordered(N nodeU, N nodeV) {
58      // Swap nodes on purpose to prevent callers from relying on the "ordering" of an unordered pair.
59      return new Unordered<N>(nodeV, nodeU);
60    }
61  
62    /** Returns an {@link EndpointPair} representing the endpoints of an edge in {@code graph}. */
63    static <N> EndpointPair<N> of(Graph<?> graph, N nodeU, N nodeV) {
64      return graph.isDirected() ? ordered(nodeU, nodeV) : unordered(nodeU, nodeV);
65    }
66  
67    /** Returns an {@link EndpointPair} representing the endpoints of an edge in {@code network}. */
68    static <N> EndpointPair<N> of(Network<?, ?> network, N nodeU, N nodeV) {
69      return network.isDirected() ? ordered(nodeU, nodeV) : unordered(nodeU, nodeV);
70    }
71  
72    /**
73     * If this {@link EndpointPair} {@link #isOrdered()}, returns the node which is the source.
74     *
75     * @throws UnsupportedOperationException if this {@link EndpointPair} is not ordered
76     */
77    public abstract N source();
78  
79    /**
80     * If this {@link EndpointPair} {@link #isOrdered()}, returns the node which is the target.
81     *
82     * @throws UnsupportedOperationException if this {@link EndpointPair} is not ordered
83     */
84    public abstract N target();
85  
86    /**
87     * If this {@link EndpointPair} {@link #isOrdered()} returns the {@link #source()}; otherwise,
88     * returns an arbitrary (but consistent) endpoint of the origin edge.
89     */
90    public final N nodeU() {
91      return nodeU;
92    }
93  
94    /**
95     * Returns the node {@link #adjacentNode(Object) adjacent} to {@link #nodeU()} along the origin
96     * edge. If this {@link EndpointPair} {@link #isOrdered()}, this is equal to {@link #target()}.
97     */
98    public final N nodeV() {
99      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 }