Coverage Summary for Class: RegularImmutableSortedSet (com.google.common.collect)

1 /*
2  * Copyright (C) 2009 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.collect;
18 
19 import static com.google.common.base.Preconditions.checkNotNull;
20 
21 import com.google.common.annotations.GwtCompatible;
22 import com.google.common.annotations.GwtIncompatible;
23 import java.util.Collection;
24 import java.util.Collections;
25 import java.util.Comparator;
26 import java.util.Iterator;
27 import java.util.NoSuchElementException;
28 import java.util.Set;
29 import java.util.Spliterator;
30 import java.util.function.Consumer;
31 import org.checkerframework.checker.nullness.qual.Nullable;
32 
33 /**
34  * An immutable sorted set with one or more elements. TODO(jlevy): Consider separate class for a
35  * single-element sorted set.
36  *
37  * @author Jared Levy
38  * @author Louis Wasserman
39  */
40 @GwtCompatible(serializable = true, emulated = true)
41 @SuppressWarnings({"serial", "rawtypes"})
42 final class RegularImmutableSortedSet<E> extends ImmutableSortedSet<E> {
43   static final RegularImmutableSortedSet<Comparable> NATURAL_EMPTY_SET =
44       new RegularImmutableSortedSet<>(ImmutableList.<Comparable>of(), Ordering.natural());
45 
46   private final transient ImmutableList<E> elements;
47 
48   RegularImmutableSortedSet(ImmutableList<E> elements, Comparator<? super E> comparator) {
49     super(comparator);
50     this.elements = elements;
51   }
52 
53   @Override
54   Object[] internalArray() {
55     return elements.internalArray();
56   }
57 
58   @Override
59   int internalArrayStart() {
60     return elements.internalArrayStart();
61   }
62 
63   @Override
64   int internalArrayEnd() {
65     return elements.internalArrayEnd();
66   }
67 
68   @Override
69   public UnmodifiableIterator<E> iterator() {
70     return elements.iterator();
71   }
72 
73   @GwtIncompatible // NavigableSet
74   @Override
75   public UnmodifiableIterator<E> descendingIterator() {
76     return elements.reverse().iterator();
77   }
78 
79   @Override
80   public Spliterator<E> spliterator() {
81     return asList().spliterator();
82   }
83 
84   @Override
85   public void forEach(Consumer<? super E> action) {
86     elements.forEach(action);
87   }
88 
89   @Override
90   public int size() {
91     return elements.size();
92   }
93 
94   @Override
95   public boolean contains(@Nullable Object o) {
96     try {
97       return o != null && unsafeBinarySearch(o) >= 0;
98     } catch (ClassCastException e) {
99       return false;
100     }
101   }
102 
103   @Override
104   public boolean containsAll(Collection<?> targets) {
105     // TODO(jlevy): For optimal performance, use a binary search when
106     // targets.size() < size() / log(size())
107     // TODO(kevinb): see if we can share code with OrderedIterator after it
108     // graduates from labs.
109     if (targets instanceof Multiset) {
110       targets = ((Multiset<?>) targets).elementSet();
111     }
112     if (!SortedIterables.hasSameComparator(comparator(), targets) || (targets.size() <= 1)) {
113       return super.containsAll(targets);
114     }
115 
116     /*
117      * If targets is a sorted set with the same comparator, containsAll can run
118      * in O(n) time stepping through the two collections.
119      */
120     Iterator<E> thisIterator = iterator();
121 
122     Iterator<?> thatIterator = targets.iterator();
123     // known nonempty since we checked targets.size() > 1
124 
125     if (!thisIterator.hasNext()) {
126       return false;
127     }
128 
129     Object target = thatIterator.next();
130     E current = thisIterator.next();
131     try {
132       while (true) {
133         int cmp = unsafeCompare(current, target);
134 
135         if (cmp < 0) {
136           if (!thisIterator.hasNext()) {
137             return false;
138           }
139           current = thisIterator.next();
140         } else if (cmp == 0) {
141           if (!thatIterator.hasNext()) {
142             return true;
143           }
144           target = thatIterator.next();
145 
146         } else if (cmp > 0) {
147           return false;
148         }
149       }
150     } catch (NullPointerException | ClassCastException e) {
151       return false;
152     }
153   }
154 
155   private int unsafeBinarySearch(Object key) throws ClassCastException {
156     return Collections.binarySearch(elements, key, unsafeComparator());
157   }
158 
159   @Override
160   boolean isPartialView() {
161     return elements.isPartialView();
162   }
163 
164   @Override
165   int copyIntoArray(Object[] dst, int offset) {
166     return elements.copyIntoArray(dst, offset);
167   }
168 
169   @Override
170   public boolean equals(@Nullable Object object) {
171     if (object == this) {
172       return true;
173     }
174     if (!(object instanceof Set)) {
175       return false;
176     }
177 
178     Set<?> that = (Set<?>) object;
179     if (size() != that.size()) {
180       return false;
181     } else if (isEmpty()) {
182       return true;
183     }
184 
185     if (SortedIterables.hasSameComparator(comparator, that)) {
186       Iterator<?> otherIterator = that.iterator();
187       try {
188         Iterator<E> iterator = iterator();
189         while (iterator.hasNext()) {
190           Object element = iterator.next();
191           Object otherElement = otherIterator.next();
192           if (otherElement == null || unsafeCompare(element, otherElement) != 0) {
193             return false;
194           }
195         }
196         return true;
197       } catch (ClassCastException e) {
198         return false;
199       } catch (NoSuchElementException e) {
200         return false; // concurrent change to other set
201       }
202     }
203     return containsAll(that);
204   }
205 
206   @Override
207   public E first() {
208     if (isEmpty()) {
209       throw new NoSuchElementException();
210     }
211     return elements.get(0);
212   }
213 
214   @Override
215   public E last() {
216     if (isEmpty()) {
217       throw new NoSuchElementException();
218     }
219     return elements.get(size() - 1);
220   }
221 
222   @Override
223   public E lower(E element) {
224     int index = headIndex(element, false) - 1;
225     return (index == -1) ? null : elements.get(index);
226   }
227 
228   @Override
229   public E floor(E element) {
230     int index = headIndex(element, true) - 1;
231     return (index == -1) ? null : elements.get(index);
232   }
233 
234   @Override
235   public E ceiling(E element) {
236     int index = tailIndex(element, true);
237     return (index == size()) ? null : elements.get(index);
238   }
239 
240   @Override
241   public E higher(E element) {
242     int index = tailIndex(element, false);
243     return (index == size()) ? null : elements.get(index);
244   }
245 
246   @Override
247   ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive) {
248     return getSubSet(0, headIndex(toElement, inclusive));
249   }
250 
251   int headIndex(E toElement, boolean inclusive) {
252     int index = Collections.binarySearch(elements, checkNotNull(toElement), comparator());
253     if (index >= 0) {
254       return inclusive ? index + 1 : index;
255     } else {
256       return ~index;
257     }
258   }
259 
260   @Override
261   ImmutableSortedSet<E> subSetImpl(
262       E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
263     return tailSetImpl(fromElement, fromInclusive).headSetImpl(toElement, toInclusive);
264   }
265 
266   @Override
267   ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive) {
268     return getSubSet(tailIndex(fromElement, inclusive), size());
269   }
270 
271   int tailIndex(E fromElement, boolean inclusive) {
272     int index = Collections.binarySearch(elements, checkNotNull(fromElement), comparator());
273     if (index >= 0) {
274       return inclusive ? index : index + 1;
275     } else {
276       return ~index;
277     }
278   }
279 
280   // Pretend the comparator can compare anything. If it turns out it can't
281   // compare two elements, it'll throw a CCE. Only methods that are specified to
282   // throw CCE should call this.
283   @SuppressWarnings("unchecked")
284   Comparator<Object> unsafeComparator() {
285     return (Comparator<Object>) comparator;
286   }
287 
288   RegularImmutableSortedSet<E> getSubSet(int newFromIndex, int newToIndex) {
289     if (newFromIndex == 0 && newToIndex == size()) {
290       return this;
291     } else if (newFromIndex < newToIndex) {
292       return new RegularImmutableSortedSet<E>(
293           elements.subList(newFromIndex, newToIndex), comparator);
294     } else {
295       return emptySet(comparator);
296     }
297   }
298 
299   @Override
300   int indexOf(@Nullable Object target) {
301     if (target == null) {
302       return -1;
303     }
304     int position;
305     try {
306       position = Collections.binarySearch(elements, target, unsafeComparator());
307     } catch (ClassCastException e) {
308       return -1;
309     }
310     return (position >= 0) ? position : -1;
311   }
312 
313   @Override
314   ImmutableList<E> createAsList() {
315     return (size() <= 1) ? elements : new ImmutableSortedAsList<E>(this, elements);
316   }
317 
318   @Override
319   ImmutableSortedSet<E> createDescendingSet() {
320     Comparator<? super E> reversedOrder = Collections.reverseOrder(comparator);
321     return isEmpty()
322         ? emptySet(reversedOrder)
323         : new RegularImmutableSortedSet<E>(elements.reverse(), reversedOrder);
324   }
325 }