ImmutableCollection.java revision 7dd252788645e940eada959bdde927426e2531c9
1/* 2 * Copyright (C) 2008 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 17package com.google.common.collect; 18 19import com.google.common.annotations.GwtCompatible; 20import com.google.common.annotations.VisibleForTesting; 21 22import java.io.Serializable; 23import java.util.Collection; 24import java.util.Iterator; 25 26import javax.annotation.Nullable; 27 28/** 29 * An immutable collection. Does not permit null elements. 30 * 31 * <p>In addition to the {@link Collection} methods, this class has an {@link 32 * #asList()} method, which returns a list view of the collection's elements. 33 * 34 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed 35 * outside of this package as it has no public or protected constructors. Thus, 36 * instances of this type are guaranteed to be immutable. 37 * 38 * @author Jesse Wilson 39 * @since 2.0 (imported from Google Collections Library) 40 */ 41@GwtCompatible(emulated = true) 42@SuppressWarnings("serial") 43// we're overriding default serialization 44public abstract class ImmutableCollection<E> implements Collection<E>, Serializable { 45 static final ImmutableCollection<Object> EMPTY_IMMUTABLE_COLLECTION = new EmptyImmutableCollection(); 46 47 ImmutableCollection() {} 48 49 /** 50 * Returns an unmodifiable iterator across the elements in this collection. 51 */ 52 53 public abstract UnmodifiableIterator<E> iterator(); 54 55 public Object[] toArray() { 56 return ObjectArrays.toArrayImpl(this); 57 } 58 59 public <T> T[] toArray(T[] other) { 60 return ObjectArrays.toArrayImpl(this, other); 61 } 62 63 public boolean contains(@Nullable Object object) { 64 return object != null && Iterators.contains(iterator(), object); 65 } 66 67 public boolean containsAll(Collection<?> targets) { 68 return Collections2.containsAllImpl(this, targets); 69 } 70 71 public boolean isEmpty() { 72 return size() == 0; 73 } 74 75 @Override 76 public String toString() { 77 return Collections2.toStringImpl(this); 78 } 79 80 /** 81 * Guaranteed to throw an exception and leave the collection unmodified. 82 * 83 * @throws UnsupportedOperationException always 84 * @deprecated Unsupported operation. 85 */ 86 @Deprecated 87 public final boolean add(E e) { 88 throw new UnsupportedOperationException(); 89 } 90 91 /** 92 * Guaranteed to throw an exception and leave the collection unmodified. 93 * 94 * @throws UnsupportedOperationException always 95 * @deprecated Unsupported operation. 96 */ 97 @Deprecated 98 public final boolean remove(Object object) { 99 throw new UnsupportedOperationException(); 100 } 101 102 /** 103 * Guaranteed to throw an exception and leave the collection unmodified. 104 * 105 * @throws UnsupportedOperationException always 106 * @deprecated Unsupported operation. 107 */ 108 @Deprecated 109 public final boolean addAll(Collection<? extends E> newElements) { 110 throw new UnsupportedOperationException(); 111 } 112 113 /** 114 * Guaranteed to throw an exception and leave the collection unmodified. 115 * 116 * @throws UnsupportedOperationException always 117 * @deprecated Unsupported operation. 118 */ 119 @Deprecated 120 public final boolean removeAll(Collection<?> oldElements) { 121 throw new UnsupportedOperationException(); 122 } 123 124 /** 125 * Guaranteed to throw an exception and leave the collection unmodified. 126 * 127 * @throws UnsupportedOperationException always 128 * @deprecated Unsupported operation. 129 */ 130 @Deprecated 131 public final boolean retainAll(Collection<?> elementsToKeep) { 132 throw new UnsupportedOperationException(); 133 } 134 135 /** 136 * Guaranteed to throw an exception and leave the collection unmodified. 137 * 138 * @throws UnsupportedOperationException always 139 * @deprecated Unsupported operation. 140 */ 141 @Deprecated 142 public final void clear() { 143 throw new UnsupportedOperationException(); 144 } 145 146 /* 147 * TODO(kevinb): Restructure code so ImmutableList doesn't contain this 148 * variable, which it doesn't use. 149 */ 150 private transient ImmutableList<E> asList; 151 152 /** 153 * Returns a list view of the collection. 154 * 155 * @since 2.0 156 */ 157 public ImmutableList<E> asList() { 158 ImmutableList<E> list = asList; 159 return (list == null) ? (asList = createAsList()) : list; 160 } 161 162 ImmutableList<E> createAsList() { 163 switch (size()) { 164 case 0: 165 return ImmutableList.of(); 166 case 1: 167 return ImmutableList.of(iterator().next()); 168 default: 169 return new RegularImmutableAsList<E>(this, toArray()); 170 } 171 } 172 173 abstract boolean isPartialView(); 174 175 private static class EmptyImmutableCollection extends ImmutableCollection<Object> { 176 177 public int size() { 178 return 0; 179 } 180 181 @Override 182 public boolean isEmpty() { 183 return true; 184 } 185 186 @Override 187 public boolean contains(@Nullable Object object) { 188 return false; 189 } 190 191 @Override 192 public UnmodifiableIterator<Object> iterator() { 193 return Iterators.EMPTY_LIST_ITERATOR; 194 } 195 196 private static final Object[] EMPTY_ARRAY = new Object[0]; 197 198 @Override 199 public Object[] toArray() { 200 return EMPTY_ARRAY; 201 } 202 203 @Override 204 public <T> T[] toArray(T[] array) { 205 if (array.length > 0) { 206 array[0] = null; 207 } 208 return array; 209 } 210 211 @Override 212 ImmutableList<Object> createAsList() { 213 return ImmutableList.of(); 214 } 215 216 @Override 217 boolean isPartialView() { 218 return false; 219 } 220 } 221 222 /** 223 * Nonempty collection stored in an array. 224 */ 225 private static class ArrayImmutableCollection<E> extends ImmutableCollection<E> { 226 private final E[] elements; 227 228 ArrayImmutableCollection(E[] elements) { 229 this.elements = elements; 230 } 231 232 public int size() { 233 return elements.length; 234 } 235 236 @Override 237 public boolean isEmpty() { 238 return false; 239 } 240 241 @Override 242 public UnmodifiableIterator<E> iterator() { 243 return Iterators.forArray(elements); 244 } 245 246 @Override 247 ImmutableList<E> createAsList() { 248 return elements.length == 1 ? new SingletonImmutableList<E>(elements[0]) 249 : new RegularImmutableList<E>(elements); 250 } 251 252 @Override 253 boolean isPartialView() { 254 return false; 255 } 256 } 257 258 /* 259 * Serializes ImmutableCollections as their logical contents. This ensures 260 * that implementation types do not leak into the serialized representation. 261 */ 262 private static class SerializedForm implements Serializable { 263 final Object[] elements; 264 265 SerializedForm(Object[] elements) { 266 this.elements = elements; 267 } 268 269 Object readResolve() { 270 return elements.length == 0 ? EMPTY_IMMUTABLE_COLLECTION 271 : new ArrayImmutableCollection<Object>(Platform.clone(elements)); 272 } 273 274 private static final long serialVersionUID = 0; 275 } 276 277 Object writeReplace() { 278 return new SerializedForm(toArray()); 279 } 280 281 /** 282 * Abstract base class for builders of {@link ImmutableCollection} types. 283 * 284 * @since 10.0 285 */ 286 public abstract static class Builder<E> { 287 static final int DEFAULT_INITIAL_CAPACITY = 4; 288 289 @VisibleForTesting 290 static int expandedCapacity(int oldCapacity, int minCapacity) { 291 if (minCapacity < 0) { 292 throw new AssertionError("cannot store more than MAX_VALUE elements"); 293 } 294 // careful of overflow! 295 int newCapacity = oldCapacity + (oldCapacity >> 1) + 1; 296 if (newCapacity < minCapacity) { 297 newCapacity = Integer.highestOneBit(minCapacity - 1) << 1; 298 } 299 if (newCapacity < 0) { 300 newCapacity = Integer.MAX_VALUE; 301 // guaranteed to be >= newCapacity 302 } 303 return newCapacity; 304 } 305 306 Builder() {} 307 308 /** 309 * Adds {@code element} to the {@code ImmutableCollection} being built. 310 * 311 * <p>Note that each builder class covariantly returns its own type from 312 * this method. 313 * 314 * @param element the element to add 315 * @return this {@code Builder} instance 316 * @throws NullPointerException if {@code element} is null 317 */ 318 public abstract Builder<E> add(E element); 319 320 /** 321 * Adds each element of {@code elements} to the {@code ImmutableCollection} 322 * being built. 323 * 324 * <p>Note that each builder class overrides this method in order to 325 * covariantly return its own type. 326 * 327 * @param elements the elements to add 328 * @return this {@code Builder} instance 329 * @throws NullPointerException if {@code elements} is null or contains a 330 * null element 331 */ 332 public Builder<E> add(E... elements) { 333 for (E element : elements) { 334 add(element); 335 } 336 return this; 337 } 338 339 /** 340 * Adds each element of {@code elements} to the {@code ImmutableCollection} 341 * being built. 342 * 343 * <p>Note that each builder class overrides this method in order to 344 * covariantly return its own type. 345 * 346 * @param elements the elements to add 347 * @return this {@code Builder} instance 348 * @throws NullPointerException if {@code elements} is null or contains a 349 * null element 350 */ 351 public Builder<E> addAll(Iterable<? extends E> elements) { 352 for (E element : elements) { 353 add(element); 354 } 355 return this; 356 } 357 358 /** 359 * Adds each element of {@code elements} to the {@code ImmutableCollection} 360 * being built. 361 * 362 * <p>Note that each builder class overrides this method in order to 363 * covariantly return its own type. 364 * 365 * @param elements the elements to add 366 * @return this {@code Builder} instance 367 * @throws NullPointerException if {@code elements} is null or contains a 368 * null element 369 */ 370 public Builder<E> addAll(Iterator<? extends E> elements) { 371 while (elements.hasNext()) { 372 add(elements.next()); 373 } 374 return this; 375 } 376 377 /** 378 * Returns a newly-created {@code ImmutableCollection} of the appropriate 379 * type, containing the elements provided to this builder. 380 * 381 * <p>Note that each builder class covariantly returns the appropriate type 382 * of {@code ImmutableCollection} from this method. 383 */ 384 public abstract ImmutableCollection<E> build(); 385 } 386} 387