Swapping keys in TreeSet?

Question

Suppose I have this class:

public class Node implements Comparable<Node>{
  public float key;
  public TreeSet<Node> neighbors;

  public Node{
    //fill neighbors somehow
  }

  @Override
  public int compareTo(Node n) {
    if(this.key == n.key)
        return 0;
    else if(this.key > n.key)
        return 1;
    else
        return -1;
  }

}

So this is a classic node of a graph, where each node is connected to a set of nodes (i.e. its neighbors). I'm using TreeSet because I often (very often) to know all the neighbors with their key bigger (smaller) than a certain value. Now, let's suppose I have this method:

//swap nodes keys
void swapKeys(Node a, Node b){
  float ak = a.key;
  a.key = b.key;
  b.key = ak; 
}

Notice that this method changes only the two nodes keys, nothing more.

Do this "break" the structure, or everything will continue to work fine?

If this breaks the structure, what about this simple solution:

//swap nodes keys
void swapKeys(Node a, Node b){
  a.remove(b);
  b.remove(a);
  float ak = a.key;
  a.key = b.key;
  b.key = ak; 
  a.add(b);
  b.add(a);
}

This will break the structure. Keys should be immutable. Hashcode cannot change once added as a key. — Piotr Gwiazda, Jun 14 '17 at 17:25
@PiotrGwiazda Thanks for your answer. What about my solution that I just posted? — justHelloWorld, Jun 14 '17 at 17:29
Why swap the nodes' keys and alter the structure when you could simply swap their values and not alter the structure? — Jonny Henly, Jun 14 '17 at 17:31
How many neighbors will a node have? Maybe you can get away with just using a list rather than a set. — arshajii, Jun 14 '17 at 17:31
@JonnyHenly I'm afraid I don't understand your comment, what do you mean? — justHelloWorld, Jun 14 '17 at 17:34
@arshajii for hubs (nodes at the center of a network with high degree) potentially thousands. — justHelloWorld, Jun 14 '17 at 17:34

bowmore · Answer 1 · 2017-06-14T18:14:12.037

From the TreeSet documentation :

Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface.

Your Node class' Comparable implementation is not consistent with equals. (compareTo can return 0 for two Node instances wich are not equal).

This in itself makes your Node class unfit to be elements of a TreeSet.

Even the proposed workaround is not sufficient.

You may be tempted to fix this by implementing equals() (and hashCode()) to be based upon the value contained in the node. But to no avail, as this would go against a warning on the documention of the general Set interface :

Note: Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set. A special case of this prohibition is that it is not permissible for a set to contain itself as an element.

So adding equals and hashCode is still not sufficient : your instances must also be immutable.

However the simplest solution, seems to be to forego the Comparable interface altogether, to not implement equals and hashCode, and to simply use a HashSet instead of a TreeSet. In that case you can change the contents of your nodes without consequences to the proper functioning of the set of neighbours.

thanks for your comment. Are you telling me that I have to implement `equals` too? — justHelloWorld, Jun 14 '17 at 18:07
`HashSet` unfortunately is not an option since I frequently use `tailSet` and `headSet` to compute topK as explained [here](https://stackoverflow.com/questions/44525091/how-to-get-the-top-k-closest-elements-in-a-java-treeset) — justHelloWorld, Jun 14 '17 at 18:39
You'll have to go with immutable Nodes then. This will entail replacing them in your graph, instead of changing their contents. Or use `HashSet` regardless, and create a `TreeSet` with a `Comparator`, locally in the algorithm to find the k nearest nodes. — bowmore, Jun 14 '17 at 18:53

Swapping keys in TreeSet?

1 Answers1