StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Probably the cleanest way to do this is to define these methods:</p> <ul> <li><code>Flows reverse()</code> that returns the reversed direction <code>Flows</code> of a given <code>Flows</code></li> <li><code>Flows canon()</code> which returns a canonicalized form of a <code>Flows</code> <ul> <li>You can define e.g. a <code>Flows</code> is canon if <code>srcAddr.compareTo(dstAddr) <= 0</code></li> <li>Otherwise, its <code>reverse()</code> is canon by definition</li> </ul></li> </ul> <p>Then for non-directional comparison, you can simply compare the canonical forms of the two flows. Having these methods makes the rest of the logic very clean and readable (see code below).</p> <hr> <h3>On <code>Comparator</code>, <code>Comparable</code>, and consistency with <code>equals</code></h3> <p>Using the <code>reverse()</code> concept above, if you want <code>f.equals(f.reverse())</code> always, then perhaps there shouldn't be any concept of directionality in the first place. If this is the case, then canonicalization is the best approach.</p> <p>If <code>f</code> is generally not <code>equals(f.reverse())</code>, and yet you may want <code>f</code> and <code>f.reverse()</code> to compare to 0, then <a href="http://download.oracle.com/javase/6/docs/api/java/lang/Comparable.html" rel="nofollow noreferrer"><code>Comparable</code></a> should not be used, because doing so would impose a natural ordering that is not consistent with equals.</p> <p>From the documentation:</p> <blockquote> <p>The natural ordering for a class <code>C</code> is said to be <em>consistent with</em> <code>equals</code> if and only if <code>e1.compareTo(e2) == 0</code> has the same boolean value as <code>e1.equals(e2)</code> for every <code>e1</code> and <code>e2</code> of class <code>C</code>.</p> <p>It is <em>strongly recommended</em> (though not required) that natural orderings be consistent with <code>equals</code>.</p> </blockquote> <p>That is, instead of imposing a natural ordering in <code>Comparable</code> that is inconsistent with <code>equals</code>, you should instead provide a non-directional <a href="http://java.sun.com/javase/6/docs/api/java/util/Comparator.html" rel="nofollow noreferrer"><code>Comparator</code></a> instead.</p> <p>As an analogy, compare this situation with <a href="http://download.oracle.com/javase/6/docs/api/java/lang/String.html" rel="nofollow noreferrer"><code>String</code></a>, which provides <a href="http://download.oracle.com/javase/6/docs/api/java/lang/String.html#CASE_INSENSITIVE_ORDER" rel="nofollow noreferrer"><code>Comparator<String> CASE_INSENSITIVE_ORDER</code></a>, which allows two strings that are not <code>equals</code> to compare to 0 by case-insensitivity.</p> <p>So here you'd write a <code>Comparator<Flows></code> that allows two <code>Flows</code> that are not <code>equals</code> to compare to 0 by directional-insensitivity.</p> <h3>See also</h3> <ul> <li><a href="http://download.oracle.com/javase/tutorial/collections/interfaces/order.html" rel="nofollow noreferrer">Java Tutorials/Collections/Object Ordering</a></li> </ul> <h3>Related questions</h3> <ul> <li><a href="https://stackoverflow.com/questions/2266827/when-to-use-comparable-vs-comparator">When to use Comparable vs Comparator</a></li> <li><a href="https://stackoverflow.com/questions/1440134/java-what-is-the-difference-between-implementing-comparable-and-comparator">Java: What is the difference between implementing Comparable and Comparator?</a></li> <li><a href="https://stackoverflow.com/questions/420223/difference-between-compare-and-compareto">difference between compare() and compareTo()</a></li> <li><a href="https://stackoverflow.com/questions/2858628/comparable-and-comparator-contract-with-regards-to-null">Comparable and Comparator contract with regards to null</a></li> <li><a href="https://stackoverflow.com/questions/2892947/why-does-the-java-collections-framework-offer-two-different-ways-to-sort/">Why does the Java Collections Framework offer two different ways to sort?</a></li> </ul> <hr> <h3>Example implementation</h3> <p>Here's an example implementation of an <code>Edge</code> class that has a <code>from</code> and <code>to</code>, with a directional natural ordering that is consistent with <code>equals</code>, which also provides a non-directional <code>Comparator</code>.</p> <p>It's then tested with 3 kinds of <code>Set</code>:</p> <ul> <li>A <code>HashSet</code>, to test <code>equals</code> and <code>hashCode</code></li> <li>A <code>TreeSet</code>, to test natural ordering</li> <li>A <code>TreeSet</code> with the custom <code>Comparator</code>, to test non-directionality</li> </ul> <p>The implementation is concise and clear, and should be instructive.</p> <pre><code>import java.util.*; class Edge implements Comparable<Edge> { final String from, to; public Edge(String from, String to) { this.from = from; this.to = to; } @Override public String toString() { return String.format("%s->%s", from, to); } public Edge reverse() { return new Edge(to, from); } public Edge canon() { return (from.compareTo(to) <= 0) ? this : this.reverse(); } @Override public int hashCode() { return Arrays.hashCode(new Object[] { from, to }); } @Override public boolean equals(Object o) { return (o instanceof Edge) && (this.compareTo((Edge) o) == 0); } @Override public int compareTo(Edge other) { int v; v = from.compareTo(other.from); if (v != 0) return v; v = to.compareTo(other.to); if (v != 0) return v; return 0; } public static Comparator<Edge> NON_DIRECTIONAL = new Comparator<Edge>() { @Override public int compare(Edge e1, Edge e2) { return e1.canon().compareTo(e2.canon()); } }; } public class Main { public static void main(String[] args) { testWith(new HashSet<Edge>()); testWith(new TreeSet<Edge>()); testWith(new TreeSet<Edge>(Edge.NON_DIRECTIONAL)); } public static void testWith(Set<Edge> set) { set.clear(); set.add(new Edge("A", "B")); set.add(new Edge("C", "D")); System.out.println(set.contains(new Edge("A", "B"))); System.out.println(set.contains(new Edge("B", "A"))); System.out.println(set.contains(new Edge("X", "Y"))); System.out.println(set); set.add(new Edge("B", "A")); set.add(new Edge("Z", "A")); System.out.println(set); System.out.println(); } } </code></pre> <p>The output is (<a href="http://ideone.com/RVUzB" rel="nofollow noreferrer">as seen on ideone.com</a>) below, annotated:</p> <pre><code>// HashSet // add(A->B), add(C->D) true // has A->B? false // has B->A? false // has X->Y? [C->D, A->B] // add(B->A), add(Z->A) [B->A, C->D, Z->A, A->B] // TreeSet, natural ordering (directional) // add(A->B), add(C->D) true // has A->B? false // has B->A? false // has X->Y [A->B, C->D] // add(B->A), add(Z->A) [A->B, B->A, C->D, Z->A] // TreeSet, custom comparator (non-directional) // add(A->B), add(C->D) true // has A->B? true // has B->A? false // has X->Y? [A->B, C->D] // add(B->A), add(Z->A) [A->B, Z->A, C->D] </code></pre> <p>Note that in the non-directional <code>TreeSet</code>, <code>Z->A</code> is canonicalized to <code>A->Z</code>, which is why it appears before <code>C->D</code> in this order. Similarly, <code>B->A</code> is canonicalized to <code>A->B</code>, which is already in the set, which explains why there are only 3 <code>Edge</code> there.</p> <h3>Key points</h3> <ul> <li><code>Edge</code> is immutable</li> <li><a href="http://download.oracle.com/javase/6/docs/api/java/util/Arrays.html#hashCode%28java.lang.Object%5B%5D%29" rel="nofollow noreferrer"><code>Arrays.hashCode(Object[])</code></a> is used for convenience; no need to code all that formulas</li> <li>If the natural ordering is consistent with <code>equals</code>, you can use <code>compareTo == 0</code> in <code>equals</code></li> <li>Use the multistep <code>return</code> logic in <code>compareTo</code> for conciseness and clarity</li> <li>Having <code>reverse()</code> and <code>canon()</code> greatly simplifies the non-directional comparison <ul> <li>Simply compare their canonicalized forms in their natural ordering</li> </ul></li> </ul> <h3>See also</h3> <ul> <li><em>Effective Java 2nd Edition</em> <ul> <li>Item 8: Obey the general contract when overriding <code>equals</code></li> <li>Item 9: Always override <code>hashCode</code> when you override <code>equals</code></li> <li>Item 10: Always override <code>toString</code></li> <li>Item 12: Consider implementing <code>Comparable</code></li> <li>Item 15: Minimize mutability</li> <li>Item 36: Consistently use <code>@Override</code> annotation</li> <li>Item 47: Know and use libraries</li> </ul></li> </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload