// speed.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <Windows.h>
#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  
//#include <sys/time.h>  

//01 modify bignotti alberto 2008-08-18
#include <stack>
class Person;
typedef std::stack<Person*> SaveArea;

class Person
{

public:

	Person(int count) : _next(NULL), _prev(NULL) { _count = count; }
	
	//02 modify bignotti alberto 2008-08-18
	void reset(int count)
	{
		_next=_prev=NULL;
		_count=count;
	}

	int shout(int shout, int nth)
	{
		if (shout < nth) return (shout + 1);
		_prev->_next = _next;


		_next->_prev = _prev;
		return 1;
	}
	int count() { return _count; }
	Person* next() { return _next; }
	void next(Person* person) { this->_next = person ; }
	Person* prev() { return _prev; }
	void prev(Person* person) { this->_prev = person; }
private:
	int _count;
	Person* _next;
	Person* _prev;
};

class Chain
{
public:
	//03 modify bignotti alberto 2008-08-18
	Chain(int size,SaveArea& reusePersons) : _first(NULL)
	{
		Person* current = NULL;
		Person* last = NULL;
		for(int i = 0 ; i < size ; i++)
		{
			if(! reusePersons.empty() )
			{
				current = reusePersons.top();
				current->reset(i);
				reusePersons.pop();
			}
			else
				current = new Person(i);

			if (_first == NULL) _first = current;
			if (last != NULL)
			{
				last->next(current);
				current->prev(last);
			}
			last = current;
		}
		_first->prev(last);
		last->next(_first);
	}

	//04 modify bignotti alberto 2008-08-18
	Person* kill(int nth,SaveArea& reusePersons)
	{
		Person* current = _first;
		int shout = 1;
		while(current->next() != current)
		{
			Person* tmp = current;
			shout = current->shout(shout,nth);
			current = current->next();
			if (shout == 1)
			{
				//delete tmp;
				reusePersons.push(tmp);
			}
		}
		_first = current;
		return current;
	}

	Person* first() { return _first; }
private:
	Person* _first;
};

int _tmain(int argc, _TCHAR* argv[])
{  
	int ITER = 10000000;  
	Chain* chain;  
	long start, end;  
	start = GetTickCount();

	//05 modify bignotti alberto 2008-08-18
	SaveArea reusePersons;

	for(int i = 0 ; i < ITER ; i++)
	{
		chain = new Chain(40,reusePersons);
		chain->kill(3,reusePersons);

		delete chain;
	}
	
	while(!reusePersons.empty())
	{
		free(reusePersons.top());
		reusePersons.pop();
	}

	end = GetTickCount();

	fprintf(stdout,"Time per iteration = %d microseconds\n\r", (end - start) );  
	return 0;  
}