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
17package com.google.common.collect;
18
19import static com.google.common.base.Preconditions.checkArgument;
20import static com.google.common.base.Preconditions.checkNotNull;
21import static com.google.common.collect.SortedLists.KeyAbsentBehavior.INVERTED_INSERTION_INDEX;
22import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_HIGHER;
23import static com.google.common.collect.SortedLists.KeyPresentBehavior.ANY_PRESENT;
24import static com.google.common.collect.SortedLists.KeyPresentBehavior.FIRST_AFTER;
25import static com.google.common.collect.SortedLists.KeyPresentBehavior.FIRST_PRESENT;
26
27import com.google.common.annotations.GwtCompatible;
28
29import java.util.Collection;
30import java.util.Collections;
31import java.util.Comparator;
32import java.util.Iterator;
33import java.util.NoSuchElementException;
34import java.util.Set;
35
36import javax.annotation.Nullable;
37
38/**
39 * An immutable sorted set with one or more elements. TODO(jlevy): Consider
40 * separate class for a single-element sorted set.
41 *
42 * @author Jared Levy
43 * @author Louis Wasserman
44 */
45@GwtCompatible(serializable = true, emulated = true)
46@SuppressWarnings("serial")
47final class RegularImmutableSortedSet<E> extends ImmutableSortedSet<E> {
48
49  private transient final ImmutableList<E> elements;
50
51  RegularImmutableSortedSet(
52      ImmutableList<E> elements, Comparator<? super E> comparator) {
53    super(comparator);
54    this.elements = elements;
55    checkArgument(!elements.isEmpty());
56  }
57
58  @Override public UnmodifiableIterator<E> iterator() {
59    return elements.iterator();
60  }
61
62  @Override public boolean isEmpty() {
63    return false;
64  }
65
66  @Override
67  public int size() {
68    return elements.size();
69  }
70
71  @Override public boolean contains(Object o) {
72    if (o == null) {
73      return false;
74    }
75    try {
76      return binarySearch(o) >= 0;
77    } catch (ClassCastException e) {
78      return false;
79    }
80  }
81
82  @Override public boolean containsAll(Collection<?> targets) {
83    // TODO(jlevy): For optimal performance, use a binary search when
84    // targets.size() < size() / log(size())
85    // TODO(kevinb): see if we can share code with OrderedIterator after it
86    // graduates from labs.
87    if (!SortedIterables.hasSameComparator(comparator(), targets)
88        || (targets.size() <= 1)) {
89      return super.containsAll(targets);
90    }
91
92    /*
93     * If targets is a sorted set with the same comparator, containsAll can run
94     * in O(n) time stepping through the two collections.
95     */
96    Iterator<E> thisIterator = iterator();
97    Iterator<?> thatIterator = targets.iterator();
98    Object target = thatIterator.next();
99
100    try {
101
102      while (thisIterator.hasNext()) {
103
104        int cmp = unsafeCompare(thisIterator.next(), target);
105
106        if (cmp == 0) {
107
108          if (!thatIterator.hasNext()) {
109
110            return true;
111          }
112
113          target = thatIterator.next();
114
115        } else if (cmp > 0) {
116          return false;
117        }
118      }
119    } catch (NullPointerException e) {
120      return false;
121    } catch (ClassCastException e) {
122      return false;
123    }
124
125    return false;
126  }
127
128  private int binarySearch(Object key) {
129    // TODO(kevinb): split this into binarySearch(E) and
130    // unsafeBinarySearch(Object), use each appropriately. name all methods that
131    // might throw CCE "unsafe*".
132
133    // Pretend the comparator can compare anything. If it turns out it can't
134    // compare a and b, we should get a CCE on the subsequent line. Only methods
135    // that are spec'd to throw CCE should call this.
136    @SuppressWarnings("unchecked")
137    Comparator<Object> unsafeComparator = (Comparator<Object>) comparator;
138
139    return Collections.binarySearch(elements, key, unsafeComparator);
140  }
141
142  @Override boolean isPartialView() {
143    return elements.isPartialView();
144  }
145
146  @Override public Object[] toArray() {
147    return elements.toArray();
148  }
149
150  @Override public <T> T[] toArray(T[] array) {
151    return elements.toArray(array);
152  }
153
154  @Override public boolean equals(@Nullable Object object) {
155    if (object == this) {
156      return true;
157    }
158    if (!(object instanceof Set)) {
159      return false;
160    }
161
162    Set<?> that = (Set<?>) object;
163    if (size() != that.size()) {
164      return false;
165    }
166
167    if (SortedIterables.hasSameComparator(comparator, that)) {
168      Iterator<?> otherIterator = that.iterator();
169      try {
170        Iterator<E> iterator = iterator();
171        while (iterator.hasNext()) {
172          Object element = iterator.next();
173          Object otherElement = otherIterator.next();
174          if (otherElement == null
175              || unsafeCompare(element, otherElement) != 0) {
176            return false;
177          }
178        }
179        return true;
180      } catch (ClassCastException e) {
181        return false;
182      } catch (NoSuchElementException e) {
183        return false; // concurrent change to other set
184      }
185    }
186    return this.containsAll(that);
187  }
188
189  @Override
190  public E first() {
191    return elements.get(0);
192  }
193
194  @Override
195  public E last() {
196    return elements.get(size() - 1);
197  }
198
199  @Override
200  ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive) {
201    int index;
202    if (inclusive) {
203      index = SortedLists.binarySearch(
204          elements, checkNotNull(toElement), comparator(), FIRST_AFTER, NEXT_HIGHER);
205    } else {
206      index = SortedLists.binarySearch(
207          elements, checkNotNull(toElement), comparator(), FIRST_PRESENT, NEXT_HIGHER);
208    }
209    return createSubset(0, index);
210  }
211
212  @Override
213  ImmutableSortedSet<E> subSetImpl(
214      E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
215    return tailSetImpl(fromElement, fromInclusive)
216        .headSetImpl(toElement, toInclusive);
217  }
218
219  @Override
220  ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive) {
221    int index;
222    if (inclusive) {
223      index = SortedLists.binarySearch(
224          elements, checkNotNull(fromElement), comparator(), FIRST_PRESENT, NEXT_HIGHER);
225    } else {
226      index = SortedLists.binarySearch(
227          elements, checkNotNull(fromElement), comparator(), FIRST_AFTER, NEXT_HIGHER);
228    }
229    return createSubset(index, size());
230  }
231
232  // Pretend the comparator can compare anything. If it turns out it can't
233  // compare two elements, it'll throw a CCE. Only methods that are specified to
234  // throw CCE should call this.
235  @SuppressWarnings("unchecked")
236  Comparator<Object> unsafeComparator() {
237    return (Comparator<Object>) comparator;
238  }
239
240  private ImmutableSortedSet<E> createSubset(int newFromIndex, int newToIndex) {
241    if (newFromIndex == 0 && newToIndex == size()) {
242      return this;
243    } else if (newFromIndex < newToIndex) {
244      return new RegularImmutableSortedSet<E>(
245          elements.subList(newFromIndex, newToIndex), comparator);
246    } else {
247      return emptySet(comparator);
248    }
249  }
250
251  @SuppressWarnings("unchecked")
252  @Override int indexOf(@Nullable Object target) {
253    if (target == null) {
254      return -1;
255    }
256    int position;
257    try {
258      position = SortedLists.binarySearch(elements, (E) target, comparator(),
259          ANY_PRESENT, INVERTED_INSERTION_INDEX);
260    } catch (ClassCastException e) {
261      return -1;
262    }
263    // TODO(kevinb): reconsider if it's really worth making feeble attempts at
264    // sanity for inconsistent comparators.
265
266    // The equals() check is needed when the comparator isn't compatible with
267    // equals().
268    return (position >= 0 && elements.get(position).equals(target))
269        ? position : -1;
270  }
271
272  @Override ImmutableList<E> createAsList() {
273    return new ImmutableSortedAsList<E>(this, elements);
274  }
275}
276