listfunc.c

Calc Software Package for Number Calc

 */
BOOL
listcmp(LIST *lp1, LIST *lp2)
{
	LISTELEM *e1, *e2;
	long count;

	if (lp1 == lp2)
		return FALSE;
	if (lp1->l_count != lp2->l_count)
		return TRUE;
	e1 = lp1->l_first;
	e2 = lp2->l_first;
	count = lp1->l_count;
	while (count-- > 0) {
		if (comparevalue(&e1->e_value, &e2->e_value))
			return TRUE;
		e1 = e1->e_next;
		e2 = e2->e_next;
	}
	return FALSE;
}


/*
 * Copy a list
 */
LIST *
listcopy(LIST *oldlp)
{
	LIST *lp;
	LISTELEM *oldep;

	lp = listalloc();
	oldep = oldlp->l_first;
	while (oldep) {
		insertlistlast(lp, &oldep->e_value);
		oldep = oldep->e_next;
	}
	return lp;
}


/*
 * Round elements of a list to a specified number of decimal digits
 */
LIST *
listround(LIST *oldlp, VALUE *v2, VALUE *v3)
{
	LIST *lp;
	LISTELEM *oldep, *ep, *eq;

	lp = listalloc();
	oldep = oldlp->l_first;
	lp->l_count = oldlp->l_count;
	if (oldep) {
		ep = elemalloc();
		lp->l_first = ep;
		for (;;) {
			roundvalue(&oldep->e_value, v2, v3, &ep->e_value);
			oldep = oldep->e_next;
			if (!oldep)
				break;
			eq = elemalloc();
			ep->e_next = eq;
			eq->e_prev = ep;
			ep = eq;
		}
		lp->l_last = ep;
	}
	return lp;
}


/*
 * Round elements of a list to a specified number of binary digits
 */
LIST *
listbround(LIST *oldlp, VALUE *v2, VALUE *v3)
{
	LIST *lp;
	LISTELEM *oldep, *ep, *eq;

	lp = listalloc();
	oldep = oldlp->l_first;
	lp->l_count = oldlp->l_count;
	if (oldep) {
		ep = elemalloc();
		lp->l_first = ep;
		for (;;) {
			broundvalue(&oldep->e_value, v2, v3, &ep->e_value);
			oldep = oldep->e_next;
			if (!oldep)
				break;
			eq = elemalloc();
			ep->e_next = eq;
			eq->e_prev = ep;
			ep = eq;
		}
		lp->l_last = ep;
	}
	return lp;
}


/*
 * Approximate a list by approximating elements by multiples of v2,
 * type of rounding determined by v3.
 */
LIST *
listappr(LIST *oldlp, VALUE *v2, VALUE *v3)
{
	LIST *lp;
	LISTELEM *oldep, *ep, *eq;

	lp = listalloc();
	oldep = oldlp->l_first;
	lp->l_count = oldlp->l_count;
	if (oldep) {
		ep = elemalloc();
		lp->l_first = ep;
		for (;;) {
			apprvalue(&oldep->e_value, v2, v3, &ep->e_value);
			oldep = oldep->e_next;
			if (!oldep)
				break;
			eq = elemalloc();
			ep->e_next = eq;
			eq->e_prev = ep;
			ep = eq;
		}
		lp->l_last = ep;
	}
	return lp;
}


/*
 * Construct a list whose elements are integer quotients of the elements
 * of a specified list by a specified number.
 */
LIST *
listquo(LIST *oldlp, VALUE *v2, VALUE *v3)
{
	LIST *lp;
	LISTELEM *oldep, *ep, *eq;

	lp = listalloc();
	oldep = oldlp->l_first;
	lp->l_count = oldlp->l_count;
	if (oldep) {
		ep = elemalloc();
		lp->l_first = ep;
		for (;;) {
			quovalue(&oldep->e_value, v2, v3, &ep->e_value);
			oldep = oldep->e_next;
			if (!oldep)
				break;
			eq = elemalloc();
			ep->e_next = eq;
			eq->e_prev = ep;
			ep = eq;
		}
		lp->l_last = ep;
	}
	return lp;
}


/*
 * Construct a list whose elements are the remainders after integral
 * division of the elements of a specified list by a specified number.
 */
LIST *
listmod(LIST *oldlp, VALUE *v2, VALUE *v3)
{
	LIST *lp;
	LISTELEM *oldep, *ep, *eq;

	lp = listalloc();
	oldep = oldlp->l_first;
	lp->l_count = oldlp->l_count;
	if (oldep) {
		ep = elemalloc();
		lp->l_first = ep;
		for (;;) {
			modvalue(&oldep->e_value, v2, v3, &ep->e_value);
			oldep = oldep->e_next;
			if (!oldep)
				break;
			eq = elemalloc();
			ep->e_next = eq;
			eq->e_prev = ep;
			ep = eq;
		}
		lp->l_last = ep;
	}
	return lp;
}


void
listreverse(LIST *lp)
{
	LISTELEM *e1, *e2;
	VALUE tmp;
	long s;

	s = lp->l_count/2;
	e1 = lp->l_first;
	e2 = lp->l_last;
	lp->l_cache = NULL;
	while (s-- > 0) {
		tmp = e1->e_value;
		e1->e_value = e2->e_value;
		e2->e_value = tmp;
		e1 = e1->e_next;
		e2 = e2->e_prev;
	}
}


void
listsort(LIST *lp)
{
	LISTELEM *start;
	LISTELEM *last, *a, *a1, *b, *next;
	LISTELEM *S[LONG_BITS+1];
	long len[LONG_BITS+1];
	long i, j, k;

	if (lp->l_count < 2)
		return;
	lp->l_cache = NULL;
	start = elemalloc();
	next = lp->l_first;
	last = start;
	start->e_next = next;
	for (k = 0; next && k < LONG_BITS; k++) {
		next->e_prev = last;
		last = next;
		S[k] = next;
		next = next->e_next;
		len[k] = 1;
		while (k > 0 && (!next || len[k] >= len[k - 1])) {/* merging */
			j = len[k];
			b = S[k--];
			i = len[k];
			a = S[k];
			a1 = b->e_prev;
			len[k] = i + j;
			if (precvalue(&b->e_value, &a->e_value)) {
				S[k] = b;
				a->e_prev->e_next = b;
				b->e_prev = a->e_prev;
				j--;
				while (j > 0) {
					b = b->e_next;
					if (!precvalue(&b->e_value,
						       &a->e_value))
						break;
					j--;
				}
				if (j == 0) {
					b->e_next = a;
					a->e_prev = b;
					last = a1;
					continue;
				}
				b->e_prev->e_next = a;
				a->e_prev = b->e_prev;
			}

			do {
				i--;
				while (i > 0) {
					a = a->e_next;
					if (precvalue(&b->e_value,
						      &a->e_value))
						break;
					i--;
				}
				if (i == 0)
					break;
				a->e_prev->e_next = b;
				b->e_prev = a->e_prev;
				j--;
				while (j > 0) {
					b = b->e_next;
					if (!precvalue(&b->e_value,
						       &a->e_value))
						break;
					j--;
				}
				if (j != 0) {
					b->e_prev->e_next = a;
					a->e_prev = b->e_prev;
				}
			} while (j != 0);

			if (i == 0) {
				a->e_next = b;
				b->e_prev = a;
			} else if (j == 0) {
				b->e_next = a;
				a->e_prev = b;
				last = a1;
			}
		}
	}
	if (k >= LONG_BITS) {
		/* this should never happen */
		math_error("impossible k overflow in listsort!");
		/*NOTREACHED*/
	}
	lp->l_first = start->e_next;
	lp->l_first->e_prev = NULL;
	lp->l_last = last;
	lp->l_last->e_next = NULL;
	elemfree(start);
}

void
listrandperm(LIST *lp)
{
	LISTELEM *ep, *eq;
	long i, s;
	VALUE val;

	s = lp->l_count;
	for (ep = lp->l_last; s > 1; ep = ep->e_prev) {
		i = irand(s--);
		if (i < s) {
			eq = listelement(lp, i);
			val = eq->e_value;
			eq->e_value = ep->e_value;
			ep->e_value = val;
		}
	}
}



/*
 * Allocate an element for a list.
 */
static LISTELEM *
elemalloc(void)
{
	LISTELEM *ep;

	ep = (LISTELEM *) malloc(sizeof(LISTELEM));
	if (ep == NULL) {
		math_error("Cannot allocate list element");
		/*NOTREACHED*/
	}
	ep->e_next = NULL;
	ep->e_prev = NULL;
	ep->e_value.v_type = V_NULL;
	ep->e_value.v_subtype = V_NOSUBTYPE;
	return ep;
}


/*
 * Free a list element, along with any contained value.
 */
static void
elemfree(LISTELEM *ep)
{
	if (ep->e_value.v_type != V_NULL)
		freevalue(&ep->e_value);
	free(ep);
}


/*
 * Allocate a new list header.
 */
LIST *
listalloc(void)
{
	register LIST *lp;

	lp = (LIST *) malloc(sizeof(LIST));
	if (lp == NULL) {
		math_error("Cannot allocate list header");
		/*NOTREACHED*/
	}
	lp->l_first = NULL;
	lp->l_last = NULL;
	lp->l_cache = NULL;
	lp->l_cacheindex = 0;
	lp->l_count = 0;
	return lp;
}


/*
 * Free a list header, along with all of its list elements.
 */
void
listfree(LIST *lp)
{
	register LISTELEM *ep;

	while (lp->l_count-- > 0) {
		ep = lp->l_first;
		lp->l_first = ep->e_next;
		elemfree(ep);
	}
	free(lp);
}


/*
 * Print out a list along with the specified number of its elements.
 * The elements are printed out in shortened form.
 */
void
listprint(LIST *lp, long max_print)
{
	long count;
	long index;
	LISTELEM *ep;

	if (max_print > lp->l_count)
		max_print = lp->l_count;
	count = 0;
	ep = lp->l_first;
	index = lp->l_count;
	while (index-- > 0) {
		if ((ep->e_value.v_type != V_NUM) ||
			(!qiszero(ep->e_value.v_num)))
				count++;
		ep = ep->e_next;
	}
	if (max_print > 0)
		math_str("\n");
	math_fmt("list (%ld element%s, %ld nonzero)", lp->l_count,
		((lp->l_count == 1) ? "" : "s"), count);
	if (max_print <= 0)
		return;

	/*
	 * Walk through the first few list elements, printing their
	 * value in short and unambiguous format.
	 */
	math_str(":\n");
	ep = lp->l_first;
	for (index = 0; index < max_print; index++) {
		math_fmt("\t[[%ld]] = ", index);
		printvalue(&ep->e_value, PRINT_SHORT | PRINT_UNAMBIG);
		math_str("\n");
		ep = ep->e_next;
	}
	if (max_print < lp->l_count)
		math_str("  ...\n");
}