Add PriorityQueue type

Added a new generic utility type, PriorityQueue, that represents a
thread-safe collection of objects that can be retrieved by the order of
their priority at enqueue. The underlying representation is based on a
hash-table, mapping items to their priority, and a binary search tree
containing the items sorted by priority. This results in the following
time complexity profile:
 * Enqueue, Dequeue ≈ O(log n)
 * Peek, Contains ≈ O(1)

Also added a specialized PunisherQueue, based on PriorityQueue, which
behaves like the standard Queue<T> of the .NET framework, with the
following main differences:
 * Thread-safe: can be simultaneously used by several threads.
 * Re-queue: Adding the same object (i.e. an object already present in
 the queue) many times will not create multiple entries in the queue for
 that object. Instead, at each call to Enqueue(), the object is moved
 from its current position to the back of the queue (i.e. "punished").

Change-Id: I3e53db1d64190f0470edf645f20312a0e8976ba4
Reviewed-by: Joerg Bornemann <joerg.bornemann@qt.io>

8 files changed, 602 insertions, 0 deletions

diff --git a/src/QtVsTools.sln b/src/QtVsTools.sln
index 223b7d42..a21c10bf 100644
--- a/src/QtVsTools.sln
+++ b/src/QtVsTools.sln
@@ -112,6 +112,8 @@ Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "QtMSBuild", "qtmsbuild\QtMS
 EndProject
 Project("{2150E333-8FDC-42A3-9474-1A3956D46DE8}") = "Tools", "Tools", "{46B0F2DF-BE7A-45DD-AC92-183CC8678054}"
 EndProject
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Test_QtVsTools.PriorityQueue", "tests\Test_QtVsTools.PriorityQueue\Test_QtVsTools.PriorityQueue.csproj", "{A5320606-37B8-4F15-97E2-16314109CAF9}"
+EndProject
 Global
 	GlobalSection(SolutionConfigurationPlatforms) = preSolution
 		Debug|Any CPU = Debug|Any CPU
@@ -414,6 +416,18 @@ Global
 		{C461C580-37A5-4B37-8A7B-10C8E1D3C5B5}.Release|x64.Build.0 = Release|Any CPU
 		{C461C580-37A5-4B37-8A7B-10C8E1D3C5B5}.Release|x86.ActiveCfg = Release|Any CPU
 		{C461C580-37A5-4B37-8A7B-10C8E1D3C5B5}.Release|x86.Build.0 = Release|Any CPU
+		{A5320606-37B8-4F15-97E2-16314109CAF9}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+		{A5320606-37B8-4F15-97E2-16314109CAF9}.Debug|Any CPU.Build.0 = Debug|Any CPU
+		{A5320606-37B8-4F15-97E2-16314109CAF9}.Debug|x64.ActiveCfg = Debug|Any CPU
+		{A5320606-37B8-4F15-97E2-16314109CAF9}.Debug|x64.Build.0 = Debug|Any CPU
+		{A5320606-37B8-4F15-97E2-16314109CAF9}.Debug|x86.ActiveCfg = Debug|Any CPU
+		{A5320606-37B8-4F15-97E2-16314109CAF9}.Debug|x86.Build.0 = Debug|Any CPU
+		{A5320606-37B8-4F15-97E2-16314109CAF9}.Release|Any CPU.ActiveCfg = Release|Any CPU
+		{A5320606-37B8-4F15-97E2-16314109CAF9}.Release|Any CPU.Build.0 = Release|Any CPU
+		{A5320606-37B8-4F15-97E2-16314109CAF9}.Release|x64.ActiveCfg = Release|Any CPU
+		{A5320606-37B8-4F15-97E2-16314109CAF9}.Release|x64.Build.0 = Release|Any CPU
+		{A5320606-37B8-4F15-97E2-16314109CAF9}.Release|x86.ActiveCfg = Release|Any CPU
+		{A5320606-37B8-4F15-97E2-16314109CAF9}.Release|x86.Build.0 = Release|Any CPU
 	EndGlobalSection
 	GlobalSection(SolutionProperties) = preSolution
 		HideSolutionNode = FALSE
@@ -442,6 +456,7 @@ Global
 		{7AF6C34B-65D2-4010-92F6-420E59DDE9BF} = {35B29B0F-0B9C-45EB-A8EF-2A8D3BF64B6F}
 		{4CEE73C9-FCFA-3A72-A0A3-036BDBB3240F} = {46B0F2DF-BE7A-45DD-AC92-183CC8678054}
 		{70711A97-D9B0-3A86-9756-9FF47337908B} = {46B0F2DF-BE7A-45DD-AC92-183CC8678054}
+		{A5320606-37B8-4F15-97E2-16314109CAF9} = {3956AF5F-164C-4D38-B5B3-298D9250C193}
 	EndGlobalSection
 	GlobalSection(ExtensibilityGlobals) = postSolution
 		SolutionGuid = {EDED4DBD-13ED-475C-B6CE-30AB88EDA03D}
diff --git a/src/qtvstools/Common/PriorityQueue.cs b/src/qtvstools/Common/PriorityQueue.cs
new file mode 100644
index 00000000..2a630273
--- /dev/null
+++ b/src/qtvstools/Common/PriorityQueue.cs
@@ -0,0 +1,156 @@
+/****************************************************************************
+**
+** Copyright (C) 2021 The Qt Company Ltd.
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the Qt VS Tools.
+**
+** $QT_BEGIN_LICENSE:GPL-EXCEPT$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company. For licensing terms
+** and conditions see https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://www.qt.io/contact-us.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3 as published by the Free Software
+** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+using System;
+using System.Collections;
+using System.Collections.Generic;
+using System.Linq;
+
+namespace QtVsTools
+{
+    public class PriorityQueue<T, TPriority> : BasePriorityQueue<T, TPriority>
+        where TPriority : IComparable<TPriority>
+    {
+        public PriorityQueue() : base()
+        { }
+
+        public PriorityQueue(Func<T, object> getItemKey) : base(getItemKey)
+        { }
+
+        public new void Enqueue(T item, TPriority priority)
+        {
+            base.Enqueue(item, priority);
+        }
+    }
+
+    public abstract class BasePriorityQueue<T, TPriority> : Concurrent, IEnumerable<T>
+        where TPriority : IComparable<TPriority>
+    {
+        SortedDictionary<TPriority, T> ItemsByPriority { get; set; }
+        Dictionary<object, TPriority> ItemPriority { get; set; }
+        T Head { get; set; }
+
+        IEnumerable<T> Items => ThreadSafe(() => ItemsByPriority.Values.ToList());
+        IEnumerator<T> IEnumerable<T>.GetEnumerator() => Items.GetEnumerator();
+        IEnumerator IEnumerable.GetEnumerator() => Items.GetEnumerator();
+
+        Func<T, object> GetItemKey { get; set; }
+
+        public BasePriorityQueue()
+        {
+            Clear();
+            GetItemKey = (x => x);
+        }
+
+        public BasePriorityQueue(Func<T, object> getItemKey)
+        {
+            Clear();
+            GetItemKey = getItemKey;
+        }
+
+        public void Clear()
+        {
+            lock (CriticalSection) {
+                ItemsByPriority = new SortedDictionary<TPriority, T>();
+                ItemPriority = new Dictionary<object, TPriority>();
+                Head = default(T);
+            }
+        }
+
+        public bool Contains(T item)
+        {
+            lock (CriticalSection) {
+                return ItemPriority.ContainsKey(GetItemKey(item));
+            }
+        }
+
+        // Base Enqueue() is protected to allow specialized implementations to
+        // hide the concept of priority (e.g. PunisherQueue).
+        //
+        protected void Enqueue(T item, TPriority priority)
+        {
+            if (item == null)
+                throw new InvalidOperationException("Item cannot be null.");
+            lock (CriticalSection) {
+                T oldItem;
+                if (ItemsByPriority.TryGetValue(priority, out oldItem) && !item.Equals(oldItem))
+                    throw new InvalidOperationException("An item with the same priority exists.");
+                TPriority oldPriority;
+                if (ItemPriority.TryGetValue(GetItemKey(item), out oldPriority))
+                    ItemsByPriority.Remove(oldPriority);
+                ItemPriority[GetItemKey(item)] = priority;
+                ItemsByPriority[priority] = item;
+                Head = ItemsByPriority.First().Value;
+            }
+        }
+
+        public bool TryPeek(out T result)
+        {
+            lock (CriticalSection) {
+                result = Head;
+                return ItemsByPriority.Any();
+            }
+        }
+
+        public T Peek()
+        {
+            lock (CriticalSection) {
+                T result;
+                if (!TryPeek(out result))
+                    throw new InvalidOperationException("Queue is empty.");
+                return result;
+            }
+        }
+
+        public bool TryDequeue(out T result)
+        {
+            lock (CriticalSection) {
+                result = Head;
+                if (!ItemsByPriority.Any())
+                    return false;
+                ItemsByPriority.Remove(ItemPriority[GetItemKey(result)]);
+                ItemPriority.Remove(GetItemKey(result));
+                if (ItemsByPriority.Any())
+                    Head = ItemsByPriority.First().Value;
+                else
+                    Head = default(T);
+                return true;
+            }
+        }
+
+        public T Dequeue()
+        {
+            lock (CriticalSection) {
+                T result;
+                if (!TryDequeue(out result))
+                    throw new InvalidOperationException("Queue is empty.");
+                return result;
+            }
+        }
+    }
+}
diff --git a/src/qtvstools/Common/PunisherQueue.cs b/src/qtvstools/Common/PunisherQueue.cs
new file mode 100644
index 00000000..9fd14f6e
--- /dev/null
+++ b/src/qtvstools/Common/PunisherQueue.cs
@@ -0,0 +1,53 @@
+/****************************************************************************
+**
+** Copyright (C) 2021 The Qt Company Ltd.
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the Qt VS Tools.
+**
+** $QT_BEGIN_LICENSE:GPL-EXCEPT$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company. For licensing terms
+** and conditions see https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://www.qt.io/contact-us.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3 as published by the Free Software
+** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+using System;
+
+namespace QtVsTools
+{
+    public class PunisherQueue<T> : BasePriorityQueue<T, long>
+    {
+        public PunisherQueue() : base()
+        { }
+
+        public PunisherQueue(Func<T, object> getItemKey) : base(getItemKey)
+        { }
+
+        /// <summary>
+        /// Enqueue/re-queue moves item to back of the queue, effectively "punishing" items that
+        /// were already in the queue.
+        /// </summary>
+        ///
+        public void Enqueue(T item)
+        {
+            lock (CriticalSection) {
+                Enqueue(item, Timestamp.Next());
+            }
+        }
+    }
+}
diff --git a/src/qtvstools/QtVsTools.csproj b/src/qtvstools/QtVsTools.csproj
index 5a68fc43..0152a5b9 100644
--- a/src/qtvstools/QtVsTools.csproj
+++ b/src/qtvstools/QtVsTools.csproj
@@ -61,12 +61,15 @@
     <Compile Include="Common\Concurrent.cs" />
     <Compile Include="Common\ConcurrentStopwatch.cs" />
     <Compile Include="Common\Disposable.cs" />
+    <Compile Include="Common\PriorityQueue.cs" />
     <Compile Include="Common\NativeAPI.cs" />
     <Compile Include="Common\Prototyped.cs" />
     <Compile Include="Common\Json\DeferredObject.cs" />
     <Compile Include="Common\Json\Serializable.cs" />
     <Compile Include="Common\Json\SerializableEnum.cs" />
     <Compile Include="Common\Json\Serializer.cs" />
+    <Compile Include="Common\PunisherQueue.cs" />
+    <Compile Include="Common\Timestamp.cs" />
     <Compile Include="DteEventsHandler.cs" />
     <Compile Include="Editors\Editor.cs" />
     <Compile Include="Editors\Editor.QtDesigner.cs" />
diff --git a/src/tests/Test_QtVsTools.PriorityQueue/Properties/AssemblyInfo.cs b/src/tests/Test_QtVsTools.PriorityQueue/Properties/AssemblyInfo.cs
new file mode 100644
index 00000000..281e9743
--- /dev/null
+++ b/src/tests/Test_QtVsTools.PriorityQueue/Properties/AssemblyInfo.cs
@@ -0,0 +1,48 @@
+/****************************************************************************
+**
+** Copyright (C) 2021 The Qt Company Ltd.
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the Qt VS Tools.
+**
+** $QT_BEGIN_LICENSE:GPL-EXCEPT$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company. For licensing terms
+** and conditions see https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://www.qt.io/contact-us.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3 as published by the Free Software
+** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+using System.Reflection;
+using System.Runtime.CompilerServices;
+using System.Runtime.InteropServices;
+
+[assembly: AssemblyTitle("Test_QtVsTools.PriorityQueue")]
+[assembly: AssemblyDescription("")]
+[assembly: AssemblyConfiguration("")]
+[assembly: AssemblyCompany("")]
+[assembly: AssemblyProduct("Test_QtVsTools.PriorityQueue")]
+[assembly: AssemblyCopyright("Copyright ©  2021")]
+[assembly: AssemblyTrademark("")]
+[assembly: AssemblyCulture("")]
+
+[assembly: ComVisible(false)]
+
+[assembly: Guid("a5320606-37b8-4f15-97e2-16314109caf9")]
+
+// [assembly: AssemblyVersion("1.0.*")]
+[assembly: AssemblyVersion("1.0.0.0")]
+[assembly: AssemblyFileVersion("1.0.0.0")]
diff --git a/src/tests/Test_QtVsTools.PriorityQueue/Test_PriorityQueue.cs b/src/tests/Test_QtVsTools.PriorityQueue/Test_PriorityQueue.cs
new file mode 100644
index 00000000..ef46a1e1
--- /dev/null
+++ b/src/tests/Test_QtVsTools.PriorityQueue/Test_PriorityQueue.cs
@@ -0,0 +1,219 @@
+/****************************************************************************
+**
+** Copyright (C) 2021 The Qt Company Ltd.
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the Qt VS Tools.
+**
+** $QT_BEGIN_LICENSE:GPL-EXCEPT$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company. For licensing terms
+** and conditions see https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://www.qt.io/contact-us.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3 as published by the Free Software
+** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+using System;
+using System.IO;
+using System.Linq;
+using System.Threading;
+using System.Threading.Tasks;
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+
+namespace QtVsTools.Test.PriorityQueue
+{
+    [TestClass]
+    public class Test_PriorityQueue
+    {
+        [TestMethod]
+        public void TestEnqueueWithPriority()
+        {
+            var q = new PriorityQueue<string, int>();
+            q.Enqueue("c", 30);
+            q.Enqueue("a", 13);
+            q.Enqueue("d", 47);
+            q.Enqueue("b", 28);
+            Assert.IsTrue(string.Join("", q) == "abcd");
+        }
+
+        [TestMethod]
+        [ExpectedException(typeof(InvalidOperationException))]
+        public void TestEnqueueWithSamePriority()
+        {
+            var q = new PriorityQueue<string, int>();
+            q.Enqueue("a", 1);
+            q.Enqueue("a", 1);
+            Assert.IsTrue(string.Join("", q) == "a");
+            q.Enqueue("b", 1);
+        }
+
+        [TestMethod]
+        public void TestEnqueueContains()
+        {
+            var q = new PunisherQueue<string>();
+            q.Enqueue("a");
+            q.Enqueue("b");
+            q.Enqueue("c");
+            Assert.IsTrue(q.Contains("a"));
+            Assert.IsTrue(q.Contains("b"));
+            Assert.IsTrue(q.Contains("c"));
+            Assert.IsTrue(string.Join("", q) == "abc");
+        }
+
+        [TestMethod]
+        public void TestEnqueueTwice()
+        {
+            var q = new PunisherQueue<string>();
+            q.Enqueue("a");
+            q.Enqueue("b");
+            q.Enqueue("a");
+            q.Enqueue("c");
+            q.Enqueue("b");
+            Assert.IsTrue(string.Join("", q) == "acb");
+        }
+
+        [TestMethod]
+        public void TestTryPeek()
+        {
+            var q = new PunisherQueue<string>();
+            string s;
+            Assert.IsTrue(!q.TryPeek(out s));
+            q.Enqueue("a");
+            q.Enqueue("b");
+            q.Enqueue("c");
+            Assert.IsTrue(q.TryPeek(out s) && s == "a");
+            Assert.IsTrue(string.Join("", q) == "abc");
+        }
+
+        [TestMethod]
+        public void TestPeek()
+        {
+            var q = new PunisherQueue<string>();
+            q.Enqueue("a");
+            q.Enqueue("b");
+            q.Enqueue("c");
+            Assert.IsTrue(q.Peek() == "a");
+            Assert.IsTrue(string.Join("", q) == "abc");
+        }
+
+        [TestMethod]
+        [ExpectedException(typeof(InvalidOperationException))]
+        public void TestPeekEmpty()
+        {
+            var q = new PunisherQueue<string>();
+            q.Peek();
+        }
+
+        [TestMethod]
+        public void TestTryDequeue()
+        {
+            var q = new PunisherQueue<string>();
+            string s;
+            Assert.IsTrue(!q.TryDequeue(out s));
+            q.Enqueue("a");
+            q.Enqueue("b");
+            q.Enqueue("c");
+            Assert.IsTrue(q.TryDequeue(out s) && s == "a");
+            Assert.IsTrue(string.Join("", q) == "bc");
+        }
+
+        [TestMethod]
+        public void TestDequeue()
+        {
+            var q = new PunisherQueue<string>();
+            q.Enqueue("a");
+            q.Enqueue("b");
+            q.Enqueue("c");
+            Assert.IsTrue(q.Dequeue() == "a");
+            Assert.IsTrue(string.Join("", q) == "bc");
+        }
+
+        [TestMethod]
+        [ExpectedException(typeof(InvalidOperationException))]
+        public void TestDequeueEmpty()
+        {
+            var q = new PunisherQueue<string>();
+            q.Dequeue();
+        }
+
+        [TestMethod]
+        public void TestClear()
+        {
+            var q = new PunisherQueue<string>();
+            q.Enqueue("a");
+            q.Enqueue("b");
+            q.Enqueue("c");
+            q.Clear();
+            q.Enqueue("x");
+            q.Enqueue("y");
+            q.Enqueue("z");
+            Assert.IsTrue(string.Join("", q) == "xyz");
+        }
+
+        [TestMethod]
+        public void TestConcurrency()
+        {
+            var q = new PunisherQueue<string>();
+            int n = 0;
+            Task.Run(() =>
+            {
+                for (int i = 0; i < 10000; ++i) {
+                    q.Enqueue(Path.GetRandomFileName());
+                    ++n;
+                    Thread.Yield();
+                }
+            });
+            for (int i = 0; i < 10000; ++i) {
+                string s;
+                if (!q.TryDequeue(out s))
+                    --i;
+                --n;
+                Thread.Yield();
+            }
+            if (n == 0)
+                Assert.Inconclusive();
+            Assert.IsTrue(q.Count() == 0);
+        }
+
+        [TestMethod]
+        public void TestGetItemKey()
+        {
+            var q = new PunisherQueue<string>(item =>
+            {
+                switch (item) {
+                    case "a":
+                    case "x":
+                        return "ax";
+                    case "b":
+                    case "y":
+                        return "by";
+                    case "c":
+                    case "z":
+                        return "cz";
+                    default:
+                        return item;
+                }
+            });
+            q.Enqueue("a");
+            q.Enqueue("b");
+            q.Enqueue("c");
+            q.Enqueue("x");
+            q.Enqueue("z");
+            q.Enqueue("w");
+            Assert.IsTrue(string.Join("", q) == "bxzw");
+        }
+    }
+}
diff --git a/src/tests/Test_QtVsTools.PriorityQueue/Test_QtVsTools.PriorityQueue.csproj b/src/tests/Test_QtVsTools.PriorityQueue/Test_QtVsTools.PriorityQueue.csproj
new file mode 100644
index 00000000..b166a430
--- /dev/null
+++ b/src/tests/Test_QtVsTools.PriorityQueue/Test_QtVsTools.PriorityQueue.csproj
@@ -0,0 +1,103 @@
+<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="$(VisualStudioVersion)" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <!--
+    *****************************************************************************
+    **
+    ** Copyright (C) 2021 The Qt Company Ltd.
+    ** Contact: https://www.qt.io/licensing/
+    **
+    ** This file is part of the Qt VS Tools.
+    **
+    ** $QT_BEGIN_LICENSE:GPL-EXCEPT$
+    ** Commercial License Usage
+    ** Licensees holding valid commercial Qt licenses may use this file in
+    ** accordance with the commercial license agreement provided with the
+    ** Software or, alternatively, in accordance with the terms contained in
+    ** a written agreement between you and The Qt Company. For licensing terms
+    ** and conditions see https://www.qt.io/terms-conditions. For further
+    ** information use the contact form at https://www.qt.io/contact-us.
+    **
+    ** GNU General Public License Usage
+    ** Alternatively, this file may be used under the terms of the GNU
+    ** General Public License version 3 as published by the Free Software
+    ** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
+    ** included in the packaging of this file. Please review the following
+    ** information to ensure the GNU General Public License requirements will
+    ** be met: https://www.gnu.org/licenses/gpl-3.0.html.
+    **
+    ** $QT_END_LICENSE$
+    **
+    *****************************************************************************
+-->
+  <Import Project="..\..\packages\MSTest.TestAdapter.1.3.2\build\net45\MSTest.TestAdapter.props" Condition="Exists('..\..\packages\MSTest.TestAdapter.1.3.2\build\net45\MSTest.TestAdapter.props')" />
+  <Import Project="$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props" Condition="Exists('$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props')" />
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <ProjectGuid>{A5320606-37B8-4F15-97E2-16314109CAF9}</ProjectGuid>
+    <OutputType>Library</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <RootNamespace>Test_QtVsTools.PriorityQueue</RootNamespace>
+    <AssemblyName>Test_QtVsTools.PriorityQueue</AssemblyName>
+    <TargetFrameworkVersion>v4.7.2</TargetFrameworkVersion>
+    <FileAlignment>512</FileAlignment>
+    <ProjectTypeGuids>{3AC096D0-A1C2-E12C-1390-A8335801FDAB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}</ProjectTypeGuids>
+    <VisualStudioVersion Condition="'$(VisualStudioVersion)' == ''">15.0</VisualStudioVersion>
+    <VSToolsPath Condition="'$(VSToolsPath)' == ''">$(MSBuildExtensionsPath32)\Microsoft\VisualStudio\v$(VisualStudioVersion)</VSToolsPath>
+    <ReferencePath>$(ProgramFiles)\Common Files\microsoft shared\VSTT\$(VisualStudioVersion)\UITestExtensionPackages</ReferencePath>
+    <IsCodedUITest>False</IsCodedUITest>
+    <TestProjectType>UnitTest</TestProjectType>
+    <NuGetPackageImportStamp>
+    </NuGetPackageImportStamp>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+    <DebugSymbols>true</DebugSymbols>
+    <DebugType>full</DebugType>
+    <Optimize>false</Optimize>
+    <OutputPath>bin\Debug\</OutputPath>
+    <DefineConstants>DEBUG;TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+    <OutputPath>bin\Release\</OutputPath>
+    <DefineConstants>TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+  </PropertyGroup>
+  <ItemGroup>
+    <Reference Include="Microsoft.VisualStudio.TestPlatform.TestFramework, Version=14.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL">
+      <HintPath>..\..\packages\MSTest.TestFramework.1.3.2\lib\net45\Microsoft.VisualStudio.TestPlatform.TestFramework.dll</HintPath>
+    </Reference>
+    <Reference Include="Microsoft.VisualStudio.TestPlatform.TestFramework.Extensions, Version=14.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL">
+      <HintPath>..\..\packages\MSTest.TestFramework.1.3.2\lib\net45\Microsoft.VisualStudio.TestPlatform.TestFramework.Extensions.dll</HintPath>
+    </Reference>
+    <Reference Include="System" />
+    <Reference Include="System.Core" />
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="Test_PriorityQueue.cs" />
+    <Compile Include="Properties\AssemblyInfo.cs" />
+  </ItemGroup>
+  <ItemGroup>
+    <None Include="packages.config" />
+  </ItemGroup>
+  <ItemGroup>
+    <ProjectReference Include="..\..\qtvstools\QtVsTools.csproj">
+      <Project>{fd7a42db-8692-4fbe-ac50-f70af423275b}</Project>
+      <Name>QtVsTools</Name>
+    </ProjectReference>
+  </ItemGroup>
+  <Import Project="$(VSToolsPath)\TeamTest\Microsoft.TestTools.targets" Condition="Exists('$(VSToolsPath)\TeamTest\Microsoft.TestTools.targets')" />
+  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
+  <Target Name="EnsureNuGetPackageBuildImports" BeforeTargets="PrepareForBuild">
+    <PropertyGroup>
+      <ErrorText>This project references NuGet package(s) that are missing on this computer. Use NuGet Package Restore to download them.  For more information, see http://go.microsoft.com/fwlink/?LinkID=322105. The missing file is {0}.</ErrorText>
+    </PropertyGroup>
+    <Error Condition="!Exists('..\..\packages\MSTest.TestAdapter.1.3.2\build\net45\MSTest.TestAdapter.props')" Text="$([System.String]::Format('$(ErrorText)', '..\..\packages\MSTest.TestAdapter.1.3.2\build\net45\MSTest.TestAdapter.props'))" />
+    <Error Condition="!Exists('..\..\packages\MSTest.TestAdapter.1.3.2\build\net45\MSTest.TestAdapter.targets')" Text="$([System.String]::Format('$(ErrorText)', '..\..\packages\MSTest.TestAdapter.1.3.2\build\net45\MSTest.TestAdapter.targets'))" />
+  </Target>
+  <Import Project="..\..\packages\MSTest.TestAdapter.1.3.2\build\net45\MSTest.TestAdapter.targets" Condition="Exists('..\..\packages\MSTest.TestAdapter.1.3.2\build\net45\MSTest.TestAdapter.targets')" />
+</Project>
\ No newline at end of file
diff --git a/src/tests/Test_QtVsTools.PriorityQueue/packages.config b/src/tests/Test_QtVsTools.PriorityQueue/packages.config
new file mode 100644
index 00000000..2f7c5a18
--- /dev/null
+++ b/src/tests/Test_QtVsTools.PriorityQueue/packages.config
@@ -0,0 +1,5 @@
+<?xml version="1.0" encoding="utf-8"?>
+<packages>
+  <package id="MSTest.TestAdapter" version="1.3.2" targetFramework="net472" />
+  <package id="MSTest.TestFramework" version="1.3.2" targetFramework="net472" />
+</packages>
\ No newline at end of file