Does Java have a function that lexicographically orders lists (rather than their elements)?
In Haskell, type lists Ord a => [a]
are lexicographically ordered. For example,
> compare [1, 2, 3] [2, 3, 4]
LT
> compare [1] [1, 2]
LT
This is an immediate generalization of the lexicographic ordering that most languages have in strings. In Java, for example
"abc".compareTo("bcd") // -1
"a".compareTo("ab") // -1
Is there any Java function in the standard library or other library that implements the lexicographic ordering of lists that Haskell has? I would assume it has a type signature along the lines
<T extends Comparable<T>> int compare(List<T>, List<T>)
Implementing this itself is not difficult, but I would not reinvent the wheel.
source to share
There is no such method that I know of. List
(and its specific implementations like ArrayList
) don't extend / implement the interface Comarable
, which means they don't do any ordering.
I think this is the correct language solution, because lists, in my opinion, are really not in canonical order.
You can implement your own comparator that compares lists and passes that to objects that need to compare the list (for example Collections.sort(list, comparator)
). For example:
class LexicographicalListComparator<T extends Comparable<T>> implements Comparator<List<T>> {
@Override
public int compare(List<T> o1, List<T> o2) {
Iterator<T> i1 = o1.iterator();
Iterator<T> i2 = o2.iterator();
int result;
do {
if (!i1.hasNext()) {
if (!i2.hasNext()) return 0; else return -1;
}
if (!i2.hasNext()) {
return 1;
}
result = i1.next().compareTo(i2.next());
} while (result == 0);
return result;
}
}
source to share
Just like Hopye said, List
doesn't implement the interface Comparable
. If you want to implement your own comparator for lexicographic comparison of strings (and you can order lists of strings after that), Java has a Collator class:
The Collator class performs a local String comparison.
If that's not enough, you can use RuleBasedCollator , it works like Collator
, but you can personalize it a lot more.
Both of them implement the interface Comparable
, so they can use compare
.
import java.text.Collator;
...
Collator c = Collator.getInstance();
c.compare(s1, s2);
If you want it to follow some language specific rules, you must do:
import java.util.Locale;
...
Collator c = Collator.getInstance(new Locale("es", "MX"));
c.compare(s1, s2);
More about Locale .
source to share