6 Replies Latest reply: Nov 17, 2010 8:22 AM by 811100 RSS

    TreeSet Comparator problem

    811100
      I've been working on a pathfinding algorithm and have been using a TreeSet with a custom comparator, but seem to have run into a problem. I'm under the assumption that a set should only contain one of each item based on the comparator. For some reason, when I do certain test cases the TreeSet will contain duplicate values. I specify that the values are equal if x == x and y == y, but somehow multiple x,y pairs are contained in the set. I use TreeSet.conatins() to determine if I should put the item in the list, but for some reason even if they share the same x,y pair it puts the same item in the list. Also, on other test cases its having trouble putting the items in the correct order. A pair of coordinates with a higher F value is in the front of the list when it should be in the back. If anyone has some suggestions i would greatly appreciate it. This is my code for the comparator. Maybe I'm doing something wrong and fresh set of eyes could help. This is my first time working with them and I'm not sure if I've made a tiny mistake or not.

      This is the custom comparator class I've implemented
          private class AStarNodeComparator implements Comparator<AStarNode>{
      
              public int compare(AStarNode o1, AStarNode o2) {
                  return (o1.compareTo(o2));
              }
          }
      And this is the compareTo, equals and hashCode method I've used for my AStarNode
          @Override
          public boolean equals(Object o){
              return(o instanceof AStarNode && this.compareTo((AStarNode)o) == 0);
          }
      
          @Override
          public int hashCode() {
              int hash = 3;
              hash = 83 * hash + this.x;
              hash = 83 * hash + this.y;
              return hash;
          }
      
          public int compareTo(AStarNode t) {
              if(this.x == t.getX() && this.y == t.getY()){
                  return 0;
              }
              else if(this.f < t.getF()){
                  return -1;
              }
              else{
                  return 1;
              }
          }
      If anyone has an idea on why this isn't sorting corectly and why it has duplicate items I would appreciate it.
        • 1. Re: TreeSet Comparator problem
          EJP
          else if(this.f < t.getF()){
              return -1;
          }
          else if (this.f > t.getF()){
              return 1;
          else{
              return 0;
          }
          • 2. Re: TreeSet Comparator problem
            811100
            Would that exclude a value from the tree if the x and y didnt equal but the f values did? Say 1,3 = 110 and 1,2 = 110. Would it exclude one of the coordinates with that final return 0 at the end? I'm trying to keep duplicate x,y pairs out and sort them by f values at the same time.
            • 3. Re: TreeSet Comparator problem
              DrClap
              RKennedy9064 wrote:
              Would that exclude a value from the tree if the x and y didnt equal but the f values did? Say 1,3 = 110 and 1,2 = 110. Would it exclude one of the coordinates with that final return 0 at the end? I'm trying to keep duplicate x,y pairs out and sort them by f values at the same time.
              But you have two conflicting goals there. One is to sort the objects by f value, and the other is to say that two objects are equal if their x and y values are equal. The result is that objects which should sort far apart, because their f values are far apart, are suddenly declared equal because their x and y values are equal. In other words your logic is incoherent. You need to declare a total ordering on all possible objects, and that code fails to do that.
              • 4. Re: TreeSet Comparator problem
                811100
                Hmm would their be a different data structure I could use that would efficiently let me store them using the x,y coordinates as positions and then find the smallest one?
                • 5. Re: TreeSet Comparator problem
                  EJP
                  Would that exclude a value from the tree if the x and y didnt equal but the f values did? Say 1,3 = 110 and 1,2 = 110. Would it exclude one of the coordinates with that final return 0 at the end?
                  No. It's the most minor key. It sorts items with equal (x,y) pairs only.
                  I'm trying to keep duplicate x,y pairs out and sort them by f values at the same time.
                  That is a contradiction in terms. If they are out how can you sort them? You have a major conceptual confusion here.
                  Hmm would their be a different data structure I could use that would efficiently let me store them using the x,y coordinates as positions and then find the smallest one?
                  It's not a question of which data structure, it's a question of how you are defining your ordering.

                  I think your comparator should look like this:
                  // Major key is 'x'
                  if (this.x > that.x)
                    return 1;
                  if (this.x < that.x)
                    return -1;
                  // Sub-major key is 'y'
                  if (this.y > that.y)
                    return 1;
                  if (this.y < that.y)
                    return -1;
                  // minor key is 'f'
                  if (this.f > that.f)
                    return 1;
                  if (this.f < that.f)
                    return -1;
                  // Everything is equal
                  return 0;
                  As you are using a TreeSet you can throw away your hashCode() method. Otherwise it should take the 'f' value into account too.
                  • 6. Re: TreeSet Comparator problem
                    811100
                    I finally got it to work. I just decided to use the comparator to order them by x,y pairs and then I made my own method to find the lowest f value in the tree. I was using a 2-d array so each node only had one x,y pair and I was trying to use the x and y comparator just so I could make sure a coordinate didn't get added again. I thought that if I made it exclude the same x,y pair that it would make it keep the same pair out so it didn't have duplicates and it would have the lowest F value so i could use TreeSet.first() to find the node I needed to jump to quickly. I guess I was just trying to fit too much into the comparator.