i am using a TreeSet in my java program and i have to remove its first element at each step..?

Question

I am using the following code:
Treeset pq=new TreeSet();
node n=new node(0,0);
pq.add(n);

boolean p=pq.remove(pq.first());

but the above line is not removing the first element..
can anybody help me to find the flaw ????

Answer 1

Most often when this fails it is because you have broken the contract with TreeSet (or with SortedSet in general).

That contract is as follows:
-- If you create a TreeSet (SortedSet) without specifying a Comparator to govern the sorting, then all the elements you add must implement the Comparable interface and must be mutually comparable (this is called "natural ordering").

My guess is that your "node" class does not implement Comparable. This breaks the contract. It is a coding error.

This error does not breaking the "pq.add(n)" operation, since adding the first element does not require any comparisons. It does not break the subsequent "pq.first()" operation either, since no comparisons are needed in a sorted tree to find the first element (just keep moving to the left until you run out of elements). However, the "pq.remove()" operation *DOES* require a comparison. This is the first TreeSet operation you have done that requires a comparison, so it is here that TreeSet discovers that you have violated the contract. So it is here that the TreeSet class throws an exception.

I am guessing that the exception stack trace looks something like this:
java.lang.ClassCastException: node
at java.util.TreeMap.compare( TreeMap.java: 1093 )
at java.util.TreeMap.getEntry( TreeMap.java: 347 )
at java.util.TreeMap.remove( TreeMap.java: 506 )
at java.util.TreeSet.remove( TreeSet.java: 223 )
....

The most direct solution to your problem is to have the node class implement java.util.Comparable and then write a "compareTo()" method that satisfies the contract for Comparable. You should also probably write an "equals()" method and a "hashCode()" method to keep comparison consistency.

Also note that sorted sets can be very tricky to use (well, I guess I don't need to tell YOU that). When you place an properly comaparable object in a sorted set you should **NEVER** change any of the properties of that object that could change the object's sort order. That can really mess up the search features of the sorted set itself and any other features (like "remove()") that use the search features.

Answer 2

Treemap Remove

Answer 3

I tried the following code:

TreeSet pq=new TreeSet();
Integer n=new Integer(0);
pq.add(n);

boolean p=pq.remove(pq.first());

System.out.println(p);
System.out.println(pq.size());

And got:

true
0

as output, which says the code works fine.
Perhaps the creation of the node fails and throws an exception which for some reason you don't see (or maybe you catch it and don't print it?). Otherwise there is no reason why this code should not work

Answer 4

E-mail Bill Gates---or Ozzie---