[concurrency-interest] RFR: CopyOnWriteArrayNavigableSet for Java 9

Dr Heinz M. Kabutz heinz at javaspecialists.eu
Thu Dec 31 05:16:12 EST 2015


May I ask why you made *CopyOnWriteArrayNavigableSet.addAll() *static, 
considering that you are always passing in "*this*" as a parameter?

Regards

Heinz
-- 
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion since 2005
JavaOne Rock Star Speaker 2012
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz



Dr Heinz M. Kabutz wrote:
> In your constructor that takes an Iterable, I would probably have the 
> last case first add the elements to an ArrayList and then add those to 
> with your clever addAll() bulk method:
>
>         } else {
>             this.comparator = (Comparator<? super E>) 
> Comparator.naturalOrder();
>             this.al = new CopyOnWriteArrayList<>();
>             if (c instanceof Collection) {
>                 CopyOnWriteArrayNavigableSet.addAll(this, 
> ((Collection) c));
>             } else {
> *                ArrayList<E> elements = new ArrayList<>();
>                 for(E e : c) {
>                     elements.add(e);
>                 }
>                 CopyOnWriteArrayNavigableSet.addAll(this, elements);*
>             }
>         }
>
> Regards
>
> Heinz
> -- 
> Dr Heinz M. Kabutz (PhD CompSci)
> Author of "The Java(tm) Specialists' Newsletter"
> Sun/Oracle Java Champion since 2005
> JavaOne Rock Star Speaker 2012
> http://www.javaspecialists.eu
> Tel: +30 69 75 595 262
> Skype: kabutz
>   
>
>
> Mike Duigou wrote:
>> Hello All;
>>
>> Enclosed is a new draft of the CopyOnWriteArrayNavigableSet 
>> implementation I have been working on for Java 9. This version 
>> incorporates review feedback from November and should be very nearly 
>> complete and ready for submission. It is not to late to provide 
>> feedback though, so if you have any comments or suggestions feel free 
>> to send them to this list.
>>
>> I am planning to post a standalone version of this class on github 
>> and probably will publish it as a maven package for use with Java 7 
>> and Java 8. This version will have he same class name and API but 
>> will be in a different package.
>>
>> Cheers,
>>
>> Mike
>>
>> ------------------------------------------------------------------------
>>
>> /* * Written by Doug Lea & Mike Duigou with assistance from members 
>> of JCP JSR-166 * Expert Group and released to the public domain, as 
>> explained at * http://creativecommons.org/publicdomain/zero/1.0/ */ 
>> package java.util.concurrent; import java.lang.reflect.Array; import 
>> java.util.Collection; import java.util.AbstractSet; import 
>> java.util.Arrays; import java.util.Collections; import 
>> java.util.Comparator; import java.util.Iterator; import 
>> java.util.List; import java.util.NavigableSet; import 
>> java.util.NoSuchElementException; import java.util.Objects; import 
>> java.util.SortedSet; import java.util.Spliterator; import 
>> java.util.Spliterators; import java.util.function.Predicate; import 
>> java.util.function.Consumer; /** * A {@link java.util.NavigableSet} 
>> that uses an internal {@link CopyOnWriteArrayList} * for all of its 
>> operations. Thus, it shares the same basic properties: *
>>
>>     * * It is best suited for applications in which set sizes
>>       generally * stay small, read-only operations * vastly outnumber
>>       mutative operations, and you need * to prevent interference
>>       among threads during traversal. *
>>     * It is thread-safe. *
>>     * Mutative operations ({@code add}, {@code set}, {@code remove},
>>       etc.) * are expensive since they usually entail copying the
>>       entire underlying * array. *
>>     * Iterators do not support the mutative {@code remove} operation. *
>>     * Traversal via iterators is fast and cannot encounter *
>>       interference from other threads. Iterators rely on * unchanging
>>       snapshots of the array at the time the iterators were *
>>       constructed. *
>>
>> * *
>>
>> *Sample Usage.* The following code sketch uses a * copy-on-write 
>> navigable set to maintain a set of ordered Handler objects that * 
>> perform some action upon state updates until one of the handlers 
>> returns * true indicating that the update has been handled. * *
>>
>>  {@code
>>  * class Handler implements Comparable {
>>  *   // returns true if update has been handled
>>  *   boolean handle();
>>  *
>>  *   // ordered from highest to lowest
>>  *   public int compareTo(Handler other) { return Integer.compare(priority, other.priority); }
>>  * }
>>  *
>>  * class X {
>>  *   // Will use "Natural Order" of Comparables
>>  *   private final CopyOnWriteArrayNavigableSet handlers
>>  *     = new CopyOnWriteArrayNavigableSet<>();
>>  *   public void addHandler(Handler h) { handlers.add(h); }
>>  *
>>  *   private long internalState;
>>  *   private synchronized void changeState() { internalState = ...; }
>>  *
>>  *   public void update() {
>>  *     changeState();
>>  *     for (Handler handler : handlers)
>>  *       if(handler.handle()) break;
>>  *   }
>>  * }}
>> * *
>>
>> This class is a member of the * * Java Collections Framework 
>> <%7B at docRoot%7D/../technotes/guides/collections/index.html>. * * @see 
>> CopyOnWriteArrayList * @since 9 * @author Doug Lea * @author Mike 
>> Duigou * @param the type of elements held in this collection */ 
>> public class CopyOnWriteArrayNavigableSet extends AbstractSet 
>> implements java.io.Serializable, NavigableSet { private static final 
>> long serialVersionUID = -3680134489612968105L; /** * Comparator for 
>> elements. */ final Comparator comparator; /** * Embedded 
>> CopyOnWriteArrayList used to hold the storage of this set. */ final 
>> CopyOnWriteArrayList al; /** * Creates a set using the provided 
>> comparator with the initial elements * of the provided COWAL. * * 
>> @param comparator * @param al */ 
>> CopyOnWriteArrayNavigableSet(Comparator comparator, 
>> CopyOnWriteArrayList al) { this.comparator = 
>> Objects.requireNonNull(comparator, "comparator"); this.al = al; } /** 
>> * Creates an empty set which can be used for mutually * {@link 
>> java.lang.Comparable Comparable} objects. */ 
>> @SuppressWarnings("unchecked") public CopyOnWriteArrayNavigableSet() 
>> { this((Comparator) Comparator.naturalOrder()); } /** * Creates an 
>> empty set with the specified comparator. * * @param comparator Used 
>> for ordering elements. For * {@link java.lang.Comparable Comparable} 
>> objects use * {@link Comparator#naturalOrder()} */ public 
>> CopyOnWriteArrayNavigableSet(Comparator comparator) { 
>> this(comparator, new CopyOnWriteArrayList<>()); } /** * Creates a set 
>> containing all of the elements of the specified * Iterable. If c is a 
>> {@link SortedSet sorted set} then the same * Comparator is used. * * 
>> @param c the elements to initially contain * @throws 
>> NullPointerException if the specified collection is null */ 
>> @SuppressWarnings("unchecked") public 
>> CopyOnWriteArrayNavigableSet(Iterable c) { if (c.getClass() == 
>> CopyOnWriteArrayNavigableSet.class) { this.comparator = 
>> ((CopyOnWriteArrayNavigableSet) c).comparator; this.al = new 
>> CopyOnWriteArrayList<>(); 
>> this.al.setArray(((CopyOnWriteArrayNavigableSet) c).al.getArray()); } 
>> else if (c instanceof SortedSet) { Comparator compare = ((SortedSet) 
>> c).comparator(); this.comparator = compare == null ? (Comparator) 
>> Comparator.naturalOrder() : compare; this.al = new 
>> CopyOnWriteArrayList<>(((SortedSet) c)); } else { this.comparator = 
>> (Comparator) Comparator.naturalOrder(); this.al = new 
>> CopyOnWriteArrayList<>(); if (c instanceof Collection) { 
>> CopyOnWriteArrayNavigableSet.addAll(this, ((Collection) c)); } else { 
>> for(E e : c) { add(this, e); } } } } /** * Creates a new empty 
>> CopyOnWriteArrayNavigableSet using natural order * ordering. * @param 
>> Type of elements * @return new CopyOnWriteArrayNavigableSet */ public 
>> static > CopyOnWriteArrayNavigableSet create() { return new 
>> CopyOnWriteArrayNavigableSet<>(); } /** * Creates a new 
>> CopyOnWriteArrayNavigableSet of the provided elements using * natural 
>> order ordering. * @param Type of elements * @param contents initial 
>> elements for the set. * @return new CopyOnWriteArrayNavigableSet */ 
>> public static > CopyOnWriteArrayNavigableSet create(Iterable 
>> contents) { return new CopyOnWriteArrayNavigableSet<>(contents); } 
>> /** * Creates a new empty CopyOnWriteArrayNavigableSet using provided 
>> * comparator for ordering. * @param Type of elements * @param 
>> comparator The comparator to use for ordering. * @return new 
>> CopyOnWriteArrayNavigableSet */ public static 
>> CopyOnWriteArrayNavigableSet create(Comparator comparator) { return 
>> new CopyOnWriteArrayNavigableSet<>(comparator); } @Override 
>> @SuppressWarnings("unchecked") public boolean contains(Object o) { 
>> return Arrays.binarySearch((E[]) al.getArray(), (E) o, comparator) >= 
>> 0; } @Override public boolean remove(Object o) { 
>> synchronized(al.lock) { @SuppressWarnings("unchecked") E[] array = 
>> (E[]) al.getArray(); @SuppressWarnings("unchecked") int loc = 
>> Arrays.binarySearch(array, (E) o, comparator); if(loc >= 0) { 
>> al.remove(loc); return true; } return false; } } @Override public 
>> boolean add(E e) { return add(this, e); } private static boolean 
>> add(CopyOnWriteArrayNavigableSet cowans, E e) { 
>> Objects.requireNonNull(e, "e"); synchronized(cowans.al.lock) { 
>> @SuppressWarnings("unchecked") E[] array = (E[]) 
>> cowans.al.getArray(); int loc = Arrays.binarySearch(array, e, 
>> cowans.comparator); if(loc < 0) { cowans.al.add(-1 - loc, e); return 
>> true; } return false; } } @Override @SuppressWarnings("unchecked") 
>> public boolean containsAll(Collection c) { 
>> @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); 
>> for(Object each : c) { if(Arrays.binarySearch(array, (E) each, 
>> comparator) < 0) { return false; } } return true; } @Override public 
>> boolean addAll(Collection c) { return 
>> CopyOnWriteArrayNavigableSet.addAll(this, c); } 
>> @SuppressWarnings("unchecked") private static boolean 
>> addAll(CopyOnWriteArrayNavigableSet cowans, Collection c) { Object[] 
>> cs = c.toArray(); if (cs.length == 0) return false; if(cs.length == 
>> 1) { return cowans.add((E) cs[0]); } synchronized (cowans.al.lock) { 
>> E[] array = (E[]) cowans.al.getArray(); int len = array.length; int 
>> added = 0; // uniquify and compact elements in cs for (int i = 0; i < 
>> cs.length; ++i) { Object e = Objects.requireNonNull(cs[i]); if 
>> (Arrays.binarySearch(array, (E) e, cowans.comparator) < 0) { int at = 
>> Arrays.binarySearch((E[]) cs, 0, added, (E) e, cowans.comparator); 
>> if(at < 0) { // insertion sort it into low portion of cs. at = -at - 
>> 1; //System.out.println( Arrays.asList(cs) + " len:" + cs.length + " 
>> e:" + e + " at:" + at + " added:" + added); System.arraycopy(cs, at, 
>> cs, at + 1, added++ - at); cs[at] = e; } } } if (added > 0) { 
>> Object[] newElements = (Object[]) 
>> Array.newInstance(array.getClass().getComponentType(), len + added); 
>> --len; --added; for(int i = newElements.length - 1; i >= 0; i--) { // 
>> merge into resulting array. Both array and cs are sorted. 
>> newElements[i] = len >= 0 && (added < 0 || 
>> cowans.comparator.compare(array[len], (E) cs[added]) > 0) ? 
>> array[len--] : cs[added--]; } cowans.al.setArray(newElements); return 
>> true; } return false; } } @Override public Iterator iterator() { 
>> return al.iterator(); } @Override public int size() { return 
>> al.size(); } @Override public boolean removeIf(Predicate filter) { 
>> return al.removeIf(filter); } @Override public void forEach(Consumer 
>> action) { al.forEach(action); } @Override public boolean 
>> retainAll(Collection c) { return al.retainAll(c); } @Override public 
>> boolean removeAll(Collection c) { return al.removeAll(c); } @Override 
>> public Object[] toArray() { return al.toArray(); } @Override public 
>> T[] toArray(T[] a) { return al.toArray(a); } @Override public void 
>> clear() { al.clear(); } /** * Returns a {@link Spliterator} over the 
>> elements in this set in the order * in which these elements were 
>> added. * *
>>
>> The {@code Spliterator} reports {@link Spliterator#ORDERED}, * {@link 
>> Spliterator#NONNULL}, {@link Spliterator#IMMUTABLE}, * {@link 
>> Spliterator#DISTINCT}, and {@link Spliterator#SIZED}. * *
>>
>> The spliterator provides a snapshot of the state of the set * when 
>> the spliterator was constructed. No synchronization is needed while * 
>> operating on the spliterator. * * @return a {@code Spliterator} over 
>> the elements in this set */ @Override public Spliterator 
>> spliterator() { return Spliterators.spliterator (al.getArray(), 
>> Spliterator.ORDERED | Spliterator.NONNULL | Spliterator.IMMUTABLE | 
>> Spliterator.DISTINCT); } // +---+---+---+---+ // | 2 | 4 | 6 | 8 | // 
>> +---+---+---+---+ // lower(0) = null // lower(2) = null // lower(3) = 
>> 2 // lower(8) = 6 // lower(9) = 8 @Override 
>> @SuppressWarnings("unchecked") public E lower(E e) { E[] array = 
>> (E[]) al.getArray(); int loc = Arrays.binarySearch(array, e, 
>> comparator); return loc > 0 ? array[loc - 1] : loc < -1 // zero or 
>> minus one means nothing strictly lower. ? array[-2 - loc] : null; } 
>> // +---+---+---+---+ // | 2 | 4 | 6 | 8 | // +---+---+---+---+ // 
>> floor(0) = null // floor(2) = 2 // floor(3) = 2 // floor(8) = 8 // 
>> floor(9) = 8 @Override @SuppressWarnings("unchecked") public E 
>> floor(E e) { E[] array = (E[]) al.getArray(); int loc = 
>> Arrays.binarySearch(array, e, comparator); return loc >= 0 ? 
>> array[loc] : loc < -1 // minus one means nothing matching or lower. ? 
>> array[-2 - loc] : null; } // +---+---+---+---+ // | 2 | 4 | 6 | 8 | 
>> // +---+---+---+---+ // ceiling(0) = 2 // ceiling(2) = 2 // 
>> ceiling(3) = 4 // ceiling(8) = 8 // ceiling(9) = null @Override 
>> @SuppressWarnings("unchecked") public E ceiling(E e) { E[] array = 
>> (E[]) al.getArray(); int loc = Arrays.binarySearch(array, e, 
>> comparator); return loc >= 0 ? array[loc] : -loc < array.length ? 
>> array[-1 - loc] : null; } // +---+---+---+---+ // | 2 | 4 | 6 | 8 | 
>> // +---+---+---+---+ // higher(0) = 2 // higher(2) = 4 // higher(3) = 
>> 4 // higher(8) = null // higher(9) = null @Override 
>> @SuppressWarnings("unchecked") public E higher(E e) { E[] array = 
>> (E[]) al.getArray(); int loc = Arrays.binarySearch(array, e, 
>> comparator); return loc >= 0 ? (loc < array.length - 1 ) ? array[loc 
>> + 1] : null : -loc < array.length ? array[-1 - loc] : null; } 
>> @Override public E pollFirst() { if(al.isEmpty()) return null; 
>> synchronized(al.lock) { if(al.isEmpty()) return null; E result = 
>> al.remove(0); return result; } } @Override public E pollLast() { 
>> if(al.isEmpty()) return null; synchronized(al.lock) { 
>> if(al.isEmpty()) return null; E result = al.remove(al.size() - 1); 
>> return result; } } @Override public NavigableSet descendingSet() { 
>> return new BoundedNavigableSet<>(comparator, al, false, null, false, 
>> false, null, false, true); } @Override @SuppressWarnings("unchecked") 
>> public Iterator descendingIterator() { final Object[] array = 
>> al.getArray(); return array.length == 0 ? Collections.emptyIterator() 
>> : new Iterator() { int index = array.length - 1; @Override public 
>> boolean hasNext() { return index >= 0; } @Override public E next() { 
>> if (hasNext()) { return (E) array[index--]; } else { throw new 
>> NoSuchElementException(); } } }; } @Override public NavigableSet 
>> subSet(E fromElement, boolean fromInclusive, E toElement, boolean 
>> toInclusive) { return new BoundedNavigableSet<>(comparator, al, true, 
>> fromElement, fromInclusive, true, toElement, toInclusive, false); } 
>> @Override public NavigableSet headSet(E toElement, boolean inclusive) 
>> { return new BoundedNavigableSet<>(comparator, al, false, null, 
>> false, true, toElement, inclusive, false); } @Override public 
>> NavigableSet tailSet(E fromElement, boolean inclusive) { return new 
>> BoundedNavigableSet<>(comparator, al, true, fromElement, inclusive, 
>> false, null, false, false); } @Override public SortedSet subSet(E 
>> fromElement, E toElement) { return subSet(fromElement, true, 
>> toElement, false); } @Override public SortedSet headSet(E toElement) 
>> { return headSet(toElement, false); } @Override public SortedSet 
>> tailSet(E fromElement) { return tailSet(fromElement, true); } 
>> @Override public Comparator comparator() { return comparator; } 
>> @Override public E first() { if(al.isEmpty()) throw new 
>> NoSuchElementException(); @SuppressWarnings("unchecked") E[] array = 
>> (E[]) al.getArray(); if(array.length == 0) throw new 
>> NoSuchElementException(); return array[0]; } @Override public E 
>> last() { if(al.isEmpty()) throw new NoSuchElementException(); 
>> @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); 
>> if(array.length == 0) throw new NoSuchElementException(); return 
>> array[array.length - 1]; } private static class BoundedNavigableSet 
>> extends CopyOnWriteArrayNavigableSet { private static final long 
>> serialVersionUID = 3830104881368453055L; /** * If true then iteration 
>> is done in descending order. */ final boolean descending; /** * If 
>> true then a lower bound relative to the super set. */ final boolean 
>> lowerBounded; /** * If true then we have an upper bound relative to 
>> the super set. */ final boolean upperBounded; /** * If true then the 
>> lower bound is included in the set. */ final boolean lowerInclusive; 
>> /** * If true then the upper bound is included in the set. */ final 
>> boolean upperInclusive; /** * The value of the lower bound. */ final 
>> E lowerBound; /** * The value of the upper bound. */ final E 
>> upperBound; @SuppressWarnings("unchecked") public 
>> BoundedNavigableSet( Comparator comparator, CopyOnWriteArrayList al, 
>> boolean lowerBounded, E fromElement, boolean lowerInclusive, boolean 
>> upperBounded, E toElement, boolean upperInclusive, boolean 
>> descending) { super(comparator, al); this.descending = descending; if 
>> (lowerBounded && upperBounded) { int fromCompared = 
>> Integer.signum(comparator.compare(fromElement,toElement)); int 
>> toCompared = 
>> Integer.signum(comparator.compare(toElement,fromElement)); 
>> if(fromCompared != -toCompared) { throw new 
>> IllegalArgumentException("inconsistent comparator"); } if 
>> (!descending) { if (fromCompared > 0) { throw new 
>> IllegalArgumentException("upper < lower"); } } else { if 
>> (fromCompared < 0) { throw new IllegalArgumentException("upper < 
>> lower"); } } } this.lowerBounded = lowerBounded; this.lowerBound = 
>> fromElement; this.lowerInclusive = lowerInclusive; this.upperBounded 
>> = upperBounded; this.upperBound = toElement; this.upperInclusive = 
>> upperInclusive; } @Override public boolean add(E e) { return 
>> super.add(inBounds(e)); } @Override @SuppressWarnings("unchecked") 
>> public boolean contains(Object o) { return checkInBounds((E) o) && 
>> super.contains(o); } @Override @SuppressWarnings("unchecked") public 
>> Comparator comparator() { return (Comparator) (descending ? 
>> comparator.reversed() : comparator); } @Override public NavigableSet 
>> descendingSet() { return new BoundedNavigableSet<>( comparator, al, 
>> upperBounded, upperBound, upperInclusive, lowerBounded, lowerBound, 
>> lowerInclusive, !descending); } @Override public NavigableSet 
>> subSet(E fromElement, boolean fromInclusive, E toElement, boolean 
>> toInclusive) { return new BoundedNavigableSet<>( comparator, al, 
>> true, inBounds(fromElement), fromInclusive, true, 
>> inBounds(toElement), toInclusive, descending); } @Override public 
>> NavigableSet headSet(E toElement, boolean inclusive) { return new 
>> BoundedNavigableSet<>( comparator, al, lowerBounded, lowerBound, 
>> lowerInclusive, true, inBounds(toElement), inclusive, descending); } 
>> @Override public NavigableSet tailSet(E fromElement, boolean 
>> inclusive) { return new BoundedNavigableSet<>( comparator, al, true, 
>> inBounds(fromElement), inclusive, upperBounded, upperBound, 
>> upperInclusive, descending); } @Override public SortedSet subSet(E 
>> fromElement, E toElement) { return subSet(fromElement, true, 
>> toElement, false); } @Override public SortedSet headSet(E toElement) 
>> { return headSet(toElement, false); } @Override public SortedSet 
>> tailSet(E fromElement) { return tailSet(fromElement, true); } private 
>> E inBounds(E element) { if (lowerBounded) { if (lowerInclusive) { if 
>> (comparator.compare(lowerBound,element) > 0) { throw new 
>> IllegalArgumentException("out of bounds: " + element + " < " + 
>> lowerBound); } } else { if (comparator.compare(lowerBound, element) 
>> >= 0) { throw new IllegalArgumentException("out of bounds: " + 
>> element + " <= " + lowerBound); } } } if (upperBounded) { if 
>> (upperInclusive) { if (comparator.compare(upperBound, element) < 0) { 
>> throw new IllegalArgumentException("out of bounds: " + element + " > 
>> " + upperBound); } } else { if (comparator.compare(upperBound, 
>> element) <= 0) { throw new IllegalArgumentException("out of bounds: " 
>> + element + " >= " + upperBound); } } } return element; } private 
>> boolean checkInBounds(E element) { if (lowerBounded) { if 
>> (lowerInclusive) { if (comparator.compare(lowerBound,element) > 0) { 
>> return false; } } else { if (comparator.compare(lowerBound, element) 
>> >= 0) { return false; } } } if (upperBounded) { if (upperInclusive) { 
>> if (comparator.compare(upperBound, element) < 0) { return false; } } 
>> else { if (comparator.compare(upperBound, element) <= 0) { return 
>> false; } } } return true; } @Override public Iterator 
>> descendingIterator() { return makeIterator(!descending); } @Override 
>> public void forEach(Consumer action) { Objects.requireNonNull(action, 
>> "action"); @SuppressWarnings("unchecked") E[] array = (E[]) 
>> al.getArray(); int start = fromLoc(array); int end = toLoc(array); 
>> for(int each=start;each filter) { Objects.requireNonNull(filter, 
>> "filter"); synchronized(al.lock) { @SuppressWarnings("unchecked") E[] 
>> array = (E[]) al.getArray(); int start = fromLoc(array); int end = 
>> toLoc(array); return al.subList(start, end).removeIf(filter); } } 
>> @Override public boolean retainAll(Collection c) { 
>> synchronized(al.lock) { @SuppressWarnings("unchecked") E[] array = 
>> (E[]) al.getArray(); int start = fromLoc(array); int end = 
>> toLoc(array); return al.subList(start, end).retainAll(c); } } 
>> @Override public boolean removeAll(Collection c) { 
>> synchronized(al.lock) { @SuppressWarnings("unchecked") E[] array = 
>> (E[]) al.getArray(); int start = fromLoc(array); int end = 
>> toLoc(array); return al.subList(start, end).removeAll(c); } } 
>> @Override public boolean addAll(Collection c) { for (E e : c) 
>> inBounds(e); return CopyOnWriteArrayNavigableSet.addAll(this, c); } 
>> @Override @SuppressWarnings("unchecked") public boolean 
>> containsAll(Collection c) { E[] array = (E[]) al.getArray(); int 
>> start = fromLoc(array); int end = toLoc(array); for (Object each : c) 
>> { if (Arrays.binarySearch(array, start, end, (E) each, comparator) < 
>> 0) { return false; } } return true; } @Override 
>> @SuppressWarnings("unchecked") public boolean remove(Object o) { 
>> return checkInBounds((E) o) && super.remove(o); } @Override public 
>> void clear() { synchronized(al.lock) { @SuppressWarnings("unchecked") 
>> E[] array = (E[]) al.getArray(); int start = fromLoc(array); int end 
>> = toLoc(array); al.removeRange(start, end); } } 
>> @SuppressWarnings("unchecked") private int fromLoc(E[] array) { int 
>> start; if(lowerBounded) { start = Arrays.binarySearch(array, 
>> lowerBound, comparator == null ? descending ? (Comparator) 
>> Comparator.reverseOrder() : null : descending ? comparator.reversed() 
>> : comparator); start = start >= 0 ? lowerInclusive ? start : start + 
>> 1 : -1 - start; } else { start = 0; } return start; } 
>> @SuppressWarnings("unchecked") private int toLoc(E[] array) { int 
>> end; if(upperBounded) { end = Arrays.binarySearch(array, upperBound, 
>> descending ? comparator.reversed() : comparator); end = end >= 0 ? 
>> upperInclusive ? end + 1 : end : -1 - end; } else { end = 
>> array.length; } return end; } @Override public T[] toArray(T[] a) { 
>> return makeArray(a, descending); } @SuppressWarnings("unchecked") 
>> public T[] makeArray(T[] a, boolean inDescending) { E[] array = (E[]) 
>> al.getArray(); int start = fromLoc(array); int end = toLoc(array); 
>> int len = end - start; if (a.length < len) { a = (T[]) 
>> Array.newInstance(a.getClass().getComponentType(), len); } 
>> System.arraycopy(array, start, a, 0, len); if(len < a.length) a[len] 
>> = null; if(inDescending) 
>> Collections.reverse(Arrays.asList(a).subList(0, len)); return a; } 
>> @Override public Object[] toArray() { return makeArray(new Object[0], 
>> descending); } @Override public Iterator iterator() { return 
>> makeIterator(descending); } @SuppressWarnings("unchecked") private 
>> Iterator makeIterator(boolean inDescending) { List asList; 
>> if(inDescending) { asList = Arrays.asList((E[]) makeArray(new 
>> Object[0], inDescending)); } else { E[] array = (E[]) al.getArray(); 
>> int start = fromLoc(array); int end = toLoc(array); asList = 
>> Arrays.asList(array).subList(start, end); } return 
>> Collections.unmodifiableList(asList).iterator(); } @Override public 
>> int size() { @SuppressWarnings("unchecked") E[] array = (E[]) 
>> al.getArray(); return toLoc(array) - fromLoc(array); } @Override 
>> @SuppressWarnings("unchecked") public E lower(E e) { E result = 
>> descending ? super.higher(e) : super.lower(e); return result != null 
>> && checkInBounds(result) ? result : null; } @Override 
>> @SuppressWarnings("unchecked") public E floor(E e) { E result = 
>> descending ? super.ceiling(e) : super.floor(e); return result != null 
>> && checkInBounds(result) ? result : null; } @Override 
>> @SuppressWarnings("unchecked") public E ceiling(E e) { E result = 
>> descending ? super.floor(e) : super.ceiling(e); return result != null 
>> && checkInBounds(result) ? result : null; } @Override 
>> @SuppressWarnings("unchecked") public E higher(E e) { E result = 
>> descending ? super.lower(e) : super.higher(e); return result != null 
>> && checkInBounds(result) ? result : null; } @Override public E 
>> pollFirst() { return descending ? doPollLast() : doPollFirst(); } 
>> private E doPollFirst() { if(lowerBounded) synchronized(al.lock) { E 
>> remove = lowerInclusive ? floor(lowerBound) : higher(lowerBound); 
>> if(null != remove) { super.remove(remove); } return remove; } else 
>> return super.pollFirst(); } @Override public E pollLast() { return 
>> descending ? doPollFirst() : doPollLast(); } private E doPollLast() { 
>> if(upperBounded) synchronized(al.lock) { E remove = upperInclusive ? 
>> floor(upperBound) : lower(upperBound); if(null != remove) { 
>> super.remove(remove); } return remove; } else return 
>> super.pollLast(); } @Override public E first() { return descending ? 
>> doLast() : doFirst(); } private E doFirst() { E result = 
>> lowerInclusive ? ceiling(lowerBound) : higher(lowerBound); if(null == 
>> result) { throw new NoSuchElementException(); } return result; } 
>> @Override public E last() { return descending ? doFirst() : doLast(); 
>> } private E doLast() { E result = upperInclusive ? floor(upperBound) 
>> : lower(upperBound); if(null == result) { throw new 
>> NoSuchElementException(); } return result; } @Override public 
>> Spliterator spliterator() { @SuppressWarnings("unchecked") E[] array 
>> = (E[]) al.getArray(); return Spliterators.spliterator( array, 
>> fromLoc(array), toLoc(array), Spliterator.ORDERED | 
>> Spliterator.NONNULL | Spliterator.IMMUTABLE | Spliterator.DISTINCT); 
>> } } }
>>
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> Concurrency-interest at cs.oswego.edu
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>   
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20151231/48944f3d/attachment-0001.html>


More information about the Concurrency-interest mailing list