SortedSet with element duplication - can't remove element

Question

I'm working on an implementation of the A-star algorithm in C# in Unity.

I need to evaluate a collection of Node :

class Node
    {
        public Cell cell;
        public Node previous;
        public int f;
        public int h;

        public Node(Cell cell, Node previous = null, int f = 0, int h = 0)
        {
            this.cell = cell;
            this.previous = previous;
            this.f = f;
            this.h = h;
        }
    }

I have a SortedSet which allows me to store several Node, sorted by h property. Though, I need to be able to store two nodes with the same h property. So I've implemented a specific IComparer, in a way that allow me sorting by h property, and triggerring equality only when two nodes are representing the exact same cell.

class ByHCost : IComparer<Node>
    {
        public int Compare(Node n1, Node n2)
        {
            int result = n1.h.CompareTo(n2.h);
            result = (result == 0) ? 1 : result;
            result = (n1.cell == n2.cell) ? 0 : result;
            return result;
        }
    }

My problem : I have a hard time to remove things from my SortedSet (I named it openSet).Here is an example:

At some point in the algorithm, I need to remove a node from the list based on some criteria (NB: I use isCell127 variable to focus my debug on an unique cell)

int removedNodesNb = openSet.RemoveWhere((Node n) => {
    bool isSame = n.cell == candidateNode.cell;
    bool hasWorseCost = n.f > candidateNode.f;

    if(isCell127)
    {
       Debug.Log(isSame && hasWorseCost); // the predicate match exactly one time and debug.log return true
    }

    return isSame && hasWorseCost;
});

if(isCell127)
{
   Debug.Log($"removed {removedNodesNb}"); // 0 nodes where removed
}

Here, the removeWhere method seems to find a match, but doesn't remove the node. I tried another way :

 Node worseNode = openSet.SingleOrDefault(n => {
      bool isSame = n.cell == candidateNode.cell;
      bool hasWorseCost = n.f > candidateNode.f;
      return isSame && hasWorseCost;
 });

 if(isCell127)
 {
      Debug.Log($"does worseNode exists ? {worseNode != null}"); // Debug returns true, it does exist.
 }

 if(worseNode != null)
 {
      if(isCell127)
      {
          Debug.Log($"openSet length {openSet.Count}"); // 10
      }
      openSet.Remove(worseNode);
      if(isCell127)
      {
          Debug.Log($"openSet length {openSet.Count}"); // 10 - It should have been 9.
      }
 }

I think the problem is related to my pretty unusual IComparer, but I can't figure whats exatcly the problem.

Also, I would like to know if there is a significative performance improvment about using an auto SortedSet instead of a manually sorted List, especially in the A-star algorithm use case.

Answer 1

I'll answer my own topic because I've a pretty complete one.

Comparison

The comparison of the IComparer interface needs to follow some rules. Like @frenchy said, my own comparison was broken. Here are math fundamentals of a comparison I totally forgot (I found them here):

1) A.CompareTo(A) must return zero.

2) If A.CompareTo(B) returns zero, then B.CompareTo(A) must return zero.

3) If A.CompareTo(B) returns zero and B.CompareTo(C) returns zero, then A.CompareTo(C) must return zero.

4) If A.CompareTo(B) returns a value other than zero, then B.CompareTo(A) must return a value of the opposite sign.

5) If A.CompareTo(B) returns a value x not equal to zero, and B.CompareTo(C) returns a value y of the same sign as x, then A.CompareTo(C) must return a value of the same sign as x and y.

6) By definition, any object compares greater than (or follows) null, and two null references compare equal to each other.

In my case, rule 4) - symetry - was broken.

I needed to store multiple node with the same h property, but also to sort by that h property. So, I needed to avoid equality when h property are the same.

What I decided to do, instead of a default value when h comparison lead to 0 (which broke 4th rule), is refine the comparison in a way that never lead to 0 with a unique value foreach node instance. Well, this implementation is probably not the best, maybe there is something better to do for a unique value, but here is what I did.

private class Node
{
   private static int globalIncrement = 0;

   public Cell cell;
   public Node previous;
   public int f;
   public int h;
   public int uid;

   public Node(Cell cell, Node previous = null, int f = 0, int h = 0)
   {
       Node.globalIncrement++;

       this.cell = cell;
       this.previous = previous;
       this.f = f;
       this.h = h;
       this.uid = Node.globalIncrement;
   }
}

private class ByHCost : IComparer<Node>
{
   public int Compare(Node n1, Node n2)
   {
       if(n1.cell == n2.cell)
       {
           return 0;
       }

       int result = n1.h.CompareTo(n2.h);
       result = (result == 0) ? n1.uid.CompareTo(n2.uid) : result; // Here is the additional comparison which never lead to 0. Depending on use case and number of object, it would be better to use another system of unique values.
       return result;
   }
}

RemoveWhere method

RemoveWhere use a predicate to look into the collection so I didn't think it cares about comparison. But RemoveWhere use internally Remove method, which do care about the comparison. So, even if the RemoveWhere have found one element, if your comparison is inconstent, it will silently pass its way. That's a pretty weird implementation, no ?

Answer 2

If i write your test you do:

          n1.h < n2.h
          n1.cell = n2.cell -> final result = 0

          n1.h > n2.h
          n1.cell = n2.cell -> final result = 0 

          n1.h = n2.h
          n1.cell != n2.cell -> final result = 1      

          n1.h < n2.h
          n1.cell != n2.cell -> final result = -1  

          n1.h > n2.h
          n1.cell != n2.cell -> final result = 1 

when you have equality on h value (test number 3) you choose to have always the same result -> 1. so its no good you have to have another test on cell to clarify the position bacause there is a confusion with other test which gives the same result (test number 5)

So i could test with sample, but i am pretty sure you break the Sort.

So if you clarify the test, i suggest you to use Linq with a list...its best performance.