We help IT Professionals succeed at work.

We've partnered with Certified Experts, Carl Webster and Richard Faulkner, to bring you two Citrix podcasts. Learn about 2020 trends and get answers to your biggest Citrix questions!Listen Now

x

How can TreeSet.first() return something that I can't remove(), isn't in contains()?

kisrael
kisrael asked
on
Medium Priority
423 Views
Last Modified: 2012-08-14
I have a TreeSet cheapestDestination that stores Integers,
with a custom comparator that looks up the cost for that Integer ID in a map

Sometimes when I call
    Object cheapestDestination = cheapestDestinationSet.first();
    println(cheapestDestinationSet.contains(cheapestDestination));
    if(!cheapestDestinationSet.remove(cheapestDestination)){
println("FAIL");
}
false and FAIL are printed. How can this be???? could my comparator be breaking it? the code for it is below

class connectionCostsComparator implements Comparator {
  Map destinationNodeIdToConnection;
  connectionCostsComparator(Map map){
    destinationNodeIdToConnection = map;
  }
 
  public int compare(Object o1, Object o2){
    Object value1 = destinationNodeIdToConnection.get(o1);
    Object value2 = destinationNodeIdToConnection.get(o2);
 
    connection conn1 = (connection)value1;
    connection conn2 = (connection)value2;
    return conn1.cost - conn2.cost;
 
  } 
}

Open in new window

Comment
Watch Question

CERTIFIED EXPERT
Top Expert 2016

Commented:
Make sure your contained object implements equals correctly
CERTIFIED EXPERT
Top Expert 2016

Commented:
That would be something like the following. If you don't want it implementing equals in this way, consider using a wrapper object for the real class that does
public boolean equals(Object other) {
	return cost == ((YourObject)other).cost;
}

Open in new window

Author

Commented:
The objects in the TreeSet are class java.lang.Integer ! How can that be wrong??
CERTIFIED EXPERT
Top Expert 2016

Commented:
Oh, so 'cheapestDestinationSet' contains *only* Integer?

Author

Commented:
Yeah, I just did a getClass() on everything an iterator over it contains... it's all Integer!

SO DAMN WEIRD
CERTIFIED EXPERT
Top Expert 2016

Commented:
>> ...the cost for that Integer ID in a map


So the Integer instances are IDs. That TreeSet would be ordered by id, not cost, so first() would return the lowest id only

Author

Commented:
A. Even if I was getting "wrong" thing back from first();, an immediate call to "remove()" on what first() returned  shouldn't fail

B. I made a new Comparator, posted above... it gets passed in a reference to a map (destinationNodeIdToConnection ) that contains a "connection" object that has a cost, and then I do subtraction
Mick BarryJava Developer
CERTIFIED EXPERT
Top Expert 2010
Commented:
>  could my comparator be breaking it?

yes that would be casued by the comparator
as a test try without it and you shouldn't see the problem


Not the solution you were looking for? Getting a personalized solution is easy.

Ask the Experts
Mick BarryJava Developer
CERTIFIED EXPERT
Top Expert 2010

Commented:
add an equals() method to your Comparator

CERTIFIED EXPERT
Top Expert 2016

Commented:
If it only contains IDs, then the Comparator is incorrect. You don't need Comparator - Integer is already Comparable
CERTIFIED EXPERT
Top Expert 2016

Commented:
>>
B. I made a new Comparator, posted above... it gets passed in a reference to a map (destinationNodeIdToConnection ) that contains a "connection" object that has a cost, and then I do subtraction
>>

Your problem is that you're confusing the Set with the Map. The former only contains IDs. The latter connects those IDs with the actual cost.
It actually wouldn't work if the Set were the cost as you couldn't have two identical costs
Mick BarryJava Developer
CERTIFIED EXPERT
Top Expert 2010

Commented:
sorry meant equals() on your key
so in your case you need to be storing connection instances in your Set, and by the looks it will no longer be a set

CERTIFIED EXPERT
Top Expert 2016

Commented:
>>A. Even if I was getting "wrong" thing back from first();, an immediate call to "remove()" on what first() returned  shouldn't fail

It fails because you've broken Comparable by using the incorrect Comparator
Mick BarryJava Developer
CERTIFIED EXPERT
Top Expert 2010
Commented:
you currently can have two elements that accoring to the Comparator are equal, but the two objects are not equal according to equals().
That breaks the contract required by a Set, thus what you are doing will not work.

Author

Commented:
Wait, so if two objects are
==
so to speak, in terms of the comparator returning 0 , they also need to be
equals() ?
Mick BarryJava Developer
CERTIFIED EXPERT
Top Expert 2010

Commented:
try something like this:

class connectionCostsComparator implements Comparator {
  Map destinationNodeIdToConnection;
  connectionCostsComparator(Map map){
    destinationNodeIdToConnection = map;
  }
 
  public int compare(Object o1, Object o2){
    Object value1 = destinationNodeIdToConnection.get(o1);
    Object value2 = destinationNodeIdToConnection.get(o2);
 
    connection conn1 = (connection)value1;
    connection conn2 = (connection)value2;
    int diff = conn1.cost - conn2.cost;
    return diff==0 ? o1.compareTo(o2) : diff;
 
  }
}
Mick BarryJava Developer
CERTIFIED EXPERT
Top Expert 2010

Commented:
> so to speak, in terms of the comparator returning 0 , they also need to be
equals() ?

correct

CERTIFIED EXPERT
Top Expert 2016

Commented:
Actually a TreeSet doesn't bother about equals
CERTIFIED EXPERT
Top Expert 2016

Commented:
If you use the correct Comparator, which of course is redundant, you'll see your code works as expected:
  public int compare(Object o1, Object o2){
    return ((Integer)o1).compareTo(o2); 
  } 

Open in new window

Author

Commented:
objects: I think I'm getting there.... generic objects don't have a .compareTo on my system, but I'll actually start comparing the components of connection (startnode, endnode)... not sure what to do if all those are equal... it should be pretty damn equal at that point !

Author

Commented:
Ugh, this is the comparator I tried, but remove() is still failing...

is there something else I should be using?
I need some kind of Sorted Collection of Integer IDs, where I can pop one off the top of the stack reliably, and it sorts on these values w/ some kind of look up off the ID...
class connectionCostsComparator implements Comparator {
  Map destinationNodeIdToConnection;
  connectionCostsComparator(Map map){
    destinationNodeIdToConnection = map;
  }
 
  public int compare(Object o1, Object o2){
    Object value1 = destinationNodeIdToConnection.get(o1);
    Object value2 = destinationNodeIdToConnection.get(o2);
    connection conn1 = (connection)value1;
    connection conn2 = (connection)value2;
    int diff = conn1.cost - conn2.cost;
    if(diff != 0) {return diff;}
    diff = conn1.startNode - conn2.startNode;
    if(diff != 0) {return diff;}
    diff = conn1.endNode - conn2.endNode;
    if(diff != 0) {return diff;}
    return 0;    
  } 
}

Open in new window

Mick BarryJava Developer
CERTIFIED EXPERT
Top Expert 2010

Commented:
what are startNode and endNode?

CERTIFIED EXPERT
Top Expert 2016

Commented:
If your intention is just to maintain an index by cost, then just use the cost of the trip in the Comparator
Mick BarryJava Developer
CERTIFIED EXPERT
Top Expert 2010

Commented:
you may need to use a list of connection's, and use a binary search to determine where to insert each new connection (to maintain correct order)

Author

Commented:
int

it's a network-type graph, and a node has an startNode, endNode and a cost...

hmm, I did give them specific numeric ids, on a whim, didn' think i'd need them but i'll try putting it into the compariosn
CERTIFIED EXPERT
Top Expert 2016
Commented:
This is all you need: fill the Set with 'Trip' references (you probably need to cast to int if cost is floating point)
  public int compare(Object o1, Object o2){
    return ((Trip)o1).getCost() - ((Trip)o2).getCost();
  } 

Open in new window

CERTIFIED EXPERT
Top Expert 2016

Commented:
Then

Object cheapestDestination = cheapestDestinationSet.first();

will work fine
CERTIFIED EXPERT
Top Expert 2016

Commented:
You can expand that with startNode and endNode as necessary, but the Map is redundant in the index
Commented:
OK, I changed gears, made the sorted bunch of IDs a normal Array list that I will sort on after insert.

objects, you seemed to have a pretty decent understanding of what I was getting at, though I'm still not sure how to not break that Set contrac.

CEHJ, at first it felt like you weren't hearing what i was tyring to do w/ the ID lookup, and now I'm not sure about the "Trip" ... is it like a one way connection?
Mick BarryJava Developer
CERTIFIED EXPERT
Top Expert 2010

Commented:
> OK, I changed gears, made the sorted bunch of IDs a normal Array list that I will sort on after insert.

I suggested that earlier :)
"you may need to use a list of connection's, and use a binary search to determine where to insert each new connection (to maintain correct order)"

CERTIFIED EXPERT
Top Expert 2016

Commented:
>>CEHJ, at first it felt like you weren't hearing what i was tyring to do w/ the ID lookup, and now I'm not sure about the "Trip" ... is it like a one way connection?

I do know what you're trying to do. In fact, i'm generally *only* interested in the goal, not in the intricacies of how it's *currently* being approached. 'Trip' is the thing i'm guessing you want to get the lowest cost of, although it doesn't matter what it's called. I've just told you how to do that. Using a Map is redundant and has led to your problem in the first place

Author

Commented:
Welllll... pretty much
to my tired brain, "use a binary search to determine where to insert" seemed weirder and tougher than "sort after each insert" :-)

the search might be more effecient though
Mick BarryJava Developer
CERTIFIED EXPERT
Top Expert 2010

Commented:
yeah, it depends on how often stuff gets added and if needs resorting is required.
Don't know enough about whats required so you can decide which works best for you.

let me know if you need any further help :)

Mick BarryJava Developer
CERTIFIED EXPERT
Top Expert 2010

Commented:
>  "sort after each insert"

that will be slower. if its already sorted then its faster to use a binary search to determine where the next element should go.
Have a look at Collections.binarySearch()

CERTIFIED EXPERT
Top Expert 2016

Commented:
"use a binary search to determine where to insert"

You don't need to know where to insert - if you're using a TreeSet, it's automatically sorted on any new insert - that's the whole point of it
Access more of Experts Exchange with a free account
Thanks for using Experts Exchange.

Create a free account to continue.

Limited access with a free account allows you to:

  • View three pieces of content (articles, solutions, posts, and videos)
  • Ask the experts questions (counted toward content limit)
  • Customize your dashboard and profile

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.