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 org.checkerframework.checker.nullness.compatqual.NullableDecl;
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
049public final class ElementOrder<T> {
050  private final Type type;
051
052  @SuppressWarnings("Immutable") // Hopefully the comparator provided is immutable!
053  @NullableDecl
054  private final Comparator<T> comparator;
055
056  /**
057   * The type of ordering that this object specifies.
058   *
059   * <ul>
060   *   <li>UNORDERED: no order is guaranteed.
061   *   <li>INSERTION: insertion ordering is guaranteed.
062   *   <li>SORTED: ordering according to a supplied comparator is guaranteed.
063   * </ul>
064   */
065  public enum Type {
066    UNORDERED,
067    INSERTION,
068    SORTED
069  }
070
071  private ElementOrder(Type type, @NullableDecl Comparator<T> comparator) {
072    this.type = checkNotNull(type);
073    this.comparator = comparator;
074    checkState((type == Type.SORTED) == (comparator != null));
075  }
076
077  /** Returns an instance which specifies that no ordering is guaranteed. */
078  public static <S> ElementOrder<S> unordered() {
079    return new ElementOrder<S>(Type.UNORDERED, null);
080  }
081
082  /** Returns an instance which specifies that insertion ordering is guaranteed. */
083  public static <S> ElementOrder<S> insertion() {
084    return new ElementOrder<S>(Type.INSERTION, null);
085  }
086
087  /**
088   * Returns an instance which specifies that the natural ordering of the elements is guaranteed.
089   */
090  public static <S extends Comparable<? super S>> ElementOrder<S> natural() {
091    return new ElementOrder<S>(Type.SORTED, Ordering.<S>natural());
092  }
093
094  /**
095   * Returns an instance which specifies that the ordering of the elements is guaranteed to be
096   * determined by {@code comparator}.
097   */
098  public static <S> ElementOrder<S> sorted(Comparator<S> comparator) {
099    return new ElementOrder<S>(Type.SORTED, comparator);
100  }
101
102  /** Returns the type of ordering used. */
103  public Type type() {
104    return type;
105  }
106
107  /**
108   * Returns the {@link Comparator} used.
109   *
110   * @throws UnsupportedOperationException if comparator is not defined
111   */
112  public Comparator<T> comparator() {
113    if (comparator != null) {
114      return comparator;
115    }
116    throw new UnsupportedOperationException("This ordering does not define a comparator.");
117  }
118
119  @Override
120  public boolean equals(@NullableDecl Object obj) {
121    if (obj == this) {
122      return true;
123    }
124    if (!(obj instanceof ElementOrder)) {
125      return false;
126    }
127
128    ElementOrder<?> other = (ElementOrder<?>) obj;
129    return (type == other.type) && Objects.equal(comparator, other.comparator);
130  }
131
132  @Override
133  public int hashCode() {
134    return Objects.hashCode(type, comparator);
135  }
136
137  @Override
138  public String toString() {
139    ToStringHelper helper = MoreObjects.toStringHelper(this).add("type", type);
140    if (comparator != null) {
141      helper.add("comparator", comparator);
142    }
143    return helper.toString();
144  }
145
146  /** Returns an empty mutable map whose keys will respect this {@link ElementOrder}. */
147  <K extends T, V> Map<K, V> createMap(int expectedSize) {
148    switch (type) {
149      case UNORDERED:
150        return Maps.newHashMapWithExpectedSize(expectedSize);
151      case INSERTION:
152        return Maps.newLinkedHashMapWithExpectedSize(expectedSize);
153      case SORTED:
154        return Maps.newTreeMap(comparator());
155      default:
156        throw new AssertionError();
157    }
158  }
159
160  @SuppressWarnings("unchecked")
161  <T1 extends T> ElementOrder<T1> cast() {
162    return (ElementOrder<T1>) this;
163  }
164}