Triads not showing up to fight? (Java Set missing an item)
I have code from two companies asoft and bsoft. I cannot change either. This is a simplified version of my situation which I'm pretty sure has enough information to the find what's causing the problem.
bsoft provides IGang , which represents a gang that can battle other gangs.
package bsoft;
public interface IGang {
/** @return negative, 0, or positive, respectively
* if this gang is weaker than, equal to, or stronger
* than the other
*/
public int compareTo(IGang g);
public int getStrength();
public String getName();
public void attack(IGang g);
public void weaken(int amount);
}
asoft provides GangWar , which allows IGang s to battle:
package asoft;
import java.util.*;
import bsoft.*;
/** An `IGang` ordered by identity (name) */
public interface ComparableGang extends IGang, Comparable<IGang> {}
package asoft;
import java.util.*;
public class GangWar {
public final Set<ComparableGang> gangs = new TreeSet<ComparableGang>();
public void add(ComparableGang g) {gangs.add(g);}
public void doBattle() {
while (gangs.size() > 1) {
Iterator<ComparableGang> i = gangs.iterator();
ComparableGang g1 = i.next();
ComparableGang g2 = i.next();
System.out.println(g1.getName() + " attacks " + g2.getName());
g1.attack(g2);
if (g2.getStrength() == 0) {
System.out.println(g1.getName() + " smokes " + g2.getName());
gangs.remove(g2);
}
if (g1.getStrength() == 0) {
System.out.println(g2.getName() + " repels " + g1.getName());
gangs.remove(g1);
}
}
for (ComparableGang g : gangs) {
System.out.println(g.getName() + " now controls the turf!");
}
}
}
It requires the additional constraint that the Gang s you supply to it are Comparable , presumably so it can sort by name or avoid duplicates. Each gang (in an arbitrary order, Set order used here for simplicity) attacks another gang, until only one gang is left (or no gangs, if the last two have a tie). I've written a simple implementation of ComparableGang to test it out:
import asoft.*;
import bsoft.*;
import java.util.*;
class Gang implements ComparableGang {
final String name;
int strength;
public Gang(String name, int strength) {
this.name = name;
this.strength = strength;
}
public String getName() {return name;}
public int getStrength() {return strength;}
public int compareTo(IGang g) {
return strength - g.getStrength();
}
public void weaken(int amount) {
if (strength < amount) strength = 0;
else strength -= amount;
}
public void attack(IGang g) {
int tmp = strength;
weaken(g.getStrength());
g.weaken(tmp);
}
public boolean equals(Object o) {
if (!(o instanceof IGang)) return false;
return name.equals(((IGang)o).getName());
}
}
class Main {
public static void main(String[] args) {
GangWar gw = new GangWar();
gw.add(new Gang("ballas", 2));
gw.add(new Gang("grove street", 9));
gw.add(new Gang("los santos", 8));
gw.add(new Gang("triads", 9));
gw.doBattle();
}
}
Testing it out...
$ java Main
ballas attacks los santos
los santos repels ballas
los santos attacks grove street
grove street repels los santos
grove street now controls the turf!
The problem is, triads do not show up to the fight. In fact, printing gangs.size() right at the start of doBattle() returns 3 instead of 4. Why? How to fix it?
The problem is, triads do not show up to the fight. In fact, printing gangs.size() right at the start of doBattle() returns 3 instead of 4. Why?
Both triads and grove street have a strength of 9. Therefore they're equal in terms of Gang.compareTo (implementing Comparable ). Therefore only one is permitted in a TreeSet .
If you don't want to remove items which are duplicates in terms of their sort order, don't use a TreeSet ...
EDIT: The ComparableGang interface description indicates what's expected:
/** An `IGang` ordered by identity (name) */
public interface ComparableGang extends IGang, Comparable<IGang> {}
Your compareTo method does not order "by identity (name)" - it orders by strength. To be honest, it's a pretty stupid interface in the first place, as it would have been perfectly easy for asoft to create a class of public class GangNameComparator : Comparator<IGang> , and then supply that as the comparator to the tree set if they wanted to order by name.
However, as they're suggesting that you should implement the comparison, you need to do so as the interface describes:
public int compareTo(IGang g) {
return name.compareTo(g.getName());
}
However... as you note in comments (and as noted in Rob's answer), this then contradicts the convention-bustingly-named IGang description:
public interface IGang {
/** @return negative, 0, or positive, respectively
* if this gang is weaker than, equal to, or stronger
* than the other
*/
public int compareTo(IGang g);
}
It's impossible to implement ComparableGang to satisfy both its own documentation and the IGang documentation. This is basically broken by design, on asoft's part.
Any code should be able to use an IGang implementation, knowing only about IGang , and relying on the implementation following the IGang contract. However, asoft broke that assumption by requiring different behaviour in an interface extending IGang .
It would have been reasonable for them to add more requirements in ComparableGang , so long as they didn't violate the existing requirements of IGang .
Note that this is an important difference between C# and Java. In C#, two functions in two different interfaces with the same signature can be combined into one interface that inherits both of them and the two methods remain distinct and accessible. In Java, the two methods, since they are completely abstract and have the same signature, are considered to be the same method and a class implementing the combined interfaces has only one such method. So in Java ComparableGang is invalid because it cannot have an implementation of compareTo() that satisfies the contract of ComparableGang and the contract of IGang.
TL;DR: Use B) Below
From the javadoc for Comparable (and same for Comparator too!):
The natural ordering for a class C is said to be consistent with equals if and only if e1.compareTo(e2) == 0 has the same boolean value as e1.equals(e2) for every e1 and e2 of class C. Note that null is not an instance of any class, and e.compareTo(null) should throw a NullPointerException even though e.equals(null) returns false.
In your case (simplified),
equals is defined as equality of name compareTo is defined as comparison of strength This fails the above condition:
strength s are equal, but the two name s are different name s are equal, but the two strength s are different (probably a condition avoided by your application logic) Answer
How to correct?
A) If your requirements allow you to have the set sorted by name (consistent with comment in asoft code):
// will only return 0 if the strengths are equal AND the names are equal
public int compareTo(ComparableGang g) {
return name.compareTo(g.getName());
}
B) If your requirements force you to have the set sorted by strength (and then name ) (consistent with comment in bsoft code).
// will return 0 if & only if the strengths are equal AND the names are equal
public int compareTo(ComparableGang g) {
int result = strength - g.getStrength();
if (result == 0) result = name.compareTo(g.getName());
return result;
}
// will return true if & only if the strengths are equal AND the names are equal
public boolean equals(Object o) {
if (!(o instanceof ComparableGang)) return false;
ComparableGang gang2 = (ComparableGang)o;
return name.equals(gang2.getName()) && strength == gang2.getStrength();
}
// For this case, if it's illegal to have two gangs of same name but different
// strength (it should be illegal!), then app logic must enforce this - the Set
// no longer will.
Comment 1: Whilst it's an issue for you to modify asoft's GangWar class, it would be better if you could place above two methods of B) into:
class ComparableGangComparator implements Comparator<ComparableGang> {
}
and then modify how GangWar constructs the Set:
public final Set<ComparableGang> gangs = new TreeSet<ComparableGang>(
new ComparableGangComparator());
That way, you can leave the two methods of A) within class Gang - leaving the class with it's "true" equals & compareTo from an object identity POV.
Comment 2: Contradicting comments on asoft's & bsoft's compareTo methods
From a theoretical POV: If asoft's comment is not a typo, then not only has asoft extended bsoft's interface, but they've changed the required behaviour of one of the methods. This is not actually a contradiction at all - it's an override : asoft's comment "wins".
From a practical POV: You need your fingers crossed asoft did this on purpose & the comment is correct. If it's a typo from asoft, then bsoft's comment is better & bsoft "wins". You could send a query to asoft or check their doc/examples to confirm.
The Gang.compareTo method is based on their strengths, so since the triads and grove street have the same strength, the TreeSet thinks they are equal and then removes them.
Based on how the ComparableGang expects to sort them, I'd say ignore the IGang interface's request for the behavior of compareTo and change it to this.
public int compareTo(IGang g) {
return name.compareTo(g.getName());
}