Guava: Ordering.explicit should handle equals values not only strictly ordered values, and should provide default lowest or highest order for unknown values

[gissuebot]

_Original issue created by amertum on 2010-02-24 at 01:10 PM_

---

I need explicit ordering with elements that are equals such as

Ordering.explicit(a, [b1, b2], c).compare(b1, b2) returns 0

explicit signature should be discussed, may be
Ordering.explicit(List<Iterable<T>> elements) should be enough ?

I need also ordering other non-explicit elements such as

Ordering.explicit(UNKNOWN_LOWER, a, [b1, b2], c).compare(d, a) returns -1

or

Ordering.explicit(UNKNOWN_GREATER, a, [b1, b2], c).compare(d, a) returns 1

because right now, com.google.common.collect.ExplicitOrdering.rank(T)
throws IncomparableValueException when the T value is known

I joined a first implementation that handle equals elements fully inspired
from package visible com.google.common.collect.ExplicitOrdering

What do you think of this need ?

[gissuebot]

_Original comment posted by amertum on 2010-02-24 at 03:49 PM_

---

edit:
because right now, com.google.common.collect.ExplicitOrdering.rank(T)
throws IncomparableValueException when the T value is UNknown

[gissuebot]

_Original comment posted by amertum on 2010-02-24 at 03:51 PM_

---

EDIT : when the T value is UNKNOWN

[gissuebot]

_Original comment posted by [email protected] on 2010-04-27 at 02:45 PM_

---

On the a-b1-b2-c case, can you provide a more full illustration of what you're really doing, so we can think
about whether there's another way to do it? I'm not sure that adding a complex new overload to support this
case would pay for itself in the API.

On handling unknown values, I think there's a chain of orderings you can use to accomplish this:

Ordering.explicit(...).nullsFirst().onResultOf(UNKNOWN_TO_NULL_FUNCTION);

It's not very compact, but if this is not a very common operation, that's fine.

[gissuebot]

_Original comment posted by amertum on 2010-04-27 at 03:49 PM_

---

The way to handle unknown values is fine. It's a nice thought I should had.

It would be great to let extends-able package final class
com.google.common.collect.ExplicitOrdering to simplify customization.

About the a-b1-b2-c case, it happened because we used enum to describe some business
data type.

Let's take an example :

we have enum RABBIT_TYPE { WHITE_RABBIT, SMALL_RABBIT, GRAY_RABBIT, BIG_RABBIT}.

The categorization is wrong among this type because we mixed different kind of
physical attribute (color and height) but we cannot change that easily.

So, for us, color attribute are equals and height attribute are equals but they all
are of the same enum type. Maybe we could create RABBIT_COLOR_TYPE and so on, but java
don't let extends enum and we are stuck with all legacy code that use these enum type.

So we'd like to use Ordering.explicit([WHITE_RABBIT, GRAY_RABBIT], [SMALL_RABBIT,
BIG_RABBIT])

Hope it helps.

[gissuebot]

_Original comment posted by [email protected] on 2010-08-25 at 05:29 PM_

---

There are two independent issues here; handling unknowns, and handling equality.

For equality, I agree that the function is probably the way to go. So for the case mentioned, it could have:

Ordering.explicit(GRAY_RABBIT, BIG_RABBIT).onResultOf(MAP_EQUALS)

where MAP_EQUALS maps WHITE_RABBIT => GRAY_RABBIT, etc.

It might be worth adding a convenience method

onResultOf(Map<F,? extends T> map)

For the null case, I agree that it would be more handy to have something built-in, rather than have to repeat the list (and take the extra lookup cost) in a separate function. Maybe something like:

exceptionsFirst() // any item that would cause a ClassCastException is sorted first (see nullsFirst)
exceptionsLast() // any item that would cause a ClassCastException is sorted last (see nullsLast)

or

exceptionsAsNulls() // items causing exceptions are treated as nulls for ordering.

[gissuebot]

_Original comment posted by ray.j.greenwell on 2010-10-14 at 08:16 PM_

---

I want to provide a default ordering for the "nulls".

Example: I have a Map<String, Object> containing a bunch of labeled fields of userdata. There are some common fields that are expected to be present like "userId", or "email", but may not be, and there may be many more fields, some added in the future.

I want an ordering where "userId" comes first, then "email", followed by any other fields in alphabetical order.

Does that clarify the use case?

What I ended up doing was destructively modifying the map: iterating through a List of "known fields", and adding them in order and removing them from the map. Then I sorted the remaining keys and added those.

Devil's advocate: probably the proper way to do this is to have one's "known fields" in an Enum, with every possible field listed, plus one at the end called CUSTOM. Then have a FieldName class that has one of two constructors: one that takes the enum (and validates that null or CUSTOM is not passed-in) and one that takes a String (for custom fields). This class is Comparable and sorts first by enum and then by the String...

[gissuebot]

_Original comment posted by [email protected] on 2010-10-16 at 05:26 PM_

---

At this point I am generally sympathetic to the notion that Ordering.explicit as currently implemented is insufficient, and we should come up with the thing that can do all the things that users need. I don't know what that will look like exactly, yet, but am open to hear specific proposals

[gissuebot]

_Original comment posted by [email protected] on 2011-01-26 at 10:45 PM_

---

_(No comment entered for this change.)_

---

Status: Accepted
Labels: Type-Enhancement

[gissuebot]

_Original comment posted by amertum on 2011-02-01 at 10:12 PM_

---

Some methods signature ideas to handle equality :

as for this ordering : WHITE_RABBIT = GRAY_RABBIT < SMART_RABBIT < FAST_RABBIT < SMALL_RABBIT = BIG_RABBIT

Ordering.explicit(newArrayList(WHITE_RABBIT, GRAY_RABBIT), newArrayList(SMART_RABBIT), newArrayList(FAST_RABBIT), newArrayList(SMALL_RABBIT, BIG_RABBIT));
Ordering.explicit(Iterable<Iterable<T>> elements)

or using newArrayList alias

Ordering.explicit(eq(WHITE_RABBIT, GRAY_RABBIT), explicit(SMART_RABBIT, FAST_RABBIT), eq(SMALL_RABBIT, BIG_RABBIT));

or method chaining (looks nice)

Ordering.explicit().eq(WHITE_RABBIT, GRAY_RABBIT).explicit(SMART_RABBIT, FAST_RABBIT).eq(SMALL_RABBIT, BIG_RABBIT);

or builder

Ordering.explicitBuilder().ascending().eq(WHITE_RABBIT, GRAY_RABBIT).then(SMART_RABBIT, FAST_RABBIT).eq(SMALL_RABBIT, BIG_RABBIT).build();
Ordering.explicitBuilder().eq(WHITE_RABBIT, GRAY_RABBIT).lowerThan(SMART_RABBIT, FAST_RABBIT).eq(SMALL_RABBIT, BIG_RABBIT).build();

Which one do you prefer ? Other ideas ?

[gissuebot]

_Original comment posted by [email protected] on 2011-07-13 at 06:18 PM_

---

_(No comment entered for this change.)_

---

Status: Triaged

[gissuebot]

_Original comment posted by [email protected] on 2011-07-16 at 08:37 PM_

---

_(No comment entered for this change.)_

---

Status: Accepted

[gissuebot]

_Original comment posted by [email protected] on 2011-11-10 at 10:53 PM_

---

I'd like to be able to this:
Ordering.explicit(List<T>).unknownsLast().compound(Comparator<T>)

So that I can order by the list, then by the comparator when the item isn't in the list. Currently I have to add all remaining possible items to the end of the list pre-sorted by the second Comparator.

[gissuebot]

_Original comment posted by [email protected] on 2011-12-10 at 03:44 PM_

---

_(No comment entered for this change.)_

---

Labels: Package-Collect

[gissuebot]

_Original comment posted by [email protected] on 2012-05-30 at 07:43 PM_

---

_(No comment entered for this change.)_

---

Labels: -Type-Enhancement, Type-Addition

[gissuebot]

_Original comment posted by drmeths on 2013-10-01 at 09:43 AM_

---

As I have just run into the problem with handling unknown values I am interested in helping with a fix.

The proposed solution earlier in this thread requires a lot of unnecessary code, and needs to use the explicit list twice in the setup chain:

Ordering.explicit(...).nullsFirst().onResultOf(UNKNOWN_TO_NULL_FUNCTION);

I think this proposed syntax is a good solution in keeping with the general chained approach to building Orderings.

Ordering.explicit(List<T>).unknownsLast().compound(Comparator<T>)

In order to achieve this and to leverage the existing rank map within ExplicitOrdering we need to have access to this. I think the neatest way to do this would be to make an inner class of ExplicitOrdering that acts (similarly to nullsFirstOrdering) as a guard and uses the rank map to check for the existence of left and right before deferring to ExplicitOrdering.

I would propose the following API changes to allow explicit ordering to take this form in order to handle unknown objects.

1) Change the visibility of ExplicitOrdering<T> to public
2) Change the factory methods for .explicit(...) in Collection to return ExplicitOrdering<T> rather than Ordering<T>
3) Add the following methods to ExplicitOrdering<T>

public Ordering<T> unknownsFirst()
public Ordering<T> unknownsLast()

I have a working prototype for this including tests if anyone is interested in looking at it.

[kevinb9n]

We still want to do some internal experimentation and potential-usage research.

[cowwoc]

@kevinb9n Can we please decouple these two unrelated issues?

1. Add Ordering.explicit(Iterable)
2. Ability to specify handling for unknown values

The first one could be implemented right away. My use-case is needing to invoke Ordering.explicit(Queue). The code in question is very performance-sensitive (invoked millions of times) so ideally I want to avoid converting the Queue to a List per invocation.

[cpovirk]

(1) is #1542. Can you post there with some benchmarks for the performance gains you'd get from Iterable handling?

Performance concerns are something we haven't see much in the past. (Possibly that's because passing a plain Iterable would perform about as poorly as newArrayList(iterable) already does, since we basically need to copy it to a list internally, while a Queue or other Collection should be better.)

[cowwoc]

@cpovirk I must have missed something then. Where in the code do you depend on the input being a List? As far as I can tell, you simply invoke a for-each loop on it, which means that an Iterable or Collection input would result in identical behavior without needing to copy the input to a List beforehand.

[cowwoc]

@cpovirk To clarify, the main reason I am angling for Iterable is because I want to pass in a ConcurrentLinkedQueue.

Another approach (if you want to prevent the method from accepting non-ordered collections) would be to add a private method that consumes Iterable and then overload explict() for all known types (including ConcurrentLinkedQueue) which delegate to the Iterable method. This would have the advantage of retaining backwards compatibility.

[cpovirk]

Sorry, it's not that we depend on having a List. It's just that we copy its contents into an ImmutableMap.Builder, and we presize that builder based on the size of the input. If the input is any kind of Collection (as in your case), that works. If it's a plain Iterable, then we can't presize†. The code will still work, but we'll be resizing the Builder as we go, so you'll end up with almost the same effect as if you copy to a List yourself.

But again, this doesn't apply to your use case.

† Edit: We could still make the signature _accept_ an Iterable, do an instanceof Collection test, and presize if the _runtime_ type is Collection.

[cowwoc]

@cpovirk Thank you for clarifying. So I agree, we should have a Collection parameter instead of Iterable.

[bjmi]

We still want to do some internal experimentation and potential-usage research.

Are there any conclusions or results yet?

Every once in a while I need exactly this comparator
Ordering.explicit(List<T>).unknownsLast()