RFR: CopyOnWriteArrayNavigableSet for Java 9

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

RFR: CopyOnWriteArrayNavigableSet for Java 9

Mike Duigou
Hello all;

Enclosed is an initial draft of the new NavigableSet implementation I
have been working on. Despite the late hour I would still like to pursue
inclusion of this feature into Java 9.

The implementation is significantly based upon the existing
CopyOnWriteArraySet implementation and is an entirely "vanilla"
NavigableSet implementation in that it implements no methods not part of
the NavigableSet interface. The only major area of work is in the
handling of subsets which COWAS did not have to handle.

I have been testing by using the existing Java Collections tests.
Extending those tests to support this new implementation was mostly a
matter of adding the new class to the lists of collections
implementations to test--I searched for both CopyOnWriteArraySet and
ConcurrentSkipListMap amongst the tests and added
CopyOnWriteArrayNavigableSet where appropriate. I can provide the
patches for anyone who is interested.

Because the spec work for this proposed change is trivial and the
testing is well covered I believe it is still feasible to consider this
proposal for Java 9.

Thanks to Paul Sandoz for his review comments on earlier drafts of this
implementation.

Comments, corrections and suggestions welcome.

Thanks,

Mike
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

CopyOnWriteArrayNavigableSet.java (53K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: RFR: CopyOnWriteArrayNavigableSet for Java 9

Justin Sampson
Neat! I just took a quick skim through. It's nice how it mostly just delegates to the CopyOnWriteArrayList, which is kept in sorted order. One concern I have is the definition of equals(), which is inconsistent with the contract of Set and therefore not symmetric with regard to other Set implementations. It should just check that the two sets contain the same elements, ignoring order.

Cheers,
Justin


-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Mike Duigou
Sent: Tuesday, November 17, 2015 3:44 PM
To: Concurrency Interest
Subject: [concurrency-interest] RFR: CopyOnWriteArrayNavigableSet for Java 9

Hello all;

Enclosed is an initial draft of the new NavigableSet implementation I
have been working on. Despite the late hour I would still like to pursue
inclusion of this feature into Java 9.

The implementation is significantly based upon the existing
CopyOnWriteArraySet implementation and is an entirely "vanilla"
NavigableSet implementation in that it implements no methods not part of
the NavigableSet interface. The only major area of work is in the
handling of subsets which COWAS did not have to handle.

I have been testing by using the existing Java Collections tests.
Extending those tests to support this new implementation was mostly a
matter of adding the new class to the lists of collections
implementations to test--I searched for both CopyOnWriteArraySet and
ConcurrentSkipListMap amongst the tests and added
CopyOnWriteArrayNavigableSet where appropriate. I can provide the
patches for anyone who is interested.

Because the spec work for this proposed change is trivial and the
testing is well covered I believe it is still feasible to consider this
proposal for Java 9.

Thanks to Paul Sandoz for his review comments on earlier drafts of this
implementation.

Comments, corrections and suggestions welcome.

Thanks,

Mike

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: RFR: CopyOnWriteArrayNavigableSet for Java 9

Mike Duigou
Thanks Justin;

You are correct about equals(). I constant forget that SortedSet doesn't
refine the equals definition as it probably should have.

I've done some refactoring on the implementation to have it extend
CopyOnWriteArraySet which eliminates a lot of duplicated code. Once I
have finished testing it I will post an update to this list.

Thanks!

Mike

On 2015-11-17 16:45, Justin Sampson wrote:

> Neat! I just took a quick skim through. It's nice how it mostly just
> delegates to the CopyOnWriteArrayList, which is kept in sorted order.
> One concern I have is the definition of equals(), which is
> inconsistent with the contract of Set and therefore not symmetric with
> regard to other Set implementations. It should just check that the two
> sets contain the same elements, ignoring order.
>
> Cheers,
> Justin
>
>
> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf Of Mike
> Duigou
> Sent: Tuesday, November 17, 2015 3:44 PM
> To: Concurrency Interest
> Subject: [concurrency-interest] RFR: CopyOnWriteArrayNavigableSet for
> Java 9
>
> Hello all;
>
> Enclosed is an initial draft of the new NavigableSet implementation I
> have been working on. Despite the late hour I would still like to
> pursue
> inclusion of this feature into Java 9.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: RFR: CopyOnWriteArrayNavigableSet for Java 9

Mike Duigou
In reply to this post by Mike Duigou
Hello all;

As promised here is an update to my CopyOnWriteArrayNavigableSet
implementation. Thanks to those who have already provided feedback. The
implementation is better because of it.

This version eliminates a lot of the commonality with
CopyOnWriteArraySet by extending CopyOnWriteArraySet rather than
extending only AbstractSet. A few changes were required to
CopyOnWriteArraySet to properly support extension so I am now providing
a patch for review (vs. jdk9-dev) rather than the Java source file.

Mike

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: RFR: CopyOnWriteArrayNavigableSet for Java 9

Mike Duigou
In reply to this post by Mike Duigou
Hello all;


Here's the missing attachment.

One piece of feedback that I have received from several people is that
they would prefer if COWANS did not extend COWAS. Originally the
implementation did not but I have done so in this most recent patch. The
primary concern is that tying the implementations together via
inheritance reduces future flexibility for COWANS optimization and
refactoring. Opinions from others?

Mike
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

CopyOnWriteArrayNavigableSet.patch (56K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: RFR: CopyOnWriteArrayNavigableSet for Java 9

Chris Povirk
Just one point from some black-box testing: emptySet.addAll(singleNullElement) will insert the null element into the set, even if the Comparator does not support it. More generally, it looks like you intend to forbid nulls, regardless of the Comparator. If this is the case, can you add docs?

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: RFR: CopyOnWriteArrayNavigableSet for Java 9

Peter Levart


On 11/23/2015 04:40 PM, Chris Povirk wrote:
Just one point from some black-box testing: emptySet.addAll(singleNullElement) will insert the null element into the set, even if the Comparator does not support it. More generally, it looks like you intend to forbid nulls, regardless of the Comparator. If this is the case, can you add docs?

One idea for adding 'e' to empty set is to:

- when using comparator, call comparator.compare(e, e);
- when using Comparable, call Objects.requireNonNull((Comparable) e);

This would trigger CCE or NPE in case 'e' is not of correct type for comparator or null when comparator doesn't support nulls or not Comparable or null when there's no comparator.

There's no reason to not allow null elements when using comparator that supports them?

Regards, Peter



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: RFR: CopyOnWriteArrayNavigableSet for Java 9

Mike Duigou
I've made some changes which will address this addAll() case.

Not supporting nulls is for a couple reasons;
- none of the other java.util.concurrent Sets support them.
- Handling some of the cases of sub-sets when nulls are involved would
require extra work. It is the usual problem of telling whether a null
return means absent or a null value. I had included "// XXX needs to
handle null" in a bunch of places as I was writing the original code and
in my original review drafts but the Java 9 deadlines have caught up
with me and so I abandoned plans to support null when using a Comparator
that allows null.
- I don't like nulls in Collections. Seriously they are a PITA and the
extra code to handle them often makes the general case slower.

That's perhaps a little stronger than I actually believe. :-) With an
unrestricted schedule I probably would have included null element
support.

Mike

On 2015-11-23 12:58, Peter Levart wrote:
> On 11/23/2015 04:40 PM, Chris Povirk wrote:
>
>> Just one point from some black-box testing:
>> emptySet.addAll(singleNullElement) will insert the null element into
>> the set, even if the Comparator does not support it.

>  There's no reason to not allow null elements when using comparator
> that supports them?
>
>  Regards, Peter

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: RFR: CopyOnWriteArrayNavigableSet for Java 9

Peter Levart


On 11/24/2015 05:37 AM, Mike Duigou wrote:

> I've made some changes which will address this addAll() case.
>
> Not supporting nulls is for a couple reasons;
> - none of the other java.util.concurrent Sets support them.
> - Handling some of the cases of sub-sets when nulls are involved would
> require extra work. It is the usual problem of telling whether a null
> return means absent or a null value. I had included "// XXX needs to
> handle null" in a bunch of places as I was writing the original code
> and in my original review drafts but the Java 9 deadlines have caught
> up with me and so I abandoned plans to support null when using a
> Comparator that allows null.
> - I don't like nulls in Collections. Seriously they are a PITA and the
> extra code to handle them often makes the general case slower.
>
> That's perhaps a little stronger than I actually believe. :-) With an
> unrestricted schedule I probably would have included null element
> support.
>

No, you're right. Methods that return null to signal the absence of an
element are enough of an argument to restrict support to non-null
elements. And NavigableSet has such methods.

Regards, Peter

>
> On 2015-11-23 12:58, Peter Levart wrote:
>> On 11/23/2015 04:40 PM, Chris Povirk wrote:
>>
>>> Just one point from some black-box testing:
>>> emptySet.addAll(singleNullElement) will insert the null element into
>>> the set, even if the Comparator does not support it.
>
>>  There's no reason to not allow null elements when using comparator
>> that supports them?
>>
>>  Regards, Peter
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: RFR: CopyOnWriteArrayNavigableSet for Java 9

Dr Heinz M. Kabutz
In reply to this post by Mike Duigou
A few small comments:

1. In the JavaDoc comment, probably use &lt;Handler> instead of <Handler>

2. I would probably delegate to the Integer.compare(int, int) method in your Handler:
 public int compareTo(Handler other) { return Integer.compare(priority, other.priority); } - otherwise we might get overflows resulting in incorrect comparisons.

3. Inside class X in the JavaDocs, use the diamond operator:
 *   private final CopyOnWriteArrayNavigableSet&lt;Handler> handlers
 *     = new CopyOnWriteArrayNavigableSet&lt;>();

4. Unless there is a compelling reason, I would make both comparator and al fields private.  Inside your BoundedNavigableSet you could then access these with super.comparator and super.al.  IMHO always better to start off as private as possible with a new class.

5. I would make the internal constructor also private:
    private CopyOnWriteArrayNavigableSet(Comparator<E> comparator, CopyOnWriteArrayList<E> al) {...}

6. Where you use the wrapped COWArrayList for locking, instead of synchronized(super.al.lock), it would probably be better to do the following (e.g. remove(Object o):

    @Override
    public boolean remove(Object o) {
        al.lock.lock();
        try {
            @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;
        } finally {
            al.lock.unlock();
        }
    }

7. I dislike turning off unchecked warnings.  Just a personal preference.  I know sometimes you cannot get around it.  In your constructor, we might have missed something that could cause potential ClassCastExceptions.  For example, try the following code:

public class COWANSTest {
    static class A {
    }

    static class B extends A implements Comparable<B> {
        int i;

        public B(int i) {
            this.i = i;
        }

        @Override
        public int compareTo(B that) {
            return Integer.compare(i, that.i);
        }
    }

    public static void main(String... args) {
        CopyOnWriteArrayNavigableSet<B> bs = new CopyOnWriteArrayNavigableSet<>();
        bs.add(new B(42));
        CopyOnWriteArrayNavigableSet<A> cows = new CopyOnWriteArrayNavigableSet<>(bs);
        cows.add(new A());

    }
}

It compiles fine, but of course when you run it we get a ClassCastException, because the comparator is of the wrong type.  I would probably change the constructor into three, thus

    @SuppressWarnings("unchecked")
    public CopyOnWriteArrayNavigableSet(Collection<? extends E> 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) {
            this.comparator = ((SortedSet) c).comparator();
            this.al = new CopyOnWriteArrayList<>(c);
        } else {
            this.comparator = null;
            this.al = new CopyOnWriteArrayList<>();
            CopyOnWriteArrayNavigableSet.addAll(this, c);
        }
    }

becomes:

    /**
     * Creates a set containing all of the elements of the specified
     * collection, assuming natural ordering.
     *
     * @param c the collection of elements to initially contain
     * @throws NullPointerException if the specified collection is null
     */
    public CopyOnWriteArrayNavigableSet(Collection<? extends E> c) {
        this.comparator = null;
        this.al = new CopyOnWriteArrayList<>();
        CopyOnWriteArrayNavigableSet.addAll(this, c);
    }

    /**
     * Creates a set containing all of the elements of the specified
     * collection, sharing the same underlying array and comparator.
     *
     * @param c the collection of elements to initially contain
     * @throws NullPointerException if the specified collection is null
     */
    public CopyOnWriteArrayNavigableSet(CopyOnWriteArrayNavigableSet<E> c) {
        this.comparator = c.comparator;
        this.al = new CopyOnWriteArrayList<>();
        this.al.setArray(c.al.getArray());
    }

    /**
     * Creates a set containing all of the elements of the specified
     * sorted set, sharing the same comparator.
     *
     * @param c the collection of elements to initially contain
     * @throws NullPointerException if the specified collection is null
     */
    public CopyOnWriteArrayNavigableSet(SortedSet<E> c) {
        this.comparator = c.comparator();
        this.al = new CopyOnWriteArrayList<>(c);
    }


Now the code COWANSTest I wrote above would not compile anymore.

8. Since we have type erasure in generics, it would probably be also a bit more accurate to use Object[] instead of E[].  See the other classes in java.util.* for comparison.  I understand why you did it - to get Arrays.binarySort() to work.  However, it is a bit messy that one could construct a CopyOnWriteArrayNavigableSet with a generic type that is not Comparable and without a Comparator and where we would get an ClassCastException the moment we use it.

9. The fromLoc and toLoc methods both have the same code for finding the comparator:

super.comparator == null ? descending ? (Comparator<E>) Comparator.reverseOrder() : null : descending ? super.comparator.reversed() : super.comparator
super.comparator == null ? descending ? (Comparator<E>) Comparator.reverseOrder() : null : descending ? super.comparator.reversed() : super.comparator

which incidentally also occurs in the comparator() method.  I have rewritten that to make it a bit clearer and to reduce the scope of the "unchecked" warning:

        @Override
        public Comparator<? super E> comparator() {
            if (descending) {
                if (super.comparator == null) {
                    @SuppressWarnings("unchecked")
                    Comparator<? super E> comparator = (Comparator<? super E>) Comparator.reverseOrder();
                    return comparator;
                } else {
                    return super.comparator.reversed();
                }
            } else {
                return super.comparator;
            }
        }

10. I am concerned by the number of methods that are being called whilst holding locks.  Whilst I don't have any concrete example, I am concerned that this could lead to deadlocks.

I have not tested correctness on the class and also not performance, however, I hope this will give you something to chew over in the meantime.  The class with my changes is as an attachment.  Please note that all I have checked is that my code compiles, not that it is correct.  It is extremely likely that I introduce logical errors into the code, so please check everything very carefully.

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 Heinz;

Here's the updated implementation as promised. I welcome any feedback you have. I have a slight preference for public feedback on concurrency-interst because more visible evidence of review will bolster confidence and increase urgency. If you'd prefer not to post publicly, that is fine too!

Thanks,

Mike

On 2015-11-23 15:20, Dr Heinz M. Kabutz wrote:
Thanks Mike,

once you're done, please send it along.  I'm at UTC at the moment, but
will hopefully get to check it out tomorrow.

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:
Certainly. I am going to try to fix some of the reported issues today including inheriting from CopyOnWriteArraySet but I would certainly appreciate and no doubt benefit from your input.

Mike

On 2015-11-23 15:04, Dr Heinz M. Kabutz wrote:
Hi Mike,

 could you please email me your latest version?  I would like to
check it for you this week.  I'm sure it's fine, but it always helps
to have extra eyes on a piece of code :-)

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 [2]
Tel: +30 69 75 595 262
Skype: kabutz

 Mike Duigou wrote:

Hello all;

Here's the missing attachment.

One piece of feedback that I have received from several people is
that they would prefer if COWANS did not extend COWAS. Originally
the implementation did not but I have done so in this most recent
patch. The primary concern is that tying the implementations
together via inheritance reduces future flexibility for COWANS
optimization and refactoring. Opinions from others?

Mike

-------------------------

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest [1]


Links:
------
[1] http://cs.oswego.edu/mailman/listinfo/concurrency-interest
[2] http://www.javaspecialists.eu




/* * 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 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. * * @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 or null if elements are Comparable and sorted in * "Natural Order". */ final Comparator comparator; /** * Embedded CopyOnWriteArrayList used to hold the storage of this set. */ final CopyOnWriteArrayList al; CopyOnWriteArrayNavigableSet(Comparator comparator, CopyOnWriteArrayList al) { this.comparator = comparator; this.al = al; } /** * Creates an empty set which can be used for mutually * {@link java.lang.Comparable Comparable} object. */ public CopyOnWriteArrayNavigableSet() { this((Comparator)null); } /** * Creates an empty set with the specified comparator. * * @param comparator Used for ordering elements. */ @SuppressWarnings("unchecked") public CopyOnWriteArrayNavigableSet(Comparator comparator) { this(comparator, new CopyOnWriteArrayList<>()); } /** * Creates a set containing all of the elements of the specified * collection. If c is a sorted set then the same comparator is used. * * @param c the collection of elements to initially contain * @throws NullPointerException if the specified collection is null */ @SuppressWarnings("unchecked") public CopyOnWriteArrayNavigableSet(Collection 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) { this.comparator = ((SortedSet) c).comparator(); this.al = new CopyOnWriteArrayList<>(c); } else { this.comparator = null; this.al = new CopyOnWriteArrayList<>(); CopyOnWriteArrayNavigableSet.addAll(this, c); } } @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) { Objects.requireNonNull(e, "e"); synchronized(al.lock) { @SuppressWarnings("unchecked") E[] array = (E[]) al.getArray(); int loc = Arrays.binarySearch(array, e, comparator); if(loc < 0) { 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.compare(array[len], (E) cs[added]) > 0) ? array[len--] : (E) 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]; } @SuppressWarnings("unchecked") final int compare(E e1, E e2) { return comparator != null ? comparator.compare(e1, e2) : ((Comparable) e1).compareTo(e2); } 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(compare(fromElement,toElement)); int toCompared = Integer.signum(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 descending ? (comparator == null ? (Comparator) Comparator.naturalOrder() : 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 (compare(lowerBound,element) > 0) { throw new IllegalArgumentException("out of bounds: " + element + " < " + lowerBound); } } else { if (compare(lowerBound, element) >= 0) { throw new IllegalArgumentException("out of bounds: " + element + " <= " + lowerBound); } } } if (upperBounded) { if (upperInclusive) { if (compare(upperBound, element) < 0) { throw new IllegalArgumentException("out of bounds: " + element + " > " + upperBound); } } else { if (compare(upperBound, element) <= 0) { throw new IllegalArgumentException("out of bounds: " + element + " >= " + upperBound); } } } return element; } private boolean checkInBounds(E element) { if (lowerBounded) { if (lowerInclusive) { if (compare(lowerBound,element) > 0) { return false; } } else { if (compare(lowerBound, element) >= 0) { return false; } } } if (upperBounded) { if (upperInclusive) { if (compare(upperBound, element) < 0) { return false; } } else { if (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, comparator == null ? descending ? (Comparator) Comparator.reverseOrder() : null : 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); } } }


package java.util.concurrent;/*
 * 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/
 */

import java.lang.reflect.Array;
import java.util.AbstractSet;
import java.util.Arrays;
import java.util.Collection;
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.Consumer;
import java.util.function.Predicate;

/**
 * A {@link java.util.NavigableSet} that uses an internal {@link java.util.concurrent.CopyOnWriteArrayList}
 * for all of its operations.  Thus, it shares the same basic properties:
 * <ul>
 * <li>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.
 * <li>It is thread-safe.
 * <li>Mutative operations ({@code add}, {@code set}, {@code remove}, etc.)
 * are expensive since they usually entail copying the entire underlying
 * array.
 * <li>Iterators do not support the mutative {@code remove} operation.
 * <li>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.
 * </ul>
 * <p>
 * <p><b>Sample Usage.</b> 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.
 * <p>
 * <pre> {@code
 * class Handler implements Comparable&lt;Handler> {
 *   // returns true if update has been handled
 *   boolean handle();
 * <p>
 *   // ordered from highest to lowest
 *   public int compareTo(Handler other) { return priority - other.priority; }
 * }
 * <p>
 * class X {
 *   // Will use "Natural Order" of Comparables
 *   private final java.util.concurrent.CopyOnWriteArrayNavigableSet&lt;Handler> handlers
 *     = new java.util.concurrent.CopyOnWriteArrayNavigableSet&lt;>();
 *   public void addHandler(Handler h) { handlers.add(h); }
 * <p>
 *   private long internalState;
 *   private synchronized void changeState() { internalState = ...; }
 * <p>
 *   public void update() {
 *     changeState();
 *     for (Handler handler : handlers)
 *       if(handler.handle()) break;
 *   }
 * }}</pre>
 * <p>
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @param <E> the type of elements held in this collection
 * @author Doug Lea
 * @author Mike Duigou
 * @see CopyOnWriteArrayList
 * @since 9
 */
public class CopyOnWriteArrayNavigableSet<E> extends AbstractSet<E>
        implements java.io.Serializable, NavigableSet<E> {

    private static final long serialVersionUID = -3680134489612968105L;

    /**
     * Comparator for elements or null if elements are Comparable and sorted in
     * "Natural Order".
     */
    private final Comparator<? super E> comparator;

    /**
     * Embedded CopyOnWriteArrayList used to hold the storage of this set.
     */
    private final CopyOnWriteArrayList<E> al;

    private CopyOnWriteArrayNavigableSet(Comparator<? super E> comparator, CopyOnWriteArrayList<E> al) {
        this.comparator = comparator;
        this.al = al;
    }

    /**
     * Creates an empty set which can be used for mutually
     * {@link java.lang.Comparable Comparable} object.
     */
    public CopyOnWriteArrayNavigableSet() {
        this((Comparator<E>) null);
    }

    /**
     * Creates an empty set with the specified comparator.
     *
     * @param comparator Used for ordering elements.
     */
    public CopyOnWriteArrayNavigableSet(Comparator<E> comparator) {
        this(comparator, new CopyOnWriteArrayList<>());
    }

    /**
     * Creates a set containing all of the elements of the specified
     * collection, assuming natural ordering.
     *
     * @param c the collection of elements to initially contain
     * @throws NullPointerException if the specified collection is null
     */
    public CopyOnWriteArrayNavigableSet(Collection<? extends E> c) {
        this.comparator = null;
        this.al = new CopyOnWriteArrayList<>();
        CopyOnWriteArrayNavigableSet.addAll(this, c);
    }

    /**
     * Creates a set containing all of the elements of the specified
     * collection, sharing the same underlying array and comparator.
     *
     * @param c the collection of elements to initially contain
     * @throws NullPointerException if the specified collection is null
     */
    public CopyOnWriteArrayNavigableSet(CopyOnWriteArrayNavigableSet<E> c) {
        this.comparator = c.comparator;
        this.al = new CopyOnWriteArrayList<>();
        this.al.setArray(c.al.getArray());
    }

    /**
     * Creates a set containing all of the elements of the specified
     * sorted set, sharing the same comparator.
     *
     * @param c the collection of elements to initially contain
     * @throws NullPointerException if the specified collection is null
     */
    public CopyOnWriteArrayNavigableSet(SortedSet<E> c) {
        this.comparator = c.comparator();
        this.al = new CopyOnWriteArrayList<>(c);
    }

    /**
     * Creates a set containing all of the elements of the specified
     * collection. If c is a sorted set then the same comparator is used.
     *
     * @param c the collection of elements to initially contain
     * @throws java.lang.NullPointerException if the specified collection is null
     *                                        /
     *                                        public CopyOnWriteArrayNavigableSet(Collection<? extends E> c) {
     *                                        if (c.getClass() == CopyOnWriteArrayNavigableSet.class) {
     *                                        CopyOnWriteArrayNavigableSet<E> cnav = (CopyOnWriteArrayNavigableSet<E>) c;
     *                                        this.comparator = cnav.comparator;
     *                                        this.al = new CopyOnWriteArrayList<>();
     *                                        this.al.setArray(cnav.al.getArray());
     *                                        } else if (c instanceof SortedSet) {
     *                                        this.comparator = ((SortedSet) c).comparator();
     *                                        this.al = new CopyOnWriteArrayList<>(c);
     *                                        } else {
     *                                        this.comparator = null;
     *                                        this.al = new CopyOnWriteArrayList<>();
     *                                        CopyOnWriteArrayNavigableSet.addAll(this, c);
     *                                        }
     *                                        }
     */

    @Override
    @SuppressWarnings("unchecked")
    public boolean contains(Object o) {
        return Arrays.binarySearch((E[]) al.getArray(), (E) o, comparator) >= 0;
    }

    @Override
    public boolean remove(Object o) {
        al.lock.lock();
        try {
            @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;
        } finally {
            al.lock.unlock();
        }
    }

    @Override
    public boolean add(E e) {
        Objects.requireNonNull(e, "e");
        al.lock.lock();
        try {
            @SuppressWarnings("unchecked")
            E[] array = (E[]) al.getArray();
            int loc = Arrays.binarySearch(array, e, comparator);
            if (loc < 0) {
                al.add(-1 - loc, e);
                return true;
            }
            return false;
        } finally {
            al.lock.unlock();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public boolean containsAll(Collection<?> c) {
        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<? extends E> c) {
        return CopyOnWriteArrayNavigableSet.addAll(this, c);
    }

    @SuppressWarnings("unchecked")
    private static <E> boolean addAll(CopyOnWriteArrayNavigableSet<E> cowans, Collection<? extends E> c) {
        Object[] cs = c.toArray();
        if (cs.length == 0)
            return false;
        if (cs.length == 1) {
            return cowans.add((E) cs[0]);
        }
        cowans.al.lock.lock();
        try {
            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.compare(array[len], (E) cs[added]) > 0)
                            ? array[len--]
                            : (E) cs[added--];
                }
                cowans.al.setArray(newElements);
                return true;
            }
            return false;
        } finally {
            cowans.al.lock.unlock();
        }
    }

    @Override
    public Iterator<E> iterator() {
        return al.iterator();
    }

    @Override
    public int size() {
        return al.size();
    }

    @Override
    public boolean removeIf(Predicate<? super E> filter) {
        return al.removeIf(filter);
    }

    @Override
    public void forEach(Consumer<? super E> 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> 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.
     * <p>
     * <p>The {@code Spliterator} reports {@link Spliterator#ORDERED},
     * {@link Spliterator#NONNULL}, {@link Spliterator#IMMUTABLE},
     * {@link Spliterator#DISTINCT}, and {@link Spliterator#SIZED}.
     * <p>
     * <p>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<E> 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;
        al.lock.lock();
        try {
            if (al.isEmpty()) return null;
            E result = al.remove(0);
            return result;
        } finally {
            al.lock.unlock();
        }
    }

    @Override
    public E pollLast() {
        if (al.isEmpty()) return null;
        al.lock.lock();
        try {
            if (al.isEmpty()) return null;
            E result = al.remove(al.size() - 1);
            return result;
        } finally {
            al.lock.unlock();
        }
    }

    @Override
    public NavigableSet<E> descendingSet() {
        return new BoundedNavigableSet<>(comparator, al, false, null, false, false, null, false, true);
    }

    @Override
    public Iterator<E> descendingIterator() {
        final Object[] array = al.getArray();

        return array.length == 0
                ? Collections.emptyIterator()
                : new Iterator<E>() {
            int index = array.length - 1;

            @Override
            public boolean hasNext() {
                return index >= 0;
            }

            @Override
            @SuppressWarnings("unchecked")
            public E next() {
                if (hasNext()) {
                    return (E) array[index--];
                } else {
                    throw new NoSuchElementException();
                }
            }

        };
    }

    @Override
    public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
        return new BoundedNavigableSet<>(comparator, al, true, fromElement, fromInclusive, true, toElement, toInclusive, false);
    }

    @Override
    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new BoundedNavigableSet<>(comparator, al, false, null, false, true, toElement, inclusive, false);
    }

    @Override
    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
        return new BoundedNavigableSet<>(comparator, al, true, fromElement, inclusive, false, null, false, false);
    }

    @Override
    public SortedSet<E> subSet(E fromElement, E toElement) {
        return subSet(fromElement, true, toElement, false);
    }

    @Override
    public SortedSet<E> headSet(E toElement) {
        return headSet(toElement, false);
    }

    @Override
    public SortedSet<E> tailSet(E fromElement) {
        return tailSet(fromElement, true);
    }

    @Override
    public Comparator<? super E> 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];
    }

    @SuppressWarnings("unchecked")
    final int compare(E e1, E e2) {
        return comparator != null ? comparator.compare(e1, e2) : ((Comparable<E>) e1).compareTo(e2);
    }

    private static class BoundedNavigableSet<E> extends CopyOnWriteArrayNavigableSet<E> {

        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;

        public BoundedNavigableSet(
                Comparator<? super E> comparator, CopyOnWriteArrayList<E> 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(compare(fromElement, toElement));
                int toCompared = Integer.signum(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
        public Comparator<? super E> comparator() {
            if (descending) {
                if (super.comparator == null) {
                    @SuppressWarnings("unchecked")
                    Comparator<? super E> comparator = (Comparator<? super E>) Comparator.reverseOrder();
                    return comparator;
                } else {
                    return super.comparator.reversed();
                }
            } else {
                return super.comparator;
            }
        }

        @Override
        public NavigableSet<E> descendingSet() {
            return new BoundedNavigableSet<>(
                    super.comparator, super.al,
                    upperBounded, upperBound, upperInclusive,
                    lowerBounded, lowerBound, lowerInclusive,
                    !descending);
        }

        @Override
        public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
            return new BoundedNavigableSet<>(
                    super.comparator, super.al,
                    true, inBounds(fromElement), fromInclusive,
                    true, inBounds(toElement), toInclusive,
                    descending);
        }

        @Override
        public NavigableSet<E> headSet(E toElement, boolean inclusive) {
            return new BoundedNavigableSet<>(
                    super.comparator, super.al,
                    lowerBounded, lowerBound, lowerInclusive,
                    true, inBounds(toElement), inclusive,
                    descending);
        }

        @Override
        public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
            return new BoundedNavigableSet<>(
                    super.comparator, super.al,
                    true, inBounds(fromElement), inclusive,
                    upperBounded, upperBound, upperInclusive,
                    descending);
        }

        @Override
        public SortedSet<E> subSet(E fromElement, E toElement) {
            return subSet(fromElement, true, toElement, false);
        }

        @Override
        public SortedSet<E> headSet(E toElement) {
            return headSet(toElement, false);
        }

        @Override
        public SortedSet<E> tailSet(E fromElement) {
            return tailSet(fromElement, true);
        }

        private E inBounds(E element) {
            if (lowerBounded) {
                if (lowerInclusive) {
                    if (compare(lowerBound, element) > 0) {
                        throw new IllegalArgumentException("out of bounds: " + element + " < " + lowerBound);
                    }
                } else {
                    if (compare(lowerBound, element) >= 0) {
                        throw new IllegalArgumentException("out of bounds: " + element + " <= " + lowerBound);
                    }
                }
            }

            if (upperBounded) {
                if (upperInclusive) {
                    if (compare(upperBound, element) < 0) {
                        throw new IllegalArgumentException("out of bounds: " + element + " > " + upperBound);
                    }
                } else {
                    if (compare(upperBound, element) <= 0) {
                        throw new IllegalArgumentException("out of bounds: " + element + " >= " + upperBound);
                    }
                }
            }

            return element;
        }


        private boolean checkInBounds(E element) {
            if (lowerBounded) {
                if (lowerInclusive) {
                    if (compare(lowerBound, element) > 0) {
                        return false;
                    }
                } else {
                    if (compare(lowerBound, element) >= 0) {
                        return false;
                    }
                }
            }

            if (upperBounded) {
                if (upperInclusive) {
                    if (compare(upperBound, element) < 0) {
                        return false;
                    }
                } else {
                    if (compare(upperBound, element) <= 0) {
                        return false;
                    }
                }
            }

            return true;
        }


        @Override
        public Iterator<E> descendingIterator() {
            return makeIterator(!descending);
        }

        @Override
        public void forEach(Consumer<? super E> action) {
            Objects.requireNonNull(action, "action");
            @SuppressWarnings("unchecked")
            E[] array = (E[]) super.al.getArray();
            int start = fromLoc(array);
            int end = toLoc(array);
            for (int each = start; each < end; each++)
                action.accept(array[each]);
        }

        @Override
        public boolean removeIf(Predicate<? super E> filter) {
            Objects.requireNonNull(filter, "filter");
            super.al.lock.lock();
            try {
                @SuppressWarnings("unchecked")
                E[] array = (E[]) super.al.getArray();
                int start = fromLoc(array);
                int end = toLoc(array);
                return super.al.subList(start, end).removeIf(filter);
            } finally {
                super.al.lock.unlock();
            }
        }

        @Override
        public boolean retainAll(Collection<?> c) {
            super.al.lock.lock();
            try {
                @SuppressWarnings("unchecked")
                E[] array = (E[]) super.al.getArray();
                int start = fromLoc(array);
                int end = toLoc(array);
                return super.al.subList(start, end).retainAll(c);
            } finally {
                super.al.lock.unlock();
            }
        }

        @Override
        public boolean removeAll(Collection<?> c) {
            super.al.lock.lock();
            try {
                @SuppressWarnings("unchecked")
                E[] array = (E[]) super.al.getArray();
                int start = fromLoc(array);
                int end = toLoc(array);
                return super.al.subList(start, end).removeAll(c);
            } finally {
                super.al.lock.unlock();
            }
        }

        @Override
        public boolean addAll(Collection<? extends E> c) {
            for (E e : c) inBounds(e);
            return CopyOnWriteArrayNavigableSet.addAll(this, c);
        }

        @Override
        @SuppressWarnings("unchecked")
        public boolean containsAll(Collection<?> c) {
            E[] array = (E[]) super.al.getArray();
            int start = fromLoc(array);
            int end = toLoc(array);
            for (Object each : c) {
                if (Arrays.binarySearch(array, start, end, (E) each, super.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() {
            super.al.lock.lock();
            try {
                @SuppressWarnings("unchecked")
                E[] array = (E[]) super.al.getArray();
                int start = fromLoc(array);
                int end = toLoc(array);
                super.al.removeRange(start, end);
            } finally {
                super.al.lock.unlock();
            }
        }

        @SuppressWarnings("unchecked")
        private int fromLoc(E[] array) {
            int start;
            if (lowerBounded) {
                start = Arrays.binarySearch(array, lowerBound, 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, comparator());
                end = end >= 0
                        ? upperInclusive ? end + 1 : end
                        : -1 - end;
            } else {
                end = array.length;
            }

            return end;
        }

        @Override
        public <T> T[] toArray(T[] a) {
            return makeArray(a, descending);
        }

        @SuppressWarnings("unchecked")
        public <T> T[] makeArray(T[] a, boolean inDescending) {
            E[] array = (E[]) super.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<E> iterator() {
            return makeIterator(descending);
        }

        @SuppressWarnings("unchecked")
        private Iterator<E> makeIterator(boolean inDescending) {
            List<E> asList;
            if (inDescending) {
                asList = Arrays.asList((E[]) makeArray(new Object[0], inDescending));
            } else {
                E[] array = (E[]) super.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[]) super.al.getArray();
            return toLoc(array) - fromLoc(array);
        }

        @Override
        public E lower(E e) {
            E result = descending
                    ? super.higher(e)
                    : super.lower(e);
            return result != null && checkInBounds(result) ? result : null;
        }

        @Override
        public E floor(E e) {
            E result = descending
                    ? super.ceiling(e)
                    : super.floor(e);
            return result != null && checkInBounds(result) ? result : null;
        }

        @Override
        public E ceiling(E e) {
            E result = descending
                    ? super.floor(e)
                    : super.ceiling(e);
            return result != null && checkInBounds(result) ? result : null;
        }

        @Override
        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) {
                super.al.lock.lock();
                try {
                    E remove = lowerInclusive ? floor(lowerBound) : higher(lowerBound);
                    if (null != remove) {
                        super.remove(remove);
                    }
                    return remove;
                } finally {
                    super.al.lock.unlock();
                }
            } else
                return super.pollFirst();
        }

        @Override
        public E pollLast() {
            return descending ? doPollFirst() : doPollLast();
        }

        private E doPollLast() {
            if (upperBounded) {
                super.al.lock.lock();
                try {
                    E remove = upperInclusive ? floor(upperBound) : lower(upperBound);
                    if (null != remove) {
                        super.remove(remove);
                    }
                    return remove;
                } finally {
                    super.al.lock.unlock();
                }
            } 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<E> spliterator() {
            @SuppressWarnings("unchecked")
            E[] array = (E[]) super.al.getArray();
            return Spliterators.spliterator(
                    array, fromLoc(array), toLoc(array), Spliterator.ORDERED | Spliterator.NONNULL | Spliterator.IMMUTABLE | Spliterator.DISTINCT);
        }
    }
}

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: RFR: CopyOnWriteArrayNavigableSet for Java 9

Dr Heinz M. Kabutz
In reply to this post by Mike Duigou
I've thought about this some more today.  At the moment you can construct a CopyOnWriteArrayNavigableSet for a type that does not have a natural ordering and without specifying a comparator.  I think that makes our lives a lot harder in the implementation.  Better would be to force the user to pass in a correct Comparator for that type.  That way we know that we always have one and we don't need to check for null anymore.  There is a precedent for this idea.  Look for example at the List.sort() function:

    default void sort(Comparator<? super E> c) {
    ...
    }

Of course, with the sort() function you could pass in null and then it would use the natural order.  My idea is to not allow null, but to make sure that it matches the correct type of comparator for our type.  It is easy enough to pass in Comparator.naturalOrder() and that also checks that E is in fact Comparable.
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:
I've made some changes which will address this addAll() case.

Not supporting nulls is for a couple reasons;
- none of the other java.util.concurrent Sets support them.
- Handling some of the cases of sub-sets when nulls are involved would require extra work. It is the usual problem of telling whether a null return means absent or a null value. I had included "// XXX needs to handle null" in a bunch of places as I was writing the original code and in my original review drafts but the Java 9 deadlines have caught up with me and so I abandoned plans to support null when using a Comparator that allows null.
- I don't like nulls in Collections. Seriously they are a PITA and the extra code to handle them often makes the general case slower.

That's perhaps a little stronger than I actually believe. :-) With an unrestricted schedule I probably would have included null element support.

Mike

On 2015-11-23 12:58, Peter Levart wrote:
On 11/23/2015 04:40 PM, Chris Povirk wrote:

Just one point from some black-box testing:
emptySet.addAll(singleNullElement) will insert the null element into
the set, even if the Comparator does not support it.

 There's no reason to not allow null elements when using comparator
that supports them?

 Regards, Peter

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: RFR: CopyOnWriteArrayNavigableSet for Java 9

Chris Povirk
On Wed, Nov 25, 2015 at 11:29 AM, Dr Heinz M. Kabutz <[hidden email]> wrote:
I've thought about this some more today.  At the moment you can construct a CopyOnWriteArrayNavigableSet for a type that does not have a natural ordering and without specifying a comparator.  I think that makes our lives a lot harder in the implementation.  Better would be to force the user to pass in a correct Comparator for that type.  That way we know that we always have one and we don't need to check for null anymore.  There is a precedent for this idea.  Look for example at the List.sort() function:

    default void sort(Comparator<? super E> c) {
    ...
    }

Of course, with the sort() function you could pass in null and then it would use the natural order.  My idea is to not allow null, but to make sure that it matches the correct type of comparator for our type.  It is easy enough to pass in Comparator.naturalOrder() and that also checks that E is in fact Comparable.

+1 for preventing users from creating a naturally ordered instance for a non-Comparable type. I have seen this surprisingly often with TreeSet. (I could try to get numbers for Google code if it would help.)

Guava (example) does this as a compile-time check by making the constructor private and setting appropriate constraints on its static factory methods. Here, it would look something like this:

private CopyOnWriteArrayNavigableSet(
    Comparator<? super E> comparator, Collection<? extends E> contents) {
  ...
}

public static <E extends Comparable<? super E>> CopyOnWriteArrayNavigableSet<E> create() {
  return new CopyOnWriteArrayNavigableSet<>(
      Comparator.naturalOrder(), Collections.emptySet());
}

public static <E extends Comparable<? super E>> CopyOnWriteArrayNavigableSet<E> create(
    Collection<? extends E> contents) {
  return new CopyOnWriteArrayNavigableSet<>(
      Comparator.naturalOrder(), contents);
}

public static <E> CopyOnWriteArrayNavigableSet<E> create(Comparator<? super E> comparator) {
  return new CopyOnWriteArrayNavigableSet<>(
      comparator, Collections.emptySet());
}

The downside is that the JDK doesn't use static factory methods as often as Guava does. (And it probably doesn't "need to" as much now that we have the diamond operator.) That means that these ones will look strange, especially alongside the constructors of CopyOnWriteArray(Set|List). At least there is some precedent for static factory methods in EnumSet (which itself differs from EnumMap).

(Small note: You may want to use "<E extends Comparable<?>>" for maximum compatibility with pre-generics types -- that is, those that implement raw "Comparable" instead of "Comparable<Foo>." I don't have a great feel for the tradeoffs here.)

(Unrelated: You could also consider accepting an Iterable instead of a Collection for further compatibility. But maybe that matters less in a world with Streams.)

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest