-
Notifications
You must be signed in to change notification settings - Fork 0
/
ArrayHelpers.h
210 lines (189 loc) · 5.73 KB
/
ArrayHelpers.h
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
#ifndef ARRAY_HELPERS_H
#define ARRAY_HELPERS_H
#include <iostream>
#include <string>
#include <vector>
#include "Sortable.generated.h"
#include "StructHelpers.generated.h"
#include "DebugHelper.h"
template<typename ValueType>
void PrintArray(ValueType* source, int arraySize, std::string comment, uint64_t(*getKeyFunc)(ValueType&) = nullptr)
{
if (getKeyFunc == nullptr)
{
getKeyFunc = &GetKey<ValueType>;
}
printf("%s: ", comment.c_str());
for (int i = 0; i < arraySize; i += 1)
{
printf("%" PRIu64 ", ", getKeyFunc(source[i]));
}
printf("\n");
}
template <typename ValueType>
void PrintVector(std::vector<ValueType> source, std::string comment)
{
printf("%s: ", comment.c_str());
for (ValueType ele : source)
{
printf("%" PRIu64 ", ", GetKey(ele));
}
printf("\n");
}
template <typename ValueType>
void CopyArray(ValueType* source, std::vector<ValueType>& destination, int arraySize)
{
for (int i = 0; i < arraySize; i += 1)
{
destination.push_back(source[i]);
}
}
template <typename ValueType>
void CopyArray(ValueType* source, ValueType* destination, size_t arraySize)
{
for (int i = 0; i < arraySize; i += 1)
{
destination[i] = source[i];
}
}
template <typename TComparable>
bool IsSorted(TComparable* items, size_t arraySize)
{
for (int i = 0; i < arraySize - 1; i += 1)
{
if (__builtin_expect(items[i] > items[i + 1], 0))
{
return false;
}
}
return true;
}
static const uint64_t p = 4294967291; // largest prime < 2^32
static const uint64_t two_to_power_of_31_minus_1 = 2147483647;
template<typename TComparable>
uint64_t GetPermutationValue(TComparable* items, size_t arraySize, uint64_t(*value_func)(TComparable& item), uint64_t& iteration)
{
for (uint64_t iter = 1; iter < 100000; iter += 1)
{
//Keys are at most 2^32, so take a z that is guaranteed larger than 2^32
uint64_t z = ((uint64_t) items) + iter;
z = (z % two_to_power_of_31_minus_1) + two_to_power_of_31_minus_1;
uint64_t v = 1;
uint64_t diff;
for (size_t i = 0; i < arraySize; i += 1)
{
diff = (z - value_func(items[i])) % p;
v = (v * diff) % p;
}
if (v != 0)
{
iteration = iter;
return v;
}
}
return 0;
}
template <typename TComparable>
void PutPermutationValues(TComparable* items, size_t arraySize, uint64_t& keyValue, uint64_t& keyIter, uint64_t& refValue, uint64_t& refIter)
{
keyValue = GetPermutationValue(items, arraySize, &GetKey<TComparable>, keyIter);
refValue = GetPermutationValue(items, arraySize, &GetReference<TComparable>, refIter);
}
template<typename TComparable>
bool CheckPermutationValue(TComparable* items, size_t arraySize, uint64_t(*value_func)(TComparable& item), size_t iteration, uint64_t permutationValueBefore)
{
uint64_t z = ((uint64_t) items) + iteration;
z = (z % two_to_power_of_31_minus_1) + two_to_power_of_31_minus_1;
uint64_t w = 1;
uint64_t diff;
for (size_t i = 0; i < arraySize; i += 1)
{
diff = (z - value_func(items[i])) % p;
w = (w * diff) % p;
}
return permutationValueBefore == w;
}
template <typename TComparable>
bool IsSortedAndPermutation(TComparable* items, size_t arraySize, size_t keyIteration, uint64_t keyValue, size_t referenceIteration, uint64_t referenceValue)
{
return IsSorted(items, arraySize)
&& CheckPermutationValue(items, arraySize, &GetKey<TComparable>, keyIteration, keyValue)
&& CheckPermutationValue(items, arraySize, &GetReference<TComparable>, referenceIteration, referenceValue);
}
template <typename TComparable>
bool NotHasEqualNeighbour(TComparable* items, size_t arraySize)
{
for (int i = 0; i < arraySize - 1; i += 1)
{
if (__builtin_expect(items[i] == items[i + 1], 0))
{
return false;
}
}
return true;
}
template <typename TComparable>
bool NotHasEqualNeighbourAndPermutation(TComparable* items, size_t arraySize, size_t keyIteration, uint64_t keyValue, size_t referenceIteration, uint64_t referenceValue)
{
return NotHasEqualNeighbour(items, arraySize)
&& CheckPermutationValue(items, arraySize, &GetKey<TComparable>, keyIteration, keyValue)
&& CheckPermutationValue(items, arraySize, &GetReference<TComparable>, referenceIteration, referenceValue);
}
template <typename TComparable>
bool IsSameArray(TComparable* left, std::vector<TComparable> right, size_t arraySize)
{
for (int i = 0; i < arraySize; i += 1)
{
if (__builtin_expect(left[i] != right[i], 0))
{
return false;
}
}
return true;
}
template <typename TComparable>
bool IsSameArray(TComparable* left, TComparable* right, size_t arraySize)
{
for (int i = 0; i < arraySize; i += 1)
{
if (__builtin_expect(left[i] != right[i], 0))
{
return false;
}
}
return true;
}
template <typename TComparable>
bool IsSortedFake(TComparable* items, size_t arraySize, TComparable fakeCompareTo)
{
for (int i = 0; i < arraySize - 1; i += 1)
{
if (__builtin_expect(items[i] > fakeCompareTo, 0))
{
return false;
}
}
return true;
}
template <typename TEquatable>
bool IsPermutation(TEquatable* arr, TEquatable* reference, int arraySize)
{
for (int i = 0; i < arraySize; i += 1)
{
bool isIncluded = false;
for (int j = 0; j < arraySize; j += 1)
{
if (arr[i] == reference[j])
{
isIncluded = true;
break;
}
}
if (!isIncluded)
{
return false;
}
}
return true;
}
#endif