#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <sstream>

using namespace std;


typedef char Word;
struct Node;
typedef vector<Node> Structure;

struct Node {
  Word word; 
  size_t id;

  Structure left;
  Structure right;
};

struct StackItem {
  char state;

  Structure d;
};

/*
 * @brief  Find node with given id below Node n.
 * @detail That's variant of BFS
 *
 */
Node*
find_in_node(Node* n, size_t const id)
{
  vector<Node*> queue;
  queue.push_back(n);
  while (!queue.empty()) {
    Node* cur = queue.back();
    queue.pop_back();
    if (id == cur->id) {
      return cur;
    } else if (id < cur->id) {
      for (size_t i = 0; i < cur->left.size(); i++)
        queue.push_back(&(cur->left[i]));
    } else if (id > cur->id) {
      for (size_t i = 0; i < cur->right.size(); i++)
        queue.push_back(&(cur->right[i]));
     }
  }

  return NULL; 
}

/*
 * @brief Pretty prints a structure.
 *
 */
ostream&
print_structure(ostream& os, Structure& s, size_t level=0, char side='-')
{
  ostringstream indent;
  for (size_t i = 0; i <= level; i++)
    indent << " ";

  if (side == 'r' || side == '-') {
    for (int i = s.size()-1; i >= 0; i--) { // sorted by id
      os << indent.str() << s[i].id << "," << s[i].word << " " << side << endl;
      print_structure(os, s[i].left, level+1, 'l');
      print_structure(os, s[i].right, level+1, 'r');
    }
  } else {
    for (size_t i = 0; i < s.size(); i++) { // sorted by id
      os << indent.str() << s[i].id << "," << s[i].word << " " << side << endl;
      print_structure(os, s[i].left, level+1, 'l');
      print_structure(os, s[i].right, level+1, 'r');
    } 
  }

  return os;
}

/*
 * @brief Fills dependency structure given words and
 *        DependencyInfo.
 *
 */
void
make_structure(Structure& s, vector<Word>& words, vector<int> links)
{
  // create nodes without hierarchy
  vector<Node> all, queue, sorted;
  size_t id = 0;
  for (vector<Word>::iterator it = words.begin();
       it != words.end(); it++) {
    Word word = *it;
    Node n;
    n.id = id;
    n.word = word;
    all.push_back(n);
    if (links[id] == -1)
      queue.push_back(n);
    id++;
  }

  // topologically sort before construction
  while (!queue.empty()) {
    Node n = queue.back();
    queue.pop_back();
    sorted.push_back(n);
    size_t i = 0;
    for (size_t j = 0; j < links.size(); j++) {
      if (links[j] == n.id)
        queue.push_back(all[i]);
      i++;
    }
  }

  // build structure/s
  for (vector<Node>::iterator n = sorted.begin();
       n != sorted.end(); n++) {
    if (links[n->id] == -1) { // top-level
      s.push_back(*n);
    } else {
      Node* a;
      for (size_t k = 0; k < s.size(); k++) {
        a = find_in_node(&(s[k]), links[n->id]);
        if (a) {
          if (n->id < a->id) { // left
            a->left.push_back(*n);
          } else { // right
            a->right.push_back(*n);
          }
          break;
        }
      }
    }
  }
}

void
score_and_prune(Node* n, bool final=false)
{
  if (n->left.size() == 0
      && n->right.size() == 0) return;

  for (int i = n->left.size()-1; i >= 0; i--)
    cout << n->left[i].word;
  cout << "{" <<  n->word;
  if (final) cout << "!";
  cout << "}";
  for (int i = n->right.size()-1; i >= 0; i--)
    cout << n->right[i].word;
  cout << endl;

  for (int i = 0; i < n->left.size(); i++)
    score_and_prune(&(n->left[i]));
  for (int i = 0; i < n->right.size(); i++)
    score_and_prune(&(n->right[i]));

  n->left.clear();
  n->right.clear();
}

/*
 * where = left or right
 *
 */
void
reduce(Node* head, Structure& a, char where)
{
  for (Structure::iterator it = a.begin();
       it != a.end(); it++) {
    if (where == 'l')
      head->left.push_back(*it);
    else // where == 'r'
      head->right.push_back(*it);
  }
} 

void
test1()
{
  cerr << "TEST 1" << endl;
  vector<Word> words;
  words.push_back('e');
  words.push_back('f');
  words.push_back('g');
  words.push_back('x');
  words.push_back('h');
  words.push_back('i');
  vector<int> links;
  links.push_back(4);
  links.push_back(0);
  links.push_back(0);
  links.push_back(2);
  links.push_back(-1);
  links.push_back(-1);
  Structure s;
  make_structure(s, words, links);
  print_structure(cout, s);
  cerr << endl;
}

void
test2()
{
  cerr << "TEST 2" << endl;
  vector<Word> words;
  words.push_back('e');
  words.push_back('f');
  words.push_back('x');
  words.push_back('g');
  words.push_back('h');
  words.push_back('i');
  vector<int> links;
  links.push_back(4);
  links.push_back(0);
  links.push_back(3);
  links.push_back(0);
  links.push_back(-1);
  links.push_back(-1);
  Structure s;
  make_structure(s, words, links);
  print_structure(cout, s);
  cerr << endl;
}

void
test3()
{
  cerr << "TEST 3" << endl;

  vector<Word> w1;
  w1.push_back('a');
  vector<int> l1;
  l1.push_back(-1);
  Structure s1;
  make_structure(s1, w1, l1);
  print_structure(cout, s1);
  cout << endl;

  vector<Word> w2;
  w2.push_back('b');
  w2.push_back('c');
  vector<int> l2;
  l2.push_back(-1);
  l2.push_back(-1);
  Structure s2;
  make_structure(s2, w2, l2);
  print_structure(cout, s2);
  cout << endl;

  vector<Word> w3;
  w3.push_back('d');
  vector<int> l3;
  l3.push_back(-1);
  Structure s3;
  make_structure(s3, w3, l3);
  print_structure(cout, s3);
  cout << endl;

  vector<Word> w4;
  w4.push_back('e');
  w4.push_back('f');
  w4.push_back('g');
  vector<int> l4;
  l4.push_back(-1);
  l4.push_back(0);
  l4.push_back(0);
  Structure s4;
  make_structure(s4, w4, l4);
  print_structure(cout, s4);
  cout << endl;

  vector<Word> w5;
  w5.push_back('h');
  vector<int> l5;
  l5.push_back(-1);
  Structure s5;
  make_structure(s5, w5, l5);
  print_structure(cout, s5);
  cout << endl;
}

void
test4()
{
  cerr << "TEST 3" << endl;
  vector<Word> words;
  words.push_back('a');
  words.push_back('b');
  words.push_back('c');
  words.push_back('d');
  words.push_back('e');
  words.push_back('f');
  words.push_back('g');
  words.push_back('h');
  words.push_back('i');
  vector<int> links;
  links.push_back(7);
  links.push_back(3);
  links.push_back(3);
  links.push_back(7);
  links.push_back(7);
  links.push_back(4);
  links.push_back(4);
  links.push_back(-1);
  links.push_back(-1);
  Structure s;
  make_structure(s, words, links);
  print_structure(cout, s);
  score_and_prune(&(s.back()), true);
  cerr << endl;
}

void
test5()
{
  cerr << "TEST 5" << endl;

  vector<Word> w2;
  w2.push_back('b');
  w2.push_back('c');
  vector<int> l2;
  l2.push_back(-1);
  l2.push_back(-1);
  Structure s2;
  make_structure(s2, w2, l2);
  print_structure(cout, s2);
  cout << endl;

  vector<Word> w3;
  w3.push_back('d');
  vector<int> l3;
  l3.push_back(-1);
  Structure s3;
  make_structure(s3, w3, l3);
  print_structure(cout, s3);
  cout << endl;

  vector<Word> w4;
  w4.push_back('e');
  w4.push_back('f');
  w4.push_back('g');
  vector<int> l4;
  l4.push_back(-1);
  l4.push_back(0);
  l4.push_back(0);
  Structure s4;
  make_structure(s4, w4, l4);
  print_structure(cout, s4);
  cout << endl;

  reduce(&(s3.back()), s2, 'l');
  print_structure(cout, s3);
  cerr << endl;

  reduce(&(s3.back()), s4, 'r');
  print_structure(cout, s3);
  cerr << endl;

  score_and_prune(&(s3.back().right[0]));
  cerr << endl;
  print_structure(cout, s3);
  cerr << endl;
  score_and_prune(&(s3.back()));
  cerr << endl;
}

int
main(void)
{
  test1();
  test2();
  test3();
  test4();
  test5();

  return 0;
}