/* after a bit of brain storming I think this is a better demonstration
   for really getting to see and understand the process.

   At each step it prints the entire stack that is in use, along with
   something to make it clear which stack you're looking at. It stops
   whenever either stack is about to produce a result (just press enter
   to continue) so you can see how the stacks interact.

   Change the trees a bit, and you'll be able to see examples of all
   possibilities */


#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

using namespace std;

class node
{ protected:
    string data;
    vector <node *> child;

  public:
    node(string d)
    { data = d; }

    node * add(node * p)
    { child.push_back(p);
      return this; }

    string getdata()
    { return data; }

    int getnumchildren()
    { return child.size(); }

    node * get(int i)
    { return child[i]; } };

node * mn(string s)
{ return new node(s); }



class stack_frame
{ public:
    string type;
    int where;

    stack_frame(string t)
    { type = t;
      where = 0; }
      
    virtual void print() = 0; };



class reverse_stack_frame: public stack_frame
{ public:
    string s;

    reverse_stack_frame(string s0): stack_frame("R")
    { s = s0; }
    
    virtual void print()
    { cout << "type " << type << ": where = " << where << 
              ", s = \"" << s << "\""; } };



class print_stack_frame: public stack_frame
{ public:
    node * p;
    int depth, num, i;

    print_stack_frame(node * p0, int depth0): stack_frame("P")
    { p = p0;
      depth = depth0; }

    virtual void print()
    { cout << "type " << type << ", where = " << where <<
              ", p contains \"" << (p == NULL ? "(nothing)" : p->getdata()) << "\"" <<
              ", i = " << i << ", num = " << num; } };


/* the original recursive versions to show the positions

   type R stack frames
   
      string reverse(const string & s)
      { [position 0]
        if (s.length() <= 1)
          return s;
        return 
           reverse(s.substr(1))
           [position 1]
           + s[0]; }

   type P stack frames
   
      void print(node * p, int depth = 0)
      { [position 0]
        cout << setw(depth*5) << "" << 
                reverse(p->getdata())
                [position 1]
                << "\n";
        int num = p->getnumchildren();
        int i = 0;
        [position 3]
        while (i < num)
        { print(p->get(i), depth+1);
          [position 2]
          i += 1; } }
*/


void show_stack(vector<stack_frame *> & v)
{ for (int i = 0; i < v.size(); i += 1)
  { cout << setw(6) << i << ": ";
    v[i]->print();
    cout << "\n"; } }


string run_until_output(vector<stack_frame *> & stack, int whichstack)
{ string string_return;
  while (stack.size() > 0)
  { cout << "stack " << whichstack << ":\n";
    show_stack(stack);
    stack_frame * sf = stack.back();

    if (sf->type == "R")
    { reverse_stack_frame * rsf = (reverse_stack_frame *) sf;
 
      if (rsf->where == 0)
      { if (rsf->s.length() <= 1)
        { string_return = rsf->s;
          stack.pop_back();
          continue; }
        else
        { stack.push_back(new reverse_stack_frame(rsf->s.substr(1)));
          rsf->where = 1;
          continue; } }

      else if (rsf->where == 1)
      { string_return = string_return + rsf->s[0];
        stack.pop_back();
        continue; } }

    else if (sf->type == "P")
    { print_stack_frame * psf = (print_stack_frame *) sf;

      if (psf->where == 0)
      { stack.push_back(new reverse_stack_frame(psf->p->getdata()));
        psf->where = 1;
        continue; }

      else if (psf->where == 1)
      { psf->where = 4;
        cout << "RETURNING \"" << string_return << "\"\n";
        cout << "press enter to continue: ";
        string x;
        getline(cin, x);
        return string_return; }

      else if (psf->where == 4)
      { psf->num = psf->p->getnumchildren();
        psf->i = 0;
        psf->where = 3;
        continue; }

      else if (psf->where == 2)
      { psf->i += 1;
        psf->where = 3;
        continue; }

      else if (psf->where == 3)
      { if (psf->i < psf->num)
        { stack.push_back(new print_stack_frame(psf->p->get(psf->i), psf->depth + 1));
          psf->where = 2;
          continue; }
        else
        { stack.pop_back();
          continue; } } } }
  return "*"; }

void compare(node * t1, node * t2)
{ string string_return;
  vector <stack_frame *> stack1, stack2;
  stack1.push_back(new print_stack_frame(t1, 0));
  stack2.push_back(new print_stack_frame(t2, 0));
  while (true)
  { string s1 = run_until_output(stack1, 1);
    string s2 = run_until_output(stack2, 2);
    cout << "COMPARE \"" << s1 << "\" with \"" << s2 << "\"\n";
    if (s1 == "*")
    { if (s2 == "*")
      { cout << "  both finished together: same\n";
        break; }
      else
      { cout << "  second has more nodes than first: different\n";
        break; } }
    else if (s2 == "*")
    { cout << "  second has more nodes than first: different\n";
      break; }
    else if (s1 != s2)
    { cout << "  different\n";
      break; }
    else
      cout << "  same output so still OK, more to come\n"; } }
      

int main()
{ node * t = mn("ant")
                      ->add(mn("bat")
                                     ->add(mn("egg")
                                                    ->add(mn("kit"))
                                                    ->add(mn("log")))
                                     ->add(mn("fig"))
                                     ->add(mn("git")
                                                    ->add(mn("map"))
                                                    ->add(mn("nut"))
                                                    ->add(mn("old"))
                                                    ->add(mn("pig"))))
                      ->add(mn("cat")
                                     ->add(mn("hat")))
                      ->add(mn("dog")
                                     ->add(mn("ink")
                                                    ->add(mn("qat"))
                                                    ->add(mn("rat")))
                                     ->add(mn("jug")
                                                    ->add(mn("sud"))
                                                    ->add(mn("tip"))));
  node * u = mn("ant")
                      ->add(mn("bat")
                                     ->add(mn("egg")
                                                    ->add(mn("kit"))
                                                    ->add(mn("log")))
                                     ->add(mn("fig"))
                                     ->add(mn("git")
                                                    ->add(mn("map"))
                                                    ->add(mn("nut"))
                                                    ->add(mn("old")))
                                     ->add(mn("pug")))
                      ->add(mn("cat")
                                     ->add(mn("hat")))
                      ->add(mn("dog")
                                     ->add(mn("ink"))
                                     ->add(mn("qat"))
                                     ->add(mn("rat"))
                                     ->add(mn("jug")
                                                    ->add(mn("sud"))
                                                    ->add(mn("tip"))));
  compare(t, u); }