Updatable binomial and fibonacci heaps break after MergeFrom

[antonioaversa]

Both UpdatableBinomialHeapPriorityQueue<T> and UpdatableFibonacciHeapPriorityQueue<T> have a bug on merging two heaps via MergeFrom.

While both classes are supposed to be tested by Tests classes extending MergeableAndUpdatablePriorityQueueTests (as done for UpdatableBinaryHeapPriorityQueue in UpdatableBinaryHeapPriorityQueueTests_AsMergeableAndUpdatableQueue), they only extend MergeablePriorityQueueTests.

[TestClass]
public class UpdatableBinomialHeapPriorityQueueTests_AsMergeableAndUpdatableQueue 
    : MergeablePriorityQueueTests<UpdatableBinomialHeapPriorityQueue<int>>
{
    public UpdatableBinomialHeapPriorityQueueTests_AsMergeableAndUpdatableQueue() : base(
        () => new UpdatableBinomialHeapPriorityQueue<int>())
    {
    }
}

// Same for UpdatableFibonacciHeapPriorityQueueTests_AsMergeableAndUpdatableQueue 

Notice that the name of the test classes seems to suggest otherwise (as it includes "AndUpdatable" in the name).

Making the two test classes inherit from MergeableAndUpdatablePriorityQueueTests reveals the problem, as the following test fails: MergeableAndUpdatablePriorityQueueTests<TPriorityQueue>.Merge_QueueUpdatesKeepWorkingOnSourceAfter.

[TestMethod]
    public void Merge_QueueUpdatesKeepWorkingOnSourceAfter()
    {
        var source = IntBuilder();
        source.Push(2, 0);
        source.Push(2, -5);
        source.Push(3, -5);

        var target = IntBuilder();
        target.Push(1, 2);
        target.Push(2, -4);

        source.MergeFrom(target);

        Assert.AreEqual(1, source.GetPrioritiesOf(1).Count()); // <- test fails here
        ...

The problem comes from the fact that MergeFrom is defined in IMergeablePriorityQueue<T, in TPQTarget> and implemented by both BinomialHeapPriorityQueue<T> and FibonacciHeapPriorityQueue<T> (non-updatable versions), but implementations are not overridden to take into account the DuplicatedItemsResolution, necessary to have "updatable" variants work.

Since UpdatableBinomialHeapPriorityQueue<T> and UpdatableFibonacciHeapPriorityQueue<T> inherit from classes which support merge, by Liskov Principle they should support merge too.