title: Partial ordered Comparator
body: <p>How to implement <code>java.util.Comparator</code> that orders its elements according to a partial order relation?</p>
  
  <p>For example given a partial order relation <em>a</em> ≺ <em>c</em>, <em>b</em> ≺ <em>c</em>; the order of <em>a</em> and <em>b</em> is undefined.</p>
  
  <p>Since <code>Comparator</code> requires a total ordering, the implementation orders elements for which the partial ordering is undefined arbitrarily but consistent.</p>
  
  <p>Would the following work?</p>
  
  <pre><code>interface Item {
      boolean before(Item other);
  }
  
  class ItemPartialOrderComperator implements Comparator&lt;Item&gt; {
      @Override
      public int compare(Item o1, Item o2) {
          if(o1.equals(o2)) {  // Comparator returns 0 if and only if o1 and o2 are equal;
              return 0;
          }
          if(o1.before(o2)) {
              return -1;
          }
          if(o2.before(o1)) {
              return +1;
          }
          return o1.hashCode() - o2.hashCode(); // Arbitrary order on hashcode
      }
  }
  </code></pre>
  
  <ul>
  <li>Is this comparator's ordering transitive?<br>
  <em>(I fear that it is not)</em></li>
  <li>Are <code>Comparators</code> required to be transitive?<br>
  <em>(when used in a <code>TreeMap</code>)</em></li>
  <li>How to implement it correctly?<br>
  <em>(if the implementation above doesn't work)<br>
  (Hashcodes can collide, for simplicity collisions the example ignores collisions; see <a href="https://stackoverflow.com/a/28494/814206">Damien B's answer</a> to <a href="https://stackoverflow.com/questions/28301/impose-a-total-ordering-on-all-instances-of-any-class-in-java">Impose a total ordering on all instances of *any* class in Java</a> for a fail-safe ordering on hashcodes.)</em>  </li>
  </ul>