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.base.Preconditions.checkState;
21
22 import com.google.common.annotations.Beta;
23 import com.google.common.base.MoreObjects;
24 import com.google.common.base.MoreObjects.ToStringHelper;
25 import com.google.common.base.Objects;
26 import com.google.common.collect.Maps;
27 import com.google.common.collect.Ordering;
28 import com.google.errorprone.annotations.Immutable;
29 import java.util.Comparator;
30 import java.util.Map;
31 import javax.annotation.CheckForNull;
32
33 /**
34 * Used to represent the order of elements in a data structure that supports different options for
35 * iteration order guarantees.
36 *
37 * <p>Example usage:
38 *
39 * <pre>{@code
40 * MutableGraph<Integer> graph =
41 * GraphBuilder.directed().nodeOrder(ElementOrder.<Integer>natural()).build();
42 * }</pre>
43 *
44 * @author Joshua O'Madadhain
45 * @since 20.0
46 */
47 @Beta
48 @Immutable
49 @ElementTypesAreNonnullByDefault
50 public final class ElementOrder<T> {
51 private final Type type;
52
53 @SuppressWarnings("Immutable") // Hopefully the comparator provided is immutable!
54 @CheckForNull
55 private final Comparator<T> comparator;
56
57 /**
58 * The type of ordering that this object specifies.
59 *
60 * <ul>
61 * <li>UNORDERED: no order is guaranteed.
62 * <li>STABLE: ordering is guaranteed to follow a pattern that won't change between releases.
63 * Some methods may have stronger guarantees.
64 * <li>INSERTION: insertion ordering is guaranteed.
65 * <li>SORTED: ordering according to a supplied comparator is guaranteed.
66 * </ul>
67 */
68 public enum Type {
69 UNORDERED,
70 STABLE,
71 INSERTION,
72 SORTED
73 }
74
75 private ElementOrder(Type type, @CheckForNull Comparator<T> comparator) {
76 this.type = checkNotNull(type);
77 this.comparator = comparator;
78 checkState((type == Type.SORTED) == (comparator != null));
79 }
80
81 /** Returns an instance which specifies that no ordering is guaranteed. */
82 public static <S> ElementOrder<S> unordered() {
83 return new ElementOrder<S>(Type.UNORDERED, null);
84 }
85
86 /**
87 * Returns an instance which specifies that ordering is guaranteed to be always be the same across
88 * iterations, and across releases. Some methods may have stronger guarantees.
89 *
90 * <p>This instance is only useful in combination with {@code incidentEdgeOrder}, e.g. {@code
91 * graphBuilder.incidentEdgeOrder(ElementOrder.stable())}.
92 *
93 * <h3>In combination with {@code incidentEdgeOrder}</h3>
94 *
95 * <p>{@code incidentEdgeOrder(ElementOrder.stable())} guarantees the ordering of the returned
96 * collections of the following methods:
97 *
98 * <ul>
99 * <li>For {@link Graph} and {@link ValueGraph}:
100 * <ul>
101 * <li>{@code edges()}: Stable order
102 * <li>{@code adjacentNodes(node)}: Connecting edge insertion order
103 * <li>{@code predecessors(node)}: Connecting edge insertion order
104 * <li>{@code successors(node)}: Connecting edge insertion order
105 * <li>{@code incidentEdges(node)}: Edge insertion order
106 * </ul>
107 * <li>For {@link Network}:
108 * <ul>
109 * <li>{@code adjacentNodes(node)}: Stable order
110 * <li>{@code predecessors(node)}: Connecting edge insertion order
111 * <li>{@code successors(node)}: Connecting edge insertion order
112 * <li>{@code incidentEdges(node)}: Stable order
113 * <li>{@code inEdges(node)}: Edge insertion order
114 * <li>{@code outEdges(node)}: Edge insertion order
115 * <li>{@code adjacentEdges(edge)}: Stable order
116 * <li>{@code edgesConnecting(nodeU, nodeV)}: Edge insertion order
117 * </ul>
118 * </ul>
119 *
120 * @since 29.0
121 */
122 public static <S> ElementOrder<S> stable() {
123 return new ElementOrder<S>(Type.STABLE, null);
124 }
125
126 /** Returns an instance which specifies that insertion ordering is guaranteed. */
127 public static <S> ElementOrder<S> insertion() {
128 return new ElementOrder<S>(Type.INSERTION, null);
129 }
130
131 /**
132 * Returns an instance which specifies that the natural ordering of the elements is guaranteed.
133 */
134 public static <S extends Comparable<? super S>> ElementOrder<S> natural() {
135 return new ElementOrder<S>(Type.SORTED, Ordering.<S>natural());
136 }
137
138 /**
139 * Returns an instance which specifies that the ordering of the elements is guaranteed to be
140 * determined by {@code comparator}.
141 */
142 public static <S> ElementOrder<S> sorted(Comparator<S> comparator) {
143 return new ElementOrder<S>(Type.SORTED, checkNotNull(comparator));
144 }
145
146 /** Returns the type of ordering used. */
147 public Type type() {
148 return type;
149 }
150
151 /**
152 * Returns the {@link Comparator} used.
153 *
154 * @throws UnsupportedOperationException if comparator is not defined
155 */
156 public Comparator<T> comparator() {
157 if (comparator != null) {
158 return comparator;
159 }
160 throw new UnsupportedOperationException("This ordering does not define a comparator.");
161 }
162
163 @Override
164 public boolean equals(@CheckForNull Object obj) {
165 if (obj == this) {
166 return true;
167 }
168 if (!(obj instanceof ElementOrder)) {
169 return false;
170 }
171
172 ElementOrder<?> other = (ElementOrder<?>) obj;
173 return (type == other.type) && Objects.equal(comparator, other.comparator);
174 }
175
176 @Override
177 public int hashCode() {
178 return Objects.hashCode(type, comparator);
179 }
180
181 @Override
182 public String toString() {
183 ToStringHelper helper = MoreObjects.toStringHelper(this).add("type", type);
184 if (comparator != null) {
185 helper.add("comparator", comparator);
186 }
187 return helper.toString();
188 }
189
190 /** Returns an empty mutable map whose keys will respect this {@link ElementOrder}. */
191 <K extends T, V> Map<K, V> createMap(int expectedSize) {
192 switch (type) {
193 case UNORDERED:
194 return Maps.newHashMapWithExpectedSize(expectedSize);
195 case INSERTION:
196 case STABLE:
197 return Maps.newLinkedHashMapWithExpectedSize(expectedSize);
198 case SORTED:
199 return Maps.newTreeMap(comparator());
200 default:
201 throw new AssertionError();
202 }
203 }
204
205 @SuppressWarnings("unchecked")
206 <T1 extends T> ElementOrder<T1> cast() {
207 return (ElementOrder<T1>) this;
208 }
209 }