Creating immutable sorted sets from already-ordered data

[GoogleCodeExporter]

Occasionally you have a List of elements which you already know to be in
sorted order. The canonical example is the results from a SQL query with an
ORDER BY clause.

You know the data to be sorted, yet you have no way to offer the niceties
of the SortedSet/NavigableSet APIs to your callers. In order to construct a
TreeSet/etc., you must re-engineer the appropriate comparator that can be
used to sort the data -- but the data is already sorted!

I believe the way out of this is a method Sets.immutablePreSortedSet(List).
 This method would copy the elements out of the list, assuming that
whatever order they come out in is the order you want.  It would not demand
a comparator from you (although, if you can provide one, perhaps it should
accept it, as this could speed up some of the operations.  and if you don't
provide one, what should the set's comparator() return?  Should it return a
Comparators.givenOrder()?).

This idea is not fully-formed, but it's a shame to see methods forced to
use List to model data which is often known to be dup-free and is ordered,
not indexed.

Original issue reported on code.google.com by kevin...@gmail.com on 23 Oct 2007 at 4:22

[GoogleCodeExporter]

This idea needs a lot more thought.

Case 1: you can provide a comparator. In this case, you should provide it -- 
and just
create an ImmutableSortedSet.  Creating that will cause a sort() to happen 
which will
be a no-op, and that's not great but not terrible.  It's possible we could 
provide
another way to create an ISS where you declare your data is already increasing, 
thus
the factory only has to check that each element is higher than the one before 
it, and
doesn't have to call sort().  Meh.

Case 2: you can't provide a comparator. Some complicated database sort was 
done, for
instance. So your comparator becomes an Ordering.givenOrder() over the elements 
you
have. ImmutableSortedSet.inGivenOrder().addAll(list).build(). I kind of like 
this,
but I haven't heard a loud demand for it. (then again, many people are not 
loudly
demanding it but are still returning List from APIs that really should be Sets.)

Original comment by kevin...@gmail.com on 17 Mar 2009 at 5:09

• Changed title: Creating immutable sorted sets from already-ordered data

[GoogleCodeExporter]

There's a problem with Case 2. Without a comparator, you can't implement the 
comparator(), headSet(), tailSet(), and subSet() methods. 

Original comment by jared.l....@gmail.com on 13 Aug 2009 at 2:06

[GoogleCodeExporter]

Could you elaborate on that a bit? E.g. why Ordering.givenOrder()/.explicit() 
wouldn't 
do?

Original comment by jim.andreou on 13 Aug 2009 at 2:20

[GoogleCodeExporter]

Yeah, those methods would only be able to accept values that are elements in 
the set,
so they'd be a bit crippled, but I'm not sure it's a deal-breaker.

This whole idea still lacks real motivation from users.

Original comment by kevin...@gmail.com on 13 Aug 2009 at 2:43

[GoogleCodeExporter]

Hmm, alright. Though it wouldn't be any more "crippled" than 
Ordering.explicit() 
itself. And you already decided that it doesn't pay off enough to allow 
defining what 
happens with elements not contained in the list (with something similar to 
nullsFirst()/nullsLast()), with which I agree, so I don't see this as a big 
issue - but 
the real deal-breaker would be indeed lack of enough demand :)

Original comment by jim.andreou on 13 Aug 2009 at 3:05

[GoogleCodeExporter]

ImmutableSortedSet should guarantee that its items are ordered using the 
comparator() 
order, so it's a good idea to accept the client assumption (that items are 
already 
ordered). But, I think, an acceptable case when the order is checked at the 
construction phase - so ImmutableSortedSet.copyOfSorted(List<E> list) can check 
the 
given list to be correct, and accept it if correct or throw an exception if not.

Original comment by leonidos on 3 Sep 2009 at 7:21

[GoogleCodeExporter]

[erratum]
In the previous message - I meant "it's not a good idea accept the client 
assumption".

Original comment by leonidos on 10 Sep 2009 at 1:36

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Original comment by kevin...@gmail.com on 17 Sep 2009 at 6:02

• Added labels: Milestone-Post1.0

[GoogleCodeExporter]

This issue has been moved to the Guava project (keeping the same id number). 
Simply replace 'google-collections' with 'guava-libraries' in your address 
bar and it should take you there.

Original comment by kevinb@google.com on 5 Jan 2010 at 11:09

• Changed state: Moved