ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/jsr166e/extra/ReadMostlyVector.java

Comparing jsr166/src/jsr166e/extra/ReadMostlyVector.java (file contents):
Revision 1.1 by dl, Fri Jul 15 23:56:18 2011 UTC vs.
Revision 1.12 by dl, Thu Jul 21 12:49:37 2011 UTC

#	Line 9 | Line 9 | import jsr166e.*;
9		import java.util.*;
10
11		/**
12	<	* A class with the same API and array-based characteristics as {@link
13	<	* java.util.Vector} but with reduced contention and improved
12	>	* A class with the same methods and array-based characteristics as
13	>	* {@link java.util.Vector} but with reduced contention and improved
14		* throughput when invocations of read-only methods by multiple
15	<	* threads are most common.  Instances of this class may have
16	<	* relatively poorer performance in other contexts.
15	>	* threads are most common.
16		*
17		* <p> The iterators returned by this class's {@link #iterator()
18		* iterator} and {@link #listIterator(int) listIterator} methods are
19		* best-effort in the presence of concurrent modifications, and do
20		* <em>NOT</em> throw {@link ConcurrentModificationException}.  An
21		* iterator's {@code next()} method returns consecutive elements as
22	<	* they appear in the underlying array upon each access.
22	>	* they appear in the underlying array upon each access. Alternatvely,
23	>	* method {@link #snapshotIterator} may be used for deterministic
24	>	* traversals, at the expense of making a copy, and unavailability of
25	>	* method {@code Iterator.remove}.
26		*
27		* <p>Otherwise, this class supports all methods, under the same
28		* documented specifications, as {@code Vector}.  Consult {@link
#	Line 35 | Line 37 | public class ReadMostlyVector<E> impleme
37
38		/*
39		* This class exists mainly as a vehicle to exercise various
40	<	* constructions using SequenceLocks, which are not yet explained
41	<	* well here.
40	>	* constructions using SequenceLocks. Read-only methods
41	>	* take one of a few forms:
42	>	*
43	>	* Short methods,including get(index), continually retry obtaining
44	>	* a snapshot of array, count, and element, using sequence number
45	>	* to validate.
46	>	*
47	>	* Methods that are potentially O(n) (or worse) try once in
48	>	* read-only mode, and then lock. When in read-only mode, they
49	>	* validate only at the end of an array scan unless the element is
50	>	* actually used (for example, as an argument of method equals).
51		*/
52
53		/**
#	Line 46 | Line 57 | public class ReadMostlyVector<E> impleme
57		private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
58
59		// fields are non-private to simpify nested class access
60	<	Object[] array;
60	>	volatile Object[] array;
61		final SequenceLock lock;
62	<	int count;
62	>	volatile int count;
63		final int capacityIncrement;
64
65		/**
#	Line 118 | Line 129 | public class ReadMostlyVector<E> impleme
129		}
130
131		// For explanation, see CopyOnWriteArrayList
132	<	final void grow(int minCapacity) {
132	>	final Object[] grow(int minCapacity) {
133		int oldCapacity = array.length;
134		int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
135		capacityIncrement : oldCapacity);
#	Line 126 | Line 137 | public class ReadMostlyVector<E> impleme
137		newCapacity = minCapacity;
138		if (newCapacity - MAX_ARRAY_SIZE > 0)
139		newCapacity = hugeCapacity(minCapacity);
140	<	array = Arrays.copyOf(array, newCapacity);
140	>	return array = Arrays.copyOf(array, newCapacity);
141		}
142
143		static int hugeCapacity(int minCapacity) {
#	Line 143 | Line 154 | public class ReadMostlyVector<E> impleme
154		* as well as sublist and iterator classes.
155		*/
156
157	<	static int internalIndexOf(Object o, Object[] items,
158	<	int index, int fence) {
157	>	// Version of indexOf that returns -1 if either not present or invalid
158	>	final int validatedIndexOf(Object x, Object[] items, int index, int fence,
159	>	long seq) {
160	>	for (int i = index; i < fence; ++i) {
161	>	Object e = items[i];
162	>	if (lock.getSequence() != seq)
163	>	break;
164	>	if ((x == null) ? e == null : x.equals(e))
165	>	return i;
166	>	}
167	>	return -1;
168	>	}
169	>
170	>	final int rawIndexOf(Object x, int index, int fence) {
171	>	Object[] items = array;
172		for (int i = index; i < fence; ++i) {
173	<	Object x = items[i];
174	<	if (o == null? x == null : (x != null && o.equals(x)))
173	>	Object e = items[i];
174	>	if ((x == null) ? e == null : x.equals(e))
175		return i;
176		}
177		return -1;
178		}
179
180	<	static int internalLastIndexOf(Object o, Object[] items,
181	<	int index, int origin) {
180	>	final int validatedLastIndexOf(Object x, Object[] items,
181	>	int index, int origin, long seq) {
182		for (int i = index; i >= origin; --i) {
183	<	Object x = items[i];
184	<	if (o == null? x == null : (x != null && o.equals(x)))
183	>	Object e = items[i];
184	>	if (lock.getSequence() != seq)
185	>	break;
186	>	if ((x == null) ? e == null : x.equals(e))
187		return i;
188		}
189		return -1;
190		}
191
192	<	final void internalAdd(E e) {
193	<	int c = count;
194	<	if (c >= array.length)
195	<	grow(c + 1);
196	<	array[c] = e;
197	<	count = c + 1;
192	>	final int rawLastIndexOf(Object x, int index, int origin) {
193	>	Object[] items = array;
194	>	for (int i = index; i >= origin; --i) {
195	>	Object e = items[i];
196	>	if ((x == null) ? e == null : x.equals(e))
197	>	return i;
198	>	}
199	>	return -1;
200	>	}
201	>
202	>	final void rawAdd(Object e) {
203	>	int n = count;
204	>	Object[] items = array;
205	>	if (n >= items.length)
206	>	items = grow(n + 1);
207	>	items[n] = e;
208	>	count = n + 1;
209		}
210
211	<	final void internalAddAt(int index, E e) {
212	<	int c = count;
213	<	if (index > c)
211	>	final void rawAddAt(int index, Object e) {
212	>	int n = count;
213	>	Object[] items = array;
214	>	if (index > n)
215		throw new ArrayIndexOutOfBoundsException(index);
216	<	if (c >= array.length)
217	<	grow(c + 1);
218	<	System.arraycopy(array, index, array, index + 1, c - index);
219	<	array[index] = e;
220	<	count = c + 1;
216	>	if (n >= items.length)
217	>	items = grow(n + 1);
218	>	if (index < n)
219	>	System.arraycopy(items, index, items, index + 1, n - index);
220	>	items[index] = e;
221	>	count = n + 1;
222		}
223
224	<	final boolean internalAddAllAt(int index, Object[] elements) {
225	<	int c = count;
226	<	if (index < 0 || index > c)
224	>	final boolean rawAddAllAt(int index, Object[] elements) {
225	>	int n = count;
226	>	Object[] items = array;
227	>	if (index < 0 || index > n)
228		throw new ArrayIndexOutOfBoundsException(index);
229		int len = elements.length;
230		if (len == 0)
231		return false;
232	<	int newCount = c + len;
233	<	if (newCount >= array.length)
234	<	grow(newCount);
235	<	int mv = count - index;
232	>	int newCount = n + len;
233	>	if (newCount >= items.length)
234	>	items = grow(newCount);
235	>	int mv = n - index;
236		if (mv > 0)
237	<	System.arraycopy(array, index, array, index + len, mv);
238	<	System.arraycopy(elements, 0, array, index, len);
237	>	System.arraycopy(items, index, items, index + len, mv);
238	>	System.arraycopy(elements, 0, items, index, len);
239		count = newCount;
240		return true;
241		}
242
243	<	final boolean internalRemoveAt(int index) {
244	<	int c = count - 1;
245	<	if (index < 0 || index > c)
243	>	final boolean rawRemoveAt(int index) {
244	>	int n = count - 1;
245	>	Object[] items = array;
246	>	if (index < 0 || index > n)
247		return false;
248	<	int mv = c - index;
248	>	int mv = n - index;
249		if (mv > 0)
250	<	System.arraycopy(array, index + 1, array, index, mv);
251	<	array[c] = null;
252	<	count = c;
250	>	System.arraycopy(items, index + 1, items, index, mv);
251	>	items[n] = null;
252	>	count = n;
253		return true;
254		}
255
256		/**
257		* Internal version of removeAll for lists and sublists. In this
258	<	* and other similar methods below, the span argument is, if
259	<	* non-negative, the purported size of a list/sublist, or is left
260	<	* negative if the size should be determined via count field under
261	<	* lock.
258	>	* and other similar methods below, the bound argument is, if
259	>	* non-negative, the purported upper bound of a list/sublist, or
260	>	* is left negative if the bound should be determined via count
261	>	* field under lock.
262		*/
263	<	final boolean internalRemoveAll(Collection<?> c, int origin, int span) {
263	>	final boolean internalRemoveAll(Collection<?> c, int origin, int bound) {
264		SequenceLock lock = this.lock;
265		boolean removed = false;
266		lock.lock();
267		try {
268	<	int fence = count;
269	<	if (span >= 0 && origin + span < fence)
229	<	fence = origin + span;
268	>	int n = count;
269	>	int fence = bound < 0 || bound > n ? n : bound;
270		if (origin >= 0 && origin < fence) {
271		for (Object x : c) {
272	<	while (internalRemoveAt(internalIndexOf(x, array,
233	<	origin, fence)))
272	>	while (rawRemoveAt(rawIndexOf(x, origin, fence)))
273		removed = true;
274		}
275		}
#	Line 240 | Line 279 | public class ReadMostlyVector<E> impleme
279		return removed;
280		}
281
282	<	final boolean internalRetainAll(Collection<?> c, int origin, int span) {
282	>	final boolean internalRetainAll(Collection<?> c, int origin, int bound) {
283		SequenceLock lock = this.lock;
284		boolean removed = false;
285		if (c != this) {
286		lock.lock();
287		try {
288	+	Object[] items = array;
289		int i = origin;
290	<	int fence = count;
291	<	if (span >= 0 && origin + span < fence)
292	<	fence = origin + span;
293	<	while (i < fence) {
254	<	if (c.contains(array[i]))
290	>	int n = count;
291	>	int fence = bound < 0 || bound > n ? n : bound;
292	>	while (i >= 0 && i < fence) {
293	>	if (c.contains(items[i]))
294		++i;
295		else {
296		--fence;
297	<	int mv = --count - i;
297	>	int mv = --n - i;
298		if (mv > 0)
299	<	System.arraycopy(array, i + 1, array, i, mv);
261	<	removed = true;
299	>	System.arraycopy(items, i + 1, items, i, mv);
300		}
301		}
302	+	if (count != n) {
303	+	count = n;
304	+	removed = true;
305	+	}
306		} finally {
307		lock.unlock();
308		}
#	Line 268 | Line 310 | public class ReadMostlyVector<E> impleme
310		return removed;
311		}
312
313	<	final void internalClear(int origin, int span) {
314	<	int c = count;
315	<	int fence = c;
274	<	if (span >= 0 && origin + span < fence)
275	<	fence = origin + span;
313	>	final void internalClear(int origin, int bound) {
314	>	int n = count;
315	>	int fence = bound < 0 || bound > n ? n : bound;
316		if (origin >= 0 && origin < fence) {
317	+	Object[] items = array;
318		int removed = fence - origin;
319	<	int newCount = c - removed;
320	<	int mv = c - (origin + removed);
319	>	int newCount = n - removed;
320	>	int mv = n - (origin + removed);
321		if (mv > 0)
322	<	System.arraycopy(array, origin + removed, array, origin, mv);
323	<	for (int i = c; i < newCount; ++i)
324	<	array[i] = null;
322	>	System.arraycopy(items, origin + removed, items, origin, mv);
323	>	for (int i = n; i < newCount; ++i)
324	>	items[i] = null;
325		count = newCount;
326		}
327		}
328
329	<	final boolean internalContainsAll(Collection<?> coll, int origin, int span) {
329	>	final boolean internalContainsAll(Collection<?> c, int origin, int bound) {
330		SequenceLock lock = this.lock;
331		boolean contained;
332		boolean locked = false;
333		try {
334		for (;;) {
335		long seq = lock.awaitAvailability();
336	+	int n = count;
337		Object[] items = array;
338		int len = items.length;
339	<	int c = count;
298	<	if (c > len)
339	>	if (n > len)
340		continue;
341	<	int fence = c;
342	<	if (span >= 0 && origin + span < fence)
302	<	fence = origin + span;
303	<	if (origin < 0 || fence > c)
341	>	int fence = bound < 0 || bound > n ? n : bound;
342	>	if (origin < 0)
343		contained = false;
344		else {
345		contained = true;
346	<	for (Object e : coll) {
347	<	if (internalIndexOf(e, items, origin, fence) < 0) {
346	>	for (Object e : c) {
347	>	int idx = (locked ?
348	>	rawIndexOf(e, origin, fence) :
349	>	validatedIndexOf(e, items, origin,
350	>	fence, seq));
351	>	if (idx < 0) {
352		contained = false;
353		break;
354		}
#	Line 323 | Line 366 | public class ReadMostlyVector<E> impleme
366		return contained;
367		}
368
369	<	final boolean internalEquals(List<?> list, int origin, int span) {
369	>	final boolean internalEquals(List<?> list, int origin, int bound) {
370		SequenceLock lock = this.lock;
328	–	boolean equal;
371		boolean locked = false;
372	+	boolean equal;
373		try {
374		for (;;) {
332	–	equal = true;
375		long seq = lock.awaitAvailability();
376		Object[] items = array;
377	<	int len = items.length;
378	<	int c = count;
337	<	if (c > len)
338	<	continue;
339	<	int fence = c;
340	<	if (span >= 0 && origin + span < fence)
341	<	fence = origin + span;
342	<	if (origin < 0 || fence > c)
377	>	int n = count;
378	>	if (n > items.length || origin < 0)
379		equal = false;
380		else {
381	+	equal = true;
382	+	int fence = bound < 0 || bound > n ? n : bound;
383		Iterator<?> it = list.iterator();
384		for (int i = origin; i < fence; ++i) {
385	<	if (!it.hasNext()) {
386	<	equal = false;
387	<	break;
388	<	}
389	<	Object x = it.next();
390	<	Object y = items[i];
353	<	if (x == null? y != null : (y == null || !x.equals(y))) {
385	>	Object x = items[i];
386	>	Object y;
387	>	if ((!locked && lock.getSequence() != seq) ||
388	>	!it.hasNext() ||
389	>	(y = it.next()) == null ?
390	>	x != null : !y.equals(x)) {
391		equal = false;
392		break;
393		}
#	Line 370 | Line 407 | public class ReadMostlyVector<E> impleme
407		return equal;
408		}
409
410	<	final int internalHashCode(int origin, int span) {
410	>	final int internalHashCode(int origin, int bound) {
411		SequenceLock lock = this.lock;
412		int hash;
413		boolean locked = false;
#	Line 379 | Line 416 | public class ReadMostlyVector<E> impleme
416		hash = 1;
417		long seq = lock.awaitAvailability();
418		Object[] items = array;
419	+	int n = count;
420		int len = items.length;
421	<	int c = count;
384	<	if (c > len)
421	>	if (n > len)
422		continue;
423	<	int fence = c;
424	<	if (span >= 0 && origin + span < fence)
388	<	fence = origin + span;
389	<	if (origin >= 0 && fence <= c) {
423	>	int fence = bound < 0 || bound > n ? n : bound;
424	>	if (origin >= 0) {
425		for (int i = origin; i < fence; ++i) {
426		Object e = items[i];
427		hash = 31*hash + (e == null ? 0 : e.hashCode());
#	Line 404 | Line 439 | public class ReadMostlyVector<E> impleme
439		return hash;
440		}
441
442	<	final String internalToString(int origin, int span) {
442	>	final String internalToString(int origin, int bound) {
443		SequenceLock lock = this.lock;
444		String ret;
445		boolean locked = false;
446		try {
447	<	for (;;) {
447	>	outer:for (;;) {
448		long seq = lock.awaitAvailability();
449		Object[] items = array;
450	+	int n = count;
451		int len = items.length;
452	<	int c = count;
417	<	if (c > len)
452	>	if (n > len)
453		continue;
454	<	int fence = c;
455	<	if (span >= 0 && origin + span < fence)
456	<	fence = origin + span;
457	<	if (origin >= 0 && fence <= c) {
458	<	if (origin == fence)
459	<	ret = "[]";
460	<	else {
461	<	StringBuilder sb = new StringBuilder();
462	<	sb.append('[');
463	<	for (int i = origin;;) {
464	<	Object e = items[i];
465	<	sb.append(e == this ? "(this Collection)" : e);
466	<	if (++i < fence)
467	<	sb.append(',').append(' ');
468	<	else {
469	<	ret = sb.append(']').toString();
470	<	break;
471	<	}
454	>	int fence = bound < 0 || bound > n ? n : bound;
455	>	if (origin < 0 || origin == fence)
456	>	ret = "[]";
457	>	else {
458	>	StringBuilder sb = new StringBuilder();
459	>	sb.append('[');
460	>	for (int i = origin;;) {
461	>	Object e = items[i];
462	>	if (e == this)
463	>	sb.append("(this Collection)");
464	>	else if (!locked && lock.getSequence() != seq)
465	>	continue outer;
466	>	else
467	>	sb.append(e.toString());
468	>	if (++i < fence)
469	>	sb.append(',').append(' ');
470	>	else {
471	>	ret = sb.append(']').toString();
472	>	break;
473		}
474		}
439	–	if (lock.getSequence() == seq)
440	–	break;
475		}
476	+	if (lock.getSequence() == seq)
477	+	break;
478		lock.lock();
479		locked = true;
480		}
#	Line 449 | Line 485 | public class ReadMostlyVector<E> impleme
485		return ret;
486		}
487
488	<	final Object[] internalToArray(int origin, int span) {
488	>	final Object[] internalToArray(int origin, int bound) {
489		Object[] result;
490		SequenceLock lock = this.lock;
491		boolean locked = false;
#	Line 458 | Line 494 | public class ReadMostlyVector<E> impleme
494		result = null;
495		long seq = lock.awaitAvailability();
496		Object[] items = array;
497	+	int n = count;
498		int len = items.length;
499	<	int c = count;
500	<	int fence = c;
501	<	if (span >= 0 && origin + span < fence)
502	<	fence = origin + span;
466	<	if (c <= len && fence <= len) {
499	>	if (n > len)
500	>	continue;
501	>	int fence = bound < 0 || bound > n ? n : bound;
502	>	if (origin >= 0)
503		result = Arrays.copyOfRange(items, origin, fence,
504		Object[].class);
505	<	if (lock.getSequence() == seq)
506	<	break;
471	<	}
505	>	if (lock.getSequence() == seq)
506	>	break;
507		lock.lock();
508		locked = true;
509		}
#	Line 479 | Line 514 | public class ReadMostlyVector<E> impleme
514		return result;
515		}
516
517	<	final <T> T[] internalToArray(T[] a, int origin, int span) {
517	>	final <T> T[] internalToArray(T[] a, int origin, int bound) {
518	>	int alen = a.length;
519		T[] result;
520		SequenceLock lock = this.lock;
521		boolean locked = false;
#	Line 487 | Line 523 | public class ReadMostlyVector<E> impleme
523		for (;;) {
524		long seq = lock.awaitAvailability();
525		Object[] items = array;
526	+	int n = count;
527		int len = items.length;
528	<	int c = count;
529	<	int fence = c;
530	<	if (span >= 0 && origin + span < fence)
531	<	fence = origin + span;
532	<	if (c <= len && fence <= len) {
533	<	if (a.length < count)
534	<	result = (T[]) Arrays.copyOfRange(array, origin,
535	<	fence, a.getClass());
536	<	else {
537	<	int n = fence - origin;
538	<	System.arraycopy(array, 0, a, origin, fence - origin);
539	<	if (a.length > n)
503	<	a[n] = null;
504	<	result = a;
505	<	}
506	<	if (lock.getSequence() == seq)
507	<	break;
528	>	if (n > len)
529	>	continue;
530	>	int fence = bound < 0 || bound > n ? n : bound;
531	>	int rlen = fence - origin;
532	>	if (rlen < 0)
533	>	rlen = 0;
534	>	if (origin < 0 || alen >= rlen) {
535	>	if (rlen > 0)
536	>	System.arraycopy(items, 0, a, origin, rlen);
537	>	if (alen > rlen)
538	>	a[rlen] = null;
539	>	result = a;
540		}
541	+	else
542	+	result = (T[]) Arrays.copyOfRange(items, origin,
543	+	fence, a.getClass());
544	+	if (lock.getSequence() == seq)
545	+	break;
546		lock.lock();
547		locked = true;
548		}
#	Line 522 | Line 559 | public class ReadMostlyVector<E> impleme
559		SequenceLock lock = this.lock;
560		lock.lock();
561		try {
562	<	internalAdd(e);
562	>	rawAdd(e);
563		} finally {
564		lock.unlock();
565		}
#	Line 533 | Line 570 | public class ReadMostlyVector<E> impleme
570		SequenceLock lock = this.lock;
571		lock.lock();
572		try {
573	<	internalAddAt(index, element);
573	>	rawAddAt(index, element);
574		} finally {
575		lock.unlock();
576		}
#	Line 547 | Line 584 | public class ReadMostlyVector<E> impleme
584		SequenceLock lock = this.lock;
585		lock.lock();
586		try {
587	<	int newCount = count + len;
588	<	if (newCount >= array.length)
589	<	grow(newCount);
590	<	System.arraycopy(elements, 0, array, count, len);
587	>	Object[] items = array;
588	>	int n = count;
589	>	int newCount = n + len;
590	>	if (newCount >= items.length)
591	>	items = grow(newCount);
592	>	System.arraycopy(elements, 0, items, n, len);
593		count = newCount;
594		} finally {
595		lock.unlock();
#	Line 564 | Line 603 | public class ReadMostlyVector<E> impleme
603		Object[] elements = c.toArray();
604		lock.lock();
605		try {
606	<	ret = internalAddAllAt(index, elements);
606	>	ret = rawAddAllAt(index, elements);
607		} finally {
608		lock.unlock();
609		}
#	Line 575 | Line 614 | public class ReadMostlyVector<E> impleme
614		SequenceLock lock = this.lock;
615		lock.lock();
616		try {
617	<	for (int i = 0; i < count; i++)
618	<	array[i] = null;
617	>	int n = count;
618	>	Object[] items = array;
619	>	for (int i = 0; i < n; i++)
620	>	items[i] = null;
621		count = 0;
622		} finally {
623		lock.unlock();
#	Line 596 | Line 637 | public class ReadMostlyVector<E> impleme
637		return true;
638		if (!(o instanceof List))
639		return false;
640	<	return internalEquals((List<?>)(o), 0, -1);
640	>	return internalEquals((List<?>)o, 0, -1);
641		}
642
643		public E get(int index) {
644		SequenceLock lock = this.lock;
645		for (;;) {
646		long seq = lock.awaitAvailability();
647	+	int n = count;
648		Object[] items = array;
649	<	int len = items.length;
608	<	int c = count;
609	<	if (c > len)
649	>	if (n > items.length)
650		continue;
651	<	E e; boolean ex;
652	<	if (index < 0 || index >= c) {
651	>	Object e; boolean ex;
652	>	if (index < 0 || index >= n) {
653		e = null;
654		ex = true;
655		}
656		else {
657	<	e = (E)items[index];
657	>	e = items[index];
658		ex = false;
659		}
660		if (lock.getSequence() == seq) {
661		if (ex)
662		throw new ArrayIndexOutOfBoundsException(index);
663		else
664	<	return e;
664	>	return (E)e;
665		}
666		}
667		}
#	Line 632 | Line 672 | public class ReadMostlyVector<E> impleme
672
673		public int indexOf(Object o) {
674		SequenceLock lock = this.lock;
675	<	long seq = lock.awaitAvailability();
676	<	Object[] items = array;
677	<	int c = count;
678	<	if (c <= items.length) {
679	<	int idx = internalIndexOf(o, items, 0, c);
680	<	if (lock.getSequence() == seq)
681	<	return idx;
682	<	}
683	<	lock.lock();
684	<	try {
685	<	return internalIndexOf(o, array, 0, count);
686	<	} finally {
687	<	lock.unlock();
675	>	for (;;) {
676	>	long seq = lock.awaitAvailability();
677	>	Object[] items = array;
678	>	int n = count;
679	>	if (n <= items.length) {
680	>	for (int i = 0; i < n; ++i) {
681	>	Object e = items[i];
682	>	if (lock.getSequence() != seq) {
683	>	lock.lock();
684	>	try {
685	>	return rawIndexOf(o, 0, count);
686	>	} finally {
687	>	lock.unlock();
688	>	}
689	>	}
690	>	else if ((o == null) ? e == null : o.equals(e))
691	>	return i;
692	>	}
693	>	return -1;
694	>	}
695		}
696		}
697
698		public boolean isEmpty() {
652	–	long ignore = lock.getSequence();
699		return count == 0;
700		}
701
702		public Iterator<E> iterator() {
703	<	return new Itr(this, 0);
703	>	return new Itr<E>(this, 0);
704		}
705
706		public int lastIndexOf(Object o) {
707		SequenceLock lock = this.lock;
708	<	long seq = lock.awaitAvailability();
709	<	Object[] items = array;
710	<	int c = count;
711	<	if (c <= items.length) {
712	<	int idx = internalLastIndexOf(o, items, c - 1, 0);
713	<	if (lock.getSequence() == seq)
714	<	return idx;
715	<	}
716	<	lock.lock();
717	<	try {
718	<	return internalLastIndexOf(o, array, count-1, 0);
719	<	} finally {
720	<	lock.unlock();
708	>	for (;;) {
709	>	long seq = lock.awaitAvailability();
710	>	Object[] items = array;
711	>	int n = count;
712	>	if (n <= items.length) {
713	>	for (int i = n - 1; i >= 0; --i) {
714	>	Object e = items[i];
715	>	if (lock.getSequence() != seq) {
716	>	lock.lock();
717	>	try {
718	>	return rawLastIndexOf(o, 0, count);
719	>	} finally {
720	>	lock.unlock();
721	>	}
722	>	}
723	>	else if ((o == null) ? e == null : o.equals(e))
724	>	return i;
725	>	}
726	>	return -1;
727	>	}
728		}
729		}
730
731		public ListIterator<E> listIterator() {
732	<	return new Itr(this, 0);
732	>	return new Itr<E>(this, 0);
733		}
734
735		public ListIterator<E> listIterator(int index) {
736	<	return new Itr(this, index);
736	>	return new Itr<E>(this, index);
737		}
738
739		public E remove(int index) {
740		SequenceLock lock = this.lock;
741	<	E oldValue;
741	>	Object oldValue;
742		lock.lock();
743		try {
744		if (index < 0 || index >= count)
745		throw new ArrayIndexOutOfBoundsException(index);
746	<	oldValue = (E)array[index];
747	<	internalRemoveAt(index);
746	>	oldValue = array[index];
747	>	rawRemoveAt(index);
748		} finally {
749		lock.unlock();
750		}
751	<	return oldValue;
751	>	return (E)oldValue;
752		}
753
754		public boolean remove(Object o) {
#	Line 703 | Line 756 | public class ReadMostlyVector<E> impleme
756		boolean removed;
757		lock.lock();
758		try {
759	<	removed = internalRemoveAt(internalIndexOf(o, array, 0, count));
759	>	removed = rawRemoveAt(rawIndexOf(o, 0, count));
760		} finally {
761		lock.unlock();
762		}
#	Line 719 | Line 772 | public class ReadMostlyVector<E> impleme
772		}
773
774		public E set(int index, E element) {
775	<	E oldValue;
775	>	Object oldValue;
776		SequenceLock lock = this.lock;
777		lock.lock();
778		try {
779	+	Object[] items = array;
780		if (index < 0 || index >= count)
781		throw new ArrayIndexOutOfBoundsException(index);
782	<	oldValue = (E)array[index];
783	<	array[index] = element;
782	>	oldValue = items[index];
783	>	items[index] = element;
784		} finally {
785		lock.unlock();
786		}
787	<	return oldValue;
787	>	return (E)oldValue;
788		}
789
790		public int size() {
737	–	long ignore = lock.getSequence();
791		return count;
792		}
793
#	Line 743 | Line 796 | public class ReadMostlyVector<E> impleme
796		int ssize = toIndex - fromIndex;
797		if (fromIndex < 0 || toIndex > c || ssize < 0)
798		throw new IndexOutOfBoundsException();
799	<	return new ReadMostlyVectorSublist(this, fromIndex, ssize);
799	>	return new ReadMostlyVectorSublist<E>(this, fromIndex, ssize);
800		}
801
802		public Object[] toArray() {
#	Line 764 | Line 817 | public class ReadMostlyVector<E> impleme
817		* Append the element if not present.
818		*
819		* @param e element to be added to this list, if absent
820	<	* @return <tt>true</tt> if the element was added
820	>	* @return {@code true} if the element was added
821		*/
822		public boolean addIfAbsent(E e) {
823		boolean added;
824		SequenceLock lock = this.lock;
825		lock.lock();
826		try {
827	<	if (internalIndexOf(e, array, 0, count) < 0) {
828	<	internalAdd(e);
827	>	if (rawIndexOf(e, 0, count) < 0) {
828	>	rawAdd(e);
829		added = true;
830		}
831		else
#	Line 803 | Line 856 | public class ReadMostlyVector<E> impleme
856		try {
857		for (int i = 0; i < clen; ++i) {
858		Object e = cs[i];
859	<	if (internalIndexOf(e, array, 0, count) < 0) {
860	<	internalAdd((E)e);
859	>	if (rawIndexOf(e, 0, count) < 0) {
860	>	rawAdd(e);
861		++added;
862		}
863		}
#	Line 815 | Line 868 | public class ReadMostlyVector<E> impleme
868		return added;
869		}
870
871	+	/**
872	+	* Returns an iterator operating over a snapshot copy of the
873	+	* elements of this collection created upon construction of the
874	+	* iterator. The iterator does <em>NOT</em> support the
875	+	* {@code remove} method.
876	+	*
877	+	* @return an iterator over the elements in this list in proper sequence
878	+	*/
879	+	public Iterator<E> snapshotIterator() {
880	+	return new SnapshotIterator<E>(this);
881	+	}
882	+
883	+	static final class SnapshotIterator<E> implements Iterator<E> {
884	+	final Object[] items;
885	+	int cursor;
886	+	SnapshotIterator(ReadMostlyVector<E> v) { items = v.toArray(); }
887	+	public boolean hasNext() { return cursor < items.length; }
888	+	public E next() {
889	+	if (cursor < items.length)
890	+	return (E) items[cursor++];
891	+	throw new NoSuchElementException();
892	+	}
893	+	public void remove() { throw new UnsupportedOperationException() ; }
894	+	}
895	+
896		// Vector-only methods
897
898		/** See {@link Vector#firstElement} */
#	Line 824 | Line 902 | public class ReadMostlyVector<E> impleme
902		long seq = lock.awaitAvailability();
903		Object[] items = array;
904		int len = items.length;
905	<	int c = count;
906	<	if (c > len || c < 0)
905	>	int n = count;
906	>	if (n > len)
907		continue;
908	<	E e; boolean ex;
909	<	if (c == 0) {
910	<	e = null;
911	<	ex = true;
908	>	Object e; boolean ex;
909	>	if (n > 0) {
910	>	e = items[0];
911	>	ex = false;
912		}
913		else {
914	<	e = (E)items[0];
915	<	ex = false;
914	>	e = null;
915	>	ex = true;
916		}
917		if (lock.getSequence() == seq) {
918		if (ex)
919		throw new NoSuchElementException();
920		else
921	<	return e;
921	>	return (E)e;
922		}
923		}
924		}
#	Line 852 | Line 930 | public class ReadMostlyVector<E> impleme
930		long seq = lock.awaitAvailability();
931		Object[] items = array;
932		int len = items.length;
933	<	int c = count;
934	<	if (c > len || c < 0)
933	>	int n = count;
934	>	if (n > len)
935		continue;
936	<	E e; boolean ex;
937	<	if (c == 0) {
938	<	e = null;
939	<	ex = true;
936	>	Object e; boolean ex;
937	>	if (n > 0) {
938	>	e = items[n - 1];
939	>	ex = false;
940		}
941		else {
942	<	e = (E)items[c - 1];
943	<	ex = false;
942	>	e = null;
943	>	ex = true;
944		}
945		if (lock.getSequence() == seq) {
946		if (ex)
947		throw new NoSuchElementException();
948		else
949	<	return e;
949	>	return (E)e;
950		}
951		}
952		}
#	Line 880 | Line 958 | public class ReadMostlyVector<E> impleme
958		boolean ex = false;
959		long seq = lock.awaitAvailability();
960		Object[] items = array;
961	<	int c = count;
961	>	int n = count;
962		boolean retry = false;
963	<	if (c > items.length)
963	>	if (n > items.length)
964		retry = true;
965		else if (index < 0)
966		ex = true;
967		else
968	<	idx = internalIndexOf(o, items, index, c);
968	>	idx = validatedIndexOf(o, items, index, n, seq);
969		if (retry || lock.getSequence() != seq) {
970		lock.lock();
971		try {
972		if (index < 0)
973		ex = true;
974		else
975	<	idx = internalIndexOf(o, array, 0, count);
975	>	idx = rawIndexOf(o, 0, count);
976		} finally {
977		lock.unlock();
978		}
#	Line 911 | Line 989 | public class ReadMostlyVector<E> impleme
989		boolean ex = false;
990		long seq = lock.awaitAvailability();
991		Object[] items = array;
992	<	int c = count;
992	>	int n = count;
993		boolean retry = false;
994	<	if (c > items.length)
994	>	if (n > items.length)
995		retry = true;
996	<	else if (index >= c)
996	>	else if (index >= n)
997		ex = true;
998		else
999	<	idx = internalLastIndexOf(o, items, index, 0);
999	>	idx = validatedLastIndexOf(o, items, index, 0, seq);
1000		if (retry || lock.getSequence() != seq) {
1001		lock.lock();
1002		try {
1003		if (index >= count)
1004		ex = true;
1005		else
1006	<	idx = internalLastIndexOf(o, array, index, 0);
1006	>	idx = rawLastIndexOf(o, index, 0);
1007		} finally {
1008		lock.unlock();
1009		}
#	Line 942 | Line 1020 | public class ReadMostlyVector<E> impleme
1020		SequenceLock lock = this.lock;
1021		lock.lock();
1022		try {
1023	<	int c = count;
1024	<	if (newSize > c)
1023	>	int n = count;
1024	>	if (newSize > n)
1025		grow(newSize);
1026		else {
1027	<	for (int i = newSize ; i < c ; i++)
1028	<	array[i] = null;
1027	>	Object[] items = array;
1028	>	for (int i = newSize ; i < n ; i++)
1029	>	items[i] = null;
1030		}
1031		count = newSize;
1032		} finally {
#	Line 971 | Line 1050 | public class ReadMostlyVector<E> impleme
1050		SequenceLock lock = this.lock;
1051		lock.lock();
1052		try {
1053	<	if (count < array.length)
1054	<	array = Arrays.copyOf(array, count);
1053	>	Object[] items = array;
1054	>	int n = count;
1055	>	if (n < items.length)
1056	>	array = Arrays.copyOf(items, n);
1057		} finally {
1058		lock.unlock();
1059		}
#	Line 994 | Line 1075 | public class ReadMostlyVector<E> impleme
1075
1076		/** See {@link Vector#elements} */
1077		public Enumeration<E> elements() {
1078	<	return new Itr(this, 0);
1078	>	return new Itr<E>(this, 0);
1079		}
1080
1081		/** See {@link Vector#capacity} */
1082		public int capacity() {
1002	–	long ignore = lock.getSequence();
1083		return array.length;
1084		}
1085
#	Line 1040 | Line 1120 | public class ReadMostlyVector<E> impleme
1120
1121		// other methods
1122
1123	<	public Object clone() {
1123	>	public ReadMostlyVector<E> clone() {
1124		SequenceLock lock = this.lock;
1125		Object[] a = null;
1046	–	int c;
1126		boolean retry = false;
1127		long seq = lock.awaitAvailability();
1128		Object[] items = array;
1129	<	c = count;
1130	<	if (c <= items.length)
1131	<	a = Arrays.copyOf(items, c);
1129	>	int n = count;
1130	>	if (n <= items.length)
1131	>	a = Arrays.copyOf(items, n);
1132		else
1133		retry = true;
1134		if (retry || lock.getSequence() != seq) {
1135		lock.lock();
1136		try {
1137	<	c = count;
1138	<	a = Arrays.copyOf(array, c);
1137	>	n = count;
1138	>	a = Arrays.copyOf(array, n);
1139		} finally {
1140		lock.unlock();
1141		}
1142		}
1143	<	return new ReadMostlyVector(a, c, capacityIncrement);
1143	>	return new ReadMostlyVector<E>(a, n, capacityIncrement);
1144		}
1145
1146		private void writeObject(java.io.ObjectOutputStream s)
#	Line 1084 | Line 1163 | public class ReadMostlyVector<E> impleme
1163		int cursor;
1164		int fence;
1165		int lastRet;
1166	<	boolean haveNext, havePrev;
1166	>	boolean validNext, validPrev;
1167
1168		Itr(ReadMostlyVector<E> list, int index) {
1169		this.list = list;
#	Line 1097 | Line 1176 | public class ReadMostlyVector<E> impleme
1176		}
1177
1178		private void refresh() {
1179	+	validNext = validPrev = false;
1180		do {
1181		seq = lock.awaitAvailability();
1182		items = list.array;
1183	<	fence = list.count;
1184	<	} while (lock.getSequence() != seq);
1183	>	} while ((fence = list.count) > items.length ||
1184	>	lock.getSequence() != seq);
1185		}
1186
1187		public boolean hasNext() {
1188	+	boolean valid;
1189		int i = cursor;
1190	<	while (i < fence && i >= 0) {
1190	>	for (;;) {
1191	>	if (i >= fence || i < 0 || i >= items.length) {
1192	>	valid = false;
1193	>	break;
1194	>	}
1195	>	next = items[i];
1196		if (lock.getSequence() == seq) {
1197	<	next = items[i];
1198	<	return haveNext = true;
1197	>	valid = true;
1198	>	break;
1199		}
1200		refresh();
1201		}
1202	<	return false;
1202	>	return validNext = valid;
1203		}
1204
1205		public boolean hasPrevious() {
1206	<	int i = cursor;
1207	<	while (i <= fence && i > 0) {
1206	>	boolean valid;
1207	>	int i = cursor - 1;
1208	>	for (;;) {
1209	>	if (i >= fence || i < 0 || i >= items.length) {
1210	>	valid = false;
1211	>	break;
1212	>	}
1213	>	prev = items[i];
1214		if (lock.getSequence() == seq) {
1215	<	prev = items[i - 1];
1216	<	return havePrev = true;
1215	>	valid = true;
1216	>	break;
1217		}
1218		refresh();
1219		}
1220	<	return false;
1220	>	return validPrev = valid;
1221		}
1222
1223		public E next() {
1224	<	if (!haveNext && !hasNext())
1225	<	throw new NoSuchElementException();
1226	<	haveNext = false;
1227	<	lastRet = cursor++;
1228	<	return (E) next;
1224	>	if (validNext || hasNext()) {
1225	>	validNext = false;
1226	>	lastRet = cursor++;
1227	>	return (E) next;
1228	>	}
1229	>	throw new NoSuchElementException();
1230		}
1231
1232		public E previous() {
1233	<	if (!havePrev && !hasPrevious())
1234	<	throw new NoSuchElementException();
1235	<	havePrev = false;
1236	<	lastRet = cursor--;
1237	<	return (E) prev;
1233	>	if (validPrev || hasPrevious()) {
1234	>	validPrev = false;
1235	>	lastRet = cursor--;
1236	>	return (E) prev;
1237	>	}
1238	>	throw new NoSuchElementException();
1239		}
1240
1241		public void remove() {
#	Line 1217 | Line 1311 | public class ReadMostlyVector<E> impleme
1311		lock.lock();
1312		try {
1313		int c = size;
1314	<	list.internalAddAt(c + offset, element);
1314	>	list.rawAddAt(c + offset, element);
1315		size = c + 1;
1316		} finally {
1317		lock.unlock();
#	Line 1231 | Line 1325 | public class ReadMostlyVector<E> impleme
1325		try {
1326		if (index < 0 || index > size)
1327		throw new ArrayIndexOutOfBoundsException(index);
1328	<	list.internalAddAt(index + offset, element);
1328	>	list.rawAddAt(index + offset, element);
1329		++size;
1330		} finally {
1331		lock.unlock();
#	Line 1246 | Line 1340 | public class ReadMostlyVector<E> impleme
1340		try {
1341		int s = size;
1342		int pc = list.count;
1343	<	list.internalAddAllAt(offset + s, elements);
1343	>	list.rawAddAllAt(offset + s, elements);
1344		added = list.count - pc;
1345		size = s + added;
1346		} finally {
#	Line 1265 | Line 1359 | public class ReadMostlyVector<E> impleme
1359		if (index < 0 || index > s)
1360		throw new ArrayIndexOutOfBoundsException(index);
1361		int pc = list.count;
1362	<	list.internalAddAllAt(index + offset, elements);
1362	>	list.rawAddAllAt(index + offset, elements);
1363		added = list.count - pc;
1364		size = s + added;
1365		} finally {
#	Line 1278 | Line 1372 | public class ReadMostlyVector<E> impleme
1372		SequenceLock lock = list.lock;
1373		lock.lock();
1374		try {
1375	<	list.internalClear(offset, size);
1375	>	list.internalClear(offset, offset + size);
1376		size = 0;
1377		} finally {
1378		lock.unlock();
#	Line 1290 | Line 1384 | public class ReadMostlyVector<E> impleme
1384		}
1385
1386		public boolean containsAll(Collection<?> c) {
1387	<	return list.internalContainsAll(c, offset, size);
1387	>	return list.internalContainsAll(c, offset, offset + size);
1388		}
1389
1390		public boolean equals(Object o) {
#	Line 1298 | Line 1392 | public class ReadMostlyVector<E> impleme
1392		return true;
1393		if (!(o instanceof List))
1394		return false;
1395	<	return list.internalEquals((List<?>)(o), offset, size);
1395	>	return list.internalEquals((List<?>)(o), offset, offset + size);
1396		}
1397
1398		public E get(int index) {
#	Line 1308 | Line 1402 | public class ReadMostlyVector<E> impleme
1402		}
1403
1404		public int hashCode() {
1405	<	return list.internalHashCode(offset, size);
1405	>	return list.internalHashCode(offset, offset + size);
1406		}
1407
1408		public int indexOf(Object o) {
#	Line 1317 | Line 1411 | public class ReadMostlyVector<E> impleme
1411		Object[] items = list.array;
1412		int c = list.count;
1413		if (c <= items.length) {
1414	<	int idx = internalIndexOf(o, items, offset, offset+size);
1414	>	int idx = list.validatedIndexOf(o, items, offset,
1415	>	offset + size, seq);
1416		if (lock.getSequence() == seq)
1417		return idx < 0 ? -1 : idx - offset;
1418		}
1419		lock.lock();
1420		try {
1421	<	int idx = internalIndexOf(o, list.array, offset, offset+size);
1421	>	int idx = list.rawIndexOf(o, offset, offset + size);
1422		return idx < 0 ? -1 : idx - offset;
1423		} finally {
1424		lock.unlock();
#	Line 1335 | Line 1430 | public class ReadMostlyVector<E> impleme
1430		}
1431
1432		public Iterator<E> iterator() {
1433	<	return new SubItr(this, offset);
1433	>	return new SubItr<E>(this, offset);
1434		}
1435
1436		public int lastIndexOf(Object o) {
#	Line 1344 | Line 1439 | public class ReadMostlyVector<E> impleme
1439		Object[] items = list.array;
1440		int c = list.count;
1441		if (c <= items.length) {
1442	<	int idx = internalLastIndexOf(o, items, offset+size-1, offset);
1442	>	int idx = list.validatedLastIndexOf(o, items, offset+size-1,
1443	>	offset, seq);
1444		if (lock.getSequence() == seq)
1445		return idx < 0 ? -1 : idx - offset;
1446		}
1447		lock.lock();
1448		try {
1449	<	int idx = internalLastIndexOf(o, list.array, offset+size-1,
1354	<	offset);
1449	>	int idx = list.rawLastIndexOf(o, offset + size - 1, offset);
1450		return idx < 0 ? -1 : idx - offset;
1451		} finally {
1452		lock.unlock();
#	Line 1359 | Line 1454 | public class ReadMostlyVector<E> impleme
1454		}
1455
1456		public ListIterator<E> listIterator() {
1457	<	return new SubItr(this, offset);
1457	>	return new SubItr<E>(this, offset);
1458		}
1459
1460		public ListIterator<E> listIterator(int index) {
1461	<	return new SubItr(this, index + offset);
1461	>	return new SubItr<E>(this, index + offset);
1462		}
1463
1464		public E remove(int index) {
1465	<	E result;
1465	>	Object result;
1466		SequenceLock lock = list.lock;
1467		lock.lock();
1468		try {
1469	<	if (index < 0 || index >= size)
1375	<	throw new ArrayIndexOutOfBoundsException(index);
1469	>	Object[] items = list.array;
1470		int i = index + offset;
1471	<	result = (E)list.array[i];
1472	<	list.internalRemoveAt(i);
1471	>	if (index < 0 || index >= size || i >= items.length)
1472	>	throw new ArrayIndexOutOfBoundsException(index);
1473	>	result = items[i];
1474	>	list.rawRemoveAt(i);
1475		size--;
1476		} finally {
1477		lock.unlock();
1478		}
1479	<	return result;
1479	>	return (E)result;
1480		}
1481
1482		public boolean remove(Object o) {
#	Line 1388 | Line 1484 | public class ReadMostlyVector<E> impleme
1484		SequenceLock lock = list.lock;
1485		lock.lock();
1486		try {
1487	<	if (list.internalRemoveAt(internalIndexOf(o, list.array, offset,
1488	<	offset+size))) {
1487	>	if (list.rawRemoveAt(list.rawIndexOf(o, offset,
1488	>	offset + size))) {
1489		removed = true;
1490		--size;
1491		}
#	Line 1400 | Line 1496 | public class ReadMostlyVector<E> impleme
1496		}
1497
1498		public boolean removeAll(Collection<?> c) {
1499	<	return list.internalRemoveAll(c, offset, size);
1499	>	return list.internalRemoveAll(c, offset, offset + size);
1500		}
1501
1502		public boolean retainAll(Collection<?> c) {
1503	<	return list.internalRetainAll(c, offset, size);
1503	>	return list.internalRetainAll(c, offset, offset + size);
1504		}
1505
1506		public E set(int index, E element) {
#	Line 1422 | Line 1518 | public class ReadMostlyVector<E> impleme
1518		int ssize = toIndex - fromIndex;
1519		if (fromIndex < 0 || toIndex > c || ssize < 0)
1520		throw new IndexOutOfBoundsException();
1521	<	return new ReadMostlyVectorSublist(list, offset+fromIndex, ssize);
1521	>	return new ReadMostlyVectorSublist<E>(list, offset+fromIndex, ssize);
1522		}
1523
1524		public Object[] toArray() {
1525	<	return list.internalToArray(offset, size);
1525	>	return list.internalToArray(offset, offset + size);
1526		}
1527
1528		public <T> T[] toArray(T[] a) {
1529	<	return list.internalToArray(a, offset, size);
1529	>	return list.internalToArray(a, offset, offset + size);
1530		}
1531
1532		public String toString() {
1533	<	return list.internalToString(offset, size);
1533	>	return list.internalToString(offset, offset + size);
1534		}
1535
1536		}
#	Line 1449 | Line 1545 | public class ReadMostlyVector<E> impleme
1545		int cursor;
1546		int fence;
1547		int lastRet;
1548	<	boolean haveNext, havePrev;
1548	>	boolean validNext, validPrev;
1549
1550		SubItr(ReadMostlyVectorSublist<E> sublist, int index) {
1551		this.sublist = sublist;
#	Line 1463 | Line 1559 | public class ReadMostlyVector<E> impleme
1559		}
1560
1561		private void refresh() {
1562	+	validNext = validPrev = false;
1563		do {
1564	+	int n;
1565		seq = lock.awaitAvailability();
1566		items = list.array;
1567	<	int c = list.count;
1567	>	if ((n = list.count) > items.length)
1568	>	continue;
1569		int b = sublist.offset + sublist.size;
1570	<	fence = b < c ? b : c;
1570	>	fence = b < n ? b : n;
1571		} while (lock.getSequence() != seq);
1572		}
1573
1574		public boolean hasNext() {
1575	+	boolean valid;
1576		int i = cursor;
1577	<	while (i < fence && i >= 0) {
1577	>	for (;;) {
1578	>	if (i >= fence || i < 0 || i >= items.length) {
1579	>	valid = false;
1580	>	break;
1581	>	}
1582	>	next = items[i];
1583		if (lock.getSequence() == seq) {
1584	<	next = items[i];
1585	<	return haveNext = true;
1584	>	valid = true;
1585	>	break;
1586		}
1587		refresh();
1588		}
1589	<	return false;
1589	>	return validNext = valid;
1590		}
1591
1592		public boolean hasPrevious() {
1593	<	int i = cursor;
1594	<	while (i <= fence && i > 0) {
1593	>	boolean valid;
1594	>	int i = cursor - 1;
1595	>	for (;;) {
1596	>	if (i >= fence || i < 0 || i >= items.length) {
1597	>	valid = false;
1598	>	break;
1599	>	}
1600	>	prev = items[i];
1601		if (lock.getSequence() == seq) {
1602	<	prev = items[i - 1];
1603	<	return havePrev = true;
1602	>	valid = true;
1603	>	break;
1604		}
1605		refresh();
1606		}
1607	<	return false;
1607	>	return validPrev = valid;
1608		}
1609
1610		public E next() {
1611	<	if (!haveNext && !hasNext())
1612	<	throw new NoSuchElementException();
1613	<	haveNext = false;
1614	<	lastRet = cursor++;
1615	<	return (E) next;
1611	>	if (validNext || hasNext()) {
1612	>	validNext = false;
1613	>	lastRet = cursor++;
1614	>	return (E) next;
1615	>	}
1616	>	throw new NoSuchElementException();
1617		}
1618
1619		public E previous() {
1620	<	if (!havePrev && !hasPrevious())
1621	<	throw new NoSuchElementException();
1622	<	havePrev = false;
1623	<	lastRet = cursor--;
1624	<	return (E) prev;
1620	>	if (validPrev || hasPrevious()) {
1621	>	validPrev = false;
1622	>	lastRet = cursor--;
1623	>	return (E) prev;
1624	>	}
1625	>	throw new NoSuchElementException();
1626		}
1627
1628		public int nextIndex() {

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines