341 lines
8.5 KiB
C
341 lines
8.5 KiB
C
|
|
#include <stdbool.h>
|
|
#include <stdio.h>
|
|
#include <assert.h>
|
|
|
|
#ifdef ZDEBUG
|
|
#define zprintf(fmt, ...) printf(fmt, ## __VA_ARGS__);
|
|
#else
|
|
#define zprintf(...) ;
|
|
#endif
|
|
|
|
#define N (256)
|
|
|
|
#define M (255)
|
|
|
|
struct sparselist {
|
|
int headtails[N], next[N], head;
|
|
|
|
bool in[N];
|
|
} b, c;
|
|
|
|
void init(struct sparselist* this)
|
|
{
|
|
this->head = -1;
|
|
|
|
for (int i = 0; i < N; i++)
|
|
{
|
|
this->headtails[i] = -1;
|
|
|
|
this->next[i] = -1;
|
|
|
|
this->in[i] = false;
|
|
}
|
|
}
|
|
|
|
void print(struct sparselist* this)
|
|
{
|
|
puts("print():");
|
|
|
|
for (int i = 0; i < N; i++)
|
|
{
|
|
if (this->headtails[i] != -1)
|
|
{
|
|
printf(" " "headtails[%3i (0b%08b)] = %i" "\n", i, i, this->headtails[i]);
|
|
}
|
|
}
|
|
|
|
printf("head = %i\n", this->head);
|
|
|
|
for (int index = this->head; index != -1; index = this->next[index])
|
|
{
|
|
printf(" " "index = %i\n", index);
|
|
}
|
|
}
|
|
|
|
void insert(struct sparselist* this, int index)
|
|
{
|
|
assert(!this->in[index]);
|
|
|
|
int head = index & 1 ? index & ~(index & -index) : index, prevhead = -1;
|
|
|
|
while (this->headtails[head] == -1 || index < this->headtails[head])
|
|
{
|
|
this->headtails[head] = index;
|
|
prevhead = head, head = head & ~(head & -head);
|
|
}
|
|
|
|
if (this->headtails[head] < index)
|
|
{
|
|
if (prevhead == -1)
|
|
{
|
|
assert(this->headtails[head] == head);
|
|
|
|
assert(this->in[head]);
|
|
|
|
this->next[head] = index;
|
|
}
|
|
else
|
|
{
|
|
int tophalftail = this->headtails[prevhead - 1];
|
|
|
|
assert(tophalftail != -1);
|
|
|
|
this->next[tophalftail] = index;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
this->head = index;
|
|
}
|
|
|
|
int n = ~index & M;
|
|
int tail = index & 1 ? index : index | (n & -n), prevtail = -1;
|
|
|
|
while (this->headtails[tail] == -1 || this->headtails[tail] < index)
|
|
{
|
|
this->headtails[tail] = index;
|
|
prevtail = tail, tail = tail | (n = ~tail & M, n & -n);
|
|
}
|
|
|
|
if (index < this->headtails[tail])
|
|
{
|
|
if (prevtail == -1)
|
|
{
|
|
assert(this->headtails[tail] == tail);
|
|
|
|
assert(this->in[tail]);
|
|
|
|
this->next[index] = tail;
|
|
}
|
|
else
|
|
{
|
|
int bottomhalfhead = this->headtails[prevtail + 1];
|
|
|
|
assert(bottomhalfhead != -1);
|
|
|
|
this->next[index] = bottomhalfhead;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
this->next[index] = -1;
|
|
}
|
|
|
|
this->in[index] = true;
|
|
}
|
|
|
|
int a = 17;
|
|
|
|
void search(
|
|
int mask,
|
|
int bheadindex, int btailindex,
|
|
int cheadindex, int ctailindex,
|
|
int calldepth)
|
|
{
|
|
zprintf("%*s" "quadrant_search():" "\n", calldepth++, "");
|
|
|
|
zprintf("%*s" "mask = 0b%05b" "\n", calldepth, "", mask);
|
|
|
|
zprintf("%*s" "bheadindex = %i" "\n", calldepth, "", bheadindex);
|
|
zprintf("%*s" "btailindex = %i" "\n", calldepth, "", btailindex);
|
|
|
|
zprintf("%*s" "cheadindex = %i" "\n", calldepth, "", cheadindex);
|
|
zprintf("%*s" "ctailindex = %i" "\n", calldepth, "", ctailindex);
|
|
|
|
if (mask)
|
|
{
|
|
// 0 ... (bsplit - 1) | bsplit ... (an - 1)
|
|
// --------------------- -------------------
|
|
// 0 | | |
|
|
// ... | first quadrant. | second quadrant |
|
|
// (csplit - 1) | | |
|
|
// --- ---------------------- -------------------
|
|
// csplit | | |
|
|
// ... | third quadrant | fourth quadrant |
|
|
// (cn - 1) | | |
|
|
// --- | | |
|
|
// ---------------------- -------------------
|
|
|
|
if (mask & a)
|
|
{
|
|
zprintf("%*s" "one case" "\n", calldepth, "");
|
|
|
|
// third quadrant
|
|
int q3_btailindex = btailindex & ~mask;
|
|
int q3_cheadindex = cheadindex | mask;
|
|
|
|
zprintf("%*s" "q3_btailindex = %i" "\n", calldepth, "", q3_btailindex);
|
|
zprintf("%*s" "q3_cheadindex = %i" "\n", calldepth, "", q3_cheadindex);
|
|
|
|
if (true
|
|
&& b.headtails[q3_btailindex] != -1
|
|
&& c.headtails[q3_cheadindex] != -1)
|
|
{
|
|
zprintf("%*s" "entering third quadrant." "\n", calldepth, "");
|
|
|
|
search(
|
|
mask >> 1,
|
|
bheadindex, q3_btailindex,
|
|
q3_cheadindex, ctailindex,
|
|
calldepth);
|
|
}
|
|
else
|
|
{
|
|
zprintf("%*s" "empty third quadrant." "\n", calldepth, "");
|
|
}
|
|
|
|
// fourth quadrant
|
|
int q4_bheadindex = bheadindex | mask;
|
|
int q4_cheadindex = cheadindex | mask;
|
|
|
|
if (true
|
|
&& b.headtails[q4_bheadindex] != -1
|
|
&& c.headtails[q4_cheadindex] != -1)
|
|
{
|
|
zprintf("%*s" "entering fourth quadrant." "\n", calldepth, "");
|
|
|
|
search(
|
|
mask >> 1,
|
|
q4_bheadindex, btailindex,
|
|
q4_cheadindex, ctailindex,
|
|
calldepth);
|
|
}
|
|
else
|
|
{
|
|
zprintf("%*s" "empty fourth quadrant." "\n", calldepth, "");
|
|
}
|
|
}
|
|
else
|
|
{
|
|
zprintf("%*s" "zero case" "\n", calldepth, "");
|
|
|
|
// first quadrant
|
|
int q1_btailindex = btailindex & ~mask;
|
|
int q1_ctailindex = ctailindex & ~mask;
|
|
|
|
zprintf("%*s" "q1_btailindex = %i" "\n", calldepth, "", q1_btailindex);
|
|
zprintf("%*s" "q1_ctailindex = %i" "\n", calldepth, "", q1_ctailindex);
|
|
|
|
if (true
|
|
&& b.headtails[q1_btailindex] != -1
|
|
&& c.headtails[q1_ctailindex] != -1)
|
|
{
|
|
zprintf("%*s" "entering first quadrant." "\n", calldepth, "");
|
|
|
|
search(
|
|
mask >> 1,
|
|
bheadindex, q1_btailindex,
|
|
cheadindex, q1_ctailindex,
|
|
calldepth);
|
|
}
|
|
else
|
|
{
|
|
zprintf("%*s" "empty first quadrant." "\n", calldepth, "");
|
|
}
|
|
|
|
// fourth quadrant
|
|
int q4_bheadindex = bheadindex | mask;
|
|
int q4_cheadindex = cheadindex | mask;
|
|
|
|
if (true
|
|
&& b.headtails[q4_bheadindex] != -1
|
|
&& c.headtails[q4_cheadindex] != -1)
|
|
{
|
|
zprintf("%*s" "entering fourth quadrant." "\n", calldepth, "");
|
|
|
|
search(
|
|
mask >> 1,
|
|
q4_bheadindex, btailindex,
|
|
q4_cheadindex, ctailindex,
|
|
calldepth);
|
|
}
|
|
else
|
|
{
|
|
zprintf("%*s" "empty fourth quadrant." "\n", calldepth, "");
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
assert(bheadindex == btailindex);
|
|
assert(cheadindex == ctailindex);
|
|
|
|
int be = b.headtails[bheadindex];
|
|
|
|
int ce = c.headtails[cheadindex];
|
|
|
|
if (be == bheadindex && ce == cheadindex && (a | be) == ce)
|
|
{
|
|
assert(b.in[be]);
|
|
assert(c.in[ce]);
|
|
|
|
printf("%2i (0b%05b) | %2i (0b%05b) == %2i (0b%05b)" "\n",
|
|
a, a, be, be, ce, ce);
|
|
}
|
|
}
|
|
|
|
calldepth--;
|
|
}
|
|
|
|
int main()
|
|
{
|
|
puts("hello, world!");
|
|
|
|
init(&b);
|
|
insert(&b, 10);
|
|
insert(&b, 11);
|
|
insert(&b, 14);
|
|
insert(&b, 19);
|
|
insert(&b, 20);
|
|
insert(&b, 23);
|
|
insert(&b, 26);
|
|
insert(&b, 29);
|
|
|
|
#ifdef ZDEBUG
|
|
print(&b);
|
|
#endif
|
|
|
|
init(&c);
|
|
insert(&c, 15);
|
|
insert(&c, 17);
|
|
insert(&c, 19);
|
|
insert(&c, 21);
|
|
insert(&c, 22);
|
|
insert(&c, 25);
|
|
insert(&c, 26);
|
|
insert(&c, 27);
|
|
insert(&c, 32);
|
|
insert(&c, 33);
|
|
insert(&c, 36);
|
|
insert(&c, 39);
|
|
insert(&c, 42);
|
|
insert(&c, 44);
|
|
insert(&c, 48);
|
|
insert(&c, 49);
|
|
|
|
#ifdef ZDEBUG
|
|
print(&c);
|
|
#endif
|
|
|
|
search(128, 0, 255, 0, 255, 0);
|
|
|
|
return 0;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|