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
85
|
#include <iostream>
#include <thread>
#include <chrono>
#include <random>
#include <time.h>
#include <assert.h>
#include "IntervalTree.h"
using namespace std;
typedef Interval<bool> interval;
typedef vector<interval> intervalVector;
typedef IntervalTree<bool> intervalTree;
template<typename K>
K randKey(K floor, K ceiling) {
K range = ceiling - floor;
return floor + range * ((double) rand() / (double) (RAND_MAX + 1.0));
}
template<class T, typename K>
Interval<T,K> randomInterval(K maxStart, K maxLength, K maxStop, const T& value) {
K start = randKey<K>(0, maxStart);
K stop = min<K>(randKey<K>(start, start + maxLength), maxStop);
return Interval<T,K>(start, stop, value);
}
int main() {
typedef vector<std::size_t> countsVector;
srand((unsigned)time(NULL));
intervalVector intervals;
intervalVector queries;
// generate a test set of target intervals
for (int i = 0; i < 10000; ++i) {
intervals.push_back(randomInterval<bool>(100000, 1000, 100000 + 1, true));
}
// and queries
for (int i = 0; i < 5000; ++i) {
queries.push_back(randomInterval<bool>(100000, 1000, 100000 + 1, true));
}
typedef chrono::high_resolution_clock Clock;
typedef chrono::milliseconds milliseconds;
// using brute-force search
countsVector bruteforcecounts;
Clock::time_point t0 = Clock::now();
for (intervalVector::iterator q = queries.begin(); q != queries.end(); ++q) {
intervalVector results;
for (intervalVector::iterator i = intervals.begin(); i != intervals.end(); ++i) {
if (i->start >= q->start && i->stop <= q->stop) {
results.push_back(*i);
}
}
bruteforcecounts.push_back(results.size());
}
Clock::time_point t1 = Clock::now();
milliseconds ms = chrono::duration_cast<milliseconds>(t1 - t0);
cout << "brute force:\t" << ms.count() << "ms" << endl;
// using the interval tree
intervalTree tree = intervalTree(intervals);
countsVector treecounts;
t0 = Clock::now();
for (intervalVector::iterator q = queries.begin(); q != queries.end(); ++q) {
intervalVector results;
tree.findContained(q->start, q->stop, results);
treecounts.push_back(results.size());
}
t1 = Clock::now();
ms = std::chrono::duration_cast<milliseconds>(t1 - t0);
cout << "interval tree:\t" << ms.count() << "ms" << endl;
// check that the same number of results are returned
countsVector::iterator b = bruteforcecounts.begin();
for (countsVector::iterator t = treecounts.begin(); t != treecounts.end(); ++t, ++b) {
assert(*b == *t);
}
return 0;
}
|
