#include <iostream.h>
#include <stdlib.h>
#include "list.h"

static const int NUMS_PER_LINE = 14;


template <class Object>
class stack 
{
  public:
    bool empty( ) const
      { return theList.empty( ); }
    const Object & top( ) const
      { return theList.front( ); }
    void push( const Object & x )
      { theList.push_front( x ); }
    void pop( Object & x )
      { x = theList.front( ); theList.pop_front( ); }
  private:
    list<Object> theList;
};

template <class Object>
class queue
{
  public:
    bool empty( ) const
      { return theList.empty( ); }
    const Object & getFront( ) const
      { return theList.front( ); }
    void enqueue( const Object & x )
      { theList.push_back( x ); }
    void dequeue( Object & x )
      { x = theList.front( ); theList.pop_front( ); }
  private:
    list<Object> theList;
};


template <class Collection>
void printCollection( const Collection & c )
{
    cout << "Collection contains: " << c.size( ) << " items" << endl;
    int i = 1;

    if( c.empty( ) )
        cout << "Empty container." << endl;
    else
    {
        for( Collection::iterator itr = c.begin( ); itr != c.end( ); itr++ )
        {
            cout << *itr << " ";
            if( i++ % NUMS_PER_LINE == 0 )
                cout << endl;
        }
        cout << endl;

        if( c.size( ) > NUMS_PER_LINE )
            return;
        cout << "In reverse: " << endl;
        for( Collection::iterator ritr = c.end( ); ritr != c.begin( ); )
            cout << *--ritr << " ";
        cout << endl << endl;
    }
}

template <class Collection, class Iterator>
void advance( const Collection & theList, Iterator & itr)
{
    if( ++itr == theList.end( ) )
         itr = theList.begin( );
}
 

int jos( int people, int passes, list<int> & order )
{
    list<int> theList;
    list<int>::iterator p = theList.begin( );
    list<int>::iterator tmp;
    stack<int> s;
    queue<int> q;
 

    order = list<int>( );

    int i;
    for( i = people; i >= 1; i-- )
        p = theList.insert( p, i );

    while( people-- != 1 )
    {
        for( i = 0; i < passes; i++ )
            advance( theList, p );

        order.push_back( *p );
        s.push( *p );
        q.enqueue( *p );
        tmp = p;
        advance( theList, p );
        theList.erase( tmp );
    }

    if( order.size( ) % 2 == 0 )
    {
        s.push( 0 );
        q.enqueue( 0 );
    }

    while( !s.empty( ) && !q.empty( ) )
    {
        int x, y;
        s.pop( x );
        q.dequeue( y );
        if( x == y )
            cout << "Middle removed is " << x << endl;
    }
    cout << "Only unremoved is ";
    return *theList.begin( );
}

    
void nonsense( int people, int passes )
{
    list<int> lastFew, theList;

    cout << jos( people, passes, lastFew ) << endl;
    
    cout << "(Removal order) ";
    printCollection( lastFew );
}

int main( )
{
    nonsense( 12, 0 );
    nonsense( 12, 1 );
    nonsense( 3737, 37 );

    return 0;
}