arraylist.h

C# ArrayList C++模仿版

//ArrayList Class
//By Justin Lee 2008-11

#define _IN_
#define _OUT_
template<class Type>
class ArrayList{
	//ArrayListClass:Like System.Collections.ArrayList class of .NET
	//But U should manage object space yourself(in other means it would not free object automaticly)
	//We insist you pass pointer type rather than object itself
private:
	void* m_pData;
#ifndef AL_FAILED//If a Method failed,this value returned
#define AL_FAILED -1
#endif
public:
	//Constructure Method,Not call by yourself
	ArrayList();

	//Destructure Method,Not call by yourself
	~ArrayList();

	//Copy al to current ArrayList
	void Clone(
		_IN_ ArrayList<Type>& al
		);
	
	//Inside Method,Not call for normally utility
	void* Get_Inside_Data();
	

	//Get The number of members in ArrayList
	unsigned long GetLength();
	
	//Get Part of ArrayList
	//Return a new ArrayList
	ArrayList<Type> GetSubList(
		_IN_ unsigned long position,
		_IN_ unsigned long length
		);
	
	//Get Part of ArrayList
	//The results will saved in a pointer array
	unsigned long GetSubList(
		_IN_ unsigned long position,
		_IN_ unsigned long length,
		_OUT_ Type** pointer_array,
		_IN_ unsigned long array_length
		);
	
	//Insert some members
	//You should saved their pointers in an array first
	unsigned long Insert(
		_IN_ unsigned long position,
		_IN_ unsigned long length,
		_IN_ Type** pointer_array,
		_IN_ unsigned long array_length
		);
	
	//Insert an arraylist
	unsigned long Insert(
		_IN_ unsigned long position,
		_IN_ ArrayList<Type>& al
		);
	
	//Remove some members
	unsigned long Remove(
		_IN_ unsigned long position,
		_IN_ unsigned long length
		);
	
	//Copy the ArrayList
	ArrayList<Type>& operator=(
		_IN_ const ArrayList<Type>& al
		)
	{
		Clone((ArrayList<Type>&)al);
		return *this;
	};

	//Append a ArrayList to the end of ArrayList
	ArrayList<Type>& operator+(
		_IN_ const ArrayList<Type>& al
		)
	{
		unsigned long l=GetLength();
		Insert(l,(ArrayList<Type>&)al);
		return *this;
	};

	//Like method above
	ArrayList<Type>& operator+=(
		_IN_ const ArrayList<Type>& al
		)
	{
		return *this+al;
	};

	//Refresh the ArrayList for merging the pointers inside
	//This Method can free some space when your operate an ArrayList too much
	//These space may come from many rubbish pointers inside
	void Refresh();

	//Clear the List
	void Clear();

	//Get a Member from the ArrayList
	Type& operator[](
		_IN_ unsigned long i
		);
};


//Implement:
////////////////////////////////////////////////////////////////
//Base functions
#ifdef WIN32
#include<windows.h>

size_t getpagesize(void){
	SYSTEM_INFO si;
	GetSystemInfo(&si);
	return (size_t)si.dwPageSize;
}
#else
#include<unistd.h>
#endif

#include<exception>
#include<memory.h>
#include<stdlib.h>
#include<math.h>
#include<vector>

static size_t PAGE_SIZE=0;
static size_t NODE_SIZE=0;

typedef struct n_ode{
	unsigned long *length;
	unsigned long *size;
	n_ode **parent;
	n_ode **next;
	void **data;
}NODE_MT_,*PNODE_MT_;

typedef struct mgr_tree{
	PNODE_MT_ pParent;
	PNODE_MT_ pChild;
	unsigned long length;
}MT_OBJ,*PMT_OBJ;

#define _MT_LENGTH_ 0
#define _MT_SIZE_ 1
#define _MT_PARENT_ 2
#define _MT_NEXT_ 3
#define _MT_DATA_ 4

void MT_Init()
{
	if(PAGE_SIZE==0||NODE_SIZE==0){
		PAGE_SIZE=(unsigned long)getpagesize()-0x80;
		NODE_SIZE=(PAGE_SIZE/sizeof(void*))-4;
	}
}

inline bool MT_FillN(void** PN,PNODE_MT_ pn)
{
	if(PN==NULL||pn==NULL)
		return false;
	try{
		pn->length=(unsigned long*)&PN[_MT_LENGTH_];
		pn->size=(unsigned long*)&PN[_MT_SIZE_];
		pn->parent=(PNODE_MT_*)&PN[_MT_PARENT_];
		pn->next=(PNODE_MT_*)&PN[_MT_NEXT_];
		pn->data=(void**)&PN[_MT_DATA_];
	}
	catch(...)
	{
		return false;
	}
	return true;
}

inline PNODE_MT_ MT_Get_Node(PMT_OBJ po,unsigned long i,unsigned long& k)
{
	PMT_OBJ pt=po;
	PNODE_MT_ pn=pt->pParent,pc=NULL;
	unsigned long j=0,l=0,len=0;
	while(pn!=NULL){
		l+=*pn->length;
		if(l>i){
			len=*pn->size;
			i-=l-(*pn->length);
			l=0;
			for(j=0;j<len;j++){
				pc=(PNODE_MT_)pn->data[j];
				l+=*pc->length;
				if(l>i){
					k=i+(*pc->length)-l;
					break;
				}
			}
			return pc;
		}
		pn=*pn->next;
	}
	return NULL;
}

inline void* MT_Get(PMT_OBJ po,unsigned long i)
{
	if(po==NULL)
		return NULL;
	if(po->length<=i)
		return NULL;
	PNODE_MT_ pn;
	unsigned long k;
	pn=MT_Get_Node(po,i,k);
	return pn->data[k];
}

inline void MT_Get(PMT_OBJ po,void** ptrarray,unsigned long i,unsigned long l)
{
	if(po==NULL)
		return;
	if(po->length<=i)
		return;
	PNODE_MT_ pn;
	unsigned long k,len;
	pn=MT_Get_Node(po,i,k);
	if(l<(*pn->length)-k){
		memcpy(ptrarray,&pn->data[k],l*sizeof(void*));
		return;
	}
	len=(*pn->length)-k;
	memcpy(ptrarray,&pn->data[k],len*sizeof(void*));
	ptrarray=&ptrarray[len];
	l-=len;
	len=0;
	pn=*pn->next;
	while(pn!=NULL){
		len+=(*pn->length);
		if(len>=l){
			l-=len-(*pn->length);
			memcpy(ptrarray,pn->data,l*sizeof(void*));
			return;
		}
		memcpy(ptrarray,pn->data,(*pn->length)*sizeof(void*));
		ptrarray=&ptrarray[*pn->length];
		pn=*pn->next;
	}
}

inline void MT_Delete_Node(PNODE_MT_ pn)
{
	try{
		free(pn->length);
		free(pn);
	}
	catch(...){
		return;
	}
}

inline PNODE_MT_ MT_Create_Node()
{
	PNODE_MT_ pn=(PNODE_MT_)malloc(sizeof(NODE_MT_));
	void** PN=(void**)malloc(PAGE_SIZE);
	memset((void*)PN,0,PAGE_SIZE);
	if(!MT_FillN(PN,pn)){
		free(pn);
		free(PN);
		return NULL;
	}
	return pn;
}

inline PNODE_MT_ MT_Create_Node(void** ptrarray,unsigned long l)
{
	PNODE_MT_ pn=MT_Create_Node();
	*pn->length=l;
	*pn->size=l;
	memcpy((void*)pn->data,ptrarray,l*sizeof(void*));
	return pn;
}

inline PNODE_MT_ MT_Create_List(void** ptrarray,unsigned long l,PNODE_MT_* plast=NULL)
{
	PNODE_MT_ pn=NULL,pb=NULL,ph=NULL;
	unsigned long left=l%NODE_SIZE;
	bool end=false;
	do{
		if(l<=left){
			pn=MT_Create_Node(ptrarray,left);
			*pn->length=left;
			*pn->size=left;
			ptrarray=&ptrarray[left];
			end=true;
		}
		else{
			pn=MT_Create_Node(ptrarray,NODE_SIZE);
			*pn->length=NODE_SIZE;
			*pn->size=NODE_SIZE;
			ptrarray=&ptrarray[NODE_SIZE];
		}
		if(ph==NULL){
			ph=pn;
		}
		if(pb!=NULL){
			*pb->next=pn;
		}
		pb=pn;
		l-=NODE_SIZE;
	}while(!end);
	if(plast!=NULL){
		*plast=pn;
	}
	return ph;
}

inline void MT_Delete_List(PNODE_MT_ pi,unsigned i,unsigned long l)
{
	unsigned long left=0,more=0,k=0;
	PNODE_MT_ pn=*pi->next,pb=NULL;
	if(i+l<=*pi->length){
		memcpy(&pi->data[i],&pi->data[i+l],((*pi->length)-i-l)*sizeof(void*));
		*pi->length-=l;
		*pi->size=*pi->length;
		memset(&pi->data[*pi->length],0,(NODE_SIZE-(*pi->length))*sizeof(void*));
		return;
	}
	more=(*pi->length)-i;
	left=l-more;
	memset(&pi->data[i],0,more*sizeof(void*));
	*pi->length=i;
	*pi->size=i;
	while(1){
		k+=*pn->length;
		if(k>=left){
			left=k-left;
			break;
		}
		pb=*pn->next;
		MT_Delete_Node(pn);
		pn=pb;
	}
	if(left<NODE_SIZE-i){
		memcpy(&pi->data[i],&pn->data[(*pn->length)-left],left*sizeof(void*));
		*pi->length+=left;
		*pi->size=*pi->length;
		*pi->next=*pn->next;
		MT_Delete_Node(pn);
		return;
	}
	*pi->next=pn;
	memcpy(pn->data,&pn->data[(*pn->length)-left],left*sizeof(void*));
	memset(&pn->data[left],0,((*pn->length)-left)*sizeof(void*));
	*pn->length=left;
	*pn->size=left;
}

inline void MT_Insert_List(PNODE_MT_ pi,unsigned i,PNODE_MT_ pit)
{
	void** buf=(void**)malloc(NODE_SIZE*sizeof(void*));
	memset(buf,0,NODE_SIZE*sizeof(void*));
	unsigned long len=*pi->length,more=0,left=NODE_SIZE-i;
	memcpy(buf,&pi->data[i],(len-i)*sizeof(void*));
	more=len-i;
	PNODE_MT_ pn=NULL,pb=NULL,pl=NULL,pt=NULL;
	*pi->length=i;
	*pi->size=i;
	while(left>=*pit->length){
		memcpy(&pi->data[i],pit->data,(*pit->length)*sizeof(void*));
		left-=*pit->length;
		i+=*pit->length;
		*pi->length+=*pit->length;
		*pi->size=*pi->length;
		pit=*pit->next;
		if(pit==NULL){
			break;
		}
	}
	pb=*pi->next;
	while(pit!=NULL){
		pn=MT_Create_Node();
		memcpy(pn->data,pit->data,(*pit->size)*sizeof(void*));
		*pn->length=*pit->size;
		*pn->size=*pit->size;
		*pi->next=pn;
		pi=*pi->next;
		pit=*pit->next;
	}
	if((*pi->length)<=NODE_SIZE-more){
		memcpy(&pi->data[*pi->length],buf,more*sizeof(void*));
		*pi->length+=more;
		*pi->size=*pi->length;
	}
	else{
		pn=MT_Create_Node();
		*pn->length=more;
		*pn->size=more;
		memcpy(pn->data,buf,more*sizeof(void*));
		*pi->next=pn;
		pi=*pi->next;
	}
	*pi->next=pb;
	free(buf);
}

inline void MT_Refresh_List(PNODE_MT_ pch)
{
	PNODE_MT_ pn=*pch->next,pt=NULL;
	while(pn!=NULL){
		if((*pn->length)+(*pch->length)<=NODE_SIZE){
			memcpy(&pch->data[*pch->length],pn->data,(*pn->length)*sizeof(void*));
			*pch->length+=*pn->length;
			*pch->size=*pch->length;
			pt=*pn->next;
			MT_Delete_Node(pn);
			pn=pt;
		}
		else{
			*pch->next=pn;
			pch=pn;
			pn=*pn->next;
		}
	}
}

inline void MT_Insert_List(PNODE_MT_ pi,unsigned i,void** ptrarray,unsigned long l)
{
	void** buf=(void**)malloc(NODE_SIZE*sizeof(void*));
	memset(buf,0,NODE_SIZE*sizeof(void*));
	unsigned long len=*pi->length,more=0,left=0;
	PNODE_MT_ pn=NULL,pb=NULL,pl=NULL,pt=NULL;
	if(l+i<NODE_SIZE){
		if(l+len<NODE_SIZE){
			memcpy(&pi->data[i+l+1],&pi->data[i+1],(len-i-1)*sizeof(void*));
			memcpy(&pi->data[i+1],ptrarray,l*sizeof(void*));
			*pi->length+=l;
			*pi->size+=l;
			free(buf);
			return;
		}
		else{
			pn=MT_Create_Node();
			memcpy(buf,&pi->data[NODE_SIZE-l],(len+l-NODE_SIZE)*sizeof(void*));
			memcpy(&pi->data[i+l+1],&pi->data[i+1],(NODE_SIZE-l-i-1)*sizeof(void*));
			memcpy(&pi->data[i+1],ptrarray,l*sizeof(void*));
			*pi->length=NODE_SIZE;
			*pi->size=NODE_SIZE;
			pb=*pi->next;
			*pi->next=pn;
			*pn->next=pb;
			memcpy(pn->data,buf,(len+l-NODE_SIZE)*sizeof(void*));
			*pn->length=(len+l-i-1);
			*pn->size=*pn->length;
			free(buf);
			return;
		}
	}
	left=(len-i-1);
	memcpy(buf,&pi->data[i+1],left*sizeof(void*));
	memcpy(&pi->data[i+1],ptrarray,(NODE_SIZE-i-1)*sizeof(void*));
	ptrarray=&ptrarray[NODE_SIZE-i-1];
	l-=NODE_SIZE-i-1;
	*pi->length=NODE_SIZE;
	*pi->size=NODE_SIZE;
	pn=MT_Create_List(ptrarray,l,&pl);
	pb=*pi->next;
	*pi->next=pn;
	len=*pl->length;
	if(len>NODE_SIZE-left){
		pt=MT_Create_Node();
		memcpy(&pl->data[len],buf,(NODE_SIZE-len)*sizeof(void*));
		*pl->length=NODE_SIZE;
		*pl->size=NODE_SIZE;
		*pl->next=pt;
		memcpy(pt->data,&buf[NODE_SIZE-len],(left+len-NODE_SIZE)*sizeof(void*));
		*pt->length=(left+len-NODE_SIZE);
		*pt->size=*pt->length;
		pl=pt;
	}
	else{
		memcpy(&pl->data[len],buf,(left)*sizeof(void*));
		*pl->length=(unsigned long)(*pl->length)+left;
		*pl->size=*pl->length;
	}
	*pl->next=pb;
	free(buf);
}

inline MT_OBJ MT_Refresh_OBJ(PNODE_MT_ pfh,PNODE_MT_ pch,PNODE_MT_* pfl=NULL,PNODE_MT_* pcl=NULL)
{
	unsigned long i=0,l=0;
	if(pfh==NULL)
		pfh=MT_Create_Node();
	PNODE_MT_ pn=NULL,pf=pfh,pc=pch;
	*pf->length=0;
	*pf->size=0;
	while(pc!=NULL){
		if(i>=NODE_SIZE){
			pn=pf;
			pf=MT_Create_Node();
			*pn->next=pf;