#include <stdio.h>
#include <stdlib.h>
#include <list>

#include <windows.h>

using namespace std;

#define ESTIMATE_LOOP	6000
#define TEST_COUNT		10
#define MAX_OBJ			2000

class Cobj
 {
 public:
	virtual bool process(void) =0;
 };

class Cchara : public Cobj
 {
 public:
	bool process(void);
 };

// for STL code
list<Cobj*> objs;

// for ARRAY code
typedef struct tag_SObjectCell
 {
	Cobj *obj;
	struct tag_SObjectCell *next;
 } SObjectCell, *SObjectCellPtr;

SObjectCell pAllObject[MAX_OBJ];
SObjectCellPtr freeList;
SObjectCellPtr enableList;

bool Cchara::process(void)
 {
	int mode = rand( ) & 255;
	if(mode < 4)
		return false;
	else if(mode < 8)
	 {
		for(int i = 0; i < 10; i ++)
			if(objs.size( ) < MAX_OBJ)
				objs.push_back((Cobj*)new Cchara);
	 }
	return true;
 }

void connect_link(void)
 {
	int i;
	for(i = 0; i < MAX_OBJ -1; i ++)
	 {
		pAllObject[i].obj = NULL;
		pAllObject[i].next = &(pAllObject[i +1]);
	 }
	pAllObject[MAX_OBJ -1].obj = NULL;
	pAllObject[MAX_OBJ -1].next = NULL;
	freeList = &(pAllObject[0]);
	enableList = NULL;
 }

void push_back(Cobj *obj)
 {
	if(freeList == NULL)
	 {
		delete obj;
		return;
	 }

	SObjectCellPtr ptr = freeList;
	freeList = freeList->next;
	ptr->next = enableList;
	enableList = ptr;
	ptr->obj = obj;
 }

void main(void)
 {
	int test, i, loop;
	DWORD start[TEST_COUNT][2], end[TEST_COUNT][2];

	for(test = 0; test < TEST_COUNT; test ++)
	 {
		srand(0);

		// using ARRAY code
		connect_link( );
		for(i = 0; i < 10; i ++)
			push_back((Cobj*)new Cchara);

		start[test][1] = timeGetTime( );
		for(loop = 0; loop < ESTIMATE_LOOP; loop ++)
		 {
			SObjectCellPtr* ptr = &(enableList);
			while(*ptr != NULL)
			 {
				if((*ptr)->obj->process( ) == false)
				 {
					// まず、オブジェクトを解放
					delete (*ptr)->obj;
					(*ptr)->obj = NULL;
	
					// 空きセルに追加
					SObjectCellPtr link = (*ptr)->next;
					(*ptr)->next = freeList;
					freeList = *ptr;

					// 削除したリストを直す
					*ptr = link;
				 }
				else
					ptr = &((*ptr)->next);
			 }
		 }
		end[test][1] = timeGetTime( );

		// using STL code
		for(i = 0; i < 10; i ++)
			objs.push_back((Cobj*)new Cchara);

		start[test][0] = timeGetTime( );
		for(loop = 0; loop < ESTIMATE_LOOP; loop ++)
		 {
			list<Cobj*>::iterator itr;
			// estimate time
			for(itr = objs.begin( ); itr != objs.end( ); )
			 {
				if((*itr)->process( ) == false)
				 {
					delete *itr;
					itr = objs.erase(itr);
				 }
				else
					itr ++;
			 }
		 }
		end[test][0] = timeGetTime( );


	 }

	for(test = 0; test < TEST_COUNT; test ++)
	 {
		for(int i = 0; i < 2; i ++)
			start[test][i] = end[test][i] - start[test][i];
		printf("%10d - %10d\n", start[test][0], start[test][1]);
	 }

 }