.Remove() removes wrong instance if priorities are identical

[ghost]

Removing an instance may fail if there are other instances with the same priority. Code sample:

	class Person
	{
		public string Name { get; set; }
		public int Priority { get; set; }
	}

	class PersonComparer : IComparer<Person>
	{
		public int Compare(Person x, Person y)
		{
			return x.Priority.CompareTo(y.Priority);
		}
	}

	public static void Main(string[] args)
	{
		PriorityQueue<Person> queue = new PriorityQueue<Person>(new PersonComparer());
		Person sam = new Person() { Name = "Sam", Priority = 1 };
		Person max = new Person() { Name = "Max", Priority = 1 };
		queue.Enqueue(sam);
		queue.Enqueue(max);
		queue.Remove(max);
		Console.WriteLine(queue.Dequeue().Name); // returns "Max" instead "Sam"
	}

[madelson]

Hi @KaaCee thanks for raising this issue!

Believe it or not, this behavior was by design. I'm still not sure it was the right design (obviously there is at least one thing wrong with it since it wasn't what you expected), but here's how I got there:

• Existing .NET classes based on comparers (e. g. SortedSet<T>, SortedDictionary<K, V>) use "compares as equal" to indicate equality rather than EqualityComparer<T>.Default. As another comparer-based collection, it seems reasonable that PQ should be consistent with those.
• It seems that Contains() and Remove() should be consistent with each other (they are currently)
• The behavior seems pretty reasonable in the case of something like a case-insensitive comparer (a PriorityQueue<string> initialized with StringComparer.OrdinalIgnoreCase). In a case-insensitive comparer if I've enqueued "A" and later I remove "a" it makes sense that "A" would get removed (I think).
• Using the comparer allows us to take advantage of the PQ's internal structure which can sometimes make Remove/Contains faster (it's still O(N)).

That said, I can certainly see counter-arguments to this:

• Unlike SortedSet and SortedDictionary, PQ doesn't imply equality, just ordering. Specifically, a PQ allows for multiple items with equal priority
• With this behavior, there's no way to remove a specific item from the collection (so long as items can compare equal). That said, you can work around this restriction by having your custom comparer guarantee that two non-equal objects never compare as equal (e. g. in your example break ties by name). Another workaround is to dequeue items until you find the item you want to remove, then put the rest back.

I'd be curious to hear the use-case in which you came across this, as well as any other thoughts you have on the matter. For example, do you know of other .NET classes which set a precedent for treating sorting and equality separately.

[ghost]

Hi @madelson

I can see your arguments. However, this seems to be an unfortunate case of interface naming: If i do a pq.Remove(item), I would assume this exact item is removed from the queue. I wouldn't assume any other item could be removed by this method.

My use case is keeping track of blocks in a blockchain. In case you're not aware of the tech behind it, i'll try a summary: Each block is linked to exactly one parent. The only exception is the root block. There might be several different branches in all these linked blocks, so these essentially form a tree. From time to time a new block is added to the tree, but I cannot know where it is added in advance (although it's most likely added to the longest chain from root to leafs). --> I need to keep track of all these blocks, especially I need to find the last (leaf) block of the longest chain. I.e.: I want to add blocks to the PQ, the "priority" is the height of the block (the number of links up to the root block).

I was trying different PQ implementations, this is why I stumbled over the "strange" behaviour (from my personal perspective) of your implementation.

Best regards Kc