CODEWITHSUNDEEP
javaset
harshit
harshit

Reputation: 7951

problem while removing an element from the TreeSet

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

Upvotes: 0

Views: 6509

Answers (3)

vladr
vladr

Reputation: 66721

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

Upvotes: 4

polygenelubricants
polygenelubricants

Reputation: 384016

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.

Upvotes: 4

Matthew Flaschen
Matthew Flaschen

Reputation: 285077

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

Upvotes: 0

Related Questions