Can it.unimi.dsi.fastutil.Pair extends Comparable?

[qblyy]

Thanks.

The Eclipse Collections has a similar (immutable) Pair series, all implemented Comparable. Can fastutil Pair series implement it too? Comparable is very useful.

[vigna]

What do they do? Lexicographic (compare the first item, in case of equality compare the second item)?

[vigna]

I have to think about how to do this properly. In Eclipse Collections, IntIntPair has no relationship with Pair, whereas in our setup IntIntPair extends Pair<Integer, Integer>. The problem is that if I declare Pair to be comparable, it can only be comparable with Pair, which means that IntIntPair cannot be Comparable. This is extremely annoying.

[qblyy]

Thanks.

What do they do? Lexicographic (compare the first item, in case of equality compare the second item)? Yes.

Maybe IntIntPair can't extends Pair<Integer, Integer>, I think this is the best way now. If fastutil needs this extension, maybe Pair<> can't be Comparable. Such as CharSequence is not, but String is Comparable.

[vigna]

One solution is to have the ObjectObjectPair interface. Presently it is not necessary, but it would just implement Comparable<ObjectObjectPair<L,R>>. It's a bit weird but I don't see any other clean way to do this.

@techsy730 @incaseoftrouble I'd love to hear your opinion on this...

[incaseoftrouble]

Not sure if I like that.

For Object-Pairs (at least one of the two things is object): 1) It weakens compile time assertions - Pair<L, R> would be comparable even for non-comparable types 2) You'd kinda want to be able to specify a comparator optionally (which overloads the interface) 3) Not sure when you'd need that (in most situations you'd get away with a comparator (Comparator.comparing(Pair::first).thenComparing(pair::second) isn't that long)

What about adding canonical comparators? Like IntIntPairs.comparator() etc.?

[vigna]

You're right about the weakening of compile-time assertions. Eclipse Collections does it that way, but I'm wary, too, about having comparable for a class without comparable types. We might have it, however, for SortedPair, as the type must be Comparable by definition.

Nonetheless, other JDK classes do the same: TreeSet does not require E to be Comparable.

Also, introducing ObjectObjectPair just for making pairs comparable is not nice (and I agree, it is difficult to imagine a use case).

But lexicographical order is the natural order for pairs—you'd just drop pairs in a SortedSet and you'd have them in lexicographical order. You could always override the method.

The main advantage of a IntIntPair().lexicographicalComparator() approach is that of avoiding ObjectObjectPair. Pair.lexicographicalComparator() would be weakly typed anyway.

[incaseoftrouble]

Nonetheless, other JDK classes do the same: TreeSet does not require E to be Comparable.

But they offer a comparator-based constructor.

But lexicographical order is the natural order for pairs—you'd just drop pairs in a SortedSet and you'd have them in lexicographical order. You could always override the method.

It might make sense to make the specific pairs comparable. However then things again start to get messy when you e.g. have LongLongPair and IntIntPair in one collection (however, this is a use case we can exclude I think)

For now, I think having a comparator is fine. Then you have fine control. I guess that quite often you might also be interested in comparing the right part of the pair first. This you can only do with a comparator.

[vigna]

I've just committed methods providing a lexicographical comparator for pairs. Any comments are welcome!

[incaseoftrouble]

Only thing I could think of is that you could make the comparator instance private static final. Then having implements Comparable<Foo> via FooPairs.lexComparator().compare(this.v, that.v) has a better chance of getting inlined.

[vigna]

Yeah, that was my idea and the original implementation. Unfortunately, it's impossible as private is not allowed in interfaces, so the instance would be visible and I didn't like the idea.

Also, lambdas are compiled into a static method and an invokedynamic instruction, and I believe that a lot of efforts have gone into making them fast and inlinable.

[incaseoftrouble]

Ah its in the interface. We don't have a XYPairs static helper class, right?

Also, lambdas are compiled into a static method and an invokedynamic instruction, and I believe that a lot of efforts have gone into making them fast and inlinable.

Very likely you are right. The lamdas there are non-capturing so the compiler should figure out quite easily that they are "static".

[vigna]

Ah its in the interface. We don't have a XYPairs static helper class, right?

No, we have so much proliferation of classes that I'm trying to put helper methods in the interfaces now.

But you were right—this solution is much less code and the resulting approach is much more flexible.