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