instlist.h

跨平台2D引擎

//instList.h
#ifndef INST_LIST_H
#define INST_LIST_H


#include <instTypes.h>
#include <instDefines.h>


namespace inst
{


template <class T> class IIterator
{
public:
	virtual ~IIterator(){}
	virtual T Get()const=0;
	virtual void Set(T val)=0;
	virtual T Prev()=0;
	virtual T Next()=0;
	virtual UInt32 GetIndex()const=0;
};

template <class T> class IList
{
public:
	virtual ~IList(){}
	virtual void Add(T item)=0;
	virtual void Remove(UInt32 index)=0;
	virtual void Clear()=0;
	virtual UInt32 Count()const=0;
//	virtual void Resize(UInt32 newsize,T defaultval=0)=0;
	virtual T Get(UInt32 index)const=0;
	virtual void Set(UInt32 index,T val)=0;
	virtual Bool Find(T val,UInt32 *pindex=null)const=0;
	virtual Bool FindRemove(T val,UInt32 *pindex=null)=0;
	virtual void Insert(UInt32 index,T item)=0; //insert BEFORE index
/*
	virtual T GetMin()const=0;
	virtual void SetMin(T val)=0;
	virtual T GetMax()const=0;
	virtual void SetMax(T val)=0;
	virtual T PopMin()=0;
	virtual T PopMax()=0;
	virtual void PushMin(T item)=0;
	virtual void PushMax(T item)=0; */
	//----------------------------------
	virtual IIterator<T> *GetIterator(UInt32 index)const=0;
	virtual IIterator<T> *FindIterator(T val)const=0;
};

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

template <class T> class ArrayList:public IList<T>
{
public:
	ArrayList();
	virtual ~ArrayList();
	virtual void Add(T val);
	virtual void Remove(UInt32 index);
	virtual void Clear();
	virtual UInt32 Count()const{ return m_Count; }
	void Resize(UInt32 newsize,T defaultval=0);
	virtual T Get(UInt32 index)const{ if(index>=0&&index<m_Count)return m_pTs[index]; else return 0; }
	virtual void Set(UInt32 index,T val){ if(index>=0&&index<m_Count)m_pTs[index]=val; }	
	virtual Bool Find(T val,UInt32 *pindex=null)const;
	virtual Bool FindRemove(T val,UInt32 *pindex=null)
	{
		UInt32 index=0;
		if(!Find(val,&index))return False;
		Remove(index);
		if(pindex)*pindex=index;
		return True;
	}
	virtual void Insert(UInt32 index,T val);
/*
	virtual T GetMin()const{ return Get(0); }
	virtual void SetMin(T val){ Set(0,val) }
	virtual T GetMax()const{ if(0==m_Count)return 0; return Get(m_Count-1); }
	virtual void SetMax(T val){ if(0==m_Count)return; return Set(m_Count-1,val); }
	virtual T PopMin(){ if(0==m_Count)return 0; T tmp=[0]; Remove(0); return tmp; }
	virtual T PopMax(){ if(0==m_Count)return 0; T tmp=[m_Count-1]; Remove(m_Count); return tmp; }
	virtual void PushMin(T item){ return; }
	virtual void PushMax(T item); */
	//----------------------------------
	virtual IIterator<T> *GetIterator(UInt32 index)const{return null;};
	virtual IIterator<T> *FindIterator(T val)const{return null;};

private:
	T* m_pTs;
	UInt32 m_Count;
	
	template <class T> class _ArrayList_IIterator:virtual public IIterator<T>
	{
	public:
		virtual ~_ArrayList_IIterator(){}
		virtual T Get()const=0;
		virtual void Set(T val)=0;
		virtual T Prev()=0;
		virtual T Next()=0;
		virtual UInt32 GetIndex()const=0;
	};

};

template <class T> void ArrayList<T>::Resize(UInt32 newsize,T defaultval)
{
	if(newsize==m_Count)return;

	if(newsize==0)
	{
		SafeDelArray(m_pTs);
		return;
	}

	T* tmp=new T[newsize];
	UInt32 i;
	for(i=0;i<MIN(newsize,m_Count);i++)
		tmp[i]=m_pTs[i];
	if(newsize>m_Count)
	{
		for(i=m_Count;i<newsize;i++)
			tmp[i]=defaultval;
	}
	SafeDelArray(m_pTs);
	m_pTs=tmp;
	m_Count=newsize;
}

template <class T> ArrayList<T>::ArrayList()
{
	m_pTs=null;
	m_Count=0;
}
template <class T> ArrayList<T>::~ArrayList()
{
	SafeDelArray(m_pTs);
	m_Count=0;
}
template <class T> void ArrayList<T>::Add(T item)
{
	T* tmp=new T[m_Count+1];
	for(UInt32 i=0;i<m_Count;i++)
	{
		tmp[i]=m_pTs[i];
	};
	SafeDelArray(m_pTs);
	m_pTs=tmp;
	m_pTs[m_Count]=item; // m_Count(OLD)+1 -1 = m_Count(old)
	m_Count+=1;
}
template <class T> void ArrayList<T>::Clear()
{
	SafeDelArray(m_pTs);
}
template <class T> void ArrayList<T>::Remove(UInt32 index)
{
	if(index<0||index>=m_Count)return;

	if(0==m_Count)
	{
		SafeDelArray(m_pTs);
		return;
	}

	T* tmp=new T[m_Count-1];
	UInt32 i;
	for(i=0;i<index;i++)
		tmp[i]=m_pTs[i];
	if(index<m_Count-1)
		for(i=index+1;i<m_Count;i++)
			tmp[i-1]=m_pTs[i];
	m_Count-=1;
	SafeDelArray(m_pTs);
	m_pTs=tmp;
}

template <class T> Bool ArrayList<T>::Find(T val,UInt32 *pindex)const
{
	if(m_Count<=0)return False;
	for(UInt32 i=0;i<m_Count;i++)
		if(m_pTs[i]==val)
		{
			if(pindex)*pindex=i;
			return True;
		}
	return False;
}
template <class T> void ArrayList<T>::Insert(UInt32 index,T item)
{
	if(index<0||index>=m_Count)return;

	return;
}

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

template <class T> class SList:public IList<T>
{
public:
	SList();
	virtual ~SList(){}
	virtual void Add(T item);
	virtual void Remove(UInt32 index);
	virtual void Clear();
	virtual UInt32 Count()const{ return m_Count;	}
	virtual T Get(UInt32 index)const; //需要优化！
	virtual void Set(UInt32 index,T val); //需要优化！
	virtual Bool Find(T val,UInt32 *pindex=null)const;
	virtual Bool FindRemove(T val,UInt32 *pindex=null);
	virtual void Insert(UInt32 index,T item){}
/*
	virtual T GetMin()const{ if(!m_pFirst)return 0; return m_pFirst->m_Val; }
	virtual void SetMin(T val){ if(!m_pFirst)return; m_pFirst->m_Val=val; }
	virtual T GetMax()const{ if(!m_pEnd)return 0; return m_pEnd->m_Val; }
	virtual void SetMax(T val){ if(!m_pEnd)return; m_pEnd->m_Val=val; }
	virtual T PopMin(){ if(!m_pFirst)return 0; T tmp=m_pFirst->m_Val; Remove(0); }
	virtual T PopMax(){ if(!m_pEnd)return 0;  }
	virtual void PushMin(T item)
	{ 
		if(0==m_Count)PushFront(item);
	
		//.................
	}
	virtual void PushMax(T item); */
	//----------------------------------
	virtual IIterator<T> *GetIterator(UInt32 index)const{return null;};
	virtual IIterator<T> *FindIterator(T val)const{return null;};
private:
	template <class T> class SNode
	{
		friend class SList<T>;
	private:
		T m_Val;
		SNode<T> *m_pNext;
	};
	UInt32 m_Count;
	SNode<T> *m_pFirst,*m_pEnd;

	template <class T> class _SList_IIterator:virtual public IIterator<T>
	{
	public:
		virtual ~_SList_IIterator(){}
		virtual T Get()const=0;
		virtual void Set(T val)=0;
		virtual T Prev()=0;
		virtual T Next()=0;
		virtual UInt32 GetIndex()const=0;
	};

};

template <class T> SList<T>::SList()
{
	m_Count=0;
	m_pFirst=null;
	m_pEnd=null;
}

template <class T> void SList<T>::Add(T item)
{
	SNode<T> *tmp=new SNode<T>;
	tmp->m_Val=item;
	tmp->m_pNext=null;

	if(m_Count>0)
		m_pEnd->m_pNext=tmp;
	else
		m_pFirst=tmp;
	m_pEnd=tmp;

	m_Count++;
}

template <class T> void SList<T>::Remove(UInt32 index)
{
	if(index<0||index>=m_Count)return;
	
	UInt32 i;
	SNode<T> *tmp=null;

	if(index==0)
	{
		tmp=m_pFirst;
		m_pFirst=m_pFirst->m_pNext;

		if(tmp==m_pEnd)m_pEnd=null; //等价于if(0==m_Count-1) 等价于if(tmp->m_pNext==null) 等价于if(m_pFirst<新>==null) 
		SAFEDEL(tmp);
	}
	else
	{
		SNode<T> *prev=m_pFirst;
		for(i=1;i<=index-1;i++)
			prev=prev->m_pNext;
		tmp=prev->m_pNext;
		prev->m_pNext = tmp->m_pNext;

		if(tmp==m_pEnd)m_pEnd=prev; //等价于if(index==m_Count-1) 等价于if(tmp->m_pNext==null) 等价于if(prev->m_pNext<新>==null)
		SAFEDEL(tmp); //这是在Add的时候创建的SNode
	}

	m_Count--;
/* also can :
	SNode<T> **pp;

	if(index==0)
	{
		pp = &(m_pFirst->m_pNext);
	}
	else
	{
		pp=&m_pFirst;
		for(i=0;i<=index-1;i++)
			pp = &( (*pp)->m_pNext );
	}

	*pp = (*pp)->m_pNext;
	if(index==m_Count-1)m_pEnd = *pp;
*/
}

template <class T> void SList<T>::Clear()
{
	if(!m_pFirst)return;

	SNode<T> *tmp1,*tmp2;
	tmp1=m_pFirst;
	do
	{
		tmp2=tmp1->m_pNext;
		SafeDel(tmp1);
		tmp1=tmp2;
	}while(tmp2);

	m_Count=0;
}

template <class T> T SList<T>::Get(UInt32 index)const
{
	if(index<0||index>=m_Count)return 0;
	
	UInt32 i;
	if(index==0)return m_pFirst->m_Val;
	if(index==m_Count-1)return m_pEnd->m_Val;
	SNode<T> *tmp;
	tmp=m_pFirst;
	for(i=0;i<=index-1;i++)
		tmp=tmp->m_pNext;
	return tmp->m_Val;
}

template <class T> void SList<T>::Set(UInt32 index,T val)
{
	if(index<0||index>=m_Count)return;

	UInt32 i;
	if(index==1)
	{
		m_pFirst->m_Val=val;
		return; 
	}
	if(index==m_Count-1)
	{
		m_pEnd->m_Val=val;
		return;
	}
	SNode<T> *tmp;
	tmp=m_pFirst;
	for(i=0;i<=index-1;i++)
		tmp=tmp->m_pNext;
	tmp->m_Val=val;
}

template <class T> Bool SList<T>::Find(T val,UInt32 *pindex)const
{
	if(m_Count<=0)return False;
	
	SNode<T> *tmp=m_pFirst;
	for(UInt32 i=0;i<m_Count;i++)
	{
		if(tmp->m_Val==val)
		{
			if(pindex)*pindex=i;
			return True;
		}
		tmp=tmp->m_pNext;
	}
	return False;
}

template <class T> Bool SList<T>::FindRemove(T val,UInt32 *pindex)
{
	if(m_Count<=0)return False;
	
	SNode<T> *tmp=null;

	if(m_pFirst->m_Val==val)
	{
		
		if(pindex)*pindex=0;

		tmp=m_pFirst;
		m_pFirst=m_pFirst->m_pNext;
		
		if(tmp==m_pEnd)m_pEnd=null; //等价于if(0==m_Count-1) 等价于if(tmp->m_pNext==null) 等价于if(m_pFirst<新>==null) 
		SAFEDEL(tmp);
	
		m_Count--;
		return True;
	
	}
	else
	{

		SNode<T> *prev=m_pFirst;
		for(UInt32 i=0;i<m_Count;i++)
		{
			if(prev->m_pNext->m_Val==val)
			{

				if(pindex)*pindex=i+1;
				
				tmp=prev->m_pNext;
				prev->m_pNext = tmp->m_pNext;

				if(tmp==m_pEnd)m_pEnd=prev; //等价于if(index==m_Count-1) 等价于if(tmp->m_pNext==null) 等价于if(prev->m_pNext<新>==null)
				SAFEDEL(tmp); //这是在Add的时候创建的SNode

				m_Count--;
				return True;

			}
			prev=prev->m_pNext;
		}

	}

	return False;
}

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

template <class T> class ArrayQueue;
template <class T> class Queue;

template <class T> class IQueue
{
	friend class ArrayQueue<T>;
	friend class Queue<T>;
public:
	virtual ~IQueue(){}
	virtual void Post(T item)=0;
	virtual T Peek(Bool remove)=0;
	virtual void Clear()=0;
	virtual UInt32 Count()const=0;
private:
	template <class T,class _L> class _Queue:public IQueue<T>
	{
		_L m_List;
	public:
		virtual ~_Queue(){}
		virtual void Post(T item){ m_List.Add(item); }
		virtual T Peek(Bool remove)
		{
			T tmp=m_List.Get(0); //如果list为空则返回0
			if(remove)m_List.Remove(0); //如果list为空则无操作
			return tmp;
		}
		virtual void Clear(){ m_List.Clear(); }
		virtual UInt32 Count()const{ return m_List.Count(); }
	};
};

template <class T> class ArrayQueue:public IQueue::_Queue<T,ArrayList<T>>
{
};

template <class T> class Queue:public IQueue::_Queue<T,SList<T>>
{
};


}// end of namespace inst


#endif //INST_LIST_H