Line data    Source code

       1             : #include <catch2/catch_get_random_seed.hpp>
       2             : #include <catch2/catch_test_macros.hpp>
       3             : #include <queue>
       4             : #include <random>
       5             : 
       6             : #include "Alg/BinaryHeap.hpp"
       7             : 
       8             : using namespace std;
       9             : 
      10             : template<class T>
      11           2 : void dump_queue(Alg::PriorityQueue<T> &q, const vector<T> &v) {
      12           4 :     REQUIRE(q.size() == v.size());
      13             : 
      14           8 :     for(size_t i = 0; i < v.size(); ++i) {
      15          12 :         REQUIRE(q.pop() == v[i]);
      16          18 :         REQUIRE(q.size() == v.size() - i - 1);
      17             :     }
      18           2 : }
      19             : 
      20           4 : TEST_CASE("Binary heap - small tests", "[binary-heap]") {
      21           4 :     Alg::PriorityQueue<int> *q = new Alg::BinaryHeap<int>();
      22             : 
      23           5 :     SECTION("Pop empty queue gives error") {
      24           3 :         REQUIRE_THROWS(q->pop());
      25             :     }
      26             : 
      27           5 :     SECTION("Insert") {
      28           1 :         q->push(3);
      29           1 :         q->push(2);
      30           1 :         q->push(1);
      31             : 
      32           3 :         REQUIRE(q->size() == 3);
      33             :     }
      34             : 
      35           5 :     SECTION("Pop") {
      36           1 :         q->push(9);
      37           1 :         q->push(5);
      38           1 :         q->push(1);
      39             : 
      40           2 :         dump_queue(*q, {1, 5, 9});
      41             :     }
      42             : 
      43           5 :     SECTION("Decrease key") {
      44           1 :         Alg::PriorityQueue<int>::Element &el = q->push(9);
      45           1 :         q->push(5);
      46           1 :         q->push(1);
      47             : 
      48           1 :         el.decreaseKey(3);
      49             : 
      50           2 :         dump_queue(*q, {1, 3, 5});
      51             :     }
      52             : 
      53           4 :     delete q;
      54           4 : }
      55             : 
      56           1 : TEST_CASE("Binary heap - stress test", "[binary-heap]") {
      57           1 :     std::mt19937 gen(0);
      58             : 
      59           1 :     std::uniform_real_distribution<float> frand(0.0f, 1.0f);
      60           1 :     std::uniform_int_distribution<int>    rand(0);
      61             : 
      62           1 :     Alg::PriorityQueue<int> *q = new Alg::BinaryHeap<int>();
      63             : 
      64           1 :     size_t NUMBER_OPERATIONS = 100;
      65           1 :     float  PROB_INSERT       = 0.6f;
      66           1 :     float  PROB_POP          = 0.3f;
      67             :     // float PROB_DECREASE_KEY = 0.1f;
      68           1 :     float PROB_TOTAL = PROB_INSERT + PROB_POP;
      69             : 
      70           1 :     priority_queue<int, vector<int>, greater<int>> s;
      71             : 
      72         101 :     for(size_t i = 0; i < NUMBER_OPERATIONS; ++i) {
      73         100 :         float p = frand(gen) * PROB_TOTAL;
      74         100 :         if(p <= PROB_INSERT) {
      75          65 :             int r = rand(gen);
      76          65 :             q->push(r);
      77          65 :             s.push(r);
      78          35 :         } else if(p < PROB_INSERT + PROB_POP && s.size() > 0) {
      79          35 :             int r1 = q->pop();
      80          70 :             REQUIRE(r1 == s.top());
      81          35 :             s.pop();
      82             :         }
      83             : 
      84         300 :         REQUIRE(q->size() == s.size());
      85             :     }
      86             : 
      87          31 :     while(!s.empty()) {
      88          60 :         REQUIRE(q->pop() == s.top());
      89          61 :         s.pop();
      90             :     }
      91             : 
      92           1 :     delete q;
      93           1 : }