Partial Ordered Comparator to Total Ordered Compar

问题:

First of all: this is not a duplicate of the question Partial Ordered Comparator but rather builds on it.

My goal is to sort a list of objects (e.g. [2, "a", 1]) in-place such that after sorting no two integers are out of order.

For this, I used the implementation in this answer with the following partial ordering and got a IllegalArgumentException:

java.lang.IllegalArgumentException: Comparison method violates its general contract!
        at java.util.TimSort.mergeHi(TimSort.java:868)
        at java.util.TimSort.mergeAt(TimSort.java:485)
        at java.util.TimSort.mergeCollapse(TimSort.java:410)
        at java.util.TimSort.sort(TimSort.java:214)
        at java.util.TimSort.sort(TimSort.java:173)
        at java.util.Arrays.sort(Arrays.java:659)
        at java.util.Collections.sort(Collections.java:217)
        at MySortUtils.sortPartially(ArimsCollectionUtils.java:150)

This is because the proposed comparator has a flaw. Demonstration:

use a partial ordering R over all Object instances for which a.before(b) iff a and b are both integers and a < b according to the integer's natural ordering:

public boolean before(Object a, Object b) {
    // only integers are ordered
    if (a instanceof Integer && b instanceof Integer) {
        int intA = ((Integer) a).intValue();
        int intB = ((Integer) b).intValue();
        return intA < intB;
    } else {
        return false;
    }
}

The reason for this is that with the following implementation

Comparator<Object> fullCmp = new Comparator<Object>() {

  // Implementation shamelessly plucked from
  // https://stackoverflow.com/a/16702332/484293
  @Override
  public int compare(Object o1, Object o2) {
    if(o1.equals(o2)) {
      return 0;
    }
    if(partialComparator.before(o1, o2)) {
        return -1;
    }
    if(partialComparator.before(o2, o1)) {
        return +1;
    }
    return getIndex(o1) - getIndex(o2);
  }

  private Map<Object ,Integer> indexMap = new HashMap<>();

  private int getIndex(Object i) {
    Integer result = indexMap.get(i);
    if (result == null) {
        indexMap.put(i, result = indexMap.size());
    }
    return result;
  }
};

this can yield a cycle in the produced ordering, since

// since 2 and "a" are incomparable, 
// 2 gets stored with index 0 
// "a" with index 1
assert fullCmp.compare(2, "a") == -1   

// since "a" and 1 are incomparable,
// "a" keeps its index 1
// 2 gets index 2
assert fullCmp.compare("a", 1) == -1

// since 1 and 2 are comparable:
assert fullCmp.compare(1,   2) == -1

are all true, i.e. 2 < "a", "a" < 1 and "1 < 2, which obviously is not a valid total ordering.

Which leaves me with the final question: How do I fix this bug?

回答1:

I cannot suggest a full solution for any partial ordering. However for your particular task (comparing integers ignoring anything else) you just have to decide whether integers go before or after anything else. This comparator which assumes that integers go first should work perfectly (using Java-8 syntax):

Comparator<Object> comparator = (a, b) -> {
    if(a instanceof Integer) {
        if(b instanceof Integer) {
            return ((Integer) a).compareTo((Integer) b);
        }
        return -1;
    }
    if(b instanceof Integer)
        return 1;
    return 0;
};

Example:

List<Object> list = Arrays.asList("a", "bb", 1, 3, "c", 0, "ad", -5, "e", 2);
list.sort(comparator);
System.out.println(list); // [-5, 0, 1, 2, 3, a, bb, c, ad, e]

回答2:

You are using getIndex() inside the comparator. This would normally be fine but not while values are being swapped around inside a sort algorithm.
So choose a comparator function that relies just on the values, not on their position in the array.
You can make the non-integers sort either before or after all integers. Either make them all equal (return 0 in the comparator), or use some additional criterion to distinguish them.

回答3:

If all you want is order integers (and not some other totally ordered type) according to their own natural order, and if you do not care how other elements are ordered with repect to the integers, but you do want the result to be a correct total ordering (i.e., transitive and antisymmetric), then a minor variation on the answer you started out with and rejected will do the trick:

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

class IntegerPartialOrderComperator implements Comparator<Object> {
    @Override
    public int compare(Object o1, Object o2) {
        return getIndex(o1) - getIndex(o2);
    }

    private int getIndex(Object i) {
        Integer result = indexMap.get(i);
        if (result == null) {
            if (i instanceof Integer) {
                result = (Integer) i*2;
            } else {
                result = indexMap.size()*2+1;
            }
            indexMap.put(i, result);
        }
        return result;
    }

    private Map<Object,Integer> indexMap = new HashMap<>();

    public static void main(String[] args) {
        Comparator<Object> cmp = new IntegerPartialOrderComperator();
        // since 2 and "a" are incomparable,
        // 2 gets stored with index 4 and "a" with index 3
        assert cmp.compare(2, "a") > 0;

        // since "a" and 1 are incomparable,
        // "a" keeps its index 3 while 1 gets index 2
        assert cmp.compare("a", 1) > 0;

        // since 1 and 2 are comparable:
        assert cmp.compare(1, 2) < 0;
    }
}

This uses run-time generated indices for all values as a basis for the comparison, where the even numbers are used as indices for the Integers and the odd numbers as indices for anything else that may come along.

If your numbers can get big (> 2^30-1) or small (< -2^30) then the doubling will overflow so you'll have to resort to BigInteger for the value type of the index map.

Note that the same trick will not work for many types beside Integer, since you need to characterise the total order you want to respect through index numbers in the first place. I think a solution will get quite a bit more tricky if that is not possible: computing an index for a new element will probably take worst time linear in the number of previously compared elements, and that just ruins the Comparator for sorting (efficiently).

回答4:

You can groups elements into those which can be compared to each other. You have the problem that canCompare(a, b) and canCompare(b, c) but !canCompare(a, c). However we assume this is not the case you can

• start with one element and compare it to all the others. If it is uncomparable to any other element, add to the results so far
• if you find it is comparable to one or more elements, sort those and add them to the results.
• keep doing this until there is no more elements left.

This doesn't lend itself to being Comparable as you are not using a conventional sorting algorithm. However if you must do this, you can start by determining the order required and comparing the indexes of the order required.

---

A simple work around is to provide an arbitrary sorting strategy so you have total ordering. The problem you have is that if you sort 1, "a", 2 What do you expect to happen? You could leave it as undefined whether you get 1, 2, "a" or "a", 1, 2 or you say that everything comparable is in order already. If the later is ok, bubble sort will do the job.

---

You cannot use TimSort for partial ordering. It assumes that if you compare a and b you can say whether it is greater than, equal to, or less than. There is no other option.

However, other sorting algorithms don't have this requirement. Insertion sort being one of them. The only requirement that is a < b and b < c then a < c must follow or you cannot order these entries.

BTW You can't have -1 mean incomparable as -1 generally means is greater than.

What you could do is

static final int INCOMPARABLE = Integer.MIN_VALUE;

// since 2 and "a" are incomparable, 
// 2 gets stored with index 0 
// "a" with index 1
assert fullCmp.compare(2, "a") == INCOMPARABLE;  

// since "a" and 1 are incomparable,
// "a" keeps its index 1
// 2 gets index 2
assert fullCmp.compare("a", 1) == INCOMPARABLE;  

// since 1 and 2 are comparable:
assert fullCmp.compare(1,   2) == -1;

assert fullCmp.compare(2,   1) == 1;