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 org.checkerframework.checker.nullness.compatqual.NullableDecl; 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 public final class ElementOrder<T> { 50 private final Type type; 51 52 @SuppressWarnings("Immutable") // Hopefully the comparator provided is immutable! 53 @NullableDecl 54 private final Comparator<T> comparator; 55 56 /** 57 * The type of ordering that this object specifies. 58 * 59 * <ul> 60 * <li>UNORDERED: no order is guaranteed. 61 * <li>INSERTION: insertion ordering is guaranteed. 62 * <li>SORTED: ordering according to a supplied comparator is guaranteed. 63 * </ul> 64 */ 65 public enum Type { 66 UNORDERED, 67 INSERTION, 68 SORTED 69 } 70 ElementOrder(Type type, @NullableDecl Comparator<T> comparator)71 private ElementOrder(Type type, @NullableDecl Comparator<T> comparator) { 72 this.type = checkNotNull(type); 73 this.comparator = comparator; 74 checkState((type == Type.SORTED) == (comparator != null)); 75 } 76 77 /** Returns an instance which specifies that no ordering is guaranteed. */ unordered()78 public static <S> ElementOrder<S> unordered() { 79 return new ElementOrder<S>(Type.UNORDERED, null); 80 } 81 82 /** Returns an instance which specifies that insertion ordering is guaranteed. */ insertion()83 public static <S> ElementOrder<S> insertion() { 84 return new ElementOrder<S>(Type.INSERTION, null); 85 } 86 87 /** 88 * Returns an instance which specifies that the natural ordering of the elements is guaranteed. 89 */ natural()90 public static <S extends Comparable<? super S>> ElementOrder<S> natural() { 91 return new ElementOrder<S>(Type.SORTED, Ordering.<S>natural()); 92 } 93 94 /** 95 * Returns an instance which specifies that the ordering of the elements is guaranteed to be 96 * determined by {@code comparator}. 97 */ sorted(Comparator<S> comparator)98 public static <S> ElementOrder<S> sorted(Comparator<S> comparator) { 99 return new ElementOrder<S>(Type.SORTED, comparator); 100 } 101 102 /** Returns the type of ordering used. */ type()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 */ comparator()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 equals(@ullableDecl Object obj)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 hashCode()133 public int hashCode() { 134 return Objects.hashCode(type, comparator); 135 } 136 137 @Override toString()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}. */ createMap(int expectedSize)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") cast()161 <T1 extends T> ElementOrder<T1> cast() { 162 return (ElementOrder<T1>) this; 163 } 164 } 165