Triads not showing up to fight? (Java Set missing an item)

Question

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 IGangs 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 Gangs 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?

Answer 1

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.

Answer 2

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:

• when the two strengths are equal, but the two names are different
• when the two names are equal, but the two strengths 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.

Answer 3

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());
}

Answer 4

Fundamentally the problem is that a ComparableGang is an IGang, but IGangs sort by strength and ComparableGangs sort by name, so a ComparableGang is not an IGang.

TL;DR The right way to fix this is to fix the interfaces and library code. The workaround for writing code to work with both libraries is explained in this answer.

---

The best solution is to fix both interfaces. bsoft only needs to change one line of their code to:

public interface IGang extends Comparable<IGang> {

Nothing else in the interface or any other code needs to change, but asoft would then be on notice that IGang's are already comparable. (EDIT: On second thought, since IGang.compareTo() is not consistent with equals(), which is the root of why the triads are not showing up to the fight, bsoft probably did the right thing in not extending Comparable. What they did wrong was declaring compareTo() instead of, say, compareStrengthTo().)

asoft doesn't need to wait for bsoft to change anything, though. It's really their fault to begin with that they created a broken-by-design interface. They should have just picked a way to get a Comparator<IGang> that sorts by name. So if I worked at asoft, GangWar would look more like this:

public class GangWar {
    public final Set<IGang> gangs;
    public GangWar(Comparator<IGang> gangNameComparator) {
        gangs = new TreeSet<IGang>(gangNameComparator);
    }
    public void add(IGang g) {gangs.add(g);}
    public void doBattle() {
        while (gangs.size() > 1) {
          Iterator<IGang> i = gangs.iterator();
          IGang g1 = i.next();
          IGang 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 (IGang g : gangs) {
            System.out.println(g.getName() + " now controls the turf!");
        }
    }
}

So rather than completely breaking IGang, they just ask for what they need (that IGang doesn't have) when they need it. With this change (and a Comparator implementation), the program outputs:

ballas attacks grove street
grove street repels ballas
grove street attacks los santos
los santos repels grove street
los santos attacks triads
triads repels los santos
triads now controls the turf!

Of course, if you're stuck with the libraries as is, you can read this answer for the general approach to living with the breakage without touching the library.