//
// FILE: strings.cpp
// Author: Leo Reyzin (with thanks to Gali Diamant)
// Purpose: code to take in strings and print them out
// in ascending or descending order, HW3 of CS112B1 Spring 2003
// 
//
#include<iostream>
#include<string>
using namespace std;


struct TreeNode {
  // a tree node contains a string
  string s;
  TreeNode *left, *right;


  TreeNode() {left=right=NULL;}
  TreeNode(string newS, TreeNode * newleft, TreeNode * newright) 
       	{s=newS; left=newleft; right=newright;}
};

// Prints the binary search tree from smallest to largest
void PrintAscending (TreeNode * tree)
{
  if (tree!=NULL) {
    PrintAscending(tree->left);
    cout<<tree->s << endl;
    PrintAscending(tree->right);
  }
}


// Prints the binary search tree from largest to smallest
void PrintDescending(TreeNode * tree)
{
  if (tree!=NULL) {
    PrintDescending(tree->right);
    cout<<tree->s << endl;
    PrintDescending(tree->left);
  }
 
}

// This function inserts the string s into the tree maintaining the binary
// search tree order (for every node, the left subtree is no bigger, and
// the right subtree is not smaller that the node).  The tree argument is
// passed by reference, because the root of the tree may change as the
// result of the insert: if the tree is empty (tree==NULL), then it will
// change to the new string.

bool TreeInsert (TreeNode * & tree, string s)
{
  // If the tree is empty, change it to contain a single node with s in it
  if (tree==NULL) {
    tree = new TreeNode(s, NULL, NULL);
    if (tree==NULL)
      return false;
    return true;
  }

  // Else, figure out whether to insert on the right or the left and recurse
  // Note that tree->left and tree->right may change as a result
  // of recursion, because they are passed by reference.
  if (s < tree->s)
    return TreeInsert (tree->left, s);

  return TreeInsert (tree->right, s);
}

// Delete the entire tree (the root and the subtrees)
void DeleteTree(TreeNode * tree)
{
  if (tree!=NULL) {
    DeleteTree (tree->left);
    DeleteTree (tree->right);
    delete tree;
  }
}

int main()
{
  string s;
  char c;
  bool done=false;
  TreeNode * tree=NULL;

  // The loop below reads the input, one operator at a time,
  // and carries out the operation depending on the operator.
  // It stops upon receiving 'q' or if the read fails.
  while (!done) {

    if (!(cin >> c)) {
      cout << "Error: cannot read input\n";
      break;
    }

    switch (c) {
    case '?':
      if (!(cin >> s)) { // Read the string
        cout << "Error: cannot read string\n"; // cin failed to read the string
        done = true;                           // so we stop
      }
      else if (TreeInsert(tree, s)==false)
	cout<<"Out of Memory\n";
      break;
 
    case 'a':
      PrintAscending(tree);
      break;

    case 'd':
      PrintDescending(tree);
      break;

    case 'q':
      done=true;
      break;

    default:
      cout<<"Invalid Input!\n";
    }

  }

  DeleteTree(tree);

  return 0;
}