google / guava

Google core libraries for Java
Apache License 2.0
50.15k stars 10.89k forks source link

ImmutableSortedList #449

Closed gissuebot closed 9 years ago

gissuebot commented 9 years ago

Original issue created by ogregoire on 2010-10-15 at 03:31 PM


Currently if you want your users to fill your lists, you just create an interface:

  public interface ListFiller {     public void fillList(List<String> builder);   }

Then you use it like this:

  List<String> builder = Lists.newArrayList();   for (ListFiller lf: fillers) {     List<String> tmp = Lists.newArrayList();     lf.fillList(tmp);     builder.addAll(tmp);   }   Collections.sort(builder, String.CASE_INSENSITIVE_ORDER);   ImmutableList<String> sortedImmutableList = ImmutableList.copyOf(builder);

But I find this extremely heavy for a such simple task. So I suggest creating a new builder for the ImmutableList that would automatically sort all elements at the build time.

  public interface ListFiller {     public void fillList(ImmutableList.Builder<String> builder);   }

That would be used this way:

  ImmutableList.Builder<String> builder = ImmutableList.builder(String.CASE_INSENSITIVE_ORDER);   for (ListFiller lf: fillers) {     lf.fillList(builder);   }   ImmutableList<String> sortedImmutableList = builder.build();

Much smaller, much more intuitive, much more readable.

I think that internally there should be a SortingBuilder but the user never sees it, so that would make this SortingBuilder extending the normal Builder.

gissuebot commented 9 years ago

Original comment posted by boppenheim@google.com on 2010-10-15 at 05:43 PM


What is the use case for having children fill a List instead of just having them return Lists?

In your example, why not:

List<String> list = Lists.newArrayList(); for(ListFiller filler : fillers) {   filler.fillList(list); } Collections.sort(list, String.CASE_INSENSITIVE_ORDER); ImmutableList<String> sortedImmutableList = ImmutableList.copyOf(sort);

It seems to me like adding sorting to ImmutableList.Builder would not be in line with the purpose of the class. While adding it might save a line of code, I think its worthwhile to keep sorting a separate behavior. IMHO, it would be nice if Collections.sort returned list as a convenience so you could do ImmutableList.copyOf(Collections.sort(list, comparator)); Although, I wonder if this would mislead people who don't read the javadoc to believe that Collections.sort returns a sorted copy.

gissuebot commented 9 years ago

Original comment posted by cgdecker on 2010-10-15 at 08:09 PM


Also keep in mind the "immutableSortedCopy" method on Ordering. You could probably use a Supplier<List<String>> rather than a "ListFiller" as well.

With the new Suppliers.supplierFunction() coming in r08, the whole thing could be done like this (using Iterables.concat and transform):

  public static ImmutableList<String> test(List<Supplier<List<String>>> suppliers) {     Iterable<String> strings = concat(transform(suppliers,         Suppliers.<List<String>>supplierFunction()))     return Ordering.from(String.CASE_INSENSITIVE_ORDER).immutableSortedCopy(strings);   }

This is probably as efficient as you can get since no actual iteration will be done prior to the call to immutableSortedCopy.

gissuebot commented 9 years ago

Original comment posted by kevinb@google.com on 2010-10-16 at 05:40 PM


This report is uncanny, as we have been quite actively evaluating the usefulness of an ImmutableSortedList class internally. I personally believe in it, and am doing the research over the Google codebase to try to demonstrate its usefulness.

I'll share the (very long) rationale for why I like it:


Suppose I was proposing this API for a common library: (eliding generics)

/**
&nbsp;* Returns the unique elements of {@code in}, according to the given
&nbsp;* equivalence relation.
&nbsp;*/
public static Collection dedup(Collection in, Equivalence eq) {...}

/**
&nbsp;* Does (something).
&nbsp;*
&nbsp;* <b>Warning:</b> you MUST have called dedup() first before using
&nbsp;* this method!
&nbsp;*
&nbsp;* @param eq the equivalence to use. <b>Warning:</b> this MUST be the
&nbsp;*     same equivalence that was used in the last call to dedup()! Or
&nbsp;*     else!!
&nbsp;*/
public static void doSomething(Collection in, Equivalence eq) {...}

... so ... what would you think of this API design?

Anyone think it's awesome?

(Don't be distracted by the peculiarities of Equivalences wrt Collections in real life.  It's just an example.)

Of course, those bold warnings in the javadoc are pretty fishy.  It seems like a failure of API design, does it not?  Why can't the type returned by dedup() be the type required by doSomething()?  Wouldn't that be the logical solution?

So, how sad is it that the java.util.Collections (and Arrays) methods sort() and binarySearch() ended up with exactly this problem?  How did it happen?

Here's how.  The Java Collections weren't built with immutability as a core principle.  Everything worked by creating things and then mutating, mutating, mutating them. So the natural way to sort was to have a method that took a List and sorted it in-place.  And, of course you can't impart a new type to an already-existing instance, so there we were.

But we should be able to do better nowadays, right?

We've had discussions about a SortedList type that's similar to SortedSet; a list that automatically sorts itself when things are added.  This gets contractually problematic (read the doc of the two forms of List.add()), and I've also been quick to point out that it encroaches on territory already nicely covered by our friend Glazed Lists.

But, if we think only about *immutable* sorted lists, most of the problems go away, and some interesting things would come out of it.

* Instead of using Ordering.(immutable)SortedCopy(Iterable), and getting a plain List back, you could use ImmutableSortedList.copyOf() and get an ISL, and thus not lose the "type information" of its sortedness. (Ordering.immutableSortedCopy would either be deprecated, or its return type modified using the magic of the bridge method injector (http://bridge-method-injector.infradna.com/).

* ImmutableSortedSet's asList() view could now return an ISL.  (So could ISL's own subList() and reverse() views.)  (Which turns out to NOT be a binary-incompatible change!)

* Instead of the kind of painfully clunky binarySearch() result-munging illustrated yesterday by Louis [ed. sorry that is missing here, just imagine it :)], ISL could simply have methods like higherIndex(), lowerIndex(), ceilingIndex() and floorIndex().  This would all add up to (imho) much more readable user code!

* Side note: we probably ought to define a type that extends Collection&lt;E> with comparator(), and have all our various sorted things implement it.  Arguably, ImmutableSortedSet could probably have a new copyOfSorted() overload that accepts that type.

To work properly, ImmutableSortedList must require that your comparator be consistent with equals at least in one direction (it can be strictly weaker than equals; that is comparison of 0 need not imply equal, but equal must imply comparison of 0).  Luckily, this is the common case (likely by far) for such things anyway (example: Sort a list of employees by name).

---

**Status:** `Accepted`
gissuebot commented 9 years ago

Original comment posted by boppenheim@google.com on 2010-10-16 at 06:13 PM


+1 to Kevin's suggestion. Adding a seperate class seems better than cluttering ImmutableList.

gissuebot commented 9 years ago

Original comment posted by jim.andreou on 2010-10-18 at 07:44 PM


Hmm. Although I don't like the notion of "ImmutableSortedList" (any ImmutableList has already a definite order, it always defines a precedence relation), I agree about the route of adding a new type. I thought about adding an ordering() method in ImmutableList - for an ImmutableList that wasn't derived from Ordering.immutableSortedCopy(), ordering() would just be another way of calling Ordering.explicitOrder(). But the latter could not support the operations Kevin mentioned (higherIndex() etc), so a new type would be required anyway, so if having such operations is desirable (to present a better API to binary search), introducing the new type from the start seems better.

gissuebot commented 9 years ago

Original comment posted by fry@google.com on 2011-01-26 at 10:27 PM


(No comment entered for this change.)


Labels: Type-Enhancement

gissuebot commented 9 years ago

Original comment posted by kevinb@google.com on 2011-01-27 at 05:53 AM


For now, we have decided to not move forward on this. Google has a very large and varied Java codebase and we have been unable to find examples of code for which an ISL would actually be the best solution.

gissuebot commented 9 years ago

Original comment posted by kevinb@google.com on 2011-07-13 at 06:18 PM


(No comment entered for this change.)


Status: Triaged

gissuebot commented 9 years ago

Original comment posted by kevinb@google.com on 2011-07-18 at 03:42 PM


(No comment entered for this change.)


Status: WorkingAsIntended