You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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]publicclassUpdatableBinomialHeapPriorityQueueTests_AsMergeableAndUpdatableQueue:MergeablePriorityQueueTests<UpdatableBinomialHeapPriorityQueue<int>>{publicUpdatableBinomialHeapPriorityQueueTests_AsMergeableAndUpdatableQueue():base(()=>newUpdatableBinomialHeapPriorityQueue<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]publicvoid Merge_QueueUpdatesKeepWorkingOnSourceAfter(){varsource= IntBuilder();
source.Push(2,0);
source.Push(2,-5);
source.Push(3,-5);vartarget= 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.
The text was updated successfully, but these errors were encountered:
Both
UpdatableBinomialHeapPriorityQueue<T>
andUpdatableFibonacciHeapPriorityQueue<T>
have a bug on merging two heaps viaMergeFrom
.While both classes are supposed to be tested by
Tests
classes extendingMergeableAndUpdatablePriorityQueueTests
(as done forUpdatableBinaryHeapPriorityQueue
inUpdatableBinaryHeapPriorityQueueTests_AsMergeableAndUpdatableQueue
), they only extendMergeablePriorityQueueTests
.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
.The problem comes from the fact that
MergeFrom
is defined inIMergeablePriorityQueue<T, in TPQTarget>
and implemented by bothBinomialHeapPriorityQueue<T>
andFibonacciHeapPriorityQueue<T>
(non-updatable versions), but implementations are not overridden to take into account theDuplicatedItemsResolution
, necessary to have "updatable" variants work.Since
UpdatableBinomialHeapPriorityQueue<T>
andUpdatableFibonacciHeapPriorityQueue<T>
inherit from classes which support merge, by Liskov Principle they should support merge too.The text was updated successfully, but these errors were encountered: