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?
IComparer
. Ignoring the first parameter,(x, 1) < (x, 3)
,(y, 2) < (x, 1)
,(x, 3) < (y, 2)
.