/* Copyright 1989, 1990 by James Aspnes, David Applegate, and Bennet Yee */
/* See the file COPYING for distribution information */
#include "alist.h"

#define alist_space_needed(size) (sizeof(datum) * 2 * (size + 1))

#define shrink_threshold(size) ((size) >> 3) /* below this you shrink */
#define grow_threshold(size) (3 * ((size) >> 2)) /* above this you grow */

#define resize_leeway(count) ((count) << 1) /* how much space to guarantee */

/* we don't worry about running off the end of this */
/* because malloc would blow out long before */
static unsigned long nice_primes[] = {
    3,
    7,
    13,
    31,
    61,
    127,
    251,
    509,
    1021,
    2039,
    4093,
    8191,
    16381,
    32749,
    65521,
    131071,
    262139,
    524287,
    1048573,
    2097143,
    4194301,
    8388593,
    16777213,
    33554393,
    67108859,
    134217689,
    268435399,
    536870909,
    1073741789,
    2147483647,
    4294967291 };

#define HASH(a, key) hash_range(alist_size(a), (key))
#define NEXT(a, key) next_probe(alist_size(a), key)
#define BETWEEN(lb, c, ub) \
    (((lb) <= (ub)) ? ((lb) <= (c) && (c) <= (ub)) \
     : ((c) >= (lb) || (c) <= (ub)))

int assoc(alist a, datum key, datum *value)
{
    unsigned long p;

    if(a == 0) return 0;

    for(p = HASH(a, key);
	alist_key(a, p) != NOTHING && alist_key(a, p) != key;
	p = NEXT(a, p));
    if(alist_key(a, p)) {
	if(value) *value = alist_value(a, p);
	return 1;
    } else {
	return 0;
    }
}


/* this just shoves it in without checking the count */
static void add_assoc1(alist a, datum key, datum value)
{
    unsigned long p;

    /* find an empty slot */
    for(p = HASH(a, key);
	alist_key(a, p) != NOTHING;
	p = NEXT(a, p));

    alist_key(a, p) = key;
    alist_value(a, p) = value;
    alist_count(a)++;
}

/* resizes an alist to fit */
static alist resize_alist(alist a)
{
    unsigned long i;
    alist a1;

    if(a) {
	for(i = 0; nice_primes[i] <= resize_leeway(alist_count(a)); i++);
    } else {
	i = 0;
    }

    /* nice_primes[i] is the new size */
    a1 = (alist) malloc(alist_space_needed(nice_primes[i]));
    alist_size(a1) = nice_primes[i];
    alist_count(a1) = 0;

    /* clear it out */
    for(i = 0; i < alist_size(a1); i++) {
	alist_key(a1, i) = NOTHING;
    }

    /* throw in everything from the old one */
    if(a) {
	for(i = 0; i < alist_size(a); i++) {
	    if(alist_key(a, i) != NOTHING) {
		add_assoc1(a1, alist_key(a, i), alist_value(a, i));
	    }
	}
	free((void *) a);
    }

    return a1;
}

/* adds an element to an alist */
alist add_assoc(alist a, datum key, datum value)
{
    if(a == 0 || alist_count(a) >= grow_threshold(alist_size(a))) {
	a = resize_alist(a);
    }

    add_assoc1(a, key, value);

    return a;
}

/* deletes an element from an alist */
/* Don't ask me how it works, read Knuth vol. 2 p. 527 (Algorithm R) */
alist del_assoc(alist a, datum key, datum value)
{
    unsigned long p;
    unsigned long ub;

    /* skip until we get it */
    for(p = HASH(a, key);
	alist_key(a, p) != NOTHING
	&& (alist_key(a, p) != key || alist_value(a, p) != value);
	p = NEXT(a, p));

    if(alist_key(a, p) == NOTHING) {
	return a;	/* not found */
    } else if(--alist_count(a) == 0) {
	/* completely empty, nuke it */
	free((void *) a);
	return 0;
    } else {
	/* scan for a replacement */
	for(;;) {
	    alist_key(a, p) = NOTHING;	/* nuke this place */
	
	    /* otherwise, look for something we can move up into p */
	    ub = p;

	    for(;;) {
		p = NEXT(a, p);
		if(alist_key(a, p) == NOTHING) {
		    /* hit the end of the block */
		    /* check for shrinkage */
		    if(alist_count(a) <= shrink_threshold(alist_size(a))) {
			a = resize_alist(a);
		    }
		    return a;
		} else if(!BETWEEN(p,
				   HASH(a, alist_key(a, p)),
				   NEXT(a, ub))) {
		    /* we've got something we can move up */
		    alist_key(a, ub) = alist_key(a, p);
		    alist_value(a, ub) = alist_value(a, p);
		    break;	/* have to fill this slot now */
		}
	    }
	}
    }
}

/* delete all occurences of key */
alist del_assocs(alist a, datum key)
{
    datum value;

    /* we'll be stupid about it, since a smart version would be painful */
    while(assoc(a, key, &value)) a = del_assoc(a, key, value);

    return a;
}

/* sets first instance of key to point to value */
/* or adds (key, value) if key isn't there already */
alist set_assoc(alist a, datum key, datum value)
{
    unsigned long p;

    if(a) {
	for(p = HASH(a,  key);
	    alist_key(a, p) != NOTHING;
	    p = NEXT(a, p)) {
	    if(alist_key(a, p) == key) {
		/* got it */
		alist_value(a, p) = value;
		return a;
	    }
	}
    }

    /* not there */
    return add_assoc(a, key, value);
}

alist copy_alist(alist a)
{
    alist a1;

    if(a == 0) return 0;	/* empty */
    
    a1 = (alist) malloc(alist_space_needed(alist_size(a)));
    bcopy((void *) a, (void *) a1, alist_space_needed(alist_size(a)));
    
    return a1;
}

datum alist_next(alist a, alist_iterator *i, datum *value)
{
    datum key;

    if(a) {
	for(i->pos++; i->pos < alist_size(a); i->pos++) {
	    if((key = alist_key(a, i->pos)) != NOTHING) {
		if(value) *value = alist_value(a, i->pos);
		return key;
	    }
	}
    }

    if(value) *value = NOTHING;
    return NOTHING;
}

datum alist_first(alist a, alist_iterator *i, datum *value)
{
    i->pos = -1;
    return alist_next(a, i, value);
}

int alist_next_match(alist a, alist_iterator *i, datum *value)
{
    datum oldpos;
    datum key;

    if(a) {
	while((key = alist_key(a, i->pos)) != NOTHING) {
	    oldpos = i->pos;
	    i->pos = next_probe(alist_size(a), i->pos);

	    if(key == i->key) {
		if(value) *value = alist_value(a, oldpos);
		return 1;
	    }
	    /* else continue */
	}
    }
    return 0;
}

int alist_first_match(alist a, alist_iterator *i, datum *value, datum key)
{
    if(a) {
	i->key = key;
	i->pos = hash_range(alist_size(a), key);
	return alist_next_match(a, i, value);
    }
    return 0;
}

int alist_member(alist a, datum key, datum value)
{
    datum v;

    FOREACH_MATCH(a, key, v) {
	if(v == value) return 1;
    } END_FOREACH;

    return 0;
}