/*
 *	Characters maps
 *	Copyright
 *		(C) 1992 Joseph H. Allen
 *
 *	This file is part of JOE (Joe's Own Editor)
 */

#include "types.h"

struct interval_list *mkinterval(struct interval_list *next, int first, int last, void *map)
{
	struct interval_list *interval_list = (struct interval_list *)joe_malloc(SIZEOF(struct interval_list));
	interval_list->next = next;
	interval_list->interval.first = first;
	interval_list->interval.last = last;
	interval_list->map = map;
	return interval_list;
}

void rminterval(struct interval_list *interval_list)
{
	while (interval_list) {
		struct interval_list *n = interval_list->next;
		free(interval_list);
		interval_list = n;
	}
}

/* Add a single character range to an interval list */

struct interval_list *interval_add(struct interval_list *interval_list, int first, int last, void *map)
{
	struct interval_list *e, **p;
	for (p = &interval_list; *p;) {
		e = *p;
		if (first > e->interval.last + 1 || (first > e->interval.last && (map != e->map))) {
			/* e is below new range, skip it */
			p = &e->next;
		} else if (e->interval.first > last + 1 || (e->interval.first > last && (map != e->map))) {
			/* e is fully above new range, so insert new one here */
			break;
		} else if (e->map == map) {
			/* merge e into new */
			if (e->interval.first <= first) {
				if (e->interval.last >= last) { /* && e->interval.first <= first */
					/* Existing covers new: we're done */
					return interval_list;
				} else { /* e->interval.last < last && e->interval.first <= first */
					/* Enlarge new, delete existing */
					first = e->interval.first;
					*p = e->next;
					e->next = 0;
					rminterval(e);
				}
			} else { /* e->interval.first > first */
				if (e->interval.last <= last) { /* && e->interval.first > first */
					/* New fully covers existing, delete existing */
					*p = e->next;
					e->next = 0;
					rminterval(e);
				} else { /* e->interval.last > last && e->interval.first > first */
					/* Extend existing */
					e->interval.first = first;
					return interval_list;
				}
			}
		} else {
			/* replace e with new */
			if (e->interval.first < first) {
				if (e->interval.last <= last) { /* && e->interval.first < first */
					/* Top part of existing get cut-off by new */
					e->interval.last = first - 1;
				} else { /* e->interval.last > last && e->interval.first < first */
					int org = e->interval.last;
					void *orgmap = e->map;
					e->interval.last = first - 1;
					p = &e->next;
					*p = mkinterval(*p, first, last, map);
					p = &(*p)->next;
					*p = mkinterval(*p, last + 1, org, orgmap);
					return interval_list;
				}
			} else { /* e->interval.first >= first */
				if (e->interval.last <= last) { /* && e->interval.first >= first */
					/* Delete existing */
					*p = e->next;
					e->next = 0;
					rminterval(e);
				} else { /* e->interval.last > last && e->interval.first >= first */
					e->interval.first = last + 1;
					break;
				}
			}
		}
	}
	*p = mkinterval(*p, first, last, map);
	return interval_list;
}

/* Add a list of intervals (typically representing a character class) to an interval list */

struct interval_list *interval_set(struct interval_list *interval_list, struct interval *list, int size, void *map)
{
	int x;
	for (x = 0; x != size; ++x)
		interval_list = interval_add(interval_list, list[x].first, list[x].last, map);
	return interval_list;
}

void *interval_lookup(struct interval_list *list, void *dflt, int item)
{
	while (list) {
		if (item >= list->interval.first && item <= list->interval.last)
			return list->map;
		list = list->next;
	}
	return dflt;
}

/* Build a cmap from an interval list */

void cmap_build(struct cmap *cmap, struct interval_list *list, void *dflt_map)
{
	struct interval_list *l;
	int x;
	/* Record default */
	cmap->dflt_map = dflt_map;
	for (x = 0; x != 128; ++x)
		cmap->direct_map[x] = dflt_map;
	/* Fill in direct map */
	for (l = list; l; l = l->next)
		if (l->interval.first >= 128)
			break;
		else {
			int ch;
			for (ch = l->interval.first; ch < 128 && ch <= l->interval.last; ++ch)
				cmap->direct_map[ch] = l->map;
		}
	/* Skip over list items which are wholly in the direct map */
	while (list && list->interval.last < 128)
		 list = list -> next;
	/* Calculate size of array */
	cmap->size = 0;
	for (l = list; l; l = l->next)
		++cmap->size;
	if (cmap->size) {
		/* Allocate and populate array */
		cmap->range_map = (struct interval_map *)joe_malloc(SIZEOF(struct interval_map) * cmap->size);
		x = 0;
		for (l = list; l; l = l->next) {
			cmap->range_map[x].interval.first = l->interval.first;
			cmap->range_map[x].interval.last = l->interval.last;
			cmap->range_map[x].map = l->map;
			if (cmap->range_map[x].interval.first < 128)
				cmap->range_map[x].interval.first = 128;
			++x;
		}
	} else
		cmap->range_map = 0;
}

/* Clear cmap, free space */

void clr_cmap(struct cmap *cmap)
{
	if (cmap->range_map)
		joe_free(cmap->range_map);
	cmap->range_map = 0;
	cmap->size = 0;
}

/* Lookup a character in a cmap, return its assigned mapping */

void *cmap_lookup(struct cmap *cmap, int ch)
{
	if (ch < 128)
		return cmap->direct_map[ch];
	if (cmap->size) {
		ptrdiff_t min = 0;
		ptrdiff_t mid;
		ptrdiff_t max = cmap->size - 1;
		if (ch < cmap->range_map[min].interval.first || ch > cmap->range_map[max].interval.last)
			goto no_match;
		while (max >= min) {
			mid = (min + max) / 2;
			if (ch > cmap->range_map[mid].interval.last)
				min = mid + 1;
			else if (ch < cmap->range_map[mid].interval.first)
				max = mid - 1;
			else
				return cmap->range_map[mid].map;
		}
	}
	no_match:
	return cmap->dflt_map;
}

#ifdef junk
struct slist {
	struct slist *next;
	char *s;
} *slist;

char *find(char *s)
{
	struct slist *l;
	for (l = slist; l; l = l->next)
		if (!zcmp(l->s, s))
			return l->s;
	l = (struct slist *)joe_malloc(SIZEOF(struct slist));
	l->next = slist;
	slist = l;
	l->s = zdup(s);
	return l->s;
}

int main(int argc, char *argv)
{
	char buf[100];
	struct interval_list *list = 0;
	while (gets(buf)) {
		if (buf[0] == 'a') {
			int first, last;
			int map;
			sscanf(buf + 1," %d %d %d",&first,&last,&map);
			printf("a %d %d %d\n", first, last, map);
			list = interval_add(list, first, last, map);
		} else if (buf[0] == 's') {
			struct interval_list *l;
			for (l = list; l; l = l->next)
				printf("%d %d %d\n",l->interval.first,l->interval.last,l->map);
		}
	}
}
#endif

/* Radix tree maps */

void *rtree_lookup(struct Rtree *r, int ch)
{
	int a = (TOPMASK & (ch >> TOPSHIFT));
	int b = (SECONDMASK & (ch >> SECONDSHIFT));
	int c = (THIRDMASK & (ch >> THIRDSHIFT));
	int d = (LEAFMASK & (ch >> LEAFSHIFT));
	if (a >= TOPSIZE)
		return NULL;
	if (a || b) { /* Full lookup for character >= 512 */
		int idx = r->top.entry[a];
		if (idx != -1) {
			idx = r->second.table.b[idx].entry[b];
			if (idx != -1) {
				idx = r->third.table.c[idx].entry[c];
				if (idx != -1)
					return r->leaf.table.d[idx].entry[d];
			}
		}
	} else { /* Quick lookup for character < 512 */
		int idx = r->mid.entry[c];
		if (idx != -1)
			return r->leaf.table.d[idx].entry[d];
	}
	return NULL;
}

void *rtree_lookup_unopt(struct Rtree *r, int ch)
{
	int a = (TOPMASK & (ch >> TOPSHIFT));
	int b = (SECONDMASK & (ch >> SECONDSHIFT));
	int c = (THIRDMASK & (ch >> THIRDSHIFT));
	int d = (LEAFMASK & (ch >> LEAFSHIFT));
	int idx;
	if (a >= TOPSIZE)
		return NULL;
	idx = r->top.entry[a];
	if (idx != -1) {
		idx = r->second.table.b[idx].entry[b];
		if (idx != -1) {
			idx = r->third.table.c[idx].entry[c];
			if (idx != -1)
				return r->leaf.table.d[idx].entry[d];
		}
	}
	return NULL;
}

void rtree_init(struct Rtree *r)
{
	int x;
	for (x = 0; x != TOPSIZE; ++x)
		r->top.entry[x] = -1;

	r->second.alloc = 0;
	r->second.size = 1;
	r->second.table.b = (struct Mid *)joe_malloc(r->second.size * SIZEOF(struct Mid));

	r->third.alloc = 0;
	r->third.size = 1;
	r->third.table.c = (struct Mid *)joe_malloc(r->third.size * SIZEOF(struct Mid));

	r->leaf.alloc = 0;
	r->leaf.size = 1;
	r->leaf.table.d = (struct Leaf *)joe_malloc(r->leaf.size * SIZEOF(struct Leaf));
}

void rtree_clr(struct Rtree *r)
{
	joe_free(r->second.table.b);
	joe_free(r->third.table.c);
	joe_free(r->leaf.table.d);
}

static int rtree_alloc(struct Level *l, int levelno)
{
	int x;
	if (l->alloc == l->size) {
		l->size *= 2;
		switch (levelno) {
			case 1: {
				l->table.b = (struct Mid *)joe_realloc(l->table.b, l->size * SIZEOF(struct Mid));
				break;
			} case 2: {
				l->table.c = (struct Mid *)joe_realloc(l->table.c, l->size * SIZEOF(struct Mid));
				break;
			} case 3: {
				l->table.d = (struct Leaf *)joe_realloc(l->table.d, l->size * SIZEOF(struct Leaf));
				break;
			}
		}
	}
	switch (levelno) {
		case 1: {
			for (x = 0; x != SECONDSIZE; ++x)
				l->table.b[l->alloc].entry[x] = -1;
			break;
		} case 2: {
			for (x = 0; x != THIRDSIZE; ++x)
				l->table.c[l->alloc].entry[x] = -1;
			break;
		} case 3: {
			for (x = 0; x != LEAFSIZE; ++x)
				l->table.d[l->alloc].entry[x] = NULL;
			break;
		}
	}
	return l->alloc++;
}

void rtree_add(struct Rtree *r, int ch, int che, void *map)
{
	int a = (TOPMASK & (ch >> TOPSHIFT));
	int b = (THIRDMASK & (ch >> SECONDSHIFT));
	int c = (SECONDMASK & (ch >> THIRDSHIFT));
	int d = (LEAFMASK & (ch >> LEAFSHIFT));

	int ib;
	int ic;
	int id;

	while (ch <= che) {

		if (a >= TOPSIZE)
			return;

		ib = r->top.entry[a];
		if (ib == -1) {
			r->top.entry[a] = ib = rtree_alloc(&r->second, 1);
		}

		while (ch <= che) {
			ic = r->second.table.b[ib].entry[b];
			if (ic == -1) {
				r->second.table.b[ib].entry[b] = ic = rtree_alloc(&r->third, 2);
			}

			while (ch <= che) {
				id = r->third.table.c[ic].entry[c];
				if (id == -1) {
					r->third.table.c[ic].entry[c] = id = rtree_alloc(&r->leaf, 3);
				}

				while (ch <= che) {
					r->leaf.table.d[id].entry[d] = map;
					++ch;
					if (++d == LEAFSIZE) {
						d = 0;
						break;
					}
				}
				if (++c == THIRDSIZE) {
					c = 0;
					break;
				}
			}
			if (++b == SECONDSIZE) {
				b = 0;
				break;
			}
		}
		++a;
	}
}

/* Optimize radix tree: de-duplicate leaf nodes and setup mid */

struct rhentry {
	struct rhentry *next;
	struct Leaf *leaf;
	int idx;
};

static ptrdiff_t rhhash(struct Leaf *l)
{
	ptrdiff_t hval = 0;
	int x;
	for (x = 0; x != LEAFSIZE; ++x)
		hval = (hval << 4) + (hval >> 28) + (ptrdiff_t)l->entry[x];
	return hval;
		
}

void rtree_opt(struct Rtree *r)
{
	int idx;
	int x;
	int rhsize;
	struct rhentry **rhtable;
	int *equiv;
	int *repl;
	int dupcount;
	int newalloc;
	struct Leaf *l;

	/* De-duplicate leaf nodes (it's not worth bothering with interior nodes) */

	equiv = joe_malloc(SIZEOF(int) * r->leaf.alloc);
	repl = joe_malloc(SIZEOF(int) * r->leaf.alloc);

	/* Create hash table index of all the leaf nodes */
	dupcount = 0;
	rhsize = 1024;
	rhtable = joe_calloc(SIZEOF(struct rhentry *), rhsize);
	for (x = 0; x != r->leaf.alloc; ++x) {
		struct rhentry *rh;
		idx = ((rhsize - 1) & rhhash(r->leaf.table.d + x));
		/* Already exists? */
		for (rh = rhtable[idx]; rh; rh = rh->next)
			if (!memcmp(rh->leaf, r->leaf.table.d + x, SIZEOF(struct Leaf)))
				break;
		if (rh) {
			equiv[x] = rh->idx;
			++dupcount;
		} else {
			equiv[x] = -1;
			rh = (struct rhentry *)joe_malloc(SIZEOF(struct rhentry));
			rh->next = rhtable[idx];
			rh->idx = x;
			rh->leaf = r->leaf.table.d + x;
			rhtable[idx] = rh;
		}
	}
	/* Free hash table */
	for (x = 0; x != 1024; ++x) {
		struct rhentry *rh, *nh;
		for (rh = rhtable[x]; rh; rh = nh) {
			nh = rh->next;
			joe_free(rh);
		}
	}
	joe_free(rhtable);

	/* Create new leaf table */
	newalloc = r->leaf.alloc - dupcount;
	l = joe_malloc(SIZEOF(struct Leaf) * newalloc);

	/* Copy entries */
	idx = 0;
	for (x = 0; x != r->leaf.alloc; ++x)
		if (equiv[x] == -1) {
			mcpy(l + idx, r->leaf.table.d + x, sizeof(struct Leaf));
			repl[x] = idx;
			++idx;
		}
	for (x = 0; x != r->leaf.alloc; ++x)
		if (equiv[x] != -1) {
			repl[x] = repl[equiv[x]];
		}

	/* Install new table */
	joe_free(r->leaf.table.d);
	r->leaf.table.d = l;
	r->leaf.alloc = newalloc;
	r->leaf.size = newalloc;

	/* Remap third level */
	for (x = 0; x != r->third.alloc; ++x)
		for (idx = 0; idx != THIRDSIZE; ++idx)
			if (r->third.table.c[x].entry[idx] != -1)
				r->third.table.c[x].entry[idx] = repl[r->third.table.c[x].entry[idx]];

	joe_free(equiv);
	joe_free(repl);

	/* Set up mid table */
	for (x = 0; x != THIRDSIZE; ++x)
		r->mid.entry[x] = -1;
	idx = r->top.entry[0];
	if (idx != -1) {
		idx = r->second.table.b[idx].entry[0];
		if (idx != -1) {
			mcpy(r->mid.entry, r->third.table.c[idx].entry, SIZEOF(r->mid.entry));
		}
	}
}

void rtree_set(struct Rtree *r, struct interval *array, ptrdiff_t len, void *map)
{
	ptrdiff_t y;
	for (y = 0; y != len; ++y) {
		rtree_add(r, array[y].first, array[y].last, map);
/*
		int x;
		for (x = array[y].first; x <= array[y].last; ++x)
			rtree_add(r, x, map);
*/
	}
}