#include <iostream>
#include <fstream>
#include <string>
using namespace std;

#include "prompt.h"
#include "strutils.h"

/**
 * illustrates reversing a list with recursion
 * and two different methods. Also illustrates
 * cloning/copying a list.
 * @author Owen Astrachan, 9/11/2000, modified 1/29/2002
 */

struct Node
{
    string info;
    Node * next;       // points to next node in list

    Node (const string& s, Node * link) : info(s), next(link)
    { }
};


Node * revList(Node * list)
// pre: list->a->b->c->..->z->NULL
// post: returns pointer to reversed list (list links are changed)
//       return value->z->...->b->a->NULL    
{
    if (list == 0 || list->next == 0) return list;

    // at leat two nodes
    
    Node * revRest = revList(list->next);  // all reversed but first

    Node * temp = revRest;    // temp points at last node of rev'd list
    while (temp->next != 0) {
	temp = temp->next;
    }
    temp->next = list;        // last points to first
    list->next = 0;           // first points to NULL
    return revRest;           // all done
}

Node * revList2(Node * list)
// pre: list->a->b->c->..->z->NULL
// post: returns pointer to reversed list (list links are changed)
//       return value->z->...->b->a->NULL        
{
    if (list == 0 || list->next == 0) return list;

    // at leat two nodes

    Node * revRest = revList2(list->next);  // all reversed but first
    
    list->next->next = list;               // last points to first
    list->next = 0;                        // first poins to NULL
    return revRest;                        // all done
}

Node * copy(Node * list)
// pre: list is NULL/0 terminated    
// post: returns a copy of list
{
    if (list == 0) return 0;
    return new Node(list->info, copy(list->next));
}


void print(ostream& out, Node * list)
// post: all values in list printed, one node per line
{
    int count = 0;
    while (list != 0) {
	out << list->info << endl;
	count++;
	list = list->next;
    }
    cout << "# values = " << count << endl;
}

int main(int argc, char * argv[])
{
    ifstream input;
    string filename,word;
    Node * list = 0;
    
    // use command line argument if it exists, else prompt user
    
    if (argc > 1) {
	filename = argv[1];
    }
    else {
	filename = PromptString("enter file name ");	
    }
    
    input.open(filename.c_str());
    if (input.fail()) {
	cerr << "could not open " << filename << endl;
	exit(1);
    }
    while (input >> word) {
	list = new Node(word,list);
    }
    print(cout, list);

    Node * clone = copy(list);

    Node * rev = revList2(list);
    cout << endl << "**reversed**" << endl << "------" << endl;
    print(cout, rev);

    cout << endl << "** copy " << endl << "------" << endl;
    print(cout,clone);

    return 0;
}