#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 main(int argc, char** argv)  
{  
    int ITER = 1000000;  
    Chain* chain;  
    struct timeval start, end;  
    gettimeofday(&#038;start,NULL);  

	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();

	}

    gettimeofday(&#038;end,NULL);  
    fprintf(stdout,"Time per iteration = %d microseconds\n\r", (((end.tv_sec - start.tv_sec) * 1000000) + (end.tv_usec - start.tv_usec)) / ITER);  
    //fprintf(stdout,"Last man standing is %d\n\r", (chain->first()->count() + 1));  
    return 0;  
}