CODEWITHSUNDEEP
javatreemapcomparable
Monkooky
Monkooky

Reputation: 31

Java TreeMap with variable Keys

I attempted to implement Fortune's algorithm in Java, and to avoid writing an AVLTree I decided to use a TreeMap with BeachNode keys. BeachNode has the following code: 

public abstract class BeachNode implements Comparable<BeachNode>{

static int idcounter=0;
int id;

public StatusNode(){
    //Allows for two nodes with the same coordinate
    id=idcounter;
    idcounter++;
}

@Override
public int compareTo(BeachNode s) {
    if(s.getX()<this.getX())
        return -1;
    if(s.getX()>this.getX())
        return 1;
    if(s.id<this.id)
        return 1;
    if(s.id>this.id)
        return -1;

    return 0;
}

public abstract double getX();
}

The getX() method of Intersection returns a value dependent on the present height of the sweep line- so it changes partway through execution.

My first question: (I'm fairly sure the answer is yes, but peace of mind would be nice)

If I ensure that for any two BeachNodes A and B, signum(A.compareTo(B)) remains constant while A and B are in the beach tree, will the TreeMap still function despite the changes underlying the compareTo?

My second question:

How can I ensure that such a contract is obeyed?

Note that in Fortune's algorithm, we track at what sweep line positions two intersections will meet- when the sweep line reaches one of these positions, one of the intersections is removed.

This means two intersections A and B in the beach tree will never cross positions, but during a CircleEvent A.compareTo(B) will return 0- interfering with processing the CircleEvent. The contract will be broken only briefly, during the CircleEvent that would remove one Intersection.

This is my first question on StackOverflow, if it is poorly posed or incomplete please inform me and I will do my best to rectify it.

Upvotes: 3

Views: 183

Answers (1)

Andrew
Andrew

Reputation: 1851

According to the TreeMap documentation, the tree will be sorted according to the compareTo method, so any changes that are not reflected in the sign of a.compareTo(b) are allowed. However, you also need to implement an equals method with the same semantics as compareTo. This is really easy if you already have a compareTo method:

public boolean equals(Object object) {
    if (!(object instanceof BeachNode)) {
        return false;
    }
    BeachNode other = (BeachNode) object;
    return this.compareTo(other) == 0;
}

And, since you're overriding equals, you should override hashCode. This is also pretty easy, since you are only using a couple fields to define equality.

public int hashCode() {
    int hash = 1;
    hash = (17 * hash) + (Double getX()).hashCode());
    hash = (31 * hash) + id;
    return hash;
}

I'm not sure about your second question, but since the id of the two intersections should stay different, wouldn't they not be equal? If I'm wrong, hopefully someone who understands the algorithm can help you work that out.

Upvotes: 1

Related Questions