Merge branch 'master' into fs_QuadricEdgeCollapse

1 files changed, 129 insertions, 118 deletions

diff --git a/tests/libslic3r/test_mutable_priority_queue.cpp b/tests/libslic3r/test_mutable_priority_queue.cpp
index 83ac28793..37b244432 100644
--- a/tests/libslic3r/test_mutable_priority_queue.cpp
+++ b/tests/libslic3r/test_mutable_priority_queue.cpp
@@ -54,12 +54,18 @@ TEST_CASE("Skip addressing", "[MutableSkipHeapPriorityQueue]") {
     }
 }
 
+struct ValueIndexPair
+{
+    int     value;
+    size_t  idx = 0;
+};
+
 template<size_t block_size = 16>
 static auto make_test_priority_queue()
 {
-    return make_miniheap_mutable_priority_queue<std::pair<int, size_t>, block_size, false>(
-        [](std::pair<int, size_t> &v, size_t idx){ v.second = idx; },
-        [](std::pair<int, size_t> &l, std::pair<int, size_t> &r){ return l.first < r.first; });
+    return make_miniheap_mutable_priority_queue<ValueIndexPair, block_size, false>(
+        [](ValueIndexPair &v, size_t idx){ v.idx = idx; },
+        [](ValueIndexPair &l, ValueIndexPair &r){ return l.value < r.value; });
 }
 
 TEST_CASE("Mutable priority queue - basic tests", "[MutableSkipHeapPriorityQueue]") {
@@ -70,18 +76,18 @@ TEST_CASE("Mutable priority queue - basic tests", "[MutableSkipHeapPriorityQueue
     }
     SECTION("an empty queue is not empty when one element is inserted") {
         auto q = make_test_priority_queue();
-        q.push(std::make_pair(1, 0U));
+        q.push({ 1 });
         REQUIRE(!q.empty());
         REQUIRE(q.size() == 1);
     }
     SECTION("a queue with one element has it on top") {
         auto q = make_test_priority_queue();
-        q.push(std::make_pair(8, 0U));
-        REQUIRE(q.top().first == 8);
+        q.push({ 8 });
+        REQUIRE(q.top().value == 8);
     }
     SECTION("a queue with one element becomes empty when popped") {
         auto q = make_test_priority_queue();
-        q.push(std::make_pair(9, 0U));
+        q.push({ 9 });
         q.pop();
         REQUIRE(q.empty());
         REQUIRE(q.size() == 0);
@@ -89,22 +95,22 @@ TEST_CASE("Mutable priority queue - basic tests", "[MutableSkipHeapPriorityQueue
     SECTION("insert sorted stays sorted") {
         auto q = make_test_priority_queue();
         for (auto i : { 1, 2, 3, 4, 5, 6, 7, 8 })
-            q.push(std::make_pair(i, 0U));
-        REQUIRE(q.top().first == 1);
+            q.push({ i });
+        REQUIRE(q.top().value == 1);
         q.pop();
-        REQUIRE(q.top().first == 2);
+        REQUIRE(q.top().value == 2);
         q.pop();
-        REQUIRE(q.top().first == 3);
+        REQUIRE(q.top().value == 3);
         q.pop();
-        REQUIRE(q.top().first == 4);
+        REQUIRE(q.top().value == 4);
         q.pop();
-        REQUIRE(q.top().first == 5);
+        REQUIRE(q.top().value == 5);
         q.pop();
-        REQUIRE(q.top().first == 6);
+        REQUIRE(q.top().value == 6);
         q.pop();
-        REQUIRE(q.top().first == 7);
+        REQUIRE(q.top().value == 7);
         q.pop();
-        REQUIRE(q.top().first == 8);
+        REQUIRE(q.top().value == 8);
         q.pop();
         REQUIRE(q.empty());
     }
@@ -116,14 +122,14 @@ TEST_CASE("Mutable priority queue - basic tests", "[MutableSkipHeapPriorityQueue
         int n[36000];
         for (auto& i : n) {
             i = dist(gen);
-            q.push(std::make_pair(i, 0U));
+            q.push({ i });
         }
 
         REQUIRE(!q.empty());
         REQUIRE(q.size() == 36000);
         std::sort(std::begin(n), std::end(n));
         for (auto i : n) {
-            REQUIRE(q.top().first == i);
+            REQUIRE(q.top().value == i);
             q.pop();
         }
         REQUIRE(q.empty());
@@ -131,176 +137,181 @@ TEST_CASE("Mutable priority queue - basic tests", "[MutableSkipHeapPriorityQueue
 }
 
 TEST_CASE("Mutable priority queue - reshedule first", "[MutableSkipHeapPriorityQueue]") {
+    struct MyValue {
+        int    value;
+        int   *ptr;
+        size_t idx;
+    };
     SECTION("reschedule top with highest prio leaves order unchanged") {
-        auto q = make_miniheap_mutable_priority_queue<std::pair<std::pair<int, int*>, size_t>, 4, false>(
-            [](std::pair<std::pair<int, int*>, size_t>& v, size_t idx) { v.second = idx; },
-            [](std::pair<std::pair<int, int*>, size_t>& l, std::pair<std::pair<int, int*>, size_t>& r) { return l.first.first < r.first.first; });
+        auto q = make_miniheap_mutable_priority_queue<MyValue, 4, false>(
+            [](MyValue& v, size_t idx) { v.idx = idx; },
+            [](MyValue& l, MyValue& r) { return l.value < r.value; });
 
         //              0  1   2   3  4   5  6   7   8
         int nums[] = { 32, 1, 88, 16, 9, 11, 3, 22, 23 };
         for (auto &i : nums)
-            q.push(std::make_pair(std::make_pair(i, &i), 0U));
-        REQUIRE(q.top().first.first == 1);
-        REQUIRE(q.top().first.second == &nums[1]);
-        REQUIRE(*q.top().first.second == 1);
+            q.push({ i, &i, 0U });
+        REQUIRE(q.top().value == 1);
+        REQUIRE(q.top().ptr == &nums[1]);
+        REQUIRE(*q.top().ptr == 1);
 
         // Update the top element.
-        q.top().first.first = 2;
+        q.top().value = 2;
         q.update(1);
 
-        REQUIRE(q.top().first.first == 2);
-        REQUIRE(q.top().first.second == &nums[1]);
+        REQUIRE(q.top().value == 2);
+        REQUIRE(q.top().ptr == &nums[1]);
         q.pop();
-        REQUIRE(q.top().first.first == 3);
-        REQUIRE(q.top().first.second == &nums[6]);
+        REQUIRE(q.top().value == 3);
+        REQUIRE(q.top().ptr == &nums[6]);
         q.pop();
-        REQUIRE(q.top().first.first == 9);
-        REQUIRE(q.top().first.second == &nums[4]);
+        REQUIRE(q.top().value == 9);
+        REQUIRE(q.top().ptr == &nums[4]);
         q.pop();
-        REQUIRE(q.top().first.first == 11);
-        REQUIRE(q.top().first.second == &nums[5]);
+        REQUIRE(q.top().value == 11);
+        REQUIRE(q.top().ptr == &nums[5]);
         q.pop();
-        REQUIRE(q.top().first.first == 16);
-        REQUIRE(q.top().first.second == &nums[3]);
+        REQUIRE(q.top().value == 16);
+        REQUIRE(q.top().ptr == &nums[3]);
         q.pop();
-        REQUIRE(q.top().first.first == 22);
-        REQUIRE(q.top().first.second == &nums[7]);
+        REQUIRE(q.top().value == 22);
+        REQUIRE(q.top().ptr == &nums[7]);
         q.pop();
-        REQUIRE(q.top().first.first == 23);
-        REQUIRE(q.top().first.second == &nums[8]);
+        REQUIRE(q.top().value == 23);
+        REQUIRE(q.top().ptr == &nums[8]);
         q.pop();
-        REQUIRE(q.top().first.first == 32);
-        REQUIRE(q.top().first.second == &nums[0]);
+        REQUIRE(q.top().value == 32);
+        REQUIRE(q.top().ptr == &nums[0]);
         q.pop();
-        REQUIRE(q.top().first.first == 88);
-        REQUIRE(q.top().first.second == &nums[2]);
+        REQUIRE(q.top().value == 88);
+        REQUIRE(q.top().ptr == &nums[2]);
         q.pop();
         REQUIRE(q.empty());
     }
     SECTION("reschedule to mid range moves element to correct place") {
-        auto q = make_miniheap_mutable_priority_queue<std::pair<std::pair<int, int*>, size_t>, 4, false>(
-            [](std::pair<std::pair<int, int*>, size_t>& v, size_t idx) { v.second = idx; },
-            [](std::pair<std::pair<int, int*>, size_t>& l, std::pair<std::pair<int, int*>, size_t>& r) { return l.first.first < r.first.first; });
+        auto q = make_miniheap_mutable_priority_queue<MyValue, 4, false>(
+            [](MyValue& v, size_t idx) { v.idx = idx; },
+            [](MyValue& l, MyValue& r) { return l.value < r.value; });
 
         //              0  1   2   3  4   5  6   7   8
         int nums[] = { 32, 1, 88, 16, 9, 11, 3, 22, 23 };
         for (auto& i : nums)
-            q.push(std::make_pair(std::make_pair(i, &i), 0U));
-        REQUIRE(q.top().first.first == 1);
-        REQUIRE(q.top().first.second == &nums[1]);
-        REQUIRE(*q.top().first.second == 1);
+            q.push({ i, &i, 0U });
+        REQUIRE(q.top().value == 1);
+        REQUIRE(q.top().ptr == &nums[1]);
+        REQUIRE(*q.top().ptr == 1);
 
         // Update the top element.
-        q.top().first.first = 12;
+        q.top().value = 12;
         q.update(1);
 
-        REQUIRE(q.top().first.first == 3);
-        REQUIRE(q.top().first.second == &nums[6]);
+        REQUIRE(q.top().value == 3);
+        REQUIRE(q.top().ptr == &nums[6]);
         q.pop();
-        REQUIRE(q.top().first.first == 9);
-        REQUIRE(q.top().first.second == &nums[4]);
+        REQUIRE(q.top().value == 9);
+        REQUIRE(q.top().ptr == &nums[4]);
         q.pop();
-        REQUIRE(q.top().first.first == 11);
-        REQUIRE(q.top().first.second == &nums[5]);
+        REQUIRE(q.top().value == 11);
+        REQUIRE(q.top().ptr == &nums[5]);
         q.pop();
-        REQUIRE(q.top().first.first == 12);
-        REQUIRE(q.top().first.second == &nums[1]);
+        REQUIRE(q.top().value == 12);
+        REQUIRE(q.top().ptr == &nums[1]);
         q.pop();
-        REQUIRE(q.top().first.first == 16);
-        REQUIRE(q.top().first.second == &nums[3]);
+        REQUIRE(q.top().value == 16);
+        REQUIRE(q.top().ptr == &nums[3]);
         q.pop();
-        REQUIRE(q.top().first.first == 22);
-        REQUIRE(q.top().first.second == &nums[7]);
+        REQUIRE(q.top().value == 22);
+        REQUIRE(q.top().ptr == &nums[7]);
         q.pop();
-        REQUIRE(q.top().first.first == 23);
-        REQUIRE(q.top().first.second == &nums[8]);
+        REQUIRE(q.top().value == 23);
+        REQUIRE(q.top().ptr == &nums[8]);
         q.pop();
-        REQUIRE(q.top().first.first == 32);
-        REQUIRE(q.top().first.second == &nums[0]);
+        REQUIRE(q.top().value == 32);
+        REQUIRE(q.top().ptr == &nums[0]);
         q.pop();
-        REQUIRE(q.top().first.first == 88);
-        REQUIRE(q.top().first.second == &nums[2]);
+        REQUIRE(q.top().value == 88);
+        REQUIRE(q.top().ptr == &nums[2]);
         q.pop();
         REQUIRE(q.empty());
     }
     SECTION("reschedule to last moves element to correct place", "heap")
     {
-        auto q = make_miniheap_mutable_priority_queue<std::pair<std::pair<int, int*>, size_t>, 4, false>(
-            [](std::pair<std::pair<int, int*>, size_t>& v, size_t idx) { v.second = idx; },
-            [](std::pair<std::pair<int, int*>, size_t>& l, std::pair<std::pair<int, int*>, size_t>& r) { return l.first.first < r.first.first; });
+        auto q = make_miniheap_mutable_priority_queue<MyValue, 4, false>(
+            [](MyValue& v, size_t idx) { v.idx = idx; },
+            [](MyValue& l, MyValue& r) { return l.value < r.value; });
 
         //              0  1   2   3  4   5  6   7   8
         int nums[] = { 32, 1, 88, 16, 9, 11, 3, 22, 23 };
         for (auto& i : nums)
-            q.push(std::make_pair(std::make_pair(i, &i), 0U));
-        REQUIRE(q.top().first.first == 1);
-        REQUIRE(q.top().first.second == &nums[1]);
-        REQUIRE(*q.top().first.second == 1);
+            q.push({ i, &i, 0U });
+        REQUIRE(q.top().value == 1);
+        REQUIRE(q.top().ptr == &nums[1]);
+        REQUIRE(*q.top().ptr == 1);
 
         // Update the top element.
-        q.top().first.first = 89;
+        q.top().value = 89;
         q.update(1);
 
-        REQUIRE(q.top().first.first == 3);
-        REQUIRE(q.top().first.second == &nums[6]);
+        REQUIRE(q.top().value == 3);
+        REQUIRE(q.top().ptr == &nums[6]);
         q.pop();
-        REQUIRE(q.top().first.first == 9);
-        REQUIRE(q.top().first.second == &nums[4]);
+        REQUIRE(q.top().value == 9);
+        REQUIRE(q.top().ptr == &nums[4]);
         q.pop();
-        REQUIRE(q.top().first.first == 11);
-        REQUIRE(q.top().first.second == &nums[5]);
+        REQUIRE(q.top().value == 11);
+        REQUIRE(q.top().ptr == &nums[5]);
         q.pop();
-        REQUIRE(q.top().first.first == 16);
-        REQUIRE(q.top().first.second == &nums[3]);
+        REQUIRE(q.top().value == 16);
+        REQUIRE(q.top().ptr == &nums[3]);
         q.pop();
-        REQUIRE(q.top().first.first == 22);
-        REQUIRE(q.top().first.second == &nums[7]);
+        REQUIRE(q.top().value == 22);
+        REQUIRE(q.top().ptr == &nums[7]);
         q.pop();
-        REQUIRE(q.top().first.first == 23);
-        REQUIRE(q.top().first.second == &nums[8]);
+        REQUIRE(q.top().value == 23);
+        REQUIRE(q.top().ptr == &nums[8]);
         q.pop();
-        REQUIRE(q.top().first.first == 32);
-        REQUIRE(q.top().first.second == &nums[0]);
+        REQUIRE(q.top().value == 32);
+        REQUIRE(q.top().ptr == &nums[0]);
         q.pop();
-        REQUIRE(q.top().first.first == 88);
-        REQUIRE(q.top().first.second == &nums[2]);
+        REQUIRE(q.top().value == 88);
+        REQUIRE(q.top().ptr == &nums[2]);
         q.pop();
-        REQUIRE(q.top().first.first == 89);
-        REQUIRE(q.top().first.second == &nums[1]);
+        REQUIRE(q.top().value == 89);
+        REQUIRE(q.top().ptr == &nums[1]);
         q.pop();
         REQUIRE(q.empty());
     }
     SECTION("reschedule top of 2 elements to last") {
         auto q = make_test_priority_queue<8>();
-        q.push(std::make_pair(1, 0U));
-        q.push(std::make_pair(2, 0U));
-        REQUIRE(q.top().first == 1);
+        q.push({ 1 });
+        q.push({ 2 });
+        REQUIRE(q.top().value == 1);
         // Update the top element.
-        q.top().first = 3;
+        q.top().value = 3;
         q.update(1);
-        REQUIRE(q.top().first == 2);
+        REQUIRE(q.top().value == 2);
     }
     SECTION("reschedule top of 3 elements left to 2nd") {
         auto q = make_test_priority_queue<8>();
-        q.push(std::make_pair(1, 0U));
-        q.push(std::make_pair(2, 0U));
-        q.push(std::make_pair(4, 0U));
-        REQUIRE(q.top().first == 1);
+        q.push({ 1 });
+        q.push({ 2 });
+        q.push({ 4 });
+        REQUIRE(q.top().value == 1);
         // Update the top element.
-        q.top().first = 3;
+        q.top().value = 3;
         q.update(1);
-        REQUIRE(q.top().first == 2);
+        REQUIRE(q.top().value == 2);
     }
     SECTION("reschedule top of 3 elements right to 2nd") {
         auto q = make_test_priority_queue<8>();
-        q.push(std::make_pair(1, 0U));
-        q.push(std::make_pair(4, 0U));
-        q.push(std::make_pair(2, 0U));
-        REQUIRE(q.top().first == 1);
+        q.push({ 1 });
+        q.push({ 4 });
+        q.push({ 2 });
+        REQUIRE(q.top().value == 1);
         // Update the top element.
-        q.top().first = 3;
+        q.top().value = 3;
         q.update(1);
-        REQUIRE(q.top().first == 2);
+        REQUIRE(q.top().value == 2);
     }
     SECTION("reschedule top random gives same resultas pop/push") {
         std::random_device rd;
@@ -312,16 +323,16 @@ TEST_CASE("Mutable priority queue - reshedule first", "[MutableSkipHeapPriorityQ
 
         for (size_t outer = 0; outer < 100; ++ outer) {
             int num = gen();
-            pq.push(std::make_pair(num, 0U));
-            stdq.push(num);
+            pq.push({ num });
+            stdq.push({ num });
             for (size_t inner = 0; inner < 100; ++ inner) {
                 int newval = gen();
                 // Update the top element.
-                pq.top().first = newval;
+                pq.top().value = newval;
                 pq.update(1);
                 stdq.pop();
-                stdq.push(newval);
-                auto n  = pq.top().first;
+                stdq.push({ newval });
+                auto n  = pq.top().value;
                 auto sn = stdq.top();
                 REQUIRE(sn == n);
             }