// TArray.h
//
// Copyright © Diehl Graphsoft, Inc. 1997.
// All Rights Reserved.
//
// Graphsoft standard dynamic array class
//
// Last SourceSafe check-in:
//		$Revision: 5 $
//		$Date: 7/25/00 9:40 AM $
//		$Author: Darick $
//
// Started long ago by Sean Flaherty

#ifndef _TARRAY_
#define _TARRAY_

#pragma once

#include "GSTypes.h"
#include "GSUtil.h"
#include "StaticArrays.h"
#include "GSDebug.h" // for TDebugObject


/////////////////////////////////////////////////////////////////////////////////////////
//
// TSmallArray
//
//	This object can index an array of up to MAX_INT elements
//
/////////////////////////////////////////////////////////////////////////////////////////

/**************************************************************************
						Warning for TSmallArray Users
**************************************************************************
Data placed in a TSmallArray is stored in an unlocked handle. Therefore, you 
must be careful to never rely on a pointer to TSmallArray data, because the 
data handle could move during a Mac system call and leave your pointer in 
the dust.  

The easiest way to make this mistake is to pass TSmallArray data to a function 
as a reference parameter. 


	TSmallArray<PStr31>	fViewName;
			
	for(int i=0; i<fViewName.NumItems(); i++){
	
		// The wrong way
		AppendMenuCk(theMenu, fViewName[i]);
		
		// The safe way
		PStr31 toolName = fViewName[i]; // PString class makes a copy of the data
		AppendMenuCk(theMenu, toolName);
	}


Normally you dont have to worry about unlocked handles because almost 
all handles in MiniCAD, including object handles, are locked.

Darick W. DeHart 2/12/98
**************************************************************************/

/**************************************************************************
/ NOTES: 
  There are two ways to construct TSmallArrayHandlers, one by passing an existing handle and one without a handle,
all other fields are the same InclusiveBetween the two.  When you pass an existing handle, such as when modifying 
a PolyTDHandle, you need to specify the byte offset to the count word and to the beginning of the data.  In
the case of PolyTDHandles, for instance, the count word is located at offsetof(TDPolyType, vertices), and the
first data byte at offsetof(TDPolyType, vertexList[0]).  If one cell has a count of 1, then the count
is NOT zero-based.

   If you do not have an existing handle, the easiest way to construct a dynamic array is without passing any
parameters.  In this case, TSmallArrayHandler sets up everything and does automatic buffering (every 10 cells).

   Use DEFINE_TARRAY to define type specific dynamic array classes.  For example, DEFINE_TARRAY(WorldRect) would
define a dynamic array type TLongRectArray.  This allows use of the [] operator and returns a reference to
the proper data type.
***************************************************************************/

extern "C" {
	typedef int (*QSortCompareFunc)(const void*, const void*);
}

class GS_COMP_API TSmallArrayHandler : public TDebugObject
{
	private:
		enum {
			kBuffSize = 10				// Number of cells buffered when fFreeMemWhenDone is true
		};
		
		Bool8	fFreeMemWhenDone;		// Dispose of fDataHandle when done
		short	fNumAllocItems;			// Number of cells actually allocated
		short	fNumUsedItems;			// Number of items the client is using
		void operator=(void *) {}  
		TSmallArrayHandler(const TSmallArrayHandler&) {} // prevents TSmallArray from accidentally being passed by value  [MAF 2/1/00]

	protected:
		GSHandle	fDataHandle;		// Handle to the data
		long		fDataSize;			// Size of each cell's data in bytes
		long		fDataOffset;		// Byte offset from beginning of handle to first data item
		long		fCountOffset;		// Byte offset from beginning of handle to count item (a short)
		Bool8		fCountZeroBased;	// Is the count 0 or 1 based?
		Bool8		fGrowGeometrically;	// Double the array size each time it is expanded
		

		void SetCount(short numDataItems)
		{
			if (fDataHandle) {
				*((short *) (*fDataHandle + fCountOffset)) = fCountZeroBased ? numDataItems-1 : numDataItems;
				fNumUsedItems = numDataItems;
				ASSERTHANDLE(kSean, fDataHandle, fDataOffset + fNumAllocItems * fDataSize);
			}
		}
		
		
		#if BUG
		void* GetCellPtr(short cellNum) const;
		#else
		void* GetCellPtr(short cellNum) const		{ short i = PIN(cellNum, 0, fNumUsedItems - 1); return (char*) (*this->fDataHandle + this->fDataOffset + i*fDataSize); }
		#endif
	
	public:
		TSmallArrayHandler(GSHandle dataH, long dataSz, long dataOff, long countOff, Bool8 zeroBasedCount);
		TSmallArrayHandler(long dataSz, long dataOff = sizeof(short), long countOff = 0L, Bool8 zeroBasedCount = false, 
					  short numCells = kBuffSize, Bool8 growGeometrically = false);
		~TSmallArrayHandler();
		
		
		#if BUG
		short NumItems() const;
		#else
		short NumItems() const			{ return fNumUsedItems; }
		#endif
		
		void Empty()					{ DeleteCells(0, NumItems()); }
		
		Bool8 AppendCellAndData(const void* cellData)
		/*
			Adds one cell and data in cellData to end of array
		*/
		{
			if (this->AppendCells(1)) {
				memcpy(this->GetCellPtr(this->NumItems()-1), cellData, (size_t) this->fDataSize);
				return true;
			}
			else
				return false;
		}

		Bool8 AppendCells(short numCells);
		Bool8 InsertCellAndData(short beforeWhere, const void* cellData);
		Bool8 InsertCells(short beforeWhere, short numCells);
		void DeleteCells(short firstCell, short numCells);


		void SortArray(QSortCompareFunc CompFunc);

		// this must be used very carefully!!!
		// if this handle is locked - it must be unlocked!!
		GSHandle GetDataHandle()
		{
			ASSERTHANDLE(kSean, fDataHandle, fDataOffset + fNumAllocItems * fDataSize);
			return (GSHandle) fDataHandle;
		}

		
		#ifdef BUG
		void CheckArrayValues() const;
		void WriteArray() const;
		#endif
};

template <class T> class TSmallArray : public TSmallArrayHandler {
	public:
		TSmallArray(GSHandle dataH, long dataOff, long countOff, Bool8 zeroBasedCount)
			: TSmallArrayHandler(dataH, sizeof(T), dataOff, countOff, zeroBasedCount) { }
		
		TSmallArray(long dataOff = sizeof(short), long countOff = 0L, Bool8 zeroBasedCount = false, 
			   short numCells = 0, Bool8 growGeometrically = false)
			: TSmallArrayHandler(sizeof(T), dataOff, countOff, zeroBasedCount, numCells, growGeometrically) { }
		
		T& operator[](short cellNum)		{ return *((T *) this->GetCellPtr(cellNum)); }
		T operator[](short cellNum) const	{ return *((T *) this->GetCellPtr(cellNum)); }
		T* GetAt(short cellNum)				{ return (T*) this->GetCellPtr(cellNum); }
		Bool8 PushData(const T& cellData)	{ return this->AppendCellAndData(&cellData); }
		Bool8 InsertData(short beforeWhere, const T& cellData) { return InsertCellAndData(beforeWhere, &cellData); }
		Bool8 InsertData(short where, short count, const T* cellData);
		T PopData();
};

template <class T> Bool8 TSmallArray<T>::InsertData(short where, short count, const T* cellData)
{
	for (int i=0; i<count; ++i, ++where) {

		if (!VERIFYN (kKarim, InsertData(where, cellData[i]))) {

			DMSG ((kEveryone, "TSmallArray<T>::InsertData --> Only the first %i items were added.\n", i));
			return false;
		}
	}

	return true;
}
 
template <class T> T TSmallArray<T>::PopData()
{
	T tmp;
	
	if (this->NumItems() > 0) {
		tmp = (*this)[ kGSMaxSint16]; DeleteCells(this->NumItems()-1, 1);
	}
	return tmp; 
}

#define DEFINE_TARRAY(DataType)			typedef TSmallArray<DataType> T##DataType##Array
#define DEFINE_NOPOP_TARRAY(DataType)	typedef TSmallArray<DataType> T##DataType##Array

/////////////////////////////////////////////////////////////////////////////////////////
//
// TLargeArray
//
//	This object can index an array of up to MAX_LONG elements
//
/////////////////////////////////////////////////////////////////////////////////////////
extern "C" {
	typedef int (*QSortCompareFunc)(const void*, const void*);
}


/*
	   There are two ways to construct TSmallArrayHandlers, one by passing an existing handle and one without a handle,
	all other fields are the same InclusiveBetween the two.  When you pass an existing handle, such as when modifying 
	a PolyTDHandle, you need to specify the byte offset to the count word and to the beginning of the data.  In
	the case of PolyTDHandles, for instance, the count word is located at offsetof(TDPolyType, vertices), and the
	first data byte at offsetof(TDPolyType, vertexList[0]).  If one cell has a count of 1, then the count
	is NOT zero-based.
	
	   If you do not have an existing handle, the easiest way to construct a dynamic array is without passing any
	parameters.  In this case, TSmallArrayHandler sets up everything and does automatic buffering (every 10 cells).
	
	   Use DEFINE_TARRAY to define type specific dynamic array classes.  For example, DEFINE_TARRAY(WorldRect) would
	define a dynamic array type TLongRectArray.  This allows use of the [] operator and returns a reference to
	the proper data type.
*/

typedef unsigned long				LargeArrayIndex;

enum EArrayGrowthMethod { eOneAtATimeGrowth,   // 1, 2, 3, 4, ... (for when have existing data handle)
						 eArithmeticGrowth,    // 10, 20, 30, 40...
					     eGeometricGrowth,     // 10, 20, 40, 80...
						 eExponentialGrowth};  // 10, 100, 1000, 10000...


#if _WINDOWS && ! _MINICAD_
class TLargeArrayHandler : public TDebugObject
#else
class TLargeArrayHandler : public TDebugObject
#endif
{
	public:
		TLargeArrayHandler(size_t dataSz, EArrayGrowthMethod growthMethod = eGeometricGrowth);
		TLargeArrayHandler(GSHandle dataH, size_t dataSz, long dataOff, long countOff, 
			Bool8 zeroBasedCount);
		~TLargeArrayHandler();
		
		LargeArrayIndex NumItems() const		{ return fNumUsedItems; }		
		void Empty()							{ DeleteCells(0, this->NumItems()); }
		
		Boolean AppendCellAndData(const void* cellData)
		/*
			Adds one cell and data in cellData to end of array
		*/
		{

			if (this->AppendCells(1)) {
				memcpy(this->GetCellPtr(this->NumItems()-1), cellData, (size_t) this->fDataSize);
				return true;
			}
			else
				return false;
		}

		Boolean AppendCells(LargeArrayIndex numCells);
		Boolean InsertCellAndData(LargeArrayIndex beforeWhere, const void* cellData);
		Boolean InsertCells(LargeArrayIndex beforeWhere, LargeArrayIndex numCells);
		void DeleteCells(LargeArrayIndex firstCellToDelete, LargeArrayIndex numCells);

#ifdef _MINICAD_
		void SortArray(QSortCompareFunc CompFunc);
#endif

		GSHandle GetDataHandle()
		// this must be used very carefully!!!
		// if this handle is locked - it must be unlocked!!
		{
			ASSERTHANDLE(kSean, fDataHandle, fDataOffset + fNumAllocItems * fDataSize);
			return (GSHandle) fDataHandle;
		}

		unsigned long SizeOf() const { return fNumAllocItems * fDataSize; }
		
		#ifdef BUG
		void CheckArrayValues() const;
		void WriteArray() const;
		#endif

	protected:
		GSHandle		    fDataHandle;			// Handle to the data
		size_t		        fDataSize;				// Size of each cellŐs data in bytes
		long				fDataOffset;			// Byte offset from beginning of handle to first data item
		long				fCountOffset;			// Byte offset from beginning of handle to count item (a long)
		Bool8				fCountZeroBased;		// Is the count 0 or 1 based?
		EArrayGrowthMethod  fGrowthMethod;
		
		void SetCount(LargeArrayIndex numDataItems)
		{
			if (fDataHandle) {
				*((long *) (*fDataHandle + fCountOffset)) = fCountZeroBased ? 
							numDataItems-1 : numDataItems;
				fNumUsedItems = numDataItems;
				ASSERTHANDLE(kSean, fDataHandle, fDataOffset + fNumAllocItems * fDataSize);
			}
		}
		
		
		#if BUG
		void* GetCellPtr(LargeArrayIndex cellNum) const;
		#else
		void* GetCellPtr(LargeArrayIndex cellNum) const		
		{ LargeArrayIndex i = PIN(cellNum, (unsigned long)0, fNumUsedItems - 1); 
		return (void*) (*this->fDataHandle + fDataOffset + i*fDataSize); }
		#endif

	private:
		enum {
			kBuffSize = 10						// Number of cells buffered when growing the handle
		};
		
		Bool8			fFreeMemWhenDone;		// Dispose of fDataHandle when done
		LargeArrayIndex	fNumAllocItems;			// Number of cells actually allocated
		LargeArrayIndex	fNumUsedItems;			// Number of items the client is using
		void operator=(void *) {}				// make this private so it can't be actually called
};


template <class T> class TLargeArray : public TLargeArrayHandler {
	public:		
		TLargeArray(EArrayGrowthMethod growthMethod = eGeometricGrowth)
			: TLargeArrayHandler(sizeof(T), growthMethod)		{ }
		TLargeArray(GSHandle dataH, long dataOff, long countOff, Bool8 zeroBasedCount)
			: TLargeArrayHandler(dataH, sizeof(T), dataOff, countOff, zeroBasedCount)	{ }
		
		T& operator[](LargeArrayIndex cellNum)		{ return *((T *) this->GetCellPtr(cellNum)); }
		T operator[](LargeArrayIndex cellNum) const	{ return *((T *) this->GetCellPtr(cellNum)); }
		T* GetAt(LargeArrayIndex cellNum)			{ return (T*) this->GetCellPtr(cellNum); }
		Boolean PushData(const T& cellData)			{ return this->AppendCellAndData(&cellData); }
		Boolean InsertData(LargeArrayIndex beforeWhere, const T& cellData) { return InsertCellAndData(beforeWhere, &cellData); }
		Boolean InsertData(LargeArrayIndex where, LargeArrayIndex count, const T* cellData);
		T PopData();
};

template <class T> Boolean TLargeArray<T>::InsertData(LargeArrayIndex where, LargeArrayIndex count, const T* cellData)
{
	for (int i=0; i<count; ++i, ++where)
		InsertData(where, cellData[i]);
	
	return true;
}
 
template <class T> T TLargeArray<T>::PopData()
{
	T tmp;
	
	if (this->NumItems() > 0) {
		tmp = (*this)[ULONG_MAX]; DeleteCells(this->NumItems()-1, 1);
	}
	return tmp; 
}

#define DEFINE_TLARGEARRAY(DataType)			typedef TLargeArray<DataType> TLarge##DataType##Array
#define DEFINE_NOPOP_TLARGEARRAY(DataType)		typedef TLargeArray<DataType> TLarge##DataType##Array

#endif // _TARRAY_
