#include "Str.h"
#include "hash.h"
#include "op.h"
#include "venus.h"
#include "xmalloc.h"
#include "zz.h"

#include <stddef.h>
#include <stdio.h>
#include <string.h>

enum {MAGIC = 23};

struct sorted {
	size_t size, length;
	struct op **array;
};

static size_t hash(const void *p, size_t seed) {
	return St_hash(p, seed);
}

static int compar(const void *a, const void *b) {
	return St_cmp(a, b);
}

static void delk(void *k) {
	St_clear(k);
	xfree(k);
}

static void delv(void *v) {
	xfree(((struct sorted *)v)->array);
	xfree(v);
}

void ve_init(struct venus *v) {
	h_init(&v->table, hash, compar, delk, delv);
}

void ve_end(struct venus *v) {
	h_end(&v->table);
}

void ve_enter(struct venus *v, const String *s, struct op *o) {
	struct sorted *x;
	void *tmp;
	size_t a, z;

	if (h_get(&v->table, s, &tmp) == H_NOENT) {
		String *label;
		x = xmalloc(1, sizeof *x);
		x->array = xmalloc(x->size = MAGIC, sizeof *x->array);
		x->array[0] = o;
		x->length = 1;
		label = xmalloc(1, sizeof *label);
		St_init(label);
		St_cpy(label, s);
		h_put(&v->table, label, x, 1);
		return;
	}
	x = tmp;

	for (a = 0, z = x->length; a < z; ) {
		if (x->array[(a + z) / 2]->line < o->line) {
			a = (a + z) / 2 + 1u;
		} else if (x->array[(a + z) / 2]->line > o->line) {
			z = (a + z) / 2;
		} else {
			NOTREACHED;
		}
	}

	if (x->length >= x->size) {
		x->array = xrealloc(x->array, x->size *= 2);
	}
	memmove(x->array + a + 1u, x->array + a, x->length - a);
	x->array[a] = o;
	x->length++;
}

struct op *ve_findnext(struct venus *v, const String *s, size_t line) {
	struct sorted *x;
	void *tmp;
	size_t a, z;

	if (h_get(&v->table, s, &tmp) == H_NOENT) {
		return NULL;
	}
	x = tmp;

	for (a = 0, z = x->length; a < z; ) {
		if (x->array[(a + z) / 2]->line < line) {
			a = (a + z) / 2 + 1u;
		} else if (x->array[(a + z) / 2]->line > line) {
			z = (a + z) / 2;
		} else {
			a = (a + z) / 2 + 1u;
			break;
		}
	}

	return x->array[a % x->length];
}

struct op *ve_findprev(struct venus *v, const String *s, size_t line) {
	struct sorted *x;
	void *tmp;
	size_t a, z;

	if (h_get(&v->table, s, &tmp) == H_NOENT) {
		return NULL;
	}
	x = tmp;

	for (a = 0, z = x->length; a < z; ) {
		if (x->array[(a + z) / 2]->line < line) {
			a = (a + z) / 2 + 1u;
		} else if (x->array[(a + z) / 2]->line > line) {
			z = (a + z) / 2;
		} else {
			a = (a + z) / 2;
			break;
		}
	}
	a += x->length - 1u;
	return x->array[a % x->length];
}

const String *ve_label(struct venus *v, const struct op *op) {
	void *key, *value;

	h_reset(&v->table);
	while (h_nextkv(&v->table, &key, &value) == H_OK) {
		const struct sorted *x = value;
		size_t i;

		for (i = 0; i < x->length; ++i) {
			if (x->array[i] == op) {
				return key;
			}
		}
	}

	return NULL;
}