#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <vector>

using namespace std;

class enumerator
{ public:
    virtual bool somethingtodo() = NULL;
    virtual int get() = NULL; };

struct treenode
{ int data;
  treenode * left, * right;
  treenode(int d); };

treenode::treenode(int d)
{ data=d;
  left=NULL;
  right=NULL; }

void insert(treenode * & t, int val)
{ if (t==NULL)
    t=new treenode(val);
  else if (val<t->data)
    insert(t->left, val);
  else
    insert(t->right, val); }

treenode * maketree(int n)
{ treenode * t = NULL;
  for (int i=0; i<n; i+=1)
    insert(t, random()%900+100);
  return t; }

void print1(treenode * t, string indent="")
{ if (t==NULL)
    printf("%s.", indent.c_str());
  else
  { print1(t->left, indent+" | ");
    printf("\n%s%d\n", indent.c_str(), t->data);
    print1(t->right, indent+" | "); } }

void print2(treenode * t)
{ // point A
  if (t==NULL)
    printf(".");
  else
  { printf("[");
    print2(t->left);
    // point B
    printf("%d", t->data);
    print2(t->right);
    // point C
    printf("]"); }
  // point D
 }

struct note
{ const treenode * t;
  char where;
  note(const treenode * a, char b) { t=a; where=b; } };

class Tenum: public enumerator
{ protected:
    vector<note> todolist;
    int nextvalue;
    bool stillalive;

  void runahead()
  { while (todolist.size() != 0)
    { note & task = todolist.back(); 
      if (task.where=='A')
      { if (task.t==NULL)
        { task.where='D'; }
        else
        { task.where='B';
          todolist.push_back(note(task.t->left, 'A')); } }
      else if (task.where=='B')
      { int value = task.t->data;
        task.where='D'; 
        todolist.push_back(note(task.t->right, 'A'));
        nextvalue = value;
        return; }
      else if (task.where=='D')
      { todolist.pop_back(); } }
    stillalive=false; }

  public:

  bool somethingtodo()
  { return stillalive; }

  Tenum(const treenode * t_orig)
  { todolist.push_back(note(t_orig, 'A'));
    stillalive=true;
    runahead(); }

  int get()
  { int value=nextvalue;
    runahead();
    return value; } };

struct Link
{ int data;
  Link * next; };

Link * makelist(int n)
{ Link * ptr = NULL;
  for (int i=0; i<=n; i+=1)
  { Link * x = new Link;
    x->data=random()%900+100;
    x->next=ptr;
    ptr=x; }
  return ptr; }

class LLenum: public enumerator
{ protected:
    Link * curr;
  public:
    LLenum(Link * x): curr(x) { }

    bool somethingtodo()
    { return curr!=NULL; }

    int get()
    { int t = curr->data;
      curr=curr->next;
      return t; } };

void check(enumerator & E, enumerator & F)
{ bool same=true;
  while (E.somethingtodo() || F.somethingtodo())
  { if (!E.somethingtodo() || !F.somethingtodo())
    { printf("different lengths\n");
      same=false;
      break; }
    int a=E.get(), b=F.get();
    printf("%d %d\n", a, b);
    if (a!=b)
      same=false; }
  if (same)
    printf("They are the same\n");
  else
    printf("They are different\n"); }

void main()
{ srandomdev();
  treenode * a = maketree(20);
  Link * b = makelist(22);
  printf("\n----------\n");
  Tenum E(a);
  LLenum F(b);
  check(E, F);
  printf("----------\n"); }