_test/meowpp_MergeableHeap.cpp


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

#include "meowpp/dsa/MergeableHeap.h"
#include "meowpp/utility.h"

#include "meowpp.h"

#include <vector>
#include <queue>
#include <cstdlib>


TEST(MergeableHeap){
  int N = 10;
  std::vector<std::priority_queue<int> > nhp;
  std::vector<meow::MergeableHeap<int> > mhp;
  for(int i = 0; i < 10; i++){
    int MM = 5000 + rand() % 10000;
    meow::messagePrintf(1, "%d-th test (M = %5d)", i, MM);
    nhp.clear(); nhp.resize(N);
    mhp.clear(); mhp.resize(N);
    int tn = 0, tm = 0, t0;
    for(int j = 0; j < MM; j++){
      if((rand() & 3) == 0){
        int a = rand() % N;
        int num = rand();
        t0 = clock(); nhp[a].push(num); tn += clock() - t0;
        t0 = clock(); mhp[a].push(num); tm += clock() - t0;
      }else if(rand() & 1){
        int a = rand() % N;
        t0 = clock(); 
        if(!nhp[a].empty()) nhp[a].pop();
        tn += clock() - t0;
        t0 = clock();
        if(!mhp[a].empty()) mhp[a].pop();
        tm += clock() - t0;
      }else{
        int a = rand() % N, b = rand() % N;
        if(b == a) b = (b + 1) % N;
        t0 = clock();
        for( ; !nhp[b].empty(); nhp[b].pop()){
          nhp[a].push(nhp[b].top());
        }
        tn += clock() - t0;
        t0 = clock();
        mhp[a].merge(&mhp[b]);
        tm += clock() - t0;
      }
    }
    bool ok = true;
    for(int j = 0; j < N; j++){
      while(!nhp[j].empty() && !mhp[j].empty()){
        if(nhp[j].top() != mhp[j].top()){
          ok = false;
          break;
        }
        nhp[j].pop();
        mhp[j].pop();
      }
      if(mhp[j].empty() != nhp[j].empty()){
        ok = false;
      }
      if(ok == false) break;
    }
    ok = true;
    if(!ok){
      meow::messagePrintf(-1, "fail");
      return false;
    }else{
      meow::messagePrintf(-1, "ok %.3f/%.3f",
                          tm * 1.0 / CLOCKS_PER_SEC,
                          tn * 1.0 / CLOCKS_PER_SEC );
    }
  }
  return true;
};