#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; }

      // e.g. in n->add(m); what's returned is n

    string get_data()
    { return data; }

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

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

node * mn(string s)   // mn calls constructor, but it shorter to type
{ return new node(s); }
    
class AR
{ protected:
    int identifier;
    node * p;
    int depth;
    int num;
    int i;
    int where;
      
    static int count;
        
  public:
    AR(node * init_p, int init_depth, int init_where = 1)
    { p = init_p;
      depth = init_depth;
      where = init_where;
      count += 1;
      identifier = count; }
      
    node * get_p() const
    { return p; }

    int get_depth() const
    { return depth; }
                                                    
    int get_num() const
    { return num; }

    void set_num(int n)
    { cout << "  num set to " << n << "\n";
      num = n; }

    int get_i() const
    { return i; }

    void set_i(int n)
    { cout << "  i set to " << n << "\n";
      i = n; }

    int get_where() const
    { return where; }

    void set_where(int n)
    { cout << "  where set to " << n << "\n";
      where = n; }

    void print(ostream & out) const
    { out << "AR" << setw(3) << identifier << ", node \"" << p->get_data() << "\", depth = " << depth
          << ", num = " << num << ", i = " << i << ", where = " << where; } };

int AR::count = 0;

ostream & operator<<(ostream & out, const AR & a)
{ a.print(out);
  return out; }

class stack: public vector <AR *>
{ public:

    void push(AR * a)
    { push_back(a); }

    AR * pop()
    { AR * result = back();
      pop_back();
      return result; }

    AR * top() const
    { return back(); }

    bool not_empty() const
    { return size() > 0; }
    
    void print() const
    { if (empty())
      { cout << "  (empty)\n";
        return; }
      cout << "  top: " << * back() << "\n";
      for (int i = size() - 2; i >= 0; i -= 1)
        cout << "       " << * at(i) << "\n"; } };
  
//
// this is the original recursive print, it won't be used any more
//
// void print(node * p, int depth = 0)
// { /* this is position 1 */
//   cout << setw(depth * 5) << " " << p->get_data() << "\n";
//   int num = p->get_num_children();
//   int i = 0;
//   /* this is position 2 */
//   while (i < num)
//   { print(p->get_child(i), depth + 1);
//     /* this is position 3 */
//     i += 1; } }
//

void nr_print(node * root)
{ stack S;
  S.push(new AR(root, 0));
  while (S.not_empty())
  { cout << "\nThe stack is:\n";
    S.print();
    AR * top = S.top();

    if (top->get_where() == 1)
    { cout << setw(top->get_depth() * 5) << " " << top->get_p()->get_data() << "\n";
      top->set_num(top->get_p()->get_num_children());
      top->set_i(0);
      top->set_where(2);
      continue; }

    else if (top->get_where() == 2)
    { if (top->get_i() < top->get_num())
      { S.push(new AR(top->get_p()->get_child(top->get_i()), top->get_depth() + 1));
        top->set_where(3);
        continue; }
      else
      { S.pop();
        continue; } }

    else if (top->get_where() == 3)
    { top->set_i(top->get_i() + 1);
      top->set_where(2);
      continue; } } }

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"))));
  nr_print(t); }