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.base.Preconditions.checkState;
021
022import com.google.common.annotations.Beta;
023import com.google.common.base.MoreObjects;
024import com.google.common.base.MoreObjects.ToStringHelper;
025import com.google.common.base.Objects;
026import com.google.common.collect.Maps;
027import com.google.common.collect.Ordering;
028import com.google.errorprone.annotations.Immutable;
029import java.util.Comparator;
030import java.util.Map;
031import javax.annotation.CheckForNull;
032
033/**
034 * Used to represent the order of elements in a data structure that supports different options for
035 * iteration order guarantees.
036 *
037 * <p>Example usage:
038 *
039 * <pre>{@code
040 * MutableGraph<Integer> graph =
041 *     GraphBuilder.directed().nodeOrder(ElementOrder.<Integer>natural()).build();
042 * }</pre>
043 *
044 * @author Joshua O'Madadhain
045 * @since 20.0
046 */
047@Beta
048@Immutable
049@ElementTypesAreNonnullByDefault
050public final class ElementOrder<T> {
051  private final Type type;
052
053  @SuppressWarnings("Immutable") // Hopefully the comparator provided is immutable!
054  @CheckForNull
055  private final Comparator<T> comparator;
056
057  /**
058   * The type of ordering that this object specifies.
059   *
060   * <ul>
061   *   <li>UNORDERED: no order is guaranteed.
062   *   <li>STABLE: ordering is guaranteed to follow a pattern that won't change between releases.
063   *       Some methods may have stronger guarantees.
064   *   <li>INSERTION: insertion ordering is guaranteed.
065   *   <li>SORTED: ordering according to a supplied comparator is guaranteed.
066   * </ul>
067   */
068  public enum Type {
069    UNORDERED,
070    STABLE,
071    INSERTION,
072    SORTED
073  }
074
075  private ElementOrder(Type type, @CheckForNull Comparator<T> comparator) {
076    this.type = checkNotNull(type);
077    this.comparator = comparator;
078    checkState((type == Type.SORTED) == (comparator != null));
079  }
080
081  /** Returns an instance which specifies that no ordering is guaranteed. */
082  public static <S> ElementOrder<S> unordered() {
083    return new ElementOrder<>(Type.UNORDERED, null);
084  }
085
086  /**
087   * Returns an instance which specifies that ordering is guaranteed to be always be the same across
088   * iterations, and across releases. Some methods may have stronger guarantees.
089   *
090   * <p>This instance is only useful in combination with {@code incidentEdgeOrder}, e.g. {@code
091   * graphBuilder.incidentEdgeOrder(ElementOrder.stable())}.
092   *
093   * <h3>In combination with {@code incidentEdgeOrder}</h3>
094   *
095   * <p>{@code incidentEdgeOrder(ElementOrder.stable())} guarantees the ordering of the returned
096   * collections of the following methods:
097   *
098   * <ul>
099   *   <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<>(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<>(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<>(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<>(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}