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 java.util.Comparator;
029import java.util.Map;
030import javax.annotation.Nullable;
031
032/**
033 * Used to represent the order of elements in a data structure that supports different options for
034 * iteration order guarantees.
035 *
036 * <p>Example usage:
037 *
038 * <pre>{@code
039 * MutableGraph<Integer> graph =
040 *     GraphBuilder.directed().nodeOrder(ElementOrder.<Integer>natural()).build();
041 * }</pre>
042 *
043 * @author Joshua O'Madadhain
044 * @since 20.0
045 */
046@Beta
047public final class ElementOrder<T> {
048  private final Type type;
049
050  @Nullable
051  private final Comparator<T> comparator;
052
053  /**
054   * The type of ordering that this object specifies.
055   *
056   * <ul>
057   * <li>UNORDERED: no order is guaranteed.
058   * <li>INSERTION: insertion ordering is guaranteed.
059   * <li>SORTED: ordering according to a supplied comparator is guaranteed.
060   * </ul>
061   */
062  public enum Type {
063    UNORDERED,
064    INSERTION,
065    SORTED
066  }
067
068  private ElementOrder(Type type, @Nullable Comparator<T> comparator) {
069    this.type = checkNotNull(type);
070    this.comparator = comparator;
071    checkState((type == Type.SORTED) == (comparator != null));
072  }
073
074  /** Returns an instance which specifies that no ordering is guaranteed. */
075  public static <S> ElementOrder<S> unordered() {
076    return new ElementOrder<S>(Type.UNORDERED, null);
077  }
078
079  /** Returns an instance which specifies that insertion ordering is guaranteed. */
080  public static <S> ElementOrder<S> insertion() {
081    return new ElementOrder<S>(Type.INSERTION, null);
082  }
083
084  /**
085   * Returns an instance which specifies that the natural ordering of the elements is guaranteed.
086   */
087  public static <S extends Comparable<? super S>> ElementOrder<S> natural() {
088    return new ElementOrder<S>(Type.SORTED, Ordering.<S>natural());
089  }
090
091  /**
092   * Returns an instance which specifies that the ordering of the elements is guaranteed to be
093   * determined by {@code comparator}.
094   */
095  public static <S> ElementOrder<S> sorted(Comparator<S> comparator) {
096    return new ElementOrder<S>(Type.SORTED, comparator);
097  }
098
099  /** Returns the type of ordering used. */
100  public Type type() {
101    return type;
102  }
103
104  /**
105   * Returns the {@link Comparator} used.
106   *
107   * @throws UnsupportedOperationException if comparator is not defined
108   */
109  public Comparator<T> comparator() {
110    if (comparator != null) {
111      return comparator;
112    }
113    throw new UnsupportedOperationException("This ordering does not define a comparator.");
114  }
115
116  @Override
117  public boolean equals(@Nullable Object obj) {
118    if (obj == this) {
119      return true;
120    }
121    if (!(obj instanceof ElementOrder)) {
122      return false;
123    }
124
125    ElementOrder<?> other = (ElementOrder<?>) obj;
126    return (type == other.type) && Objects.equal(comparator, other.comparator);
127  }
128
129  @Override
130  public int hashCode() {
131    return Objects.hashCode(type, comparator);
132  }
133
134  @Override
135  public String toString() {
136    ToStringHelper helper = MoreObjects.toStringHelper(this).add("type", type);
137    if (comparator != null) {
138      helper.add("comparator", comparator);
139    }
140    return helper.toString();
141  }
142
143  /** Returns an empty mutable map whose keys will respect this {@link ElementOrder}. */
144  <K extends T, V> Map<K, V> createMap(int expectedSize) {
145    switch (type) {
146      case UNORDERED:
147        return Maps.newHashMapWithExpectedSize(expectedSize);
148      case INSERTION:
149        return Maps.newLinkedHashMapWithExpectedSize(expectedSize);
150      case SORTED:
151        return Maps.newTreeMap(comparator());
152      default:
153        throw new AssertionError();
154    }
155  }
156
157  @SuppressWarnings("unchecked")
158  <T1 extends T> ElementOrder<T1> cast() {
159    return (ElementOrder<T1>) this;
160  }
161}