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

#define population 20000
#define column 200
#define row 300

struct node {
	int unit;
	int x, oldX;
	int y, oldY;
	int nature;
	struct node * parent;
	struct node * enfant;
} ; 

struct purge {
	struct node *ame[population];
	int premier;
	int dernier;
};

struct node array[population];
struct node *matrix[column][row];
struct node *naitre;
struct node *etre;
struct node *fate;

struct purge styx;

//==============================================================================================
//==============================================================================================
//==============================================================================================
//==============================================================================================

struct node * birth(void)
{
//add a filter is there no soul in the styx
	struct node * newborn;
	newborn = (styx.ame[(styx.premier)]);
	styx.premier = styx.premier + 1;
	newborn->parent = fate;
	newborn->enfant = NULL;
	if (fate != NULL)
	{
		fate->enfant = newborn;
	}
	if (naitre == NULL)
	{
		naitre = newborn;
	}
	fate = newborn;
	return newborn;
}

//==============================================================================================
//==============================================================================================
//==============================================================================================
//==============================================================================================

int kill(struct node *mort)
{
//add a filter if there nobody to kill or the styx is full
	if ((mort->enfant == NULL)&&(mort->parent == NULL))
	{	return 0;		}

	if (mort->parent != NULL)
	{
		mort->parent->enfant = mort->enfant;
	} else { naitre = mort->enfant; }

	if (mort->enfant != NULL)
	{
		mort->enfant->parent = mort->parent;
	} else { fate = mort->parent; }

	if (styx.dernier == 0)
	{	styx.dernier = 1;	}
	if (styx.premier == 0)
	{	styx.premier = 1;	}

	styx.ame[styx.dernier] = mort;
	if (styx.dernier < population)
	{
	styx.dernier = styx.dernier + 1;
	} else { styx.dernier = 1 ; }

	mort->parent = NULL;
	mort->enfant = NULL;

	return 0;
}

//==============================================================================================
//==============================================================================================
//==============================================================================================
//==============================================================================================

void existance(void)
{
	etre = naitre;
	while (etre->enfant != NULL)
	{
		if ((etre->x != etre->oldX)&&(etre->y != etre->oldY))
		{
			matrix[etre->oldX][etre->oldY] = NULL;
			etre->oldX = etre->x;
			etre->oldY = etre->y;
		}
		if ((matrix[etre->x][etre->y] != NULL)&&(matrix[etre->x][etre->y] != etre))
		{		kill(matrix[etre->x][etre->y]);
		}	
				matrix[etre->x][etre->y] = (etre);
		

		etre = etre->enfant;
	}
}

//==============================================================================================
//==============================================================================================
//==============================================================================================
//==============================================================================================

void in_the_begining(void)
{
	int unit;
	for (unit = 1; unit < population; unit = unit+1)
	{

		if (unit != 1)
		{
			array[unit].parent = &(array[unit-1]);
		} else {
			array[unit].parent = NULL;
			naitre = &(array[unit]);
			etre = naitre;
		}
		if (unit != population)
		{
			array[unit].enfant = &(array[unit+1]);
		} else {
			array[unit].enfant = NULL;
		}
		
		array[unit].unit = unit;
	}
}

//==============================================================================================
//==============================================================================================
//==============================================================================================
//==============================================================================================