/* @(#)vector.c 1.5 95/09/16 */

/*
 * Copyright (c) 1994, 1995 by Wayne C. Gramlich.  All rights reserved.
 *
 * Permission to use, copy, modify, distribute, and sell this software
 * for any purpose is hereby granted without fee provided that the above
 * copyright notice and this permission are retained.  The author makes
 * no representations about the suitability of this software for any purpose.
 * It is provided "as is" without express or implied warranty.
 */

/* LINTLIBRARY */

#include <stdio.h>
#include "memory_extern.h"
#include "vector_extern.h"

struct vector_struct {
    unsigned index;	/* Loop iteration index */
    unsigned size;	/* Number of pointers in vector */
    Pointer *data;	/* Pointer array */
    unsigned limit;	/* Maximum number of pointers before forced resize */
};

static void vector_bounds_error(Vector, unsigned);
static void vector_limit_set(Vector, unsigned);
static void vector_range_delete(Vector, unsigned, unsigned);

/*
 * vector_append(vector, pointer)
 *	This will append {pointer} to the end of {vector}.
 */
void
vector_append(
    Vector		vector,
    Pointer		pointer)
{
    unsigned	limit;

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

/*
 * vector_bounds_error(vector, index)
 *	This routine will print a bounds error for "vector" and "index".
 */
static void
vector_bounds_error(
    Vector vector,
    unsigned index)
{
    (void)fprintf(stderr, "vector 0x%x: Bounds error (%u not in [0:%u])",
      (unsigned)vector, index, vector->size - 1);
}		

/*
 * vector_clear(vector)
 *	This routine will remove all elements from {vector}.
 */
void
vector_clear(
    Vector vector)
{
    vector_trim(vector, 0);
}

/*
 * vector_create(
 * 	This will create and return a new empty vector.
 */
Vector
vector_create(void)
{
    Vector vector;

    vector = (Vector)memory_allocate(sizeof *vector);
    vector->index = 0;
    vector->size = 0;
    vector->limit = 0;
    vector->data = (Pointer *)0;
    return vector;
}

/*
 * vector_delete(vector, index)
 *	This routine will remove "vector[index]" from vector and then shift
 *	everything over by one.
 */
void
vector_delete(
    Vector vector,
    unsigned index)
{
    vector_range_delete(vector, index, 1);
}

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

/*
 * vector_fetch(vector, index)
 *	This routine will return {vector[index]}.
 */
Pointer
vector_fetch(
    Vector vector,
    unsigned index)
{
    if (index >= vector->size) {
	vector_bounds_error(vector, index);
    }
    return vector->data[index];
}

/*
 * vector_limit_set(vector, new_limit)
 *	This routine will make the number of elements available in {vector}
 *	exactly equal to {new_limit}.
 */
static void
vector_limit_set(
    Vector vector,
    unsigned new_limit)
{
    unsigned old_limit;
    unsigned size;

    old_limit = vector->limit;
    if (old_limit == new_limit) {
	return;
    }
    size = new_limit * sizeof(Pointer);
    if (old_limit == 0) {
	vector->data = (Pointer *)memory_allocate(size);
    } else {
	vector->data =
	  (Pointer *)memory_reallocate((Pointer)vector->data, size);
    }
    vector->limit = new_limit;
}

/*
 * vector_loop_init(vector)
 *	This routine initializes {vector} for loop iteration and
 *	return the first value from {vector}.  If {vector} is empty
 *	{(Pointer)0} is returned.  The loop iterator macros are not
 *	reentrant -- only one loop at a time works.  Unfortunately,
 *	because of the C "break" statement, there is no way to detect
 *	bogus reentrant calls.
 */
Pointer
vector_loop_init(
    Vector vector)
{
    vector->index = 0;
    if (vector->size == 0) {
	return (Pointer)0;
    }
    return vector->data[0];
}

/*
 * vector_loop_next(vector)
 *	This routine will return the next value from {vector} or
 *	if there is no next value, {(Pointer)0} is returned.
 */
Pointer
vector_loop_next(
    Vector vector)
{
    unsigned index;

    index = vector->index + 1;
    if (index == vector->size) {
	return (Pointer)0;
    }
    vector->index = index;
    return vector->data[index];
}

/*
 * 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)
 */
static void
vector_range_delete(
    Vector vector,
    unsigned index,
    unsigned number)
{
    unsigned size;

    size = vector->size;
    if (index + number > size) {
	vector_bounds_error(vector, index + number);
    }
    memory_copy((void *)(vector->data + index),
	(void *)(vector->data + index + number),
	(size - (number + index)) * sizeof(Pointer));
    vector->size -= number;
}
	
/*
 * vector_size(vector)
 *	This routine will return the size of "vector".
 */
unsigned
vector_size(
    Vector vector)
{
    return vector->size;
}

/*
 * vector_sort(vector, compare_routine, handle)
 *	This will sort each element in {vector} using 
 *	{compare_routine}(element1, element2, handle) => {-1, 0, 1}
 *	to compare elements.
 */
void
vector_sort(
    Vector vector,
    Vector_compare_element compare_routine,
    void *handle)
{
    int bytes;
    int count1a;
    int count1b;
    Pointer *data;
    Pointer *data1;
    Pointer *data2;
    Pointer *data_new;
    Pointer *data_temp;
    unsigned index;
    unsigned offset;
    Pointer *pointer1a;
    Pointer *pointer1b;
    Pointer *pointer2;
    unsigned power;
    unsigned size;
    unsigned step1;
    unsigned step2;
    unsigned temp;

    size = vector->size;
    if (size == 0) {
	return;
    }
    data = vector->data;
    for (power = 0, temp = 1; temp < size; power++, temp <<= 1)
	;
    bytes = size * sizeof(Pointer);
    data_new = (Pointer *)memory_allocate(bytes);
    if ((power & 1) == 1) {
	memory_copy(data_new, 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 ((*compare_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;
    }
    memory_free(data_new);
}

/*
 * vector_trim(vector, size)
 *	This will trim any excess values from the end of {vector}
 *	{vector} has no more than {size} elements.
 */
void
vector_trim(
    Vector vector,
    unsigned size)
{
    if (size < vector->size) {
	vector->size = size;
    }
}

#ifdef UNUSED
/*
 * vector_copy(old_vector)
 *	This routine will return a duplicate copy of "old_vector" from the
 *	same heap. O(n)
 */
Vector
vector_copy(
	Vector		old_vector)
{
	Vector		new_vector;

	new_vector = vector_create(old_vector->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_destroy(vector)
 *	This routien will release all of the storage associated with
 *	"vector". O(k)
 */
void
vector_destroy(
	Vector		vector)
{
	if (vector->data != (Vector_datum *)0) {
		heap_free(vector->heap, (Pointer)vector->data);
	}
	heap_free(vector->heap, (Pointer)vector);
}

/*
 * 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(
	Vector			vector1,
	Vector			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_index(vector)
 *	This routine will return the current loop index for "vector" from
 *	"VEC_LOOP" macro.
 */
int
vector_index(
	Vector		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(
	Vector		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(
	Vector			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(
	Vector		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(
	Vector		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(
	Vector		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(
	Vector		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(
	Vector		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(
	Vector		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(
	Vector		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"
 *	allocated from "heap".  Each element will be read by calling
 *	"routine(in_file, heap, handle)=>element".  This routine is
 *	is the complement of vector_write().
 */
Vector
vector_read(
	Vector_routine_hfh	routine,
	Stdio			in_file,
	Heap			heap,
	Vector_handle		handle)
{
	Vector_datum		*data;
	int			size;
	Vector			vector;

	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(
	Vector			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_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(
	Vector			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;

	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(vector->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(vector->heap, (Pointer)data_new);
}

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

/*
 * 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(
	Vector		vector_dest,
	Vector		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(
	Vector			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);
	}
}
#endif /* UNUSED */