#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <windows.h>
#pragma comment(lib, "winmm.lib")

#define ESTIMATE	5					// テスト回数
#define FRAME		(4*60*60)			// 何フレーム計測するか
#define TAMA_FRAME	100

#define FintTo(x)	((x)<<16)
typedef int	Fint;

typedef struct tag_STama
 {
	Fint	x, y, vx, vy;
	int		frame;
	int		next;
 } STama, *STamaPtr;

int numcell[] = { 100, 200, 400, 800, 1600, 3200, 6400, -1 };

#define PI 3.1415926535897932384626433832795
// Sin,Cos
Fint Sin(Fint theta);
Fint Cos(Fint theta);

static DWORD mRnd;
const DWORD alpha = 12869;
const DWORD beta = 6925;

DWORD Rnd(DWORD n)
 {
	mRnd = alpha * mRnd + beta;
	return mRnd % n;
 }

Fint SinCosTable[4096 +1024];
Fint ArcTanTable[1025];

//----------------------------------------------------------------------
// テーブル初期化
void InitUtil(void)
 {
	// Sin/Cosテーブル初期化
	for(int theta = 0; theta < 4096 +1024; theta ++)
		SinCosTable[theta] = (Fint)(sin(theta * 2.0 * PI/4096.0) * 65536.0);
 }
//----------------------------------------------------------------------
// sin
Fint Sin(Fint theta)
 {	return SinCosTable[theta]; }
//----------------------------------------------------------------------
// cos
Fint Cos(Fint theta)
 {	return SinCosTable[theta +1024]; }


void CalcTama1(int maxnum);
void CalcTama2(int maxnum);
bool tamaProcess(STamaPtr ptr);
void addtama1(STamaPtr array, int *num, int dir, int maxnum);
void addtama2(STamaPtr array, int dir, int *active, int *deactive);

void main(void)
 {
	InitUtil( );
	for(int i = 0; numcell[i] != -1; i ++)
	 {
		printf("セル数：%d\n", numcell[i]);

		mRnd = 0;	CalcTama1(numcell[i]);
		mRnd = 0;	CalcTama2(numcell[i]);
	 }
 }

void CalcTama1(int maxnum)
 {
	//int mnum = 0;									// 最大弾数
	STama *tama = new STama[maxnum];
	int		numtama;
	DWORD start[ESTIMATE], end[ESTIMATE];

	for(int estim = 0; estim < ESTIMATE; estim ++)
	 {
		// 初期化
		numtama = 0;

		// 弾発射方向
		int dir = 0;

		start[estim] = timeGetTime( );

		for(int frame = 0; frame < FRAME; frame ++)
		 {
			//if(mnum < numtama)	mnum = numtama;		// 弾数
			// すべての弾の移動処理
			int i = 0;
			while(i < numtama)
			 {
				if(tamaProcess(&tama[i]) == false)
				 {
					numtama --;
					tama[i] = tama[numtama];
				 }
				else
					i ++;
			 }
			// 適当に弾をばら撒く
			for(i = 0; i < TAMA_FRAME; i ++)
			 {
				addtama1(tama, &numtama, dir, maxnum);
				dir = (dir +10) & 4095;
			 }
		 }
		end[estim] = timeGetTime( );
	 }

	for(estim = 0; estim < ESTIMATE; estim ++)
		printf("%5d ", end[estim] - start[estim]);
	puts("");
	//printf("%d\n", mnum);							// 最大弾数
	delete[] tama;
 }

bool tamaProcess(STamaPtr ptr)
 {
	ptr->frame ++;
	ptr->x += ptr->vx;
	ptr->y += ptr->vy;
	if(ptr->x < FintTo(0) || ptr->x > FintTo(639) || ptr->y < FintTo(0) || ptr->y > FintTo(479))
		return false;
	if(ptr->frame > 60)
		if(Rnd(10) == 0)	return false;
	return true;
 }

void addtama1(STamaPtr array, int *num, int dir, int maxnum)
 {
	if(*num >= maxnum)	return;
	array[*num].frame = 0;
	array[*num].x = FintTo(320);
	array[*num].y = FintTo(240);
	array[*num].vx = Cos(dir);
	array[*num].vy = Sin(dir);
	(*num) ++;
 }
void addtama2(STamaPtr array, int dir, int *active, int *deactive)
 {
	if(*deactive == -1)	return;
	int tmp = *deactive;
	*deactive = array[tmp].next;		// deactiveから削除
	array[tmp].next = *active;
	*active = tmp;
	array[tmp].frame = 0;
	array[tmp].x = FintTo(320);
	array[tmp].y = FintTo(240);
	array[tmp].vx = Cos(dir) * 3;
	array[tmp].vy = Sin(dir) * 3;
 }

	
void CalcTama2(int maxnum)
 {
	STama *tama = new STama[maxnum];
	DWORD start[ESTIMATE], end[ESTIMATE];
	int		active, deactive;

	for(int estim = 0; estim < ESTIMATE; estim ++)
	 {
		// 初期化
		for(int i = 0; i < maxnum-1; i ++)
			tama[i].next = i +1;
		tama[i].next = -1;
		active = -1;
		deactive = 0;

		// 弾発射方向
		int dir = 0;

		start[estim] = timeGetTime( );

		for(int frame = 0; frame < FRAME; frame ++)
		 {
			// すべての弾の移動処理
			int *ptr = &active;
			while(*ptr != -1)
			 {
				if(tamaProcess(&tama[*ptr]) == false)
				 {
					int tmp = *ptr;
					*ptr = tama[*ptr].next;		// activeから切り離し
					tama[tmp].next = deactive;	// deactiveに追加
					deactive = tmp;
				 }
				else
					ptr = &(tama[*ptr].next);
			 }
			// 適当に弾をばら撒く
			for(i = 0; i < TAMA_FRAME; i ++)
			 {
				addtama2(tama, dir, &active, &deactive);
				dir = (dir +10) & 4095;
			 }
		 }
		end[estim] = timeGetTime( );
	 }

	for(estim = 0; estim < ESTIMATE; estim ++)
		printf("%5d ", end[estim] - start[estim]);
	puts("");

	delete[] tama;
 }