1/*
2 * Copyright (C) 2009 Google Inc.
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;
20
21import java.util.Collection;
22import java.util.Comparator;
23import java.util.Iterator;
24import java.util.NoSuchElementException;
25import java.util.Set;
26
27import javax.annotation.Nullable;
28
29/**
30 * An immutable sorted set with one or more elements.
31 * TODO: Consider creating a separate class for a single-element sorted set.
32 *
33 * @author Jared Levy
34 */
35@GwtCompatible(serializable = true)
36@SuppressWarnings("serial")
37final class RegularImmutableSortedSet<E>
38    extends ImmutableSortedSet<E> {
39
40  private final Object[] elements;
41  /**
42   * The index of the first element that's in the sorted set (inclusive
43   * index).
44   */
45  private final int fromIndex;
46  /**
47   * The index after the last element that's in the sorted set (exclusive
48   * index).
49   */
50  private final int toIndex;
51
52  RegularImmutableSortedSet(Object[] elements,
53      Comparator<? super E> comparator) {
54    super(comparator);
55    this.elements = elements;
56    this.fromIndex = 0;
57    this.toIndex = elements.length;
58  }
59
60  RegularImmutableSortedSet(Object[] elements,
61      Comparator<? super E> comparator, int fromIndex, int toIndex) {
62    super(comparator);
63    this.elements = elements;
64    this.fromIndex = fromIndex;
65    this.toIndex = toIndex;
66  }
67
68  // The factory methods ensure that every element is an E.
69  @SuppressWarnings("unchecked")
70  @Override public UnmodifiableIterator<E> iterator() {
71    return (UnmodifiableIterator<E>)
72        Iterators.forArray(elements, fromIndex, size());
73  }
74
75  @Override public boolean isEmpty() {
76    return false;
77  }
78
79  public int size() {
80    return toIndex - fromIndex;
81  }
82
83  @Override public boolean contains(Object o) {
84    if (o == null) {
85      return false;
86    }
87    try {
88      return binarySearch(o) >= 0;
89    } catch (ClassCastException e) {
90      return false;
91    }
92  }
93
94  @Override public boolean containsAll(Collection<?> targets) {
95    // TODO: For optimal performance, use a binary search when
96    // targets.size() < size() / log(size())
97    if (!hasSameComparator(targets, comparator()) || (targets.size() <= 1)) {
98      return super.containsAll(targets);
99    }
100
101    /*
102     * If targets is a sorted set with the same comparator, containsAll can
103     * run in O(n) time stepping through the two collections.
104     */
105    int i = fromIndex;
106    Iterator<?> iterator = targets.iterator();
107    Object target = iterator.next();
108
109    while (true) {
110      if (i >= toIndex) {
111        return false;
112      }
113
114      int cmp = unsafeCompare(elements[i], target);
115
116      if (cmp < 0) {
117        i++;
118      } else if (cmp == 0) {
119        if (!iterator.hasNext()) {
120          return true;
121        }
122        target = iterator.next();
123        i++;
124      } else if (cmp > 0) {
125        return false;
126      }
127    }
128  }
129
130  private int binarySearch(Object key) {
131    int lower = fromIndex;
132    int upper = toIndex - 1;
133
134    while (lower <= upper) {
135      int middle = lower + (upper - lower) / 2;
136      int c = unsafeCompare(key, elements[middle]);
137      if (c < 0) {
138        upper = middle - 1;
139      } else if (c > 0) {
140        lower = middle + 1;
141      } else {
142        return middle;
143      }
144    }
145
146    return -lower - 1;
147  }
148
149  @Override public Object[] toArray() {
150    Object[] array = new Object[size()];
151    Platform.unsafeArrayCopy(elements, fromIndex, array, 0, size());
152    return array;
153  }
154
155  // TODO: Move to ObjectArrays (same code in ImmutableList).
156  @Override public <T> T[] toArray(T[] array) {
157    int size = size();
158    if (array.length < size) {
159      array = ObjectArrays.newArray(array, size);
160    } else if (array.length > size) {
161      array[size] = null;
162    }
163    Platform.unsafeArrayCopy(elements, fromIndex, array, 0, size);
164    return array;
165  }
166
167  @Override public boolean equals(@Nullable Object object) {
168    if (object == this) {
169      return true;
170    }
171    if (!(object instanceof Set)) {
172      return false;
173    }
174
175    Set<?> that = (Set<?>) object;
176    if (size() != that.size()) {
177      return false;
178    }
179
180    if (hasSameComparator(that, comparator)) {
181      Iterator<?> iterator = that.iterator();
182      try {
183        for (int i = fromIndex; i < toIndex; i++) {
184          Object otherElement = iterator.next();
185          if (otherElement == null
186              || unsafeCompare(elements[i], otherElement) != 0) {
187            return false;
188          }
189        }
190        return true;
191      } catch (ClassCastException e) {
192        return false;
193      } catch (NoSuchElementException e) {
194        return false; // concurrent change to other set
195      }
196    }
197    return this.containsAll(that);
198  }
199
200  @Override public int hashCode() {
201    // not caching hash code since it could change if the elements are mutable
202    // in a way that modifies their hash codes
203    int hash = 0;
204    for (int i = fromIndex; i < toIndex; i++) {
205      hash += elements[i].hashCode();
206    }
207    return hash;
208  }
209
210  // The factory methods ensure that every element is an E.
211  @SuppressWarnings("unchecked")
212  public E first() {
213    return (E) elements[fromIndex];
214  }
215
216  // The factory methods ensure that every element is an E.
217  @SuppressWarnings("unchecked")
218  public E last() {
219    return (E) elements[toIndex - 1];
220  }
221
222  @Override ImmutableSortedSet<E> headSetImpl(E toElement) {
223    return createSubset(fromIndex, findSubsetIndex(toElement));
224  }
225
226  @Override ImmutableSortedSet<E> subSetImpl(E fromElement, E toElement) {
227    return createSubset(
228        findSubsetIndex(fromElement), findSubsetIndex(toElement));
229  }
230
231  @Override ImmutableSortedSet<E> tailSetImpl(E fromElement) {
232    return createSubset(findSubsetIndex(fromElement), toIndex);
233  }
234
235  private int findSubsetIndex(E element) {
236    int index = binarySearch(element);
237    return (index >= 0) ? index : (-index - 1);
238  }
239
240  private ImmutableSortedSet<E> createSubset(
241      int newFromIndex, int newToIndex) {
242    if (newFromIndex < newToIndex) {
243      return new RegularImmutableSortedSet<E>(elements, comparator,
244          newFromIndex, newToIndex);
245    } else {
246      return emptySet(comparator);
247    }
248  }
249
250  @Override boolean hasPartialArray() {
251    return (fromIndex != 0) || (toIndex != elements.length);
252  }
253
254  @Override int indexOf(Object target) {
255    if (target == null) {
256      return -1;
257    }
258    int position;
259    try {
260      position = binarySearch(target);
261    } catch (ClassCastException e) {
262      return -1;
263    }
264    // The equals() check is needed when the comparator isn't compatible with
265    // equals().
266    return (position >= 0 && elements[position].equals(target))
267        ? position - fromIndex : -1;
268  }
269
270  @Override ImmutableList<E> createAsList() {
271    return new ImmutableSortedAsList<E>(elements, fromIndex, size(), this);
272  }
273}
274