CircularArrayList - list with fast remove/add at both ends; not synchronized; broken? [1013598]

sclass CircularArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
  private transient Object[] elementData;
  private int size;
  private int head;
  private int tail;
  
  *(int initialCapacity) {
  	if (initialCapacity < 0) {
  		throw new IllegalArgumentException(
  				"Illegal Capacity: " + initialCapacity);
  	}
  
  	elementData = new Object[initialCapacity];
  	size = tail = head = 0;
  }
  
  *() { this(10); }
  
  *(Collection<? extends E> c) {
  	elementData = c.toArray();
  	tail = 0;
  	size = head = elementData.length;
  
  	// c.toArray might (incorrectly) not return Object[] (see 6260652)
  	if (elementData.getClass() != Object[].class)
  		elementData = Arrays.copyOf(elementData, size, Object[].class);
  }
  
  private void copy(Object[] src, Object[] dest) {
  	System.arraycopy(src, 0, dest, 0, head);
  	System.arraycopy(src, src.length + tail, 
  			dest, dest.length + tail, -tail);
  }
  
  private void ensureCapacityInternal(int minCapacity) {
  	modCount++;
  
  	// overflow-conscious code
  	if (minCapacity - elementData.length > 0)
  		grow(minCapacity);
  }
  
  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  
  /**
   * Increases the capacity to ensure that it can hold at least the
   * number of elements specified by the minimum capacity argument.
   *
   * @param minCapacity the desired minimum capacity
   */
  private void grow(int minCapacity) {
  
  	// overflow-conscious code
  	int oldCapacity = elementData.length;
  	int newCapacity = oldCapacity + (oldCapacity >> 1);
  
  	if (newCapacity - minCapacity < 0)
  		newCapacity = minCapacity;
  
  	if (newCapacity - MAX_ARRAY_SIZE > 0)
  		newCapacity = hugeCapacity(minCapacity);
  
  	Object[] oldData = elementData;
  	elementData = new Object[newCapacity];
  
  	copy(oldData, elementData);
  }
  
  private static int hugeCapacity(int minCapacity) {
  	if (minCapacity < 0) // overflow
  		throw new OutOfMemoryError();
  
  	return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
  }
  
  public int size() {
  	return size;
  }
  
  public boolean isEmpty() {
  	return size == 0;
  }
  
  public boolean contains(Object o) {
  	return indexOf(o) >= 0;
  }
  
  public int indexOf(Object o) {
  	if (o == null) {
  		for (int i = 0; i < size; i++)
  			if (elementData[pos(i)] == null)
  				return i;
  	} else {
  		for (int i = 0; i < size; i++)
  			if (o.equals(elementData[pos(i)]))
  				return i;
  	}
  	return -1;
  }
  
  public int lastIndexOf(Object o) {
  	if (o == null) {
  		for (int i = size - 1; i >= 0; i--)
  			if (elementData[pos(i)] == null)
  				return i;
  	} else {
  		for (int i = size - 1; i >= 0; i--)
  			if (o.equals(elementData[pos(i)]))
  				return i;
  	}
  	return -1;
  }
  
  public Object clone() {
  	try {
  		@SuppressWarnings("unchecked")
  			CircularArrayList<E> c = (CircularArrayList<E>) super.clone();
  
  		c.elementData = new Object[size];
  		copy(elementData, c.elementData);
  		c.modCount = 0;
  		return c;
  	} catch (CloneNotSupportedException e) {
  		// this shouldn't happen, since we are Cloneable
  		throw new InternalError();
  	}
  }
  
  public Object[] toArray() {
  	Object[] a = new Object[size];
  
  	System.arraycopy(elementData, elementData.length + tail, a, 0, -tail);
  	System.arraycopy(elementData, 0, a, -tail, head);
  
  	return a;
  }
  
  public <T> T[] toArray(T[] a) {
  	if (a.length < size) {
  		// Make a new array of a's runtime type
  		a = ((Object)a.getClass() == (Object)Object[].class)
  				? (T[]) new Object[size]
  				: (T[]) Array.newInstance(a.getClass().getComponentType(), size);
  
  	}
  
  	System.arraycopy(elementData, elementData.length + tail, a, 0, -tail);
  	System.arraycopy(elementData, 0, a, -tail, head);
  
  	if (a.length > size) {
  		a[size] = null;
  	}
  
  	return a;
  }
  
  private int pos(int index) {
  	return (elementData.length + tail + index) % elementData.length;
  }
  
  public E get(int index) {
  	rangeCheck(index);
  
  	return (E) elementData[pos(index)];
  }
  
  public E set(int index, E element) {
  	rangeCheck(index);
  
  	int pos = pos(index);
  	E oldValue = (E) elementData[pos];
  	elementData[pos] = element;
  	return oldValue;
  }
  
  public boolean add(E e) {
  	ensureCapacityInternal(size + 1); // Increments modCount!!
  	elementData[head] = e;
  	head++;
  	size++;
  	return true;
  }
  
  public void add(int index, E element) {
  	rangeCheckForAdd(index);
  
  	ensureCapacityInternal(size + 1); // Increments modCount!!
  
  	int i = index + tail;
  	if (i <= 0) {
  
  		System.arraycopy(elementData, elementData.length + tail, 
  						 elementData, elementData.length + tail - 1, 
  						 index);
  
  		elementData[elementData.length + i - 1] = element;
  		tail--;
  	} else {
  
  		System.arraycopy(elementData, i, elementData, i + 1, size - index);
  		elementData[i] = element;
  		head++;
  	}
  
  	size++;
  }
  
  public E remove(int index) {
  	rangeCheck(index);
  
  	E value = (E) elementData[pos(index)];
  	fastRemove(index);
  
  	return value;
  }
  
  public boolean remove(Object o) {
  	if (o == null) {
  		for (int index = 0; index < size; index++)
  			if (elementData[pos(index)] == null) {
  				fastRemove(index);
  				return true;
  			}
  	} else {
  		for (int index = 0; index < size; index++)
  			if (o.equals(elementData[pos(index)])) {
  				fastRemove(index);
  				return true;
  			}
  	}
  	return false;
  }
  
  private void fastRemove(int index) {
  	modCount++;
  
  	int i = index + tail;
  	if (i < 0) {
  		int numMoved = index;
  		if (numMoved > 0)
  			System.arraycopy(elementData, elementData.length + tail, 
  							 elementData, elementData.length + tail + 1,
  							 numMoved);
  
  		elementData[elementData.length + tail] = null; // Let gc do its work
  		tail++;
  	} else {
  		int numMoved = size - index - 1;
  		if (numMoved > 0)
  			System.arraycopy(elementData, i + 1, elementData, i, numMoved);
  
  		head--;
  		elementData[head] = null; // Let gc do its work
  	}
  
  	size--;
  }
  
  public void clear() {
  	modCount++;
  
  	// Let gc do its work
  	for (int i = 0; i < size; i++)
  		elementData[pos(i)] = null;
  
  	size = tail = head = 0;
  }
  
  public boolean addAll(Collection<? extends E> c) {
  	Object[] a = c.toArray();
  	int numNew = a.length;
  	ensureCapacityInternal(size + numNew); // Increments modCount
  	System.arraycopy(a, 0, elementData, head, numNew);
  	head += numNew;
  	size += numNew;
  	return numNew != 0;
  }
  
  private void rangeCheck(int index) {
  	if (index >= size || index < 0) {
  		throw new IndexOutOfBoundsException(
  				"Index: " + index + ", Size: " + size);
  	}
  }
  
  private void rangeCheckForAdd(int index) {
  	if (index > size || index < 0)
  		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  }
  
  private String outOfBoundsMsg(int index) {
  	return "Index: " + index + ", Size: " + size;
  }
}

Travelled to 14 computer(s): aoiabmzegqzx, bhatertpkbcr, cbybwowwnfue, cfunsshuasjs, gwrvuhgaqvyk, irmadwmeruwu, ishqpsrjomds, lpdgvwnxivlt, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tslmcundralx, tvejysmllsmz, vouqrxazstgt

Snippet ID:	#1013598
Snippet name:	CircularArrayList - list with fast remove/add at both ends; not synchronized; broken?
Eternal ID of this version:	#1013598/6
Text MD5:	ca6f9c7033542f5bca27965182478cb1
Author:	stefan
Category:	javax / collections
Type:	JavaX fragment (include)
Public (visible to everyone):	Yes
Archived (hidden from active list):	No
Created/modified:	2018-06-29 01:38:11
Source code size:	7312 bytes / 294 lines
Pitched / IR pitched:	No / No
Views / Downloads:	371 / 981
Version history:	5 change(s)
Referenced in:	[show references]

< > BotCompany Repo | #1013598 // CircularArrayList - list with fast remove/add at both ends; not synchronized; broken?

JavaX fragment (include)

Author comment

1	sclass CircularArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
2	private transient Object[] elementData;
3	private int size;
4	private int head;
5	private int tail;
6
7	*(int initialCapacity) {
8	if (initialCapacity < 0) {
9	throw new IllegalArgumentException(
10	"Illegal Capacity: " + initialCapacity);
11	}
12
13	elementData = new Object[initialCapacity];
14	size = tail = head = 0;
15	}
16
17	*() { this(10); }
18
19	*(Collection<? extends E> c) {
20	elementData = c.toArray();
21	tail = 0;
22	size = head = elementData.length;
23
24	// c.toArray might (incorrectly) not return Object[] (see 6260652)
25	if (elementData.getClass() != Object[].class)
26	elementData = Arrays.copyOf(elementData, size, Object[].class);
27	}
28
29	private void copy(Object[] src, Object[] dest) {
30	System.arraycopy(src, 0, dest, 0, head);
31	System.arraycopy(src, src.length + tail,
32	dest, dest.length + tail, -tail);
33	}
34
35	private void ensureCapacityInternal(int minCapacity) {
36	modCount++;
37
38	// overflow-conscious code
39	if (minCapacity - elementData.length > 0)
40	grow(minCapacity);
41	}
42
43	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
44
45	/**
46	* Increases the capacity to ensure that it can hold at least the
47	* number of elements specified by the minimum capacity argument.
48	*
49	* @param minCapacity the desired minimum capacity
50	*/
51	private void grow(int minCapacity) {
52
53	// overflow-conscious code
54	int oldCapacity = elementData.length;
55	int newCapacity = oldCapacity + (oldCapacity >> 1);
56
57	if (newCapacity - minCapacity < 0)
58	newCapacity = minCapacity;
59
60	if (newCapacity - MAX_ARRAY_SIZE > 0)
61	newCapacity = hugeCapacity(minCapacity);
62
63	Object[] oldData = elementData;
64	elementData = new Object[newCapacity];
65
66	copy(oldData, elementData);
67	}
68
69	private static int hugeCapacity(int minCapacity) {
70	if (minCapacity < 0) // overflow
71	throw new OutOfMemoryError();
72
73	return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
74	}
75
76	public int size() {
77	return size;
78	}
79
80	public boolean isEmpty() {
81	return size == 0;
82	}
83
84	public boolean contains(Object o) {
85	return indexOf(o) >= 0;
86	}
87
88	public int indexOf(Object o) {
89	if (o == null) {
90	for (int i = 0; i < size; i++)
91	if (elementData[pos(i)] == null)
92	return i;
93	} else {
94	for (int i = 0; i < size; i++)
95	if (o.equals(elementData[pos(i)]))
96	return i;
97	}
98	return -1;
99	}
100
101	public int lastIndexOf(Object o) {
102	if (o == null) {
103	for (int i = size - 1; i >= 0; i--)
104	if (elementData[pos(i)] == null)
105	return i;
106	} else {
107	for (int i = size - 1; i >= 0; i--)
108	if (o.equals(elementData[pos(i)]))
109	return i;
110	}
111	return -1;
112	}
113
114	public Object clone() {
115	try {
116	@SuppressWarnings("unchecked")
117	CircularArrayList<E> c = (CircularArrayList<E>) super.clone();
118
119	c.elementData = new Object[size];
120	copy(elementData, c.elementData);
121	c.modCount = 0;
122	return c;
123	} catch (CloneNotSupportedException e) {
124	// this shouldn't happen, since we are Cloneable
125	throw new InternalError();
126	}
127	}
128
129	public Object[] toArray() {
130	Object[] a = new Object[size];
131
132	System.arraycopy(elementData, elementData.length + tail, a, 0, -tail);
133	System.arraycopy(elementData, 0, a, -tail, head);
134
135	return a;
136	}
137
138	public <T> T[] toArray(T[] a) {
139	if (a.length < size) {
140	// Make a new array of a's runtime type
141	a = ((Object)a.getClass() == (Object)Object[].class)
142	? (T[]) new Object[size]
143	: (T[]) Array.newInstance(a.getClass().getComponentType(), size);
144
145	}
146
147	System.arraycopy(elementData, elementData.length + tail, a, 0, -tail);
148	System.arraycopy(elementData, 0, a, -tail, head);
149
150	if (a.length > size) {
151	a[size] = null;
152	}
153
154	return a;
155	}
156
157	private int pos(int index) {
158	return (elementData.length + tail + index) % elementData.length;
159	}
160
161	public E get(int index) {
162	rangeCheck(index);
163
164	return (E) elementData[pos(index)];
165	}
166
167	public E set(int index, E element) {
168	rangeCheck(index);
169
170	int pos = pos(index);
171	E oldValue = (E) elementData[pos];
172	elementData[pos] = element;
173	return oldValue;
174	}
175
176	public boolean add(E e) {
177	ensureCapacityInternal(size + 1); // Increments modCount!!
178	elementData[head] = e;
179	head++;
180	size++;
181	return true;
182	}
183
184	public void add(int index, E element) {
185	rangeCheckForAdd(index);
186
187	ensureCapacityInternal(size + 1); // Increments modCount!!
188
189	int i = index + tail;
190	if (i <= 0) {
191
192	System.arraycopy(elementData, elementData.length + tail,
193	elementData, elementData.length + tail - 1,
194	index);
195
196	elementData[elementData.length + i - 1] = element;
197	tail--;
198	} else {
199
200	System.arraycopy(elementData, i, elementData, i + 1, size - index);
201	elementData[i] = element;
202	head++;
203	}
204
205	size++;
206	}
207
208	public E remove(int index) {
209	rangeCheck(index);
210
211	E value = (E) elementData[pos(index)];
212	fastRemove(index);
213
214	return value;
215	}
216
217	public boolean remove(Object o) {
218	if (o == null) {
219	for (int index = 0; index < size; index++)
220	if (elementData[pos(index)] == null) {
221	fastRemove(index);
222	return true;
223	}
224	} else {
225	for (int index = 0; index < size; index++)
226	if (o.equals(elementData[pos(index)])) {
227	fastRemove(index);
228	return true;
229	}
230	}
231	return false;
232	}
233
234	private void fastRemove(int index) {
235	modCount++;
236
237	int i = index + tail;
238	if (i < 0) {
239	int numMoved = index;
240	if (numMoved > 0)
241	System.arraycopy(elementData, elementData.length + tail,
242	elementData, elementData.length + tail + 1,
243	numMoved);
244
245	elementData[elementData.length + tail] = null; // Let gc do its work
246	tail++;
247	} else {
248	int numMoved = size - index - 1;
249	if (numMoved > 0)
250	System.arraycopy(elementData, i + 1, elementData, i, numMoved);
251
252	head--;
253	elementData[head] = null; // Let gc do its work
254	}
255
256	size--;
257	}
258
259	public void clear() {
260	modCount++;
261
262	// Let gc do its work
263	for (int i = 0; i < size; i++)
264	elementData[pos(i)] = null;
265
266	size = tail = head = 0;
267	}
268
269	public boolean addAll(Collection<? extends E> c) {
270	Object[] a = c.toArray();
271	int numNew = a.length;
272	ensureCapacityInternal(size + numNew); // Increments modCount
273	System.arraycopy(a, 0, elementData, head, numNew);
274	head += numNew;
275	size += numNew;
276	return numNew != 0;
277	}
278
279	private void rangeCheck(int index) {
280	if (index >= size \|\| index < 0) {
281	throw new IndexOutOfBoundsException(
282	"Index: " + index + ", Size: " + size);
283	}
284	}
285
286	private void rangeCheckForAdd(int index) {
287	if (index > size \|\| index < 0)
288	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
289	}
290
291	private String outOfBoundsMsg(int index) {
292	return "Index: " + index + ", Size: " + size;
293	}
294	}