/////////////////////////////////////////////////////////////
// CINEMA 4D SDK                                           //
/////////////////////////////////////////////////////////////
// (c) 1989-2004 MAXON Computer GmbH, all rights reserved  //
/////////////////////////////////////////////////////////////

#ifndef __GE_MTOOLS_H
#define __GE_MTOOLS_H

#include "c4d_memory.h"

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

#ifndef GCC
	#define STATIC_CAST(a,b) static_cast<a>(b)
	#define CONST_CAST(a,b) const_cast<a>(b)
#else
	#define STATIC_CAST(a,b) (a)(b)
	#define CONST_CAST(a,b) (a)(b)
#endif

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

#define GE_TOOL_NOT_FOUND (-1)

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

class GeToolNode2D
{
	friend class GeToolList2D;
		
	protected:
		GeToolNode2D(void) : next(NULL), prev(NULL) { }
		virtual ~GeToolNode2D(void);
	
		void*	GetNext(void) const { return (next && next->next) ? STATIC_CAST(void*,next) : NULL; }
		void*	GetPrev(void) const { return (prev && prev->prev) ? STATIC_CAST(void*,prev) : NULL; }
	
		void	InsertBefore(void *nv);
		void	InsertAfter(void *nv);
		void	Remove(void);
		
	private:
	  GeToolNode2D*	next;
	  GeToolNode2D*	prev;
};

class GeToolNode4D;

class GeToolList2D
{
	friend class GeToolList4D;
	friend class GeToolNode4D;

	protected:
	  GeToolList2D(void);
		virtual ~GeToolList2D(void);
	
	  void*	GetFirst(void) const { return (head.next != &tail) ? STATIC_CAST(void*,head.next) : NULL; }
		void*	GetLast(void) const { return (tail.prev != &head) ? STATIC_CAST(void*,tail.prev) : NULL; }
		void*	GetIndex(LONG index) const;
	
		void	Insert(void *nv);
		void	Append(void *nv);
	
		void	Clear(void);
		void	FlushAll(void);
		void	RemoveAll(void);
	
		LONG	GetCount(void) const;
				
	private:
		GeToolNode2D	head;
		GeToolNode2D	tail;
		GeToolNode4D*	node;
};

class GeToolNode4D : public GeToolNode2D
{
	friend class GeToolList4D;

	protected:
		GeToolNode4D(void) { list.node = this; }
		virtual ~GeToolNode4D(void) { }

		void	InsertUnder(void *nv) { if (nv) ((GeToolNode4D*)nv)->list.Insert(this); }
		void	InsertUnderLast(void *nv) { if (nv) ((GeToolNode4D*)nv)->list.Append(this); }

		void*	GetDown(void) const { return list.GetFirst(); }
		void*	GetUp(void) const { return list.node; }
		
	private:
		GeToolList2D	list;
};

class GeToolList4D : public GeToolList2D
{
	protected:
		virtual ~GeToolList4D(void) { }
};

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

// GeTempPrivateNode2D - read only access

template<class TYPE>
class GeTempPrivateNode2D : private GeToolNode2D
{
	public:
		TYPE* GetNext() const { return STATIC_CAST(TYPE*,GeToolNode2D::GetNext()); }
		TYPE* GetPrev() const { return STATIC_CAST(TYPE*,GeToolNode2D::GetPrev()); }
};

// GeTempPrivateList2D - read only access

template<class TYPE>
class GeTempPrivateList2D : private GeToolList2D
{
	public:
		TYPE* GetFirst() const { return STATIC_CAST(TYPE*,GeToolList2D::GetFirst()); }
		TYPE* GetLast() const { return STATIC_CAST(TYPE*,GeToolList2D::GetLast()); }
		TYPE* GetIndex(LONG index) const { return STATIC_CAST(TYPE*,GeToolList2D::GetIndex(index)); }
		LONG	GetCount(void) const { return GeToolList2D::GetCount(); }
};

// GeTempPublicNode2D - read & write access

template<class TYPE>
class GeTempPublicNode2D : private GeToolNode2D
{
	public:
		TYPE* GetNext() const { return STATIC_CAST(TYPE*,GeToolNode2D::GetNext()); }
		TYPE* GetPrev() const { return STATIC_CAST(TYPE*,GeToolNode2D::GetPrev()); }

		void	InsertBefore(TYPE *n) { GeToolNode2D::InsertBefore(STATIC_CAST(void*,n)); }
		void	InsertAfter(TYPE *n) { GeToolNode2D::InsertAfter(STATIC_CAST(void*,n)); }
		void	Remove(void) { GeToolNode2D::Remove(); }
};

// GeTempPublicList2D - read & write access

template<class TYPE>
class GeTempPublicList2D : private GeToolList2D
{
	public:
		TYPE* GetFirst() const { return STATIC_CAST(TYPE*,GeToolList2D::GetFirst()); }
		TYPE* GetLast() const { return STATIC_CAST(TYPE*,GeToolList2D::GetLast()); }
		TYPE*	GetIndex(LONG index) const { return STATIC_CAST(TYPE*,GeToolList2D::GetIndex(index)); }
		LONG	GetCount(void) const { return GeToolList2D::GetCount(); }

		void Insert(TYPE *n) { GeToolList2D::Insert(STATIC_CAST(void*,n)); }
		void Append(TYPE *n) { GeToolList2D::Append(STATIC_CAST(void*,n)); }
		
		void FlushAll(void) { GeToolList2D::FlushAll(); }
		void RemoveAll(void) { GeToolList2D::RemoveAll(); }
};

// nodes with additional type info

template<class TYPE, class CLASS>
class GeTempExtPrivateNode2D : public GeTempPrivateNode2D<CLASS>
{
	public:
		const TYPE&	GetType(void) const { return type; }
		void				SetType(const TYPE &p_type) { type = p_type; }

	private:
		TYPE type;
};

template<class TYPE, class CLASS>
class GeTempExtPublicNode2D : private GeTempPublicNode2D<CLASS>
{
	public:
		const TYPE& GetType(void) const { return type; }
		void				SetType(const TYPE &p_type) { type = p_type; }

	private:
		TYPE type;
};

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

// GeTempPrivateNode4D - read only access

template<class TYPE>
class GeTempPrivateNode4D : private GeToolNode4D
{
	public:
		TYPE* GetNext() const { return STATIC_CAST(TYPE*,GeToolNode4D::GetNext()); }
		TYPE* GetPrev() const { return STATIC_CAST(TYPE*,GeToolNode4D::GetPrev()); }
		TYPE* GetDown() const { return STATIC_CAST(TYPE*,GeToolNode4D::GetDown()); }
		TYPE* GetUp() const { return STATIC_CAST(TYPE*,GeToolNode4D::GetUp()); }
};

// GeTempPrivateList4D - read only access

template<class TYPE>
class GeTempPrivateList4D : private GeToolList4D
{
	public:
		TYPE* GetFirst() const { return STATIC_CAST(TYPE*,GeToolList4D::GetFirst()); }
		TYPE* GetLast() const { return STATIC_CAST(TYPE*,GeToolList4D::GetLast()); }
		TYPE*	GetIndex(LONG index) const { return STATIC_CAST(TYPE*,GeToolList4D::GetIndex(index)); }
		LONG	GetCount(void) const { return GeToolList4D::GetCount(); }
};

// GeTempPublicNode4D - read & write access

template<class TYPE>
class GeTempPublicNode4D : private GeToolNode4D
{
	public:

		TYPE* GetNext() const { return STATIC_CAST(TYPE*,GeToolNode4D::GetNext()); }
		TYPE* GetPrev() const { return STATIC_CAST(TYPE*,GeToolNode4D::GetPrev()); }
		TYPE* GetDown() const { return STATIC_CAST(TYPE*,GeToolNode4D::GetDown()); }
		TYPE* GetUp() const { return STATIC_CAST(TYPE*,GeToolNode4D::GetUp()); }

		void	InsertBefore(TYPE *n) { GeToolNode4D::InsertBefore(STATIC_CAST(void*,n)); }
		void	InsertAfter(TYPE *n) { GeToolNode4D::InsertAfter(STATIC_CAST(void*,n)); }
		void	InsertUnder(TYPE *n) { GeToolNode4D::InsertUnder(STATIC_CAST(void*,n)); }
		void	InsertUnderLast(TYPE *n) { GeToolNode4D::InsertUnderLast(STATIC_CAST(void*,n)); }
		void	Remove(void) { GeToolNode4D::Remove(); }
};

// GeTempPublicList4D - read & write access

template<class TYPE>
class GeTempPublicList4D : private GeToolList4D
{
	public:
		TYPE* GetFirst() const { return STATIC_CAST(TYPE*,GeToolList4D::GetFirst()); }
		TYPE* GetLast() const { return STATIC_CAST(TYPE*,GeToolList4D::GetLast()); }
		TYPE* GetIndex(LONG index) const { return STATIC_CAST(TYPE*,GeToolList4D::GetIndex(index)); }
		LONG GetCount(void) const { return GeToolList4D::GetCount(); }

		void Insert(TYPE *n) { GeToolList4D::Insert(STATIC_CAST(void*,n)); }
		void Append(TYPE *n) { GeToolList4D::Append(STATIC_CAST(void*,n)); }
		
		void FlushAll(void) { GeToolList4D::FlushAll(); }
		void RemoveAll(void) { GeToolList4D::RemoveAll(); }
};

// nodes with additional type info

template<class TYPE, class CLASS>
class GeTempExtPrivateNode4D : public GeTempPrivateNode4D<CLASS>
{
	public:
		const TYPE&	GetType(void) const { return type; }
		void				SetType(const TYPE &p_type) { type = p_type; }

	private:
		TYPE type;
};

template<class TYPE, class CLASS>
class GeTempExtPublicNode4D : public GeTempPublicNode4D<CLASS>
{
	public:
		const TYPE&	GetType(void) const { return type; }
		void				SetType(const TYPE &p_type) { type = p_type; }

	private:
		TYPE type;
};

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

template<class TYPE>
void GeTempSwap(TYPE& a,TYPE& b)
{
	TYPE t = a; a = b; b = t;
}

class GeToolDynArray
{
	friend class GeToolDynClassArray;

	private:
		void** 	array;
		LONG 		count; // actual array entries 
		LONG		size;  // allocated array entries
		LONG		init;  // nr of entries for the first alloc
		LONG		step;  // enlarge quantum for succeding allocs 
				
	protected:
		GeToolDynArray(LONG p_init = 1, LONG p_step = 0) : array(NULL), count(0), size(0), init(p_init), step(p_step) { }
		virtual ~GeToolDynArray(void);

		void** GetRoot() { return array; }

		void  SetAlloc(LONG p_init = 1, LONG p_step = 0) { init = p_init; step = p_step; }
		LONG	GetCount(void) const { return count; }
		void* GetIndex(LONG i) const { if (i >= 0 && i < count) return array[i]; return NULL; }
		void* GetFirst(void) const { if (count > 0) return array[0]; return NULL; }
		void* GetLast(void) const { if (count > 0) return array[count - 1]; return NULL; }

		Bool 	SetIndex(LONG i, void *e) const { if (i < 0 || i >= count) return FALSE; array[i] = e; return TRUE;}
		Bool 	SetIndexEnlarge(LONG i, void *e);

		void 	Swap(LONG a, LONG b); 		
		void 	Move(LONG source, LONG dest); 		
		void  Sort(LONG (*compare)(void *a, void *b));
		void* Search(void *key,LONG (*search)(void *a, void *b));

		void* Pop(void);		
		Bool 	Append(void *e);
		Bool 	Insert(void *e, LONG n);
		Bool 	Remove(LONG n);
		Bool	Remove(void *e);
		LONG	Find(const void *e) const;

		void 	ResetCount(void);
		void 	FlushThis(void);

		Bool	CopyTo(GeToolDynArray *dest) const;

	private:
		Bool Enlarge(void);
};

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

template<class TYPE>
class GeTempDynArray : private GeToolDynArray
{
	protected:
		void** GetRoot() { return GeToolDynArray::GetRoot(); }

	public:
		GeTempDynArray(LONG p_init = 1, LONG p_step = 0) : GeToolDynArray(p_init,p_step) { }

		void  SetAlloc(LONG p_init = 1, LONG p_step = 0) { GeToolDynArray::SetAlloc(p_init,p_step); }
		LONG	GetCount(void) const { return GeToolDynArray::GetCount(); }
		TYPE* GetIndex(LONG i) const { return STATIC_CAST(TYPE*,GeToolDynArray::GetIndex(i)); }
		TYPE* GetFirst(void) const { return STATIC_CAST(TYPE*,GeToolDynArray::GetFirst()); }
		TYPE* GetLast(void) const { return STATIC_CAST(TYPE*,GeToolDynArray::GetLast()); }
		Bool 	SetIndex(LONG i, TYPE *e) const {return GeToolDynArray::SetIndex(i,STATIC_CAST(void*,e));}
		Bool 	SetIndexEnlarge(LONG i, TYPE *e) {return GeToolDynArray::SetIndexEnlarge(i,STATIC_CAST(void*,e));}

		void 	Swap(LONG a, LONG b) { GeToolDynArray::Swap(a,b); }
		void 	Move(LONG source, LONG dest) { GeToolDynArray::Move(source,dest); }
		void  Sort(LONG (*compare)(TYPE **a,TYPE **b)) { GeToolDynArray::Sort((LONG (*)(void *a,void *b))compare); }
		TYPE** Search(void *key,LONG (*search)(void *key, TYPE **b)) { return (TYPE**)GeToolDynArray::Search(key,(LONG (*)(void *a,void *b))search); }
				
		Bool 	Append(TYPE *e) { return GeToolDynArray::Append(STATIC_CAST(void*,e)); }
		TYPE*	AppendNew() { TYPE *e = gNew TYPE; if (!e) return NULL; if (!Append(e)) gDelete(e); return e; }

		Bool 	Insert(TYPE *e, LONG n) { return GeToolDynArray::Insert(STATIC_CAST(void*,e),n); }
		Bool 	Remove(LONG n) { return GeToolDynArray::Remove(n); }
		Bool 	Remove(TYPE *e) { return GeToolDynArray::Remove(STATIC_CAST(void*,e)); }
		LONG	Find(const TYPE *e) const { return GeToolDynArray::Find((void*)e); }
		void 	ResetCount(void) { GeToolDynArray::ResetCount(); }
		void 	FlushThis(void) { GeToolDynArray::FlushThis(); }
		Bool  CopyTo(GeTempDynArray *dest) const { return GeToolDynArray::CopyTo(dest); }

		void 	FlushAll(void)
		{
			TYPE *c; LONG i;

			for (i = 0; i < GeToolDynArray::GetCount(); ++i)
			{
				c = STATIC_CAST(TYPE*,GeToolDynArray::GetIndex(i)); gDelete(c);
			}
			GeToolDynArray::FlushThis();
		}

		TYPE* operator [] (LONG l) { return GetIndex(l); }
		const TYPE* operator [] (LONG l) const { return GetIndex(l); }
};

template<class TYPE>
class GeTempDynStack : private GeToolDynArray
{
	public:
		GeTempDynStack(LONG p_init = 1, LONG p_step = 0) : GeToolDynArray(p_init,p_step) { }

		void  SetAlloc(LONG p_init = 1, LONG p_step = 0) { GeToolDynArray::SetAlloc(p_init,p_step); }
		LONG	GetCount(void) const { return GeToolDynArray::GetCount();}
		TYPE* GetIndex(LONG i) const { return STATIC_CAST(TYPE*,GeToolDynArray::GetIndex(i)); }
		TYPE* GetFirst(void) const { return STATIC_CAST(TYPE*,GeToolDynArray::GetFirst()); }
		TYPE* GetLast(void) const { return STATIC_CAST(TYPE*,GeToolDynArray::GetLast()); }

		void 	Swap(LONG a, LONG b) { GeToolDynArray::Swap(a,b); }

		Bool 	Push(TYPE *e) { return GeToolDynArray::Append(STATIC_CAST(void*,e)); }
		TYPE* Pop(void) { return STATIC_CAST(TYPE*,GeToolDynArray::Pop()); }
		void 	ResetCount(void) { GeToolDynArray::ResetCount(); }
		void 	FlushThis(void) { GeToolDynArray::FlushThis(); }
		Bool  CopyTo(GeTempDynStack *dest) const { return GeToolDynArray::CopyTo(dest); }

		void 	FlushAll(void)
		{
			TYPE *c; LONG i;

			for (i = 0; i < GeToolDynArray::GetCount(); ++i)
			{
				c = STATIC_CAST(TYPE*,GeToolDynArray::GetIndex(i)); gDelete(c);
			}
			GeToolDynArray::FlushThis();
		}
};



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

#include "ge_sort.h"


template <class CLASS,class TYPE> class GeToolTempDynSortArraySort : public GeSortAndSearch
{
	CLASS *ptr;
	LONG (CLASS::*compare_func)(TYPE *a,TYPE *b);

public:
	GeToolTempDynSortArraySort(CLASS *t_ptr,LONG (CLASS::*compare)(TYPE *a, TYPE *b)) : ptr(t_ptr), compare_func(compare) { }

	LONG Compare(void *a, void *b) { return (ptr->*compare_func)(*(TYPE**)a,*(TYPE**)b); }
};

template <class CLASS,class TYPE,class SEARCH> class GeToolTempDynSortArraySearch : public GeSortAndSearch
{
	CLASS *ptr;
	LONG (CLASS::*compare_func)(SEARCH *a,TYPE *b);

public:
	GeToolTempDynSortArraySearch(CLASS *t_ptr,LONG (CLASS::*search)(SEARCH *a, TYPE *b)) : ptr(t_ptr), compare_func(search) { }

	LONG Compare(void *a, void *b) { return (ptr->*compare_func)((SEARCH*)a,*(TYPE**)b); }
};



template <class TYPE,class SEARCH,int FLUSH> class GeTempDynSortSearchArray : private GeTempDynArray<TYPE>
{
	Bool m_sorted;

	void CheckSort()
	{
		if (!m_sorted)
		{
			GeToolTempDynSortArraySort<GeTempDynSortSearchArray<TYPE,SEARCH,FLUSH>,TYPE> sort(this,&GeTempDynSortSearchArray<TYPE,SEARCH,FLUSH>::CompareFunc);
			sort.Sort(GeTempDynArray<TYPE>::GetRoot(),GeTempDynArray<TYPE>::GetCount(),sizeof(TYPE*));

			((GeTempDynSortSearchArray*)this)->m_sorted = TRUE;	
		}
	}

private:

	// OVERRIDE THIS
	virtual LONG CompareFunc(TYPE *aa,TYPE *bb) = 0;
	virtual LONG SearchFunc(SEARCH *data,TYPE *bb) = 0;
	// OVERRIDE THIS

public:
	GeTempDynSortSearchArray()
	{
		m_sorted = FALSE;
	}

	~GeTempDynSortSearchArray()
	{
		if (FLUSH)
			FlushAll();
	}

	void FlushAll()
	{
		GeTempDynArray<TYPE>::FlushAll();
		m_sorted = FALSE; 
	}

	void FlushThis()
	{
		GeTempDynArray<TYPE>::FlushThis();
		m_sorted = FALSE; 
	}

	Bool Append(TYPE *vi)
	{
		m_sorted = FALSE; 
		return GeTempDynArray<TYPE>::Append(vi);			
	}

	Bool Remove(TYPE *vi)
	{
		return GeTempDynArray<TYPE>::Remove(vi);
	}

	Bool Remove(LONG i)
	{
		return GeTempDynArray<TYPE>::Remove(i);
	}

	TYPE *GetIndex(LONG i)
	{
		return GeTempDynArray<TYPE>::GetIndex(i);
	}

	const TYPE *GetIndex(LONG i) const
	{
		return GeTempDynArray<TYPE>::GetIndex(i);
	}

	LONG GetIndex(const TYPE *o) const
	{
		return GeTempDynArray<TYPE>::Find(o);
	}

	TYPE* operator [] (LONG i)
	{
		return GeTempDynArray<TYPE>::GetIndex(i);
	}

	const TYPE* operator [] (LONG i) const
	{
		return GeTempDynArray<TYPE>::GetIndex(i);
	}

	LONG GetCount() const
	{
		return GeTempDynArray<TYPE>::GetCount();
	}

	TYPE *Find(SEARCH data, TYPE ***ptr=NULL)
	{
		CheckSort();

		GeToolTempDynSortArraySearch<GeTempDynSortSearchArray<TYPE,SEARCH,FLUSH>,TYPE,SEARCH> sort(this,&GeTempDynSortSearchArray<TYPE,SEARCH,FLUSH>::SearchFunc);
		TYPE** res = (TYPE**)sort.Search(&data,GeTempDynArray<TYPE>::GetRoot(),GeTempDynArray<TYPE>::GetCount(),sizeof(TYPE*));
		if (res)
		{
			if (ptr) *ptr = res;
			return *res;
		}
		if (ptr) *ptr = NULL;
		return NULL;
	}

	const TYPE *Find(SEARCH data, const TYPE ***ptr=NULL) const { return (const TYPE*)((GeTempDynSortSearchArray*)this)->Find(data,(TYPE ***)ptr); }

	TYPE* AppendNew() { m_sorted = FALSE; return GeTempDynArray<TYPE>::AppendNew(); }

	void Sort() { CheckSort(); }

	// important! call this if elements has been changed and array need to be resorted!
	void SortChanged() { m_sorted = FALSE; }

};

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

#endif //#ifndef __GE_MTOOLS_H

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