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