ImmutableSortedList

[GoogleCodeExporter]

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.

Original issue reported on code.google.com by ogregoire on 15 Oct 2010 at 3:31

[GoogleCodeExporter]

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.

Original comment by boppenh...@google.com on 15 Oct 2010 at 5:43

[GoogleCodeExporter]

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.

Original comment by cgdec...@gmail.com on 15 Oct 2010 at 8:09

[GoogleCodeExporter]

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)

/**

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

/**

• Does (something). *
• Warning: you MUST have called dedup() first before using
• this method! *
• @param eq the equivalence to use. Warning: this MUST be the
• same equivalence that was used in the last call to dedup()! Or
• else!! */ 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 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).

Original comment by `kevinb@google.com` on 16 Oct 2010 at 5:40
* Changed title: **ImmutableSortedList**
* Changed state: **Accepted**

[GoogleCodeExporter]

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

Original comment by boppenh...@google.com on 16 Oct 2010 at 6:13

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

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.

Original comment by jim.andreou on 18 Oct 2010 at 7:44

[GoogleCodeExporter]

Original comment by fry@google.com on 26 Jan 2011 at 10:27

• Added labels: Type-Enhancement

[GoogleCodeExporter]

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.

Original comment by kevinb@google.com on 27 Jan 2011 at 5:53

[GoogleCodeExporter]

Original comment by kevinb@google.com on 13 Jul 2011 at 6:18

• Changed state: Triaged

[GoogleCodeExporter]

Original comment by kevinb@google.com on 18 Jul 2011 at 3:42

• Changed state: WorkingAsIntended

[GoogleCodeExporter]

This issue has been migrated to GitHub.

It can be found at https://github.com/google/guava/issues/<id>

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:15

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:09

• Added labels: Restrict-AddIssueComment-Commit