• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 388
  • Last Modified:

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

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

0
kisrael
Asked:
kisrael
  • 15
  • 11
  • 9
4 Solutions
 
CEHJCommented:
Make sure your contained object implements equals correctly
0
 
CEHJCommented:
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

0
 
kisraelAuthor Commented:
The objects in the TreeSet are class java.lang.Integer ! How can that be wrong??
0
Cloud Class® Course: Microsoft Azure 2017

Azure has a changed a lot since it was originally introduce by adding new services and features. Do you know everything you need to about Azure? This course will teach you about the Azure App Service, monitoring and application insights, DevOps, and Team Services.

 
CEHJCommented:
Oh, so 'cheapestDestinationSet' contains *only* Integer?
0
 
kisraelAuthor Commented:
Yeah, I just did a getClass() on everything an iterator over it contains... it's all Integer!

SO DAMN WEIRD
0
 
CEHJCommented:
>> ...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
0
 
kisraelAuthor 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
0
 
objectsCommented:
>  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


0
 
objectsCommented:
add an equals() method to your Comparator

0
 
CEHJCommented:
If it only contains IDs, then the Comparator is incorrect. You don't need Comparator - Integer is already Comparable
0
 
CEHJCommented:
>>
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
0
 
objectsCommented:
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

0
 
CEHJCommented:
>>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
0
 
objectsCommented:
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.

0
 
kisraelAuthor Commented:
Wait, so if two objects are
==
so to speak, in terms of the comparator returning 0 , they also need to be
equals() ?
0
 
objectsCommented:
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;
 
  }
}
0
 
objectsCommented:
> so to speak, in terms of the comparator returning 0 , they also need to be
equals() ?

correct

0
 
CEHJCommented:
Actually a TreeSet doesn't bother about equals
0
 
CEHJCommented:
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

0
 
kisraelAuthor 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 !
0
 
kisraelAuthor 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

0
 
objectsCommented:
what are startNode and endNode?

0
 
CEHJCommented:
If your intention is just to maintain an index by cost, then just use the cost of the trip in the Comparator
0
 
objectsCommented:
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)

0
 
kisraelAuthor 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
0
 
CEHJCommented:
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

0
 
CEHJCommented:
Then

Object cheapestDestination = cheapestDestinationSet.first();

will work fine
0
 
CEHJCommented:
You can expand that with startNode and endNode as necessary, but the Map is redundant in the index
0
 
kisraelAuthor 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?
0
 
objectsCommented:
> 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)"

0
 
CEHJCommented:
>>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
0
 
kisraelAuthor 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
0
 
objectsCommented:
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 :)

0
 
objectsCommented:
>  "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()

0
 
CEHJCommented:
"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
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

  • 15
  • 11
  • 9
Tackle projects and never again get stuck behind a technical roadblock.
Join Now