problem while removing an element from the TreeSet

Question

I am doing the following

class RuleObject implements Comparable{



    @Override
    public String toString() {
        return "RuleObject [colIndex=" + colIndex + ", probability="
                + probability + ", rowIndex=" + rowIndex + ", rule=" + rule
                + "]";
    }
    String rule;
    double probability;
    int rowIndex;

    int colIndex;

    public RuleObject(String rule, double probability) {
        this.rule = rule;
        this.probability = probability;
    }
    @Override
    public int compareTo(Object o) {

        RuleObject ruleObj = (RuleObject)o;
        System.out.println(ruleObj);
        System.out.println("---------------");
        System.out.println(this);
        if(ruleObj.probability > probability)
            return 1;
        else if(ruleObj.probability < probability)
            return -1;
        else{
            if(ruleObj.colIndex == this.colIndex && ruleObj.rowIndex == this.rowIndex && ruleObj.probability == this.probability && ruleObj.rule.equals(this.rule))
                return 0;
        }
        return 1;

    }


}

And I have a TreeSet containing elements of RuleObject. I am trying to do the following :

System.out.println(sortedHeap.size());
        RuleObject ruleObj = sortedHeap.first();
        sortedHeap.remove(ruleObj);
System.out.println(sortedHeap.size());

I can see that the size of set remains same. I am not able to understand why is it not being deleted. Also while deleting I could see compareTo method is called. But it is called for only 3 object whereas in set there are 8 objects. Thanks

Answer 1

As polygenelubricants indicated, you must implement equals on your RuleObjects.

Moreover, your comparator is essentially broken. It does not impose total ordering, i.e. in certain cases it will claim that a RuleObject a is both greater than and less than another RuleObject b (e.g. if a.probability==b.probability and a.colIndex != b.colIndex.) This will result in unwanted behaviour during tree insertion, traversal etc.

In the end, compareTo must also be consistent with equals, i.e.

The natural ordering for a class C is said to be consistent with equals if and only if (e1.compareTo((Object)e2) == 0) has the same boolean value as e1.equals((Object)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.

If you do not care about RuleObjects ordering, use a HashSet.

Otherwise (i.e. you want to iterate over the TreeSet in a well defined, e.g. priority, order), implement Comparable to take into account all fields of interest, e.g.:

public int compareTo(Object o) {
  RuleObject r = (RuleObject)o;
  // assume no nulls for now, but you should eventually check
  // also assume o is always of type RuleObject for now,
  //  but you should eventually check
  return
    priority < r.priority ? -1 :
    priority > r.priority ? 1 :
    colIndex < r.colIndex ? -1 :
    colIndex > r.colIndex ? 1 :
    rowIndex < r.rowIndex ? -1 :
    rowIndex > r.rowIndex ? 1 : 0;
}

boolean equals(Object o) {
  // Delegate to compareTo(); no code duplication, consistent.
  return compareTo(o) == 0;
}

Cheers, V.

Answer 2

Look at the specification for remove:

Removes the specified element from this set if it is present. More formally, removes an element e such that (o==null ? e==null : o.equals(e)), if this set contains such an element.

Your problem is that RuleObject does not @Override equals(Object other). You need to do that, and of course, with that you also need to @Override hashCode().

---

Also, the reason why compareTo is being called fewer times than the number of elements is because it's supposed to be a O(log N) operation; that's the whole purpose of using TreeSet. If you have 1024 elements, you can expect compareTo to be called no more than 10 times.

---

As Vlad points out, your comparator is broken. Specifically, the last statement return 1; breaks it. You should expand the equal probability case to return -1, 0, +1 depending on the other fields.

Answer 3

If you want it to Just Work™, try Apache's CompareToBuilder, HashCodeBuilder, and EqualsBuilder. I have provided sample code to start from below. You certainly don't have to take this route, but I think you will find it simplifies things. Note the consistent pattern between the different functions.

public int compareTo(Object o) {
  RuleObject ruleObj = (RuleObject) o;
  return new CompareToBuilder()
    .append(this.probability, ruleObj.probability)
    .append(this.colIndex, ruleObj.colIndex)
    .append(this.rowIndex, ruleObj.rowIndex)
    .append(this.rule, ruleObj.rule)
    .toComparison();
}

public int hashCode() {
  // You should customize the hard-coded numbers, as described in the docs.
  return new HashCodeBuilder(17, 37).
    append(probability).
    append(colIndex).
    append(rowIndex).
    append(rule).
    toHashCode();
}

public boolean equals(Object obj) {
  if (obj == null) { return false; }
  if (obj == this) { return true; }
  if (obj.getClass() != getClass()) {
    return false;
  }
  RuleObject rhs = (RuleObject) obj;
  return new EqualsBuilder()
    .append(probability, rhs.probability)
    .append(colIndex, rhs.colIndex)
    .append(colIndex, rhs.colIndex)
    .append(rule, rhs.rule)
    .isEquals();
}