Java TreeMap with variable keys
I tried to implement the luck algorithm in Java, and in order to avoid writing an AVLTree I decided to use the TreeMap and 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 () Intersection method returns a value based on the current scanline height, so it changes partially through execution.
My first question is: (I'm sure the answer is yes, but peace of mind would be nice)
If I guarantee that for any two BeachNodes A and B the signum (A.compareTo (B)) remains constant and A and B are in the beach tree, will the TreeMap function still work despite the changes underlying the comparison?
My second question:
How can I enforce such a contract?
Please note that in the luck algorithm we keep track of which positions of the sweep line two intersections meet, when the sweep line reaches one of these positions, one of the intersections is removed.
This means that the two intersections A and B in the shore tree never intersect positions, but during the CircleEvent A.compareTo (B) will return a 0-intervention in handling the CircleEvent. The contract will only be short lived, during the CircleEvent, which will remove one intersection.
This is my first question on StackOverflow, if it's poorly posed or incomplete please let me know and I'll do my best to fix it.
source to share
According to the TreeMap documentation, the tree will be sorted according to the method compareTo
, so any changes that are not reflected in the sign are a.compareTo(b)
allowed. However, you also need to implement a method equals
with the same semantics as compareTo
. It's very easy if you already have a method compareTo
:
public boolean equals(Object object) {
if (!(object instanceof BeachNode)) {
return false;
}
BeachNode other = (BeachNode) object;
return this.compareTo(other) == 0;
}
And, since you are overriding equals
, you must override hashCode
. It's also pretty easy since you only use a couple of 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
two intersections should remain different, won't they be equal? If I'm wrong, hopefully someone who understands the algorithm can help you with this.
source to share