SortedSet is not removing some element from it

Question

SortedSet not removing some elements

I am trying to implement the A* pathfinding algorithm, everything is good so far except one this, SortedSet not removing some element. It removes element, but some element is not removing and because of it the loop is going forever.

while (openNodes.Count > 0)
{
    currentPoint = openNodes.Min;
    currentPoint.SetIsSearched(true);
    openNodes.Remove(currentPoint);

    if (openNodes.Contains(currentPoint))
    {
        throw new Exception("MalFunctioning Detected...");
    }

    // Rest of the code 
}

My WayPoint class implemented IComparable interface

public int CompareTo(WayPoint other)
{
    // Index is the position in grid, grid contains the walkable and non walkable node, 
    // this class purpose is to hold data until shorted path found
    // If both points are at same location they are same

    if (other.Index.x == Index.x && other.Index.y == Index.y) return 0;
    else if (F < other.F || F == other.F && H < other.H) return -1;
    else return 1;
}

I'm sure nothing other than this is wrong with my code since, using List makes it run and finding path as expected. I'm so frustrated by this, it's appreciable if anyone can explain to me what and why this happening.

Answer 1

Well, comparison must be antisymmetric, i.e. if

A > B

then

B < A

for all A and B. You break this rule; if this and other are not equal (i.e. Index.x or/and Index.y are not equal)

...

else if (F < other.F || F == other.F && H < other.H) 
  return -1;
else
  return 1; // <- when this.F == other.F && this.H == other.H

in case this.F == other.F && H == other.H 1 is returned and we have this > other; if we swap this and other we expect -1 to be returned, but we sill get 1.

You, probably, want

public int CompareTo(WayPoint other) {
  // null is the smallest item 
  if (other is null)
    return 1;

  // Do you really want to compare y and y?
  if (other.Index.x == Index.x && other.Index.y == Index.y) 
    return 0;

  // Compare F's
  int compare = F.CompareTo(other.F);

  // If F's are not equal return the result
  if (compare != 0) 
    return compare;

  // Otherwise, compare H's
  return H.CompareTo(other.H);
}

Answer 2

The problem was that I was changing the value and not updating the set. Solution is simple just remove the item before changing values that are affecting the sorting and add the item again to list, that sort the list again.

Also changed the comparison function too (according to Dmitry Bychenko)

        if (other == null) return 1;

        if (other.Index.x == Index.x && other.Index.y == Index.y) return 0;

        if (F != other.F)
            return F.CompareTo(other.F);
        else if (H != other.H)
            return H.CompareTo(other.H);
        else if (G != other.G)
            return G.CompareTo(other.G);
        else
            return 0;

Answer 3

The best way to write a CompareTo function is to use the Waterfall pattern: each field is compared using CompareTo, if the result is not 0 then return it.

So x and y are compared separately, this way if either of them are different then you can have a guaranteed sort order.

You also have the comparison backwards: you need to compare this with other.

public int CompareTo(WayPoint? other)
{
    // Index is the position in grid, grid contains the walkable and non walkable node, 
    // this class purpose is to hold data until shorted path found
    // If both points are at same location they are same

    if (other == null)
        return 1;

    var cmp = Index.x.CompareTo(other.Index.x)
    if (cmp != 0)
        return cmp;

    cmp = Index.y.CompareTo(other.Index.y);
    if (cmp != 0)
        return cmp;

    cmp = F.CompareTo(other.F);
    if (cmp != 0)
        return cmp;

    cmp = G.CompareTo(other.G);
    if (cmp != 0)
        return cmp;

    cmp = H.CompareTo(other.H);
    return cmp;
}

You can refactor the Index comparison into its own CompareTo function as well.

---

If the Index by itself tells you that the values are equal, but does not sort them, then you can use this

public int CompareTo(WayPoint? other)
{
    // Index is the position in grid, grid contains the walkable and non walkable node, 
    // this class purpose is to hold data until shorted path found
    // If both points are at same location they are same

    if (other == null)
        return 1;

    if (Index.x == other.Index.x && Index.y == other.Index.y)
        return 0;

    cmp = F.CompareTo(other.F);
    if (cmp != 0)
        return cmp;

    cmp = G.CompareTo(other.G);
    if (cmp != 0)
        return cmp;

    cmp = H.CompareTo(other.H);
    return cmp;
}