SortedSet.Remove() doesn't remove element returned by SortedSet.Min

Question

I'm trying to implement a custom sorted Queue where items are sorted in this way:

• If both items have the same parent path, sort them in FIFO manner
• If items have different parent path, the item with bigger index should be dequeued first.

I've implemented it using the SortedSet. The problem is that while it generally works, in some cases, e.g. lots of adding and removing items at random, _mSortedSet.Remove(entry) returns false.

I've implemented it as such:

public class CustomSortingQueue<T> : IComparer<(T work, string fullPath, ulong index)>
    {
        private readonly SortedSet<(T work, string fullPath, ulong index)> _mSortedSet;
        private readonly Comparer<ulong> _mIndexComparer = Comparer<ulong>.Default;

        private ulong _mNextIndex = 0;

        public CustomSortingQueue() {
            _mSortedSet = new SortedSet<(T work, string fullPath, ulong index)>(this);
        }

        public int Compare((T work, string fullPath, ulong index) x, (T work, string fullPath, ulong index) y)
        {
            if (x.fullPath == y.fullPath)
            {
                // For same paths we want to do normal counting - e.g. bigger index means should be done later
                return _mIndexComparer.Compare(x.index, y.index);
            }

            // For different paths, we want the new one to be done as fast as possible -> bigger index should be done faster
            return _mIndexComparer.Compare(y.index, x.index);
        }

        public void Enqueue(T work, string fullPath)
        {
            _mSortedSet.Add((work, fullPath, _mNextIndex++));
        }

        public (T work, string fullPath) Dequeue()
        {
            var entry = _mSortedSet.Min;
            _mSortedSet.Remove(entry);
            return (entry.work, entry.fullPath);
        }
    }

In the cases it fails I found that Remove returns false from sortedset.cs by failing if (Is2Node(current)).

Looking in the debugger at my _mSortedSet I can see that it has items like this (I'll be skipping the exact values of the T parameter for brevity, as it's unused in comparison):

(T, "Y:\\", 538),
(T, "Y:\\", 566),
(T, "Y:\\", 570),
...
(T, "X:\\", 537),
(T, "X:\\", 546),
(T, "X:\\", 595),
...
(T, null, 531),
(T, null, 532),
...
(T, null, 740),
(T, "Y:\\", 530),
(T, "Z:\\", 529)

The _mSortedSet.Min is (T, "Y:\\", 538). I see that the most probable culprit is the second to last item, which has a curious place in the output. My best guess is that something inside the sorted set breaks when recomputing the weighted tree.

I suspect this might be a problem in my Compare function (as is the case with most Remove problems) but I cannot pinpoint exactly why. Any help with understanding why the Remove fails even though Min is found would be greatly appreciated. Am I using the SortedSet for a wrong use-case?

Answer 1

The problem is that your comparer is not transitive, and comparers need to be transitive when sorting items.

The sorted collections all rely on there being a single valid ordering of items, and do not support collections with numerous valid orderings, which is the case given your requirements.

Answer 2

Thanks for all the help with the transitive property! For posterity - I've found that using the SortedSet wasn't giving much performance improvements in my use-case so I just went with a normal List<(string, Queue<T>)> _mBuckets instead.

where

private List<(string, Queue<T>)> _mBuckets = new List<string, Queue<T>)>();
public void Enqueue(T work, string fullPath)
{
    var foundItem = _mBuckets.FirstOrDefault(o => o.Item1 == fullPath);
    if (foundItem.Equals(default))
    {
      // New paths are always pushed first
      _mBuckets.Insert(0, (fullPath, new Queue<T>(new T[] { work })));
    }
    else
    {
       foundItem.Item2.Enqueue(work);
    }
}