RangeReporter/range.h at master · EverNebula/RangeReporter · GitHub

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#ifndef RANGE_HEADER
#define RANGE_HEADER

#include "BOBHash32.h"
#include "utils.h"

class RangeBF
{
private:
	int size, beta;
	double max_ts, unit_ts;

	int *bf;
	BOBHash32 hash;

	void recursive_insert(int dep, uint32_t hsh, double t, int l, int r);
	void recursive_query(int dep, uint32_t hsh, int l, int r, vector<PDD>& ans);

public:
	RangeBF(int size, int beta, double max_ts)
	: size(size), beta(beta), max_ts(max_ts) { unit_ts = max_ts / size; }
	~RangeBF();
	void init();
	void insert(int v, double t);
	vector<PDD> query(int v);
};

RangeBF::~RangeBF()
{
	if (bf)
		delete [] bf;
}

void
RangeBF::init()
{
	hash.initialize(2020);
	bf = new int[size];
	memset(bf, 0, size * sizeof(int));
}

void
RangeBF::insert(int v, double t)
{
	if (t > max_ts + EPS)
	{
		printf("ERROR: timestamp is too big.\n");
		exit(0);
	}

	uint32_t hsh = hash.run((char*)&v, sizeof(int));
	recursive_insert(0, hsh, t, 0, size);
}

void
RangeBF::recursive_insert(int dep, uint32_t hsh, double t, int l, int r)
{
	// printf("%d %d %d %d %d\n", dep, hsh, t, l, r);
	if (dep == beta || r - l <= 1)
		return;

	if (l > r)
	{
		printf("ERROR: insert bound error.\n");
		exit(0);
	}

	int len = r - l;
	int pos = hsh % len + l;
	double pos_ts = pos * unit_ts;
	// printf("%d\n", pos);

	if (pos_ts <= t)
	{
		bf[pos] |= 1;
		recursive_insert(dep+1, hsh, t, pos, r);
	}
	else
	{
		bf[pos] |= 2;
		recursive_insert(dep+1, hsh, t, l, pos+1);
	}
}

vector<PDD>
RangeBF::query(int v)
{
	uint32_t hsh = hash.run((char*)&v, sizeof(int));
	vector<PDD> ans;

	recursive_query(0, hsh, 0, size, ans);

	return ans;
}

void
RangeBF::recursive_query(int dep, uint32_t hsh, int l, int r, vector<PDD>& ans)
{
	// printf("%d %d %d %d\n", dep, hsh, l, r);

	if (dep == beta || r - l <= 1)
	{
		ans.push_back(mp(unit_ts*l, unit_ts*r));
		return;
	}

	if (l > r)
	{
		printf("ERROR: query bound error.\n");
		exit(0);
	}

	int len = r - l;
	int pos = hsh % len + l;

	if (bf[pos] & 2)
		recursive_query(dep+1, hsh, l, pos+1, ans);
	if (bf[pos] & 1)
		recursive_query(dep+1, hsh, pos, r, ans);
}

#endif