// Copyright 1999
// College of Computer Science
// Northeastern University Boston MA 02115

// This software may be used for educational purposes as long as this copyright
// notice is retained at the top of all files

// Should this software be modified, the words "Modified from Original" must be
// included as a comment below this notice

// All publication rights are retained.  This software or its documentation may
// not be published in any media either in whole or in part.

///////////////////////////////////////////////////////////////////////////////

//	ArrayT.h

///////////////////////////////////////////////////////////////////////////////


/******************************************************************************

Design considerations:

1. Use templates

2. Use dynamic allocation
		If allocation fails during construction throw a string exception with
		message: "memory allocation failed"
		If allocation fails when increasing memory then leave the array as is

3. Support the concepts of
		totalsize	Total space allocated	Require: totalsize >= 1
		validsize	Total space in use		Require: 0 <= validsize <= totalsize
		
4. Support changing the memory allocation in several ways:
		Expand			Double totalsize
		Extend			Increment totalsize by the amount specified
		ChangeMemory	Change totalsize to the amount specified 

5. Use Append to add an element to the array and increment validsize.
   Use Expand if validsize == totalsize when Append is called.

6. Use Remove to remove the final element in the array and decrement validsize.

7. Use operator[] to support range-check on array access.  A valid index must
satisfy: 0 <= index < validsize.

8. Throw string exception if an invalid index is passed to operator[] and say
in the message whether index is "too low" or "too high".

9. Define a member function Access as a synonym for operator[].  The reason
this is useful is that when a class inherits from the Array class it is not
easy to call operator[] in internal definitions because there is no named
base array object to attach the brackets [] to.

10. Define a member function FastAccess to support access with no range-check.
This option is provided to support maximum runtime efficiency.

It is then the responsibility of the caller to make sure that the index is in
range.  Use FastAccess with extreme care!

11. Cells are automatically validated if data is added or removed using Append
or Remove.  To manally set validation use:

		ValidateAll		Validate all allocated cells
		ValidateNone	Make all allocatied cells invalid
		ValidateSome	Specify which allocated cells are valid

These calls will not change the amount of memory allocated.

12. If the items stored in the array require memory management (new or delete)
then this must be done manually by the caller.  The Array class cannot know or
manage such requirements.

******************************************************************************/


#ifndef ARRAY_TEMPLATE_H_
#define ARRAY_TEMPLATE_H_

#include "AllocT.h"


// array class

template <class DataType>
class Array {
	DataType*	data;				// pointer to the array
	int			totalsize;			// total array space
	int			validsize;			// valid array space


	// Copy is the heart of the copy constructor and operator=
	// Copy assumes data is invalid and does no extra delete[]
	//
	// Copy allocates the minimal memory needed to make copy
	
	void Copy(const Array& Original) {
		// set important fields to zero in case allocate fails
		data = 0;
		totalsize = 0;
		validsize = 0;
		
		// allocate
		Allocate(data, Original.validsize);
		
		// set new parameters
		totalsize	= Original.validsize;
		validsize	= Original.validsize;
		
		// copy valid data

		CopyData(data, Original.data, 0, 0, validsize);
	};


	// check range for index
	// if index is invalid throw out_of_range
	
	void range_check(int i) const {
		if (i < 0)
			throw string("invalid index: too low");
		
		if (i >= validsize)
			throw string("invalid index: too high");
	};
	
public:
	// provide means for caller to recover DataType

	typedef DataType datatype;


	// provide means for caller to get at the internal array if needed
	// this permits interface with certain system routines
	// use this facility with extreme care!

	const DataType* DataPointer() const { return data; };	// const version

	DataType* DataPointer() { return data; };				// non-const version


	// routines to return internal size information
	
	int TotalSize() const { return totalsize; };
	
	int ValidSize() const { return validsize; };
	

	// ValidateAll:  Make all array cells valid
	
	void ValidateAll() { validsize = totalsize; };

	// ValidateNone: Make all array cells invalid
	
	void ValidateNone() { validsize = 0; };
	

	// ValidateSome: Make some array cells valid
	// Do not automatically increase memory allocation
	// To increase memory allocation call functions provided
	
	void ValidateSome(int maxvalid) {
		if (maxvalid < 0)
			maxvalid = 0;

		if (maxvalid > totalsize)
			maxvalid = totalsize;

		validsize = maxvalid;
	};
	

	// standard constructor
	// totalsize is initialized to size
	// validsize is initialized to zero
	
	Array(int size = 1) {
		// set important fields to zero in case allocate fails
		data = 0;
		totalsize = 0;
		validsize = 0;
		
		if (size < 1) size = 1;			// force size positive
		
		Allocate(data, size);			// allocate the memory
		
		totalsize = size;				// set totalsize
	};
	

	// destructor
	
	~Array() {
		delete [] data;
	};
	

	// copy constructor
	// totalsize of copy equals validsize of original
	// this design minimizes memory allocation during copy
	
	Array(const Array& Original) {
		Copy(Original);
	};


	// assignment: operator=
	// totalsize of copy equals validsize of original
	// this design minimizes memory allocation during copy
	
	Array& operator= (const Array& Original) {
		// if this object is the same as original just return
		if (this == &Original)
			return *this;
		
		// delete allocated memory in object
		delete [] data;
		
		// copy
		Copy(Original);
		
		return *this;
	};
	

	// ChangeMemory: Change allocated memory size to new size
	
	Array& ChangeMemory(int NewSize) {
		// return immediately if no change
		if (NewSize == totalsize)
			return *this;
		
		// error check parameter
		if (NewSize < 1)
			NewSize = 1;
		
		// save original data
		DataType* original = data;
		
		// allocate and catch error

		try {
			Allocate(data, NewSize);
		}
		catch (string& s) {
			// print message
			cout << s << endl << endl;

			// restore original and return immediately
			data = original;
			return *this;
		}

		// reset totalsize and validsize

		totalsize = NewSize;

		if (validsize > totalsize)
			validsize = totalsize;
		
		// copy valid data
		CopyData(data, original, 0, 0, validsize);

		// delete original data
		delete [] original;
		
		return *this;
	};

	
	// Expand: Double the size
	
	Array& Expand() {
		return ChangeMemory(2 * totalsize);
	};
	

	// Extend: Increase size by increment
	
	Array& Extend(int increment) {
		return ChangeMemory(totalsize + increment);
	};
	

	// operator []: array access with bounds check
	
	const DataType& operator[] (long i) const {	// const version
		range_check(i);
		return data[i];
	};


	DataType& operator[] (long i) {				// non-const version
		range_check(i);
		return data[i];
	};


	// Access: Synonym for operator[]
	// Access is provided to support inheritance from the Array class

	const DataType& Access (long i) const {		// const version
		range_check(i);
		return data[i];
	};


	DataType& Access (long i) {					// non-const version
		range_check(i);
		return data[i];
	};


	// FastAccess: array access with no bounds check
	// FastAccess is provided for runtime efficiency
	// Caller must guarantee by other means that index is in bounds!
	// Use FastAccess with extreme care!

	const DataType& FastAccess (long i) const {	// const version
		return data[i];
	};


	DataType& FastAccess (long i) {				// non-const version
		return data[i];
	};


	// Append: Increase validsize and add new data value.
	// Expand if needed.
	
	bool Append(const DataType& value) {
		// check if more space is needed
		if (validsize == totalsize)
			Expand();
		
		// append the value if there is enough space now
		if (validsize < totalsize) {
			data[validsize] = value;		// store value
			validsize++;					// increment count
			return true;
		}
		else
			return false;
	};


	// Remove: Return final value and decrease validsize
	
	bool Remove(DataType& value) {
		if (validsize > 0) {
			validsize--;					// decrement count
			value = data[validsize];		// deliver value
			return true;
		}
		else
			return false;
	};
};

#endif // ARRAY_TEMPLATE_H_