SmartList implements RandomAccess
[idea/community.git] / platform / util / src / com / intellij / util / SmartList.java
1 /*
2  * Copyright 2000-2014 JetBrains s.r.o.
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 package com.intellij.util;
17
18 import com.intellij.util.containers.EmptyIterator;
19 import com.intellij.util.containers.SingletonIteratorBase;
20 import org.jetbrains.annotations.NotNull;
21
22 import java.lang.reflect.Array;
23 import java.util.*;
24
25 /**
26  * A List which is optimised for the sizes of 0 and 1,
27  * in which cases it would not allocate array at all.
28  */
29 @SuppressWarnings({"unchecked"})
30 public class SmartList<E> extends AbstractList<E> implements RandomAccess {
31   private int mySize = 0;
32   private Object myElem = null; // null if mySize==0, (E)elem if mySize==1, Object[] if mySize>=2
33
34   public SmartList() { }
35
36   public SmartList(E element) {
37     add(element);
38   }
39
40   public SmartList(@NotNull Collection<? extends E> elements) {
41     int size = elements.size();
42     if (size == 1) {
43       E element = elements instanceof List ? (E)((List)elements).get(0) : elements.iterator().next();
44       add(element);
45     }
46     else if (size > 0) {
47       mySize = size;
48       myElem = elements.toArray(new Object[size]);
49     }
50   }
51
52   public SmartList(@NotNull E... elements) {
53     if (elements.length == 1) {
54       add(elements[0]);
55     }
56     else if (elements.length > 0) {
57       mySize = elements.length;
58       myElem = Arrays.copyOf(elements, mySize);
59     }
60   }
61
62   @Override
63   public E get(int index) {
64     if (index < 0 || index >= mySize) {
65       throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + mySize);
66     }
67     if (mySize == 1) {
68       return (E)myElem;
69     }
70     return (E)((Object[])myElem)[index];
71   }
72
73   @Override
74   public boolean add(E e) {
75     if (mySize == 0) {
76       myElem = e;
77     }
78     else if (mySize == 1) {
79       Object[] array = new Object[2];
80       array[0] = myElem;
81       array[1] = e;
82       myElem = array;
83     }
84     else {
85       Object[] array = (Object[])myElem;
86       int oldCapacity = array.length;
87       if (mySize >= oldCapacity) {
88         // have to resize
89         int newCapacity = oldCapacity * 3 / 2 + 1;
90         int minCapacity = mySize + 1;
91         if (newCapacity < minCapacity) {
92           newCapacity = minCapacity;
93         }
94         Object[] oldArray = array;
95         myElem = array = new Object[newCapacity];
96         System.arraycopy(oldArray, 0, array, 0, oldCapacity);
97       }
98       array[mySize] = e;
99     }
100
101     mySize++;
102     modCount++;
103     return true;
104   }
105
106   @Override
107   public void add(int index, E e) {
108     if (index < 0 || index > mySize) {
109       throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + mySize);
110     }
111
112     if (mySize == 0) {
113       myElem = e;
114     }
115     else if (mySize == 1 && index == 0) {
116       Object[] array = new Object[2];
117       array[0] = e;
118       array[1] = myElem;
119       myElem = array;
120     }
121     else {
122       Object[] array = new Object[mySize + 1];
123       if (mySize == 1) {
124         array[0] = myElem; // index == 1
125       }
126       else {
127         Object[] oldArray = (Object[])myElem;
128         System.arraycopy(oldArray, 0, array, 0, index);
129         System.arraycopy(oldArray, index, array, index + 1, mySize - index);
130       }
131       array[index] = e;
132       myElem = array;
133     }
134
135     mySize++;
136     modCount++;
137   }
138
139   @Override
140   public int size() {
141     return mySize;
142   }
143
144   @Override
145   public void clear() {
146     myElem = null;
147     mySize = 0;
148     modCount++;
149   }
150
151   @Override
152   public E set(final int index, final E element) {
153     if (index < 0 || index >= mySize) {
154       throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + mySize);
155     }
156
157     final E oldValue;
158     if (mySize == 1) {
159       oldValue = (E)myElem;
160       myElem = element;
161     }
162     else {
163       final Object[] array = (Object[])myElem;
164       oldValue = (E)array[index];
165       array[index] = element;
166     }
167     return oldValue;
168   }
169
170   @Override
171   public E remove(final int index) {
172     if (index < 0 || index >= mySize) {
173       throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + mySize);
174     }
175
176     final E oldValue;
177     if (mySize == 1) {
178       oldValue = (E)myElem;
179       myElem = null;
180     }
181     else {
182       Object[] array = (Object[])myElem;
183       oldValue = (E)array[index];
184
185       if (mySize == 2) {
186         myElem = array[1 - index];
187       }
188       else {
189         int numMoved = mySize - index - 1;
190         if (numMoved > 0) {
191           System.arraycopy(array, index + 1, array, index, numMoved);
192         }
193         array[mySize - 1] = null;
194       }
195     }
196     mySize--;
197     modCount++;
198     return oldValue;
199   }
200
201   @NotNull
202   @Override
203   public Iterator<E> iterator() {
204     if (mySize == 0) {
205       return EmptyIterator.getInstance();
206     }
207     if (mySize == 1) {
208       return new SingletonIterator();
209     }
210     return super.iterator();
211   }
212
213   private class SingletonIterator extends SingletonIteratorBase<E> {
214     private final int myInitialModCount;
215
216     public SingletonIterator() {
217       myInitialModCount = modCount;
218     }
219
220     @Override
221     protected E getElement() {
222       return (E)myElem;
223     }
224
225     @Override
226     protected void checkCoModification() {
227       if (modCount != myInitialModCount) {
228         throw new ConcurrentModificationException("ModCount: " + modCount + "; expected: " + myInitialModCount);
229       }
230     }
231
232     @Override
233     public void remove() {
234       checkCoModification();
235       clear();
236     }
237   }
238
239   public void sort(Comparator<? super E> comparator) {
240     if (mySize >= 2) {
241       Arrays.sort((E[])myElem, 0, mySize, comparator);
242     }
243   }
244
245   public int getModificationCount() {
246     return modCount;
247   }
248
249   @NotNull
250   @Override
251   public <T> T[] toArray(@NotNull T[] a) {
252     int aLength = a.length;
253     if (mySize == 1) {
254       if (aLength != 0) {
255         a[0] = (T)myElem;
256       }
257       else {
258         T[] r = (T[])Array.newInstance(a.getClass().getComponentType(), 1);
259         r[0] = (T)myElem;
260         return r;
261       }
262     }
263     else if (aLength < mySize) {
264       return (T[])Arrays.copyOf((E[])myElem, mySize, a.getClass());
265     }
266     else if (mySize != 0) {
267       //noinspection SuspiciousSystemArraycopy
268       System.arraycopy(myElem, 0, a, 0, mySize);
269     }
270
271     if (aLength > mySize) {
272       a[mySize] = null;
273     }
274     return a;
275   }
276
277   /**
278    * Trims the capacity of this list to be the
279    * list's current size.  An application can use this operation to minimize
280    * the storage of a list instance.
281    */
282   public void trimToSize() {
283     if (mySize < 2) return;
284     Object[] array = (Object[])myElem;
285     int oldCapacity = array.length;
286     if (mySize < oldCapacity) {
287       modCount++;
288       myElem = Arrays.copyOf(array, mySize);
289     }
290   }
291 }