float intersectionratio) {

if (sizeratio < 1)

throw runtime_error("sizeratio should be larger or equal to 1");

if (intersectionratio < 0)

throw runtime_error("intersectionratio should be positive");

if (intersectionratio > 1)

throw runtime_error("intersectionratio cannot be larger than 1");

const uint32_t maxlenth =

static_cast<uint32_t>(round(static_cast<float>(minlength) * sizeratio));

if (maxlenth > Max)

throw runtime_error(

"I can't generate an array so large in such a small range.");

if (maxlenth < minlength)

throw runtime_error("something went wrong, possibly an overflow.");

// we basically assume that, if we do nothing, intersections are very small

const uint32_t intersize = static_cast<uint32_t>(

round(static_cast<float>(minlength) * intersectionratio));

vector<uint32_t> inter = gen.generate(intersize, Max);

vector<uint32_t> smallest =

unite(gen.generate(static_cast<uint32_t>(minlength - inter.size()), Max),

inter);

vector<uint32_t> largest = unite(

gen.generate(static_cast<uint32_t>(maxlenth - inter.size()), Max), inter);

vector<uint32_t> intersection = intersect(smallest, largest);

if (largest.size() > smallest.size())

return pair<vector<uint32_t>, vector<uint32_t>>(smallest, largest);

return pair<vector<uint32_t>, vector<uint32_t>>(largest, smallest);

const size_t /*Rlength*/) {

uint16_t high = 0;

int partition_length = 0;

size_t partition_size_position = 1;

size_t counter = 0;

size_t p = 0;

if (p < s_a) {

uint16_t chigh = _high16(A[p]); // upper dword

uint16_t clow = _low16(A[p]); // lower dword

if (chigh == 0) {

R[counter++] = chigh; // partition prefix

R[counter++] = 0; // reserve place for partition size

R[counter++] = clow; // write the first element

partition_length = 1; // reset counters

high = chigh;

++p;

}

}

for (; p < s_a; p++) {

uint16_t chigh = _high16(A[p]); // upper dword

uint16_t clow = _low16(A[p]); // lower dword

if (chigh == high && p != 0) { // add element to the current partition

R[counter++] = clow;

partition_length++;

} else { // start new partition

R[counter++] = chigh; // partition prefix

R[counter++] = 0; // reserve place for partition size

R[counter++] = clow; // write the first element

R[partition_size_position] =

static_cast<uint16_t>(partition_length - 1); // store "-1"

partition_length = 1; // reset counters

partition_size_position = counter - 2;

high = chigh;

}

}

R[partition_size_position] = static_cast<uint16_t>(partition_length - 1);

return counter;

const size_t s_a, const size_t s_b,

uint16_t *C) {

size_t count = 0;

size_t i_a = 0, i_b = 0;

const size_t st_a = (s_a / 8) * 8;

const size_t st_b = (s_b / 8) * 8;

__m128i v_a, v_b;

if ((i_a < st_a) and (i_b < st_b)) {

v_a = _mm_loadu_si128((const __m128i *)&A[i_a]);

v_b = _mm_loadu_si128((const __m128i *)&B[i_b]);

while (true) {

const __m128i res_v = _mm_cmpestrm(

v_b, 16, v_a, 16,

_SIDD_UWORD_OPS | _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK);

const int r = _mm_extract_epi32(res_v, 0);

__m128i p = _mm_shuffle_epi8(v_a, shuffle_mask16[r]);

_mm_storeu_si128((__m128i *)&C[count], p);

count += _mm_popcnt_u32(r);

const uint16_t a_max = A[i_a + 7];

const uint16_t b_max = B[i_b + 7];

if (a_max <= b_max) {

i_a += 8;

if (i_a == st_a)

break;

v_a = _mm_loadu_si128((const __m128i *)&A[i_a]);

}

if (b_max <= a_max) {

i_b += 8;

if (i_b == st_b)

break;

v_b = _mm_loadu_si128((const __m128i *)&B[i_b]);

}

}

}

// intersect the tail using scalar intersection

while (i_a < s_a && i_b < s_b) {

if (A[i_a] < B[i_b]) {

i_a++;

} else if (B[i_b] < A[i_a]) {

i_b++;

} else {

C[count] = A[i_a];

count++;

i_a++;

i_b++;

}

}

return count;

const size_t s_a, const size_t s_b,

uint16_t *C) {

size_t count = 0;

size_t i_a = 0, i_b = 0;

const size_t st_a = (s_a / 8) * 8;

const size_t st_b = (s_b / 8) * 8;

__m128i v_a, v_b;

if ((i_a < st_a) and (i_b < st_b)) {

v_a = _mm_loadu_si128((const __m128i *)&A[i_a]);

v_b = _mm_loadu_si128((const __m128i *)&B[i_b]);

while ((A[i_a] == 0) or (B[i_b] == 0)) {

const __m128i res_v =

_mm_cmpestrm(v_b, 8, v_a, 8,

_SIDD_UWORD_OPS | _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK);

const int r = _mm_extract_epi32(res_v, 0);

__m128i p = _mm_shuffle_epi8(v_a, shuffle_mask16[r]);

_mm_storeu_si128((__m128i *)&C[count], p);

count += _mm_popcnt_u32(r);

const uint16_t a_max = A[i_a + 7];

const uint16_t b_max = B[i_b + 7];

if (a_max <= b_max) {

i_a += 8;

if (i_a == st_a)

break;

v_a = _mm_loadu_si128((const __m128i *)&A[i_a]);

}

if (b_max <= a_max) {

i_b += 8;

if (i_b == st_b)

break;

v_b = _mm_loadu_si128((const __m128i *)&B[i_b]);

}

}

if ((i_a < st_a) and (i_b < st_b))

while (true) {

const __m128i res_v = _mm_cmpistrm(

v_b, v_a, _SIDD_UWORD_OPS | _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK);

const int r = _mm_extract_epi32(res_v, 0);

__m128i p = _mm_shuffle_epi8(v_a, shuffle_mask16[r]);

_mm_storeu_si128((__m128i *)&C[count], p);

count += _mm_popcnt_u32(r);

const uint16_t a_max = A[i_a + 7];

const uint16_t b_max = B[i_b + 7];

if (a_max <= b_max) {

i_a += 8;

if (i_a == st_a)

break;

v_a = _mm_loadu_si128((const __m128i *)&A[i_a]);

}

if (b_max <= a_max) {

i_b += 8;

if (i_b == st_b)

break;

v_b = _mm_loadu_si128((const __m128i *)&B[i_b]);

}

}

}

// intersect the tail using scalar intersection

while (i_a < s_a && i_b < s_b) {

if (A[i_a] < B[i_b]) {

i_a++;

} else if (B[i_b] < A[i_a]) {

i_b++;

} else {

C[count] = A[i_a];

count++;

i_a++;

i_b++;

}

}

return count;

const size_t s_a, const size_t s_b,

uint16_t *C) {

// intersect the tail using scalar intersection

size_t count = 0, i_a = 0, i_b = 0;

while (i_a < s_a && i_b < s_b) {

if (A[i_a] < B[i_b]) {

i_a++;

} else if (B[i_b] < A[i_a]) {

i_b++;

} else {

C[count] = A[i_a];

count++;

i_a++;

i_b++;

}

}

return count;

const uint16_t *B, const size_t s_b,

uint16_t *C) {

size_t i_a = 0, i_b = 0;

size_t counter = 0;

while (i_a < s_a && i_b < s_b) {

if (A[i_a] < B[i_b]) {

do {

i_a += static_cast<size_t>(A[i_a + 1]) + 2 + 1;

if (i_a >= s_a)

goto end;

} while (A[i_a] < B[i_b]);

}

if (B[i_b] < A[i_a]) {

do {

i_b += static_cast<size_t>(B[i_b + 1]) + 2 + 1;

if (i_b >= s_b)

goto end;

} while (B[i_b] < A[i_a]);

} else {