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}