/*
 * This file contains a simple binary-tree example in C++.
 * Copyright: Jyrki Katajainen, October 1998
 *
 * Please send any comments to jyrki@di.ku.dk
 *
 * Run at DIKU as follows:
 * > g++ -fguiding-decls binary_tree.cpp
 * > a.out
 */

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

template <class D>
class Tree {
private:
  struct Node {
    D data;
    Node* left;
    Node* right;

    Node(const D & v, Node* p, Node* q) : data(v), left(p), right(q) {
    }
  };
  Node* root;
  Node* create_tree(D* first, D* last) {
    Node* p;
    if (first == last) return 0;
    else {
      D* middle = first + (last - first) / 2;
      return new Node(*middle, create_tree(first, middle), 
		      create_tree(middle + 1, last));
    }
  }
  void inorder(ostream& s, Node* root) {
    if (root != 0) {
      inorder(s, root -> left);
      s << root -> data;
      inorder(s, root -> right);
    }
  }
public:
  Tree() : root(0) {
  }
  Tree(D* first, D* last) : root(create_tree(first, last)) {
  }
  friend void print_tree(ostream &, Tree<D>&);
  // ...
};

template <class D>
void print_tree(ostream& s, Tree<D>& t) {
  t.inorder(s, t.root);
}

int main() {
  Tree<char> t;

  std::string s = "Fint, ikke!";
  t = Tree<char>(s.begin(), s.end());
  print_tree<char>(std::cout, t);
  std::cout << endl;

  char* c = "C++ is a better C";
  unsigned int len = strlen(c);
  std::vector<char> v(&c[0], &c[len]);
  t = Tree<char>(v.begin(), v.end());
  print_tree<char>(std::cout, t);
  std::cout << endl;
  
  char* g = "På gensyn!";
  len = strlen(g);
  t = Tree<char>(&g[0], &g[len]);
  print_tree<char>(std::cout, t);
  std::cout << endl;
  
  return 0;
}