1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
using System;
using System.Collections.Generic;
using System.Linq;
using Xunit;
namespace PriorityQueue.Tests
{
using Node = Node<int>;
using Queue = PriorityQueue<Node<int>, int>;
public class CreatePriorityQueue
{
[Theory]
[InlineData(false, new int[] { 3, 14, 7, 9, 99, 2, 46 }, 4, 99)]
[InlineData(true, new int[] { 3, 14, 7, 9, 99, 2, 46 }, 5, 2)]
public void Insert_WhenArray_ShouldPQ(bool isMin, int[] input, int expectedId, int expectedkey)
{
// Arrange
int id = 0;
Queue priorityQueue = new Queue(input.Length, isMin);
Node expected = new Node(expectedId, expectedkey);
// Act
foreach (var key in input)
priorityQueue.Insert(new Node(id++, key));
// Assert
Assert.Equal(expected, priorityQueue.Peek());
}
[Theory]
[InlineData(false, new int[] { 3, 14, 7, 9, 99, 2, 46 })]
[InlineData(true, new int[] { 3, 14, 7, 9, 99, 2, 46 })]
public void Extract_WhenPG_ShouldReturnLargest(bool isMin, int[] input)
{
// Arrange
int id = 0;
Node curr, next;
List<Node> actual = new List<Node>();
Queue queue = new Queue(input.Length, isMin);
Func<Node, Node, bool> compare = (first, second) =>
first.CompareTo(second) * (isMin ? -1 : 1) >= 0;
// Act
foreach (var key in input)
queue.Insert(new Node(id++, key));
// Assert
while (!queue.IsEmpty())
Assert.True(compare(
curr = queue.Extract(),
next = queue.Peek()
));
}
[Theory]
[InlineData(false, 4, 99)]
[InlineData(true, 5, 2)]
public void ChangeKey_GivenPQ_ShouldReorderPQ(bool isMin, int expectedId, int expectedkey)
{
// Arrange
int id = 0;
int[] array = new int[] { 3, 14, 7, 9, 99, 2, 46 };
List<Node> actual = new List<Node>();
Queue priorityQueue = new Queue(array.Length, isMin);
foreach (var key in array)
priorityQueue.Insert(new Node(id++, key));
// Act
// Assert
Node prev = priorityQueue.Extract();
while (!priorityQueue.IsEmpty())
actual.Add(priorityQueue.Extract());
foreach (Node node in actual)
Assert.True(prev.Key > (prev = node).Key);
}
}
}
|
