/***************************************************************************
  This is part of the evolver toolkit for exploring genetic progamming.
  Copyright (C) 1996 Benjamin Bennett and Yeasah G. Pell

  This library is free software; you can redistribute it and/or modify
  it under the terms of the GNU Library General Public License as
  published by the Free Software Foundation; either version 2 of the
  License, or (at your option) any later version.

  This library is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Library General Public License for more details.

  You should have received a copy of the GNU Library General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

  Contact information: Benjamin Bennett<fiji@limey.net> and Yeasah
    G. Pell<yeasah@wpi.edu>
  *************************************************************************/

#ifndef __GENERIC_H
#define __GENERIC_H

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

#include "debug_malloc.H"
#include "object.H"

#define ARRAY_CHUNK 8

extern int num_arrays;

/// Code for integer dynamic array class 
/*@Doc:
  This is a dynamic array that grows as needed.  {\it Holes} are not 
  allowed in the array so you can not grow the array by more than one
  element when allocating.  You can explicitly {\tt SetSize()} if you 
  want to save time by preventing multiple calls to {\tt realloc()}.
*/
class GIntArray : public GObject
{
	/// The size in chunks
	int vsize;
	/// The size in elements
	int size;
	/// Array of objects
	int *array;

	/// Function that deals with resizing the array
	int ChangeSize(
		/// Amount to change array relative to current size
		int change);

public:
	///
	GIntArray();

	///
	~GIntArray();

	/// Sets the size of the array to 'asize' elements
	int SetSize(int asize);
	
	/// Retrieves the current size of the array, in elements
	int GetSize();
	
	/// Appends a value to the end of the array, returns index
	int Append(int);
	
	/// returns the last value in the array
	int &Last();

	/// Returns and removes the last value in the array
	int Pop();

	/// Overloaded index operator for the array
	int &operator[](int index);

	/// Overloaded assignment operator for array (copy)
	GIntArray& operator=(GIntArray &input);

	/// Sort the array given a decision function
	void Sort(int (*compar)(const void *, const void *));
};

/// Code for the Dynamic Array template for storing pointers
/*@Doc:
  This is a dynamic array that grows as needed.  {\it Holes} are not 
  allowed in the array so you can not grow the array by more than one
  element when allocating.  You can explicitly {\tt SetSize()} if you 
  want to save time by preventing multiple calls to {\tt realloc()}.

  {\bf Warning:} This array automatically calls {\tt delete} on all 
  of the elements when the array is destroyed.  If you want to get 
  around this call {\tt Clear()} before the array gets destroyed.
*/
template<class T>
class GArray : public GObject
{
	/// The size in chunks
	int vsize;
	/// The size in elements
	int size;
	/// Array of objects
	T **array;

	/// Function that deals with resizing the array and deleting members
	int ChangeSize(
		/// Amount to change array relative to current size
		int change);

public:
	///
	GArray();

	/// Removes the dynamic array and calls delete on all of the elements
	~GArray();

	/// Clears the array without deleting elements
	void Clear();

	/// Sets the size of the array to 'asize' elements
	int SetSize(int asize);
	
	/// Retrieves the current size of the array, in elements
	int GetSize();
	
	/// Appends a value to the end of the array, returns index
	int Append(T *);
	
	/// Returns the last value in the array
	T * &Last();

	/// Returns and removes the last value in the array (but does not delete)
	T *Pop();

	/// Overloaded index operator for the array
	T * &operator[](int index);

	/// Overloaded assignment operator for array (copy)
	GArray<T>& operator=(GArray<T> &input);

	/// Sort the array given a decision function
	void Sort(int (*compar)(const void *, const void *));
};

/*===================== TEMPLATE CODE DEFINITONS =========================*/
/**************THIS CAN NOT BE IN A .C FILE, IT MUST BE HERE***************/

// constructor
template<class T>
GArray<T>::GArray()
{
	num_arrays++;
	// start with nothing
	vsize = 0;
	size = 0;
	array = NULL;
}

// destructor
template<class T>
GArray<T>::~GArray()
{
	num_arrays--;

	// free the array
	SetSize(0);
}

template<class T>
void GArray<T>::Clear()
{
	for(int i=0; i<size; i++)
		array[i] = NULL;

	SetSize(0);
}

// sets the size of the array to 'asize' elements
template<class T>
int GArray<T>::SetSize(int asize)
{
	int chunks, retval;

	// make sure they didn't slip us a bogus value
	if(asize >= 0)
    {
		// if we are shrinking, delete objects
		if(size > asize)
		{
			for(int i=asize; i<size; i++)
			{
				delete array[i];
				array[i] = NULL;
			}
		}

		// set the new size
		size = asize;

		// calculate the new size in chunks
		chunks = asize / ARRAY_CHUNK + (asize % ARRAY_CHUNK ? 1 : 0);

		// change the array by the difference in sizes
		retval = ChangeSize(chunks-vsize);

		if(asize == 0 && array != NULL)
			cerr << "SetSize(0): Didn't free array" << endl;

		return retval;
    }
	else 
		return -1;
}

// retrieves the current size of the array, in elements
template<class T>
int GArray<T>::GetSize()
{
	return size;
}

// appends a value to the end of the array, returns index
template<class T>
int GArray<T>::Append(T *t)
{
	(*this)[size] = t;
	return size-1;
}

// return the last value in the array
template<class T>
T * &GArray<T>::Last()
{
	int index = size;

	// make sure there are elements in the list
	if(index > 0)
		index--;
	else
		cerr << "GArray::Last: array is empty" << endl;
	
	return array[index];
}

// shrink the array by one
template<class T>
T *GArray<T>::Pop()
{
	T *temp = NULL;

	// make sure there are elements in the list
	if(size > 0)
	{
		temp = array[size-1];
		array[size-1] = NULL;
		SetSize(size-1);
	}
	else
		cerr << "GArray::Pop: array is empty" << endl;

	return temp;
}

// array operator -- hole-proof
template<class T>
T * &GArray<T>::operator[](int index)
{
	// array references must be non-negative
	if (index < 0)
	{
		cerr << "GArray::operator[]: Bad Array Index:" << index << endl;
		exit(-1);
	}

	// if index is past end of array, grow array to fit
	if (index == size) SetSize(size + 1);
	else if(index > size)
	{
		cerr << "GArray::operator[]: Attempt to create hole" << endl;
		exit(-1);
	}

	// return the actual value
	return array[index];
}

// overloaded assignment operator for array (copy)
template<class T>
GArray<T> &GArray<T>::operator=(GArray<T> &input)
{
	// free the array
	this->SetSize(0);

	this->vsize = input.vsize;
	this->size = input.size;
	this->array = (T **)debug_malloc(this->vsize * ARRAY_CHUNK 
		* sizeof(T *));
	if(this->array == NULL)
	if (array == NULL)
    {
		cerr << "Array creation failed\n";
		exit(1);
    }
	memcpy(this->array, input.array, this->size * sizeof(T *));

	return *this;
}

// private member function to change array size
// this is where most of the work gets done
// change gives +/- array size change in chunks of ARRAY_CHUNK elements
// NOTE: This member function doesn't update size, only vsize.
template<class T>
int GArray<T>::ChangeSize(int change)
{
	T **temp = (T **)NULL;

	// set the new vsize
	vsize += change;
  
	// if change is positive, we should grow the array by 'change' chunks
	if(change > 0)
    {
		// if we already have an array, change it's size
		if(array != NULL)
		{
			// change the size of the array
			array = (T **) realloc((void *) array, vsize * 
						 		   ARRAY_CHUNK * sizeof(T *));
			if (array == NULL) 
			{
				perror("GArray::ChangeSize");
				exit(-1);
			}
		}
		
		// starting from scratch, just allocate an array
		else
		{
			array = (T **) debug_malloc(vsize * ARRAY_CHUNK * sizeof(T *));
			if (array == NULL)
			{
				perror("GArray<T>::GArray");
				exit(-1);
			}
		}
	}      

	// if change is negative, we should shrink the array by 'change' chunks
	else if(change < 0)
    {
		// resize the array only if there is anything left
		if(vsize > 0)
		{
			// allocate a new, smaller array
			temp = (T **) debug_malloc(vsize * ARRAY_CHUNK * sizeof(T *));
			if (temp == NULL)
			{
				perror("GArray::ChangeSize");
				exit(-1);
			}

			// copy some of the old array into the new
			memcpy((void *) temp, (void *) array, size * sizeof(T *));
		}
		
		// free the old array, and replace with new
		debug_free((void *)array);
		array = temp;
	}

#ifdef DEBUG
		
	cerr << "(Array changed size by " << change * ARRAY_CHUNK << 
		" entries, new vsize " << vsize << ")" << endl;
#endif // DEBUG
	
	return 0;
}

// sort the array
// compar is the function to use to perform the comparison
template<class T>
void GArray<T>::Sort(int (*compar)(const void *, const void *))
{
	qsort(array, size, sizeof(T *), compar);
}

#endif // __GENERIC_H