1 /*
2  * Copyright (C) 2013, 2014 Brett Wooldridge
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.zaxxer.hikari.util;
18
19 import java.io.Serializable;
20 import java.lang.reflect.Array;
21 import java.util.Collection;
22 import java.util.Comparator;
23 import java.util.Iterator;
24 import java.util.List;
25 import java.util.ListIterator;
26 import java.util.NoSuchElementException;
27 import java.util.RandomAccess;
28 import java.util.Spliterator;
29 import java.util.function.Consumer;
30 import java.util.function.Predicate;
31 import java.util.function.UnaryOperator;
32
33 /**
34  * Fast list without range checking.
35  *
36  * @author Brett Wooldridge
37  */
38 public final class FastList<T> implements List<T>, RandomAccess, Serializable
39 {
40    private static final long serialVersionUID = -4598088075242913858L;
41
42    private final Class<?> clazz;
43    private T[] elementData;
44    private int size;
45
46    /**
47     * Construct a FastList with a default size of 32.
48     * @param clazz the Class stored in the collection
49     */
50    @SuppressWarnings("unchecked")
51    public FastList(Class<?> clazz)
52    {
53       this.elementData = (T[]) Array.newInstance(clazz, 32);
54       this.clazz = clazz;
55    }
56
57    /**
58     * Construct a FastList with a specified size.
59     * @param clazz the Class stored in the collection
60     * @param capacity the initial size of the FastList
61     */
62    @SuppressWarnings("unchecked")
63    public FastList(Class<?> clazz, int capacity)
64    {
65       this.elementData = (T[]) Array.newInstance(clazz, capacity);
66       this.clazz = clazz;
67    }
68
69    /**
70     * Add an element to the tail of the FastList.
71     *
72     * @param element the element to add
73     */
74    @Override
75    public boolean add(T element)
76    {
77       if (size < elementData.length) {
78          elementData[size++] = element;
79       }
80       else {
81          // overflow-conscious code
82          final int oldCapacity = elementData.length;
83          final int newCapacity = oldCapacity << 1;
84          @SuppressWarnings("unchecked")
85          final T[] newElementData = (T[]) Array.newInstance(clazz, newCapacity);
86          System.arraycopy(elementData, 0, newElementData, 0, oldCapacity);
87          newElementData[size++] = element;
88          elementData = newElementData;
89       }
90
91       return true;
92    }
93
94    /**
95     * Get the element at the specified index.
96     *
97     * @param index the index of the element to get
98     * @return the element, or ArrayIndexOutOfBounds is thrown if the index is invalid
99     */
100    @Override
101    public T get(int index)
102    {
103       return elementData[index];
104    }
105
106    /**
107     * Remove the last element from the list.  No bound check is performed, so if this
108     * method is called on an empty list and ArrayIndexOutOfBounds exception will be
109     * thrown.
110     *
111     * @return the last element of the list
112     */
113    public T removeLast()
114    {
115       T element = elementData[--size];
116       elementData[size] = null;
117       return element;
118    }
119
120    /**
121     * This remove method is most efficient when the element being removed
122     * is the last element.  Equality is identity based, not equals() based.
123     * Only the first matching element is removed.
124     *
125     * @param element the element to remove
126     */
127    @Override
128    public boolean remove(Object element)
129    {
130       for (int index = size - 1; index >= 0; index--) {
131          if (element == elementData[index]) {
132             final int numMoved = size - index - 1;
133             if (numMoved > 0) {
134                System.arraycopy(elementData, index + 1, elementData, index, numMoved);
135             }
136             elementData[--size] = null;
137             return true;
138          }
139       }
140
141       return false;
142    }
143
144    /**
145     * Clear the FastList.
146     */
147    @Override
148    public void clear()
149    {
150       for (int i = 0; i < size; i++) {
151          elementData[i] = null;
152       }
153
154       size = 0;
155    }
156
157    /**
158     * Get the current number of elements in the FastList.
159     *
160     * @return the number of current elements
161     */
162    @Override
163    public int size()
164    {
165       return size;
166    }
167
168    /** {@inheritDoc} */
169    @Override
170    public boolean isEmpty()
171    {
172       return size == 0;
173    }
174
175    /** {@inheritDoc} */
176    @Override
177    public T set(int index, T element)
178    {
179       T old = elementData[index];
180       elementData[index] = element;
181       return old;
182    }
183
184    /** {@inheritDoc} */
185    @Override
186    public T remove(int index)
187    {
188       if (size == 0) {
189          return null;
190       }
191
192       final T old = elementData[index];
193
194       final int numMoved = size - index - 1;
195       if (numMoved > 0) {
196          System.arraycopy(elementData, index + 1, elementData, index, numMoved);
197       }
198
199       elementData[--size] = null;
200
201       return old;
202    }
203
204    /** {@inheritDoc} */
205    @Override
206    public boolean contains(Object o)
207    {
208       throw new UnsupportedOperationException();
209    }
210
211    /** {@inheritDoc} */
212    @Override
213    public Iterator<T> iterator()
214    {
215       return new Iterator<T>() {
216          private int index;
217
218          @Override
219          public boolean hasNext()
220          {
221             return index < size;
222          }
223
224          @Override
225          public T next()
226          {
227             if (index < size) {
228                return elementData[index++];
229             }
230
231             throw new NoSuchElementException("No more elements in FastList"); 
232          }
233       };
234    }
235
236    /** {@inheritDoc} */
237    @Override
238    public Object[] toArray()
239    {
240       throw new UnsupportedOperationException();
241    }
242
243    /** {@inheritDoc} */
244    @Override
245    public <E> E[] toArray(E[] a)
246    {
247       throw new UnsupportedOperationException();
248    }
249
250    /** {@inheritDoc} */
251    @Override
252    public boolean containsAll(Collection<?> c)
253    {
254       throw new UnsupportedOperationException();
255    }
256
257    /** {@inheritDoc} */
258    @Override
259    public boolean addAll(Collection<? extends T> c)
260    {
261       throw new UnsupportedOperationException();
262    }
263
264    /** {@inheritDoc} */
265    @Override
266    public boolean addAll(int index, Collection<? extends T> c)
267    {
268       throw new UnsupportedOperationException();
269    }
270
271    /** {@inheritDoc} */
272    @Override
273    public boolean removeAll(Collection<?> c)
274    {
275       throw new UnsupportedOperationException();
276    }
277
278    /** {@inheritDoc} */
279    @Override
280    public boolean retainAll(Collection<?> c)
281    {
282       throw new UnsupportedOperationException();
283    }
284
285    /** {@inheritDoc} */
286    @Override
287    public void add(int index, T element)
288    {
289       throw new UnsupportedOperationException();
290    }
291
292    /** {@inheritDoc} */
293    @Override
294    public int indexOf(Object o)
295    {
296       throw new UnsupportedOperationException();
297    }
298
299    /** {@inheritDoc} */
300    @Override
301    public int lastIndexOf(Object o)
302    {
303       throw new UnsupportedOperationException();
304    }
305
306    /** {@inheritDoc} */
307    @Override
308    public ListIterator<T> listIterator()
309    {
310       throw new UnsupportedOperationException();
311    }
312
313    /** {@inheritDoc} */
314    @Override
315    public ListIterator<T> listIterator(int index)
316    {
317       throw new UnsupportedOperationException();
318    }
319
320    /** {@inheritDoc} */
321    @Override
322    public List<T> subList(int fromIndex, int toIndex)
323    {
324       throw new UnsupportedOperationException();
325    }
326
327    /** {@inheritDoc} */
328    @Override
329    public Object clone()
330    {
331       throw new UnsupportedOperationException();
332    }
333
334    /** {@inheritDoc} */
335    @Override
336    public void forEach(Consumer<? super T> action)
337    {
338       throw new UnsupportedOperationException();
339    }
340
341    /** {@inheritDoc} */
342    @Override
343    public Spliterator<T> spliterator()
344    {
345       throw new UnsupportedOperationException();
346    }
347
348    /** {@inheritDoc} */
349    @Override
350    public boolean removeIf(Predicate<? super T> filter)
351    {
352       throw new UnsupportedOperationException();
353    }
354
355    /** {@inheritDoc} */
356    @Override
357    public void replaceAll(UnaryOperator<T> operator)
358    {
359       throw new UnsupportedOperationException();
360    }
361
362    /** {@inheritDoc} */
363    @Override
364    public void sort(Comparator<? super T> c)
365    {
366       throw new UnsupportedOperationException();
367    }
368 }
369