/* %Z%%M% %I% %E% */

/*
 * Copyright (c) 1990-2005 by Wayne C. Gramlich.
 * All rights reserved.
 */

/* Implementation of dynamic array data abstraction: */

#ifndef ERROR_EXPORTS_H
#include "error_exports.h"
#endif

#ifndef FILE_EXPORTS_H
#include "file_exports.h"
#endif

#ifndef HEAP_EXPORTS_H
#include "heap_exports.h"
#endif

#ifndef LIBC_EXPORTS_H
#include "libc_exports.h"
#endif

#ifndef UNIX_MEMORY_H
#include "unix_memory.h"
#endif

#ifndef VECTOR_DEFS_H
#include "vector_defs.h"
#endif

extern void vector_limit_set(Vektor, int);

/* LINTLIBRARY */

/*
 * vector_append(vector, datum)
 *	This will append "datum" to the end of "vector".  O(k)
 */
void
vector_append(
	Vektor		vector,
	Vector_datum	datum)
{
	int		limit;

	limit = vector->limit;
	if (vector->size == limit) {
		vector_limit_set(vector, (limit == 0) ? 1 : limit << 1);
	}
	vector->data[vector->size++] = datum;
}

/*
 * vector_bounds_error(vector, index)
 *	This routine will print a bounds error for "vector" and "index".
 */
void
vector_bounds_error(
	Vektor		vector,
	Vector_index	index)
{
	error_fatal("vector 0x%x: Bounds error (%d not in [0:%d])",
		    vector, index, vector->size - 1);
}		

/*
 * vector_copy(old_vector)
 *	This routine will return a duplicate copy of "old_vector". O(n)
 */
Vektor
vector_copy(
	Vektor		old_vector)
{
	Vektor		new_vector;
	Heap		heap;

	heap = heap_standard_create();
	new_vector = vector_create(heap);
	vector_limit_set(new_vector, old_vector->size);
	(void)memcpy((Str)new_vector->data, (Str)old_vector->data,
		     old_vector->size * sizeof(Vector_datum));
	new_vector->size = old_vector->size;
	return new_vector;
}

/*
 * vector_create(heap)
 * 	This will create and return a new empty vector. O(k)
 */
Vektor
vector_create(
	Heap		heap)
{
	Vektor		vector;

	heap = heap_standard_create();
	vector = heap_allocate(heap, Vektor);
	vector->heap = heap;
	vector->size = 0;
	vector->limit = 0;
	vector->data = (Vector_datum *)0;
	return vector;
}

/*
 * vector_xcreate()
 * 	This will create and return a new empty vector. O(k)
 */
Vektor
vector_xcreate(void)
{
	Vektor		vector;
	Heap		heap;

	heap = heap_standard_create();
	vector = heap_allocate(heap, Vektor);
	vector->heap = heap;
	vector->size = 0;
	vector->limit = 0;
	vector->data = (Vector_datum *)0;
	return vector;
}

/*
 * vector_delete(vector, index)
 *	This routien will remove "vector[index]" from vector and then shift
 *	everything over by one.  The deleted element is returned. O(n)
 */
void
vector_delete(
	Vektor		vector,
	Vector_index	index)
{
	vector_range_delete(vector, index, 1);
}

/*
 * vector_destroy(vector)
 *	This routien will release all of the storage associated with
 *	"vector". O(k)
 */
void
vector_destroy(
	Vektor		vector)
{
	Heap		heap;

	heap = heap_standard_create();
	if (vector->data != (Vector_datum *)0) {
		heap_free(heap, (Pointer)vector->data);
	}
	heap_free(heap, (Pointer)vector);
}

/*
 * vector_empty(vector)
 *	This routine will return 1 if "vector" is empty and 0 otherwise.
 */
int
vector_empty(
	Vektor		vector)
{
	return (int)(vector->size == 0);
}

/*
 * vector_equal(vector1, vector2, routine, handle)
 *	This routine will return 1 if each datum in "vector1" is equal
 *	to the corresponding datum in "vector2".  Two datums are considered
 *	equal if "routine(datum1, datum2, handle)" returns 1.  0 is returned
 *	if either the vector sizes are not equal or two corresponding datums
 *	are not equal.
 */
int
vector_equal(
	Vektor			vector1,
	Vektor			vector2,
	Vector_routine_tth	routine,
	Vector_handle		handle)
{
	int			size;
	Vector_datum		*pointer1;
	Vector_datum		*pointer2;

	size = vector1->size;
	if (size != vector2->size) {
		return 0;
	}
	pointer1 = vector1->data;
	pointer2 = vector2->data;
	while (size-- > 0) {
		if (!(*routine)(*pointer1++, *pointer2++, handle)) {
			return 0;
		}
	}
	return 1;
}

/*
 * vector_fetch(vector, index)
 *	This routine will return "vector[index]". O(k)
 */
Vector_datum
vector_fetch(
	Vektor		vector,
	Vector_size	index)
{
	if (index >= vector->size) {
		vector_bounds_error(vector, index);
	}
	return vector->data[index];
}

/*
 * vector_index(vector)
 *	This routine will return the current loop index for "vector" from
 *	"VEC_LOOP" macro.
 */
int
vector_index(
	Vektor		vector)
{
	return vector->index;
}

/* vector_insert(vector, index, datum)
 *	This routine will insert "datum" into "vector[index]" after
 *	shifting everything over by one.  O(n)
 */
void
vector_insert(
	Vektor		vector,
	Vector_index	index,
	Vector_datum	datum)
{
	vector_range_insert(vector, index, 1, datum);
}

/*
 * vector_iterate(vector, routine, handle)
 *	This routine will iterate through each element in "vector" by calling
 *	"routine(vector[i], handle)=>value".  The sum of all the returned
 *	values will be returned.  "routine" is not permited to change the
 *	size of "vector." O(n)*O(routine))
 */
int
vector_iterate(
	Vektor			vector,
	Vector_routine_th	routine,
	Vector_handle		handle)
{
	Vector_datum		*data;
	int			sum;
	int			size;

	sum = 0;
	data = vector->data;
	size = vector->size;
	for (size = vector->size; size > 0; size--) {
		sum += (*routine)(*data++, handle);
	}
	return sum;
}

/*
 * vector_lop(vector)
 *	This will remove the first element from vector and shift all of the
 *	elements down by one.  O(n)
 */
Vector_datum
vector_lop(
	Vektor		vector)
{
	Vector_datum	datum;

	if (vector->size == 0) {
		vector_bounds_error(vector, 0);
	}
	datum = vector->data[0];
	vector_delete(vector, 0);
	return datum;
}

/*
 * vector_pop(vector)
 *	This will remove the top element from "vector" and return it. O(k)
 */
Vector_datum
vector_pop(
	Vektor		vector)
{
	if (vector->size == 0) {
		vector_bounds_error(vector, 0);
	}
	return vector->data[--vector->size];
}

/*
 * vector_predict(vector, size)
 *	This will ensure that at least "size" elements are available in
 *	"vector".  O(k)
 */
void
vector_predict(
	Vektor		vector,
	int		size)
{
	if (size > vector->limit) {
		vector_limit_set(vector, size);
	}
}

/*
 * vector_prepend(vector, datum)
 *	This routine will stick "datum" at the beginning of "vector"
 *	after shifting all of the elements in vector over by one.  O(n)
 */
void
vector_prepend(
	Vektor		vector,
	Vector_datum	datum)
{
	vector_insert(vector, 0, datum);
}

/*
 * vector_range_delete(vector, index, number)
 *	This routine will remove "vector[index]" through
 *	"vector[index+number-1]" and then shift everything over by
 *	"number". O(n)
 */
void
vector_range_delete(
	Vektor		vector,
	Vector_index	index,
	Vector_number	number)
{
	int		size;

	size = vector->size;
	if (index + number > size) {
		vector_bounds_error(vector, index + number);
	}
	(void)memcpy((Str)(vector->data + index),
		     (Str)(vector->data + index + number),
		     (size - (number + index)) * sizeof(Vector_datum));
	vector->size -= number;
}
	
/*
 * vector_range_insert(vector, index, number, datum)
 *	This routine will insert "datum" into "vector[index]" through
 *	"vector[index+number-1]" after moving everything over by "number".
 *	O(n)
 */
void
vector_range_insert(
	Vektor		vector,
	Vector_index	index,
	Vector_number	number,
	Vector_datum	datum)
{
	int		count;
	Vector_datum	*from_pointer;
	int		new_size;
	int		size;
	Vector_datum	*to_pointer;

	size = vector->size;
	if (index > size) {
		vector_bounds_error(vector, index);
	}
	new_size = size + number;
	if (new_size >= vector->limit) {
		vector_limit_set(vector, new_size);
	}

	from_pointer = vector->data + size;
	to_pointer = vector->data + new_size;
	for (count = size - index; count > 0; count--) {
		*--to_pointer = *--from_pointer;
	}
	for (count = number; count > 0; count--) {
		*--to_pointer = datum;
	}
	vector->size = new_size;
}

/*
 * vector_range_store(vector, index, number, datum)
 *	This routine will insert "datum" into "vector[index]" through
 *	"vector[index+number-1]". O(n)
 */
void
vector_range_store(
	Vektor		vector,
	Vector_index	index,
	Vector_number	count,
	Vector_datum	datum)
{
	Vector_datum	*data;

	if (index + count > vector->size) {
		vector_bounds_error(vector, index + count);
	}
	data = vector->data + index;
	while (count-- > 0) {
		*data++ = datum;
	}
}

/*
 * vector_read(routine, in_file, heap, handle)
 *	This routine will read in and return a vector from "in_file".
 *	Each element will be read by calling
 *	"routine(in_file, heap, handle)=>element".  This routine is
 *	is the complement of vector_write().
 */
Vektor
vector_read(
	Vector_routine_hfh	routine,
	Stdio			in_file,
	Heap			heap,
	Vector_handle		handle)
{
	Vector_datum		*data;
	int			size;
	Vektor			vector;

	heap = heap_standard_create();
	vector = vector_create(heap);
	size = getw(in_file);
	vector_predict(vector, size);
	vector->size = size;
	data = vector->data;
	while (size-- > 0) {
		*data++ = (*routine)(in_file, heap, handle);
	}
	return vector;
}

/*
 * vector_search_binary(vector, datum, routine, handle)
 * 	This routine will perform a binary search on "vector" using
 *	"routine(datum, vector[i], handle)=>{-1, 0, 1}".  This
 *	operation only makes sense if "vector" is ordered such that
 *	for all i and i+1, "routine(vector[i], vector[i+1], handle)=>{-1, 0}".
 *	If there are several elements in "vector" that match "datum",
 *	the lowest matching index is returned.  If there are no elements
 *	"vector" that match "datum", the index that is returned will be
 *	the one where "routine(datum, vector[index], handle)=>-1" and
 *	"routine(datum, vector[index+1], handle)=>1". O(log(n))*O(routine)
 */
Vector_index
vector_search_binary(
	Vektor			vector,
	Vector_datum		datum,
	Vector_routine_tth	routine,
	Vector_handle		handle)
{
	Vector_datum		*data;
	Vector_index		lower;
	Vector_index		index;
	int			result;
	Vector_index		upper;

	if (vector->size == 0) {
		return 0;
	}
	data = vector->data;
	lower = 0;
	upper = vector->size - 1;
	while (lower + 1 < upper) {
		index = (lower + upper) >> 1;
		if ((*routine)(datum, data[index], handle) >= 0) {
			lower = index;
		} else {
			upper = index;
		}
	}
	result = (*routine)(datum, data[lower], handle);
	if (result <= 0) {
		return lower;
	} else {
		result = (*routine)(datum, data[upper], handle);
		if (result > 0) {
			return upper + 1;
		} else {
			return upper;
		}
	}
}

/*
 * vector_size(vector)
 *	This routine will return the size of "vector". O(k)
 */
int
vector_size(
	Vektor		vector)
{
	return vector->size;
}

/*
 * vector_sort(vector, routine, handle)
 *	This will sort each element in "vector" using 
 *	"routine(datum1, datum2, handle) => {-1, 0, 1}".
 *	O(n*log(n))*O(routine)
 */
void
vector_sort(
	Vektor			vector,
	Vector_routine_tth	routine,
	Vector_handle		handle)
{
	int			bytes;
	int			count1a;
	int			count1b;
	Vector_datum		*data;
	Vector_datum		*data1;
	Vector_datum		*data2;
	Vector_datum		*data_new;
	Vector_datum		*data_temp;
	int			index;
	int			offset;
	Vector_datum		*pointer1a;
	Vector_datum		*pointer1b;
	Vector_datum		*pointer2;
	int			power;
	int			size;
	int			step1;
	int			step2;
	int			temp;
	Heap			heap;

	heap = heap_standard_create();
	size = vector->size;
	if (size == 0) {
		return;
	}
	data = vector->data;
	for (power = 0, temp = 1; temp < size; power++, temp <<= 1)
		;
	bytes = size * sizeof(Vector_datum);
	data_new = (Vector_datum *)heap_alloc(heap, bytes);
	if ((power & 1) == 1) {
		(void)memcpy((Str)data_new, (Str)data, bytes);
		data1 = data_new;
		data2 = data;
	} else {
		data1 = data;
		data2 = data_new;
	}
	step1 = 1;
	step2 = 2;
	for (index = power; index > 0; index--) {
		pointer2 = data2;
		pointer1a = data1;
		pointer1b = data1 + step1;
		for (offset = 0; offset < size; offset += step2) {
			count1a = step1;
			temp = size - offset;
			if (temp < step1) {
				count1a = temp;
			}
			count1b = step1;
			temp = size - offset - step1;
			if (temp < step1) {
				count1b = temp;
			}
			while ((count1a > 0) && (count1b > 0)) {
				if ((*routine)(*pointer1a, *pointer1b, handle)
				    < 0) {
					*pointer2++ = *pointer1a++;
					count1a--;
				} else {
					*pointer2++ = *pointer1b++;
					count1b--;
				}
			}
			while (count1a > 0) {
				count1a--;
				*pointer2++ = *pointer1a++;
			}
			while (count1b > 0) {
				count1b--;
				*pointer2++ = *pointer1b++;
			}
			pointer1a += step1;
			pointer1b += step1;
		}
		data_temp = data1;
		data1 = data2;
		data2 = data_temp;
		step1 <<= 1;
		step2 <<= 1;
	}
	heap_free(heap, (Pointer)data_new);
}

/*
 * vector_store(vector, index, datum)
 *	This will store "datum" into "vector[index]". O(k)
 */
void
vector_store(
	Vektor		vector,
	Vector_index	index,
	Vector_datum	datum)
{
	if (index >= vector->size) {
		vector_bounds_error(vector, index);
	}
	vector->data[index] = datum;
}

/*
 * vector_trim(vector, size)
 *	This will remove elements from "vector" until
 *	"vector_size(vector) <= size". O(k).
 */
void
vector_trim(
	Vektor		vector,
	int		size)
{
	if (size < vector->size) {
		vector->size = size;
	}
}

/*
 * vector_vector_append(vector_dest, vector_source)
 *	This routine will append each element of "vector_source" to the end
 *	of "vector_dest".
 */
void
vector_vector_append(
	Vektor		vector_dest,
	Vektor		vector_source)
{
	int		limit;
	int		size;

	size = vector_dest->size + vector_source->size;
	limit = vector_dest->limit;
	if (limit < size) {
		if (limit == 0) {
			limit = 1;
		}
		while (limit < size) {
			limit <<= 1;
		}
		vector_limit_set(vector_dest, limit);
	}
	(void)memcpy((Str)(vector_dest->data + vector_dest->size),
		     (Str)vector_source->data,
		     vector_source->size * sizeof(Vector_datum));
	vector_dest->size = size;
}

/*
 * vector_write(vector, routine, out_file, handle)
 *	This routine will write out each element of "vector" to "out_file"
 *	using "routine(element, out_file, handle)" to write out each element.
 *	The resulting vector can be reread using vector_read().
 */
void
vector_write(
	Vektor			vector,
	Vector_routine_th	routine,
	Stdio			out_file,
	Vector_handle		handle)
{
	Vector_datum		*data;
	int			size;

	size = vector->size;
	(void)putw(size, out_file);
	data = vector->data;
	while (size-- > 0) {
		(*routine)(*data++, out_file, handle);
	}
}

/* Internal routines: */

/*
 * vector_limit_set(vector, new_limit)
 *	This routine will make the number of elements available in "vector"
 *	exactly equal to "new_limit".
 */
void
vector_limit_set(
	Vektor		vector,
	int		new_limit)
{
	int		old_limit;
	int		size;
	Heap		heap;

	heap = heap_standard_create();
	old_limit = vector->limit;
	if (old_limit == new_limit) {
		return;
	}
	size = new_limit * sizeof(Vector_datum);
	if (old_limit == 0) {
		vector->data = (Vector_datum *)heap_alloc(heap, size);
	} else {
		vector->data = (Vector_datum *)heap_realloc(heap,
						       (Pointer)vector->data,
						       size);
	}
	vector->limit = new_limit;
}