55 */
56 static final int SALT;
57 static {
58 long nt = System.nanoTime();
59 SALT = (int)((nt >>> 32) ^ nt);
60 }
61
62 /** No instances. */
63 private ImmutableCollections() { }
64
65 /**
66 * The reciprocal of load factor. Given a number of elements
67 * to store, multiply by this factor to get the table size.
68 */
69 static final int EXPAND_FACTOR = 2;
70
71 static UnsupportedOperationException uoe() { return new UnsupportedOperationException(); }
72
73 // ---------- List Implementations ----------
74
75 abstract static class AbstractImmutableList<E> extends AbstractList<E>
76 implements RandomAccess, Serializable {
77 @Override public boolean add(E e) { throw uoe(); }
78 @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
79 @Override public boolean addAll(int index, Collection<? extends E> c) { throw uoe(); }
80 @Override public void clear() { throw uoe(); }
81 @Override public boolean remove(Object o) { throw uoe(); }
82 @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
83 @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
84 @Override public void replaceAll(UnaryOperator<E> operator) { throw uoe(); }
85 @Override public boolean retainAll(Collection<?> c) { throw uoe(); }
86 @Override public void sort(Comparator<? super E> c) { throw uoe(); }
87 }
88
89 static final class List0<E> extends AbstractImmutableList<E> {
90 private static final List0<?> INSTANCE = new List0<>();
91
92 @SuppressWarnings("unchecked")
93 static <T> List0<T> instance() {
94 return (List0<T>) INSTANCE;
95 }
96
97 private List0() { }
98
99 @Override
100 public int size() {
101 return 0;
102 }
103
104 @Override
105 public E get(int index) {
106 Objects.checkIndex(index, 0); // always throws IndexOutOfBoundsException
107 return null; // but the compiler doesn't know this
108 }
109
110 @Override
111 public Iterator<E> iterator() {
112 return Collections.emptyIterator();
113 }
114
115 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
116 throw new InvalidObjectException("not serial proxy");
117 }
118
119 private Object writeReplace() {
120 return new CollSer(CollSer.IMM_LIST);
121 }
122
123 @Override
124 public boolean contains(Object o) {
125 Objects.requireNonNull(o);
126 return false;
127 }
128
129 @Override
130 public boolean containsAll(Collection<?> o) {
131 return o.isEmpty(); // implicit nullcheck of o
132 }
133
134 @Override
135 public int hashCode() {
136 return 1;
137 }
138 }
139
140 static final class List1<E> extends AbstractImmutableList<E> {
141 @Stable
142 private final E e0;
143
144 List1(E e0) {
145 this.e0 = Objects.requireNonNull(e0);
146 }
147
148 @Override
149 public int size() {
150 return 1;
151 }
152
153 @Override
154 public E get(int index) {
155 Objects.checkIndex(index, 1);
156 return e0;
157 }
158
159 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
160 throw new InvalidObjectException("not serial proxy");
161 }
162
163 private Object writeReplace() {
164 return new CollSer(CollSer.IMM_LIST, e0);
165 }
166
167 @Override
168 public boolean contains(Object o) {
169 return o.equals(e0); // implicit nullcheck of o
170 }
171
172 @Override
173 public int hashCode() {
174 return 31 + e0.hashCode();
175 }
176 }
177
178 static final class List2<E> extends AbstractImmutableList<E> {
179 @Stable
180 private final E e0;
181 @Stable
182 private final E e1;
183
184 List2(E e0, E e1) {
185 this.e0 = Objects.requireNonNull(e0);
186 this.e1 = Objects.requireNonNull(e1);
187 }
188
189 @Override
190 public int size() {
191 return 2;
192 }
193
194 @Override
195 public E get(int index) {
196 Objects.checkIndex(index, 2);
197 if (index == 0) {
198 return e0;
199 } else { // index == 1
200 return e1;
201 }
202 }
203
204 @Override
205 public boolean contains(Object o) {
206 return o.equals(e0) || o.equals(e1); // implicit nullcheck of o
207 }
208
209 @Override
210 public int hashCode() {
211 int hash = 31 + e0.hashCode();
212 return 31 * hash + e1.hashCode();
213 }
214
215 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
216 throw new InvalidObjectException("not serial proxy");
217 }
218
219 private Object writeReplace() {
220 return new CollSer(CollSer.IMM_LIST, e0, e1);
221 }
222 }
223
224 static final class ListN<E> extends AbstractImmutableList<E> {
225 @Stable
226 private final E[] elements;
227
228 @SafeVarargs
229 ListN(E... input) {
230 // copy and check manually to avoid TOCTOU
231 @SuppressWarnings("unchecked")
232 E[] tmp = (E[])new Object[input.length]; // implicit nullcheck of input
233 for (int i = 0; i < input.length; i++) {
234 tmp[i] = Objects.requireNonNull(input[i]);
235 }
236 this.elements = tmp;
237 }
238
239 @Override
240 public int size() {
241 return elements.length;
242 }
243
244 @Override
245 public E get(int index) {
246 Objects.checkIndex(index, elements.length);
247 return elements[index];
248 }
249
250 @Override
251 public boolean contains(Object o) {
252 for (E e : elements) {
253 if (o.equals(e)) { // implicit nullcheck of o
254 return true;
255 }
256 }
257 return false;
258 }
259
260 @Override
261 public int hashCode() {
262 int hash = 1;
263 for (E e : elements) {
264 hash = 31 * hash + e.hashCode();
265 }
266 return hash;
267 }
268
269 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
270 throw new InvalidObjectException("not serial proxy");
271 }
272
273 private Object writeReplace() {
274 return new CollSer(CollSer.IMM_LIST, elements);
275 }
276 }
277
278 // ---------- Set Implementations ----------
279
280 abstract static class AbstractImmutableSet<E> extends AbstractSet<E> implements Serializable {
281 @Override public boolean add(E e) { throw uoe(); }
282 @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
283 @Override public void clear() { throw uoe(); }
284 @Override public boolean remove(Object o) { throw uoe(); }
285 @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
286 @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
287 @Override public boolean retainAll(Collection<?> c) { throw uoe(); }
288 }
289
290 static final class Set0<E> extends AbstractImmutableSet<E> {
291 private static final Set0<?> INSTANCE = new Set0<>();
292
293 @SuppressWarnings("unchecked")
294 static <T> Set0<T> instance() {
295 return (Set0<T>) INSTANCE;
296 }
297
298 private Set0() { }
299
300 @Override
301 public int size() {
302 return 0;
303 }
304
305 @Override
306 public boolean contains(Object o) {
307 Objects.requireNonNull(o);
308 return false;
309 }
310
311 @Override
312 public boolean containsAll(Collection<?> o) {
313 return o.isEmpty(); // implicit nullcheck of o
314 }
315
316 @Override
317 public Iterator<E> iterator() {
318 return Collections.emptyIterator();
319 }
320
321 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
322 throw new InvalidObjectException("not serial proxy");
323 }
324
325 private Object writeReplace() {
326 return new CollSer(CollSer.IMM_SET);
327 }
328
329 @Override
330 public int hashCode() {
331 return 0;
332 }
333 }
334
335 static final class Set1<E> extends AbstractImmutableSet<E> {
336 @Stable
337 private final E e0;
338
339 Set1(E e0) {
340 this.e0 = Objects.requireNonNull(e0);
341 }
342
343 @Override
344 public int size() {
345 return 1;
346 }
347
348 @Override
349 public boolean contains(Object o) {
350 return o.equals(e0); // implicit nullcheck of o
351 }
352
353 @Override
354 public Iterator<E> iterator() {
355 return Collections.singletonIterator(e0);
356 }
357
358 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
359 throw new InvalidObjectException("not serial proxy");
360 }
361
362 private Object writeReplace() {
363 return new CollSer(CollSer.IMM_SET, e0);
364 }
365
366 @Override
367 public int hashCode() {
368 return e0.hashCode();
369 }
370 }
371
372 static final class Set2<E> extends AbstractImmutableSet<E> {
373 @Stable
374 final E e0;
375 @Stable
376 final E e1;
377
378 Set2(E e0, E e1) {
379 if (e0.equals(Objects.requireNonNull(e1))) { // implicit nullcheck of e0
380 throw new IllegalArgumentException("duplicate element: " + e0);
381 }
382
383 if (SALT >= 0) {
384 this.e0 = e0;
385 this.e1 = e1;
386 } else {
387 this.e0 = e1;
388 this.e1 = e0;
389 }
390 }
391
392 @Override
393 public int size() {
394 return 2;
395 }
396
397 @Override
398 public boolean contains(Object o) {
399 return o.equals(e0) || o.equals(e1); // implicit nullcheck of o
400 }
401
402 @Override
403 public int hashCode() {
404 return e0.hashCode() + e1.hashCode();
405 }
406
407 @Override
408 public Iterator<E> iterator() {
409 return new Iterator<E>() {
410 private int idx = 0;
411
412 @Override
413 public boolean hasNext() {
414 return idx < 2;
415 }
416
417 @Override
418 public E next() {
419 if (idx == 0) {
420 idx = 1;
421 return e0;
422 } else if (idx == 1) {
423 idx = 2;
424 return e1;
425 } else {
426 throw new NoSuchElementException();
427 }
428 }
429 };
430 }
431
432 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
433 throw new InvalidObjectException("not serial proxy");
434 }
435
436 private Object writeReplace() {
437 return new CollSer(CollSer.IMM_SET, e0, e1);
438 }
439 }
440
441 /**
442 * An array-based Set implementation. The element array must be strictly
443 * larger than the size (the number of contained elements) so that at
444 * least one null is always present.
445 * @param <E> the element type
446 */
447 static final class SetN<E> extends AbstractImmutableSet<E> {
448 @Stable
449 final E[] elements;
450 @Stable
451 final int size;
452
453 @SafeVarargs
454 @SuppressWarnings("unchecked")
455 SetN(E... input) {
456 size = input.length; // implicit nullcheck of input
457
458 elements = (E[])new Object[EXPAND_FACTOR * input.length];
459 for (int i = 0; i < input.length; i++) {
460 E e = input[i];
461 int idx = probe(e); // implicit nullcheck of e
462 if (idx >= 0) {
463 throw new IllegalArgumentException("duplicate element: " + e);
464 } else {
465 elements[-(idx + 1)] = e;
466 }
467 }
468 }
469
470 @Override
471 public int size() {
472 return size;
473 }
474
475 @Override
476 public boolean contains(Object o) {
477 return probe(o) >= 0; // implicit nullcheck of o
478 }
479
480 @Override
481 public Iterator<E> iterator() {
482 return new Iterator<E>() {
483 private int idx = 0;
484
485 @Override
486 public boolean hasNext() {
487 while (idx < elements.length) {
488 if (elements[idx] != null)
489 return true;
490 idx++;
491 }
492 return false;
493 }
494
495 @Override
496 public E next() {
497 if (! hasNext()) {
548 }
549
550 // ---------- Map Implementations ----------
551
552 abstract static class AbstractImmutableMap<K,V> extends AbstractMap<K,V> implements Serializable {
553 @Override public void clear() { throw uoe(); }
554 @Override public V compute(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
555 @Override public V computeIfAbsent(K key, Function<? super K,? extends V> mf) { throw uoe(); }
556 @Override public V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
557 @Override public V merge(K key, V value, BiFunction<? super V,? super V,? extends V> rf) { throw uoe(); }
558 @Override public V put(K key, V value) { throw uoe(); }
559 @Override public void putAll(Map<? extends K,? extends V> m) { throw uoe(); }
560 @Override public V putIfAbsent(K key, V value) { throw uoe(); }
561 @Override public V remove(Object key) { throw uoe(); }
562 @Override public boolean remove(Object key, Object value) { throw uoe(); }
563 @Override public V replace(K key, V value) { throw uoe(); }
564 @Override public boolean replace(K key, V oldValue, V newValue) { throw uoe(); }
565 @Override public void replaceAll(BiFunction<? super K,? super V,? extends V> f) { throw uoe(); }
566 }
567
568 static final class Map0<K,V> extends AbstractImmutableMap<K,V> {
569 private static final Map0<?,?> INSTANCE = new Map0<>();
570
571 @SuppressWarnings("unchecked")
572 static <K,V> Map0<K,V> instance() {
573 return (Map0<K,V>) INSTANCE;
574 }
575
576 private Map0() { }
577
578 @Override
579 public Set<Map.Entry<K,V>> entrySet() {
580 return Set.of();
581 }
582
583 @Override
584 public boolean containsKey(Object o) {
585 Objects.requireNonNull(o);
586 return false;
587 }
588
589 @Override
590 public boolean containsValue(Object o) {
591 Objects.requireNonNull(o);
592 return false;
593 }
594
595 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
596 throw new InvalidObjectException("not serial proxy");
597 }
598
599 private Object writeReplace() {
600 return new CollSer(CollSer.IMM_MAP);
601 }
602
603 @Override
604 public int hashCode() {
605 return 0;
606 }
607 }
608
609 static final class Map1<K,V> extends AbstractImmutableMap<K,V> {
610 @Stable
611 private final K k0;
612 @Stable
613 private final V v0;
614
615 Map1(K k0, V v0) {
616 this.k0 = Objects.requireNonNull(k0);
617 this.v0 = Objects.requireNonNull(v0);
618 }
619
620 @Override
621 public Set<Map.Entry<K,V>> entrySet() {
622 return Set.of(new KeyValueHolder<>(k0, v0));
623 }
624
625 @Override
626 public boolean containsKey(Object o) {
627 return o.equals(k0); // implicit nullcheck of o
628 }
641 }
642
643 @Override
644 public int hashCode() {
645 return k0.hashCode() ^ v0.hashCode();
646 }
647 }
648
649 /**
650 * An array-based Map implementation. There is a single array "table" that
651 * contains keys and values interleaved: table[0] is kA, table[1] is vA,
652 * table[2] is kB, table[3] is vB, etc. The table size must be even. It must
653 * also be strictly larger than the size (the number of key-value pairs contained
654 * in the map) so that at least one null key is always present.
655 * @param <K> the key type
656 * @param <V> the value type
657 */
658 static final class MapN<K,V> extends AbstractImmutableMap<K,V> {
659 @Stable
660 final Object[] table; // pairs of key, value
661 @Stable
662 final int size; // number of pairs
663
664 MapN(Object... input) {
665 if ((input.length & 1) != 0) { // implicit nullcheck of input
666 throw new InternalError("length is odd");
667 }
668 size = input.length >> 1;
669
670 int len = EXPAND_FACTOR * input.length;
671 len = (len + 1) & ~1; // ensure table is even length
672 table = new Object[len];
673
674 for (int i = 0; i < input.length; i += 2) {
675 @SuppressWarnings("unchecked")
676 K k = Objects.requireNonNull((K)input[i]);
677 @SuppressWarnings("unchecked")
678 V v = Objects.requireNonNull((V)input[i+1]);
679 int idx = probe(k);
680 if (idx >= 0) {
681 throw new IllegalArgumentException("duplicate key: " + k);
682 } else {
683 int dest = -(idx + 1);
684 table[dest] = k;
685 table[dest+1] = v;
686 }
687 }
688 }
689
690 @Override
691 public boolean containsKey(Object o) {
692 return probe(o) >= 0; // implicit nullcheck of o
693 }
694
695 @Override
696 public boolean containsValue(Object o) {
697 for (int i = 1; i < table.length; i += 2) {
698 Object v = table[i];
699 if (v != null && o.equals(v)) { // implicit nullcheck of o
700 return true;
701 }
702 }
703 return false;
704 }
705
706 @Override
707 public int hashCode() {
708 int hash = 0;
709 for (int i = 0; i < table.length; i += 2) {
710 Object k = table[i];
711 if (k != null) {
712 hash += k.hashCode() ^ table[i + 1].hashCode();
713 }
714 }
715 return hash;
716 }
717
718 @Override
719 @SuppressWarnings("unchecked")
720 public V get(Object o) {
721 int i = probe(o);
722 if (i >= 0) {
723 return (V)table[i+1];
724 } else {
725 return null;
726 }
727 }
728
729 @Override
730 public int size() {
731 return size;
732 }
733
734 @Override
735 public Set<Map.Entry<K,V>> entrySet() {
736 return new AbstractSet<Map.Entry<K,V>>() {
737 @Override
738 public int size() {
739 return MapN.this.size;
740 }
931 * @throws InvalidObjectException if the tag value is illegal or if an exception
932 * is thrown during creation of the collection
933 * @throws ObjectStreamException if another serialization error has occurred
934 * @since 9
935 */
936 private Object readResolve() throws ObjectStreamException {
937 try {
938 if (array == null) {
939 throw new InvalidObjectException("null array");
940 }
941
942 // use low order 8 bits to indicate "kind"
943 // ignore high order 24 bits
944 switch (tag & 0xff) {
945 case IMM_LIST:
946 return List.of(array);
947 case IMM_SET:
948 return Set.of(array);
949 case IMM_MAP:
950 if (array.length == 0) {
951 return ImmutableCollections.Map0.instance();
952 } else if (array.length == 2) {
953 return new ImmutableCollections.Map1<>(array[0], array[1]);
954 } else {
955 return new ImmutableCollections.MapN<>(array);
956 }
957 default:
958 throw new InvalidObjectException(String.format("invalid flags 0x%x", tag));
959 }
960 } catch (NullPointerException|IllegalArgumentException ex) {
961 InvalidObjectException ioe = new InvalidObjectException("invalid object");
962 ioe.initCause(ex);
963 throw ioe;
964 }
965 }
966 }
|
55 */
56 static final int SALT;
57 static {
58 long nt = System.nanoTime();
59 SALT = (int)((nt >>> 32) ^ nt);
60 }
61
62 /** No instances. */
63 private ImmutableCollections() { }
64
65 /**
66 * The reciprocal of load factor. Given a number of elements
67 * to store, multiply by this factor to get the table size.
68 */
69 static final int EXPAND_FACTOR = 2;
70
71 static UnsupportedOperationException uoe() { return new UnsupportedOperationException(); }
72
73 // ---------- List Implementations ----------
74
75 static final List<?> EMPTY_LIST = new ListN<>();
76
77 static final Set<?> EMPTY_SET = new SetN<>();
78
79 static final Map<?,?> EMPTY_MAP = new MapN<>();
80
81 @SuppressWarnings("unchecked")
82 static <T> List<T> emptyList() {
83 return (List<T>) EMPTY_LIST;
84 }
85
86 @SuppressWarnings("unchecked")
87 static <T> Set<T> emptySet() {
88 return (Set<T>) EMPTY_SET;
89 }
90
91 @SuppressWarnings("unchecked")
92 static <K,V> Map<K,V> emptyMap() {
93 return (Map<K,V>) EMPTY_MAP;
94 }
95
96 static final class ListN<E> extends AbstractCollection<E>
97 implements List<E>, RandomAccess, Serializable {
98
99 // all mutating methods throw UnsupportedOperationException
100 @Override public boolean add(E e) { throw uoe(); }
101 @Override public void add(int index, E element) { throw uoe(); }
102 @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
103 @Override public boolean addAll(int index, Collection<? extends E> c) { throw uoe(); }
104 @Override public void clear() { throw uoe(); }
105 @Override public boolean remove(Object o) { throw uoe(); }
106 @Override public E remove(int index) { throw uoe(); }
107 @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
108 @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
109 @Override public void replaceAll(UnaryOperator<E> operator) { throw uoe(); }
110 @Override public boolean retainAll(Collection<?> c) { throw uoe(); }
111 @Override public E set(int index, E element) { throw uoe(); }
112 @Override public void sort(Comparator<? super E> c) { throw uoe(); }
113
114 @Override
115 public int indexOf(Object o) {
116 Objects.requireNonNull(o);
117 ListIterator<E> it = listIterator();
118 while (it.hasNext()) {
119 if (o.equals(it.next())) {
120 return it.previousIndex();
121 }
122 }
123 return -1;
124 }
125
126 @Override
127 public int lastIndexOf(Object o) {
128 Objects.requireNonNull(o);
129 ListIterator<E> it = listIterator();
130 while (it.hasNext()) {
131 if (o.equals(it.next())) {
132 return it.previousIndex();
133 }
134 }
135 return -1;
136 }
137
138 @Override
139 public boolean equals(Object o) {
140 if (o == this) {
141 return true;
142 }
143
144 if (!(o instanceof List)) {
145 return false;
146 }
147
148 if (!(o instanceof ListN)) {
149 ListN<?> other = (ListN<?>)o;
150 return this.size == other.size && this.value.equals(other.value);
151 }
152
153 ListIterator<E> e1 = listIterator();
154 ListIterator<?> e2 = ((List<?>) o).listIterator();
155 while (e1.hasNext() && e2.hasNext()) {
156 E o1 = e1.next();
157 Object o2 = e2.next();
158 if (!(o1==null ? o2==null : o1.equals(o2)))
159 return false;
160 }
161 return !(e1.hasNext() || e2.hasNext());
162 }
163
164 @Override
165 public List<E> subList(int fromIndex, int toIndex) {
166 int size = size();
167 Objects.checkFromToIndex(fromIndex, toIndex, size);
168 if (size == 0 || fromIndex == toIndex) {
169 return emptyList();
170 } else if (size == 1) {
171 // checks above deal with corner cases subList(0,0) and subList(1,1)
172 // that would return the empty list
173 assert(fromIndex == 0 && toIndex == 1);
174 return this;
175 } else {
176 return new SubList<E>(this, fromIndex, toIndex);
177 }
178 }
179
180 private static class SubList<E> extends AbstractList<E> implements RandomAccess {
181 private final List<E> root;
182 private final int offset;
183 int size;
184
185 // all mutating methods throw UnsupportedOperationException
186 @Override public boolean add(E e) { throw uoe(); }
187 @Override public void add(int index, E element) { throw uoe(); }
188 @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
189 @Override public boolean addAll(int index, Collection<? extends E> c) { throw uoe(); }
190 @Override public void clear() { throw uoe(); }
191 @Override public boolean remove(Object o) { throw uoe(); }
192 @Override public E remove(int index) { throw uoe(); }
193 @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
194 @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
195 @Override public void replaceAll(UnaryOperator<E> operator) { throw uoe(); }
196 @Override public boolean retainAll(Collection<?> c) { throw uoe(); }
197 @Override public E set(int index, E element) { throw uoe(); }
198 @Override public void sort(Comparator<? super E> c) { throw uoe(); }
199
200 /**
201 * Constructs a sublist of an arbitrary AbstractList, which is
202 * not a SubList itself.
203 */
204 public SubList(List<E> root, int fromIndex, int toIndex) {
205 this.root = root;
206 this.offset = fromIndex;
207 this.size = toIndex - fromIndex;
208 }
209
210 /**
211 * Constructs a sublist of another SubList.
212 */
213 protected SubList(SubList<E> parent, int fromIndex, int toIndex) {
214 this.root = parent.root;
215 this.offset = parent.offset + fromIndex;
216 this.size = toIndex - fromIndex;
217 }
218
219 public E get(int index) {
220 Objects.checkIndex(index, size);
221 return root.get(offset + index);
222 }
223
224 public int size() {
225 return size;
226 }
227
228 protected void removeRange(int fromIndex, int toIndex) {
229 throw uoe();
230 }
231
232 public Iterator<E> iterator() {
233 return listIterator();
234 }
235
236 public ListIterator<E> listIterator(int index) {
237 rangeCheck(index);
238
239 return new ListIterator<E>() {
240 private final ListIterator<E> i =
241 root.listIterator(offset + index);
242
243 public boolean hasNext() {
244 return nextIndex() < size;
245 }
246
247 public E next() {
248 if (hasNext())
249 return i.next();
250 else
251 throw new NoSuchElementException();
252 }
253
254 public boolean hasPrevious() {
255 return previousIndex() >= 0;
256 }
257
258 public E previous() {
259 if (hasPrevious())
260 return i.previous();
261 else
262 throw new NoSuchElementException();
263 }
264
265 public int nextIndex() {
266 return i.nextIndex() - offset;
267 }
268
269 public int previousIndex() {
270 return i.previousIndex() - offset;
271 }
272
273 public void remove() { throw uoe(); }
274 public void set(E e) { throw uoe(); }
275 public void add(E e) { throw uoe(); }
276 };
277 }
278
279 public List<E> subList(int fromIndex, int toIndex) {
280 subListRangeCheck(fromIndex, toIndex, size);
281 return new SubList<>(this, fromIndex, toIndex);
282 }
283
284 private void rangeCheck(int index) {
285 if (index < 0 || index > size)
286 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
287 }
288
289 private String outOfBoundsMsg(int index) {
290 return "Index: "+index+", Size: "+size;
291 }
292 }
293
294 @Stable
295 private final Object value;
296
297 private final int size;
298
299 @SafeVarargs
300 ListN(E... input) {
301 if (input.length == 1) {
302 value = Objects.requireNonNull(input[0]);
303 size = 1;
304 } else {
305 // copy and check manually to avoid TOCTOU
306 @SuppressWarnings("unchecked")
307 E[] tmp = (E[])new Object[input.length]; // implicit nullcheck of input
308 for (int i = 0; i < input.length; i++) {
309 tmp[i] = Objects.requireNonNull(input[i]);
310 }
311 value = tmp;
312 size = input.length;
313 }
314 }
315
316 @Override
317 public boolean isEmpty() {
318 return size() == 0;
319 }
320
321 @Override
322 public int size() {
323 return size;
324 }
325
326 @Override
327 public E get(int index) {
328 if (size() == 1) {
329 return getSingle(index);
330 } else {
331 return getFromArray(index);
332 }
333 }
334
335 @SuppressWarnings("unchecked")
336 private E getFromArray(int index) {
337 return ((E[])value)[index];
338 }
339
340 @SuppressWarnings("unchecked")
341 private E getSingle(int index) {
342 Objects.checkIndex(index, size);
343 return (E)value;
344 }
345
346 @Override
347 @SuppressWarnings("unchecked")
348 public boolean contains(Object o) {
349 int size = size();
350 Objects.requireNonNull(o);
351 if (size == 1) {
352 return o.equals(value);
353 } else {
354 for (E e : (E[])value) {
355 if (o.equals(e)) { // implicit nullcheck of o
356 return true;
357 }
358 }
359 return false;
360 }
361 }
362
363 @Override
364 @SuppressWarnings("unchecked")
365 public int hashCode() {
366 if (size == 1) {
367 return 31 + value.hashCode();
368 }
369
370 int hash = 1;
371 for (E e : (E[])value) {
372 hash = 31 * hash + e.hashCode();
373 }
374 return hash;
375 }
376
377 @Override
378 public Iterator<E> iterator() {
379 return new Itr();
380 }
381
382 @Override
383 public ListIterator<E> listIterator() {
384 return listIterator(0);
385 }
386
387 @Override
388 public ListIterator<E> listIterator(final int index) {
389 Objects.checkIndex(index, size());
390 return new ListItr(index);
391 }
392
393 private class Itr implements Iterator<E> {
394 Itr() {
395 size = size();
396 }
397
398 int cursor = 0;
399
400 private final int size;
401
402 public boolean hasNext() {
403 return cursor != size;
404 }
405
406 public E next() {
407 try {
408 int i = cursor;
409 E next = get(i);
410 cursor = i + 1;
411 return next;
412 } catch (IndexOutOfBoundsException e) {
413 throw new NoSuchElementException();
414 }
415 }
416
417 public void remove() {
418 throw uoe();
419 }
420 }
421
422 private class ListItr extends Itr implements ListIterator<E> {
423 ListItr(int index) {
424 cursor = index;
425 }
426
427 public boolean hasPrevious() {
428 return cursor != 0;
429 }
430
431 public E previous() {
432 try {
433 int i = cursor - 1;
434 E previous = get(i);
435 cursor = i;
436 return previous;
437 } catch (IndexOutOfBoundsException e) {
438 throw new NoSuchElementException();
439 }
440 }
441
442 public int nextIndex() {
443 return cursor;
444 }
445
446 public int previousIndex() {
447 return cursor - 1;
448 }
449
450 public void set(E e) {
451 throw uoe();
452 }
453
454 public void add(E e) {
455 throw uoe();
456 }
457 }
458
459 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
460 throw new InvalidObjectException("not serial proxy");
461 }
462
463 @SuppressWarnings("unchecked")
464 private Object writeReplace() {
465 int size = size();
466 if (size == 1) {
467 return new CollSer(CollSer.IMM_LIST, (E)value);
468 } else {
469 return new CollSer(CollSer.IMM_LIST, (E[])value);
470 }
471 }
472 }
473
474 // ---------- Set Implementations ----------
475
476 abstract static class AbstractImmutableSet<E> extends AbstractSet<E> implements Serializable {
477 @Override public boolean add(E e) { throw uoe(); }
478 @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
479 @Override public void clear() { throw uoe(); }
480 @Override public boolean remove(Object o) { throw uoe(); }
481 @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
482 @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
483 @Override public boolean retainAll(Collection<?> c) { throw uoe(); }
484 }
485
486 static final class Set1<E> extends AbstractImmutableSet<E> {
487 @Stable
488 private final E e0;
489
490 Set1(E e0) {
491 this.e0 = Objects.requireNonNull(e0);
492 }
493
494 @Override
495 public int size() {
496 return 1;
497 }
498
499 @Override
500 public boolean contains(Object o) {
501 return o.equals(e0); // implicit nullcheck of o
502 }
503
504 @Override
505 public Iterator<E> iterator() {
506 return Collections.singletonIterator(e0);
507 }
508
509 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
510 throw new InvalidObjectException("not serial proxy");
511 }
512
513 private Object writeReplace() {
514 return new CollSer(CollSer.IMM_SET, e0);
515 }
516
517 @Override
518 public int hashCode() {
519 return e0.hashCode();
520 }
521 }
522
523 /**
524 * An array-based Set implementation. The element array must be strictly
525 * larger than the size (the number of contained elements) so that at
526 * least one null is always present.
527 * @param <E> the element type
528 */
529 static final class SetN<E> extends AbstractImmutableSet<E> {
530 @Stable
531 final E[] elements;
532 @Stable
533 final int size;
534
535 @SafeVarargs
536 @SuppressWarnings("unchecked")
537 SetN(E... input) {
538 size = input.length; // implicit nullcheck of input
539
540 elements = (E[])new Object[EXPAND_FACTOR * input.length];
541 for (int i = 0; i < input.length; i++) {
542 E e = input[i];
543 int idx = probe(e); // implicit nullcheck of e
544 if (idx >= 0) {
545 throw new IllegalArgumentException("duplicate element: " + e);
546 } else {
547 elements[-(idx + 1)] = e;
548 }
549 }
550 }
551
552 @Override
553 public int size() {
554 return size;
555 }
556
557 @Override
558 public boolean contains(Object o) {
559 Objects.requireNonNull(0);
560 return size > 0 && probe(o) >= 0; // implicit nullcheck of o
561 }
562
563 @Override
564 public Iterator<E> iterator() {
565 return new Iterator<E>() {
566 private int idx = 0;
567
568 @Override
569 public boolean hasNext() {
570 while (idx < elements.length) {
571 if (elements[idx] != null)
572 return true;
573 idx++;
574 }
575 return false;
576 }
577
578 @Override
579 public E next() {
580 if (! hasNext()) {
631 }
632
633 // ---------- Map Implementations ----------
634
635 abstract static class AbstractImmutableMap<K,V> extends AbstractMap<K,V> implements Serializable {
636 @Override public void clear() { throw uoe(); }
637 @Override public V compute(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
638 @Override public V computeIfAbsent(K key, Function<? super K,? extends V> mf) { throw uoe(); }
639 @Override public V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
640 @Override public V merge(K key, V value, BiFunction<? super V,? super V,? extends V> rf) { throw uoe(); }
641 @Override public V put(K key, V value) { throw uoe(); }
642 @Override public void putAll(Map<? extends K,? extends V> m) { throw uoe(); }
643 @Override public V putIfAbsent(K key, V value) { throw uoe(); }
644 @Override public V remove(Object key) { throw uoe(); }
645 @Override public boolean remove(Object key, Object value) { throw uoe(); }
646 @Override public V replace(K key, V value) { throw uoe(); }
647 @Override public boolean replace(K key, V oldValue, V newValue) { throw uoe(); }
648 @Override public void replaceAll(BiFunction<? super K,? super V,? extends V> f) { throw uoe(); }
649 }
650
651 static final class Map1<K,V> extends AbstractImmutableMap<K,V> {
652 @Stable
653 private final K k0;
654 @Stable
655 private final V v0;
656
657 Map1(K k0, V v0) {
658 this.k0 = Objects.requireNonNull(k0);
659 this.v0 = Objects.requireNonNull(v0);
660 }
661
662 @Override
663 public Set<Map.Entry<K,V>> entrySet() {
664 return Set.of(new KeyValueHolder<>(k0, v0));
665 }
666
667 @Override
668 public boolean containsKey(Object o) {
669 return o.equals(k0); // implicit nullcheck of o
670 }
683 }
684
685 @Override
686 public int hashCode() {
687 return k0.hashCode() ^ v0.hashCode();
688 }
689 }
690
691 /**
692 * An array-based Map implementation. There is a single array "table" that
693 * contains keys and values interleaved: table[0] is kA, table[1] is vA,
694 * table[2] is kB, table[3] is vB, etc. The table size must be even. It must
695 * also be strictly larger than the size (the number of key-value pairs contained
696 * in the map) so that at least one null key is always present.
697 * @param <K> the key type
698 * @param <V> the value type
699 */
700 static final class MapN<K,V> extends AbstractImmutableMap<K,V> {
701 @Stable
702 final Object[] table; // pairs of key, value
703 final int size; // number of pairs
704
705 MapN(Object... input) {
706 if ((input.length & 1) != 0) { // implicit nullcheck of input
707 throw new InternalError("length is odd");
708 }
709 size = input.length >> 1;
710
711 int len = EXPAND_FACTOR * input.length;
712 len = (len + 1) & ~1; // ensure table is even length
713 table = new Object[len];
714
715 for (int i = 0; i < input.length; i += 2) {
716 @SuppressWarnings("unchecked")
717 K k = Objects.requireNonNull((K)input[i]);
718 @SuppressWarnings("unchecked")
719 V v = Objects.requireNonNull((V)input[i+1]);
720 int idx = probe(k);
721 if (idx >= 0) {
722 throw new IllegalArgumentException("duplicate key: " + k);
723 } else {
724 int dest = -(idx + 1);
725 table[dest] = k;
726 table[dest+1] = v;
727 }
728 }
729 }
730
731 @Override
732 public boolean containsKey(Object o) {
733 Objects.requireNonNull(0);
734 return size > 0 && probe(o) >= 0;
735 }
736
737 @Override
738 public boolean containsValue(Object o) {
739 for (int i = 1; i < table.length; i += 2) {
740 Object v = table[i];
741 if (v != null && o.equals(v)) { // implicit nullcheck of o
742 return true;
743 }
744 }
745 return false;
746 }
747
748 @Override
749 public int hashCode() {
750 int hash = 0;
751 for (int i = 0; i < table.length; i += 2) {
752 Object k = table[i];
753 if (k != null) {
754 hash += k.hashCode() ^ table[i + 1].hashCode();
755 }
756 }
757 return hash;
758 }
759
760 @Override
761 @SuppressWarnings("unchecked")
762 public V get(Object o) {
763 if (size == 0) {
764 return null;
765 }
766 int i = probe(o);
767 if (i >= 0) {
768 return (V)table[i+1];
769 } else {
770 return null;
771 }
772 }
773
774 @Override
775 public int size() {
776 return size;
777 }
778
779 @Override
780 public Set<Map.Entry<K,V>> entrySet() {
781 return new AbstractSet<Map.Entry<K,V>>() {
782 @Override
783 public int size() {
784 return MapN.this.size;
785 }
976 * @throws InvalidObjectException if the tag value is illegal or if an exception
977 * is thrown during creation of the collection
978 * @throws ObjectStreamException if another serialization error has occurred
979 * @since 9
980 */
981 private Object readResolve() throws ObjectStreamException {
982 try {
983 if (array == null) {
984 throw new InvalidObjectException("null array");
985 }
986
987 // use low order 8 bits to indicate "kind"
988 // ignore high order 24 bits
989 switch (tag & 0xff) {
990 case IMM_LIST:
991 return List.of(array);
992 case IMM_SET:
993 return Set.of(array);
994 case IMM_MAP:
995 if (array.length == 0) {
996 return ImmutableCollections.emptyMap();
997 } else if (array.length == 2) {
998 return new ImmutableCollections.Map1<>(array[0], array[1]);
999 } else {
1000 return new ImmutableCollections.MapN<>(array);
1001 }
1002 default:
1003 throw new InvalidObjectException(String.format("invalid flags 0x%x", tag));
1004 }
1005 } catch (NullPointerException|IllegalArgumentException ex) {
1006 InvalidObjectException ioe = new InvalidObjectException("invalid object");
1007 ioe.initCause(ex);
1008 throw ioe;
1009 }
1010 }
1011 }
|