#include <cassert>
#include <cstdlib>
#include <unistd.h>
#include <iostream>
#include <string>


// Deja vu, c++ style.

   struct tree_node;
   struct list_node;

static tree_node * tree_null = 0;
static list_node * list_null = 0;


struct tree_node {

  int val;
  tree_node * left, * right;

  tree_node(int val) : val(val), left(0), right(0) { }
 ~tree_node() { delete left; delete right; left = right = tree_null; }

  private:

    tree_node(const tree_node &) { 
      assert(!"calling the tree-node copy constructor"); }

    tree_node & operator = (const tree_node &) {
      assert(!"calling the tree-node assignment"); 
      return *this; 
      }
  };


struct list_node {
  
  int val;
  list_node * prev, * next;

  list_node(int v) : val(v), prev(0), next(0) { }
  list_node(int v, list_node * p, list_node * n) : val(v), prev(p), next(n) { }
 ~list_node() { delete next; next = prev = list_null; }

  private:

    list_node(const list_node &) { 
      assert(!"calling the list-node copy constructor"); }

    list_node & operator = (const list_node &) {
      assert(!"calling the list-node assignment");
      return *this; 
      }
  };


struct ptr_pair {
  list_node * begin, * end;
  ptr_pair(list_node * b, list_node * e) : begin(b), end(e) { }
  };


// Deja vu, c++ style;

   static tree_node * fold(const list_node *, unsigned);
   static list_node * make_list(unsigned &);
   static void print_list(std::ostream &, const list_node *);
   static void print_tree(std::ostream &, const tree_node *, std::string);
   static void run_test(bool);


static ptr_pair
flatten(const tree_node * root) {

  // Flatten the tree at the given root into a list, return pointers to the
  // ends of the list.

  if (root == tree_null)
    return ptr_pair(list_null, list_null);

  ptr_pair
    left_pp = flatten(root->left),
    right_pp = flatten(root->right);

  list_node * const mid = 
    new list_node(root->val, left_pp.end, right_pp.begin);

  if (mid->prev == list_null)
    left_pp.begin = mid;
  else
    mid->prev->next = mid;

  if (mid->next == list_null)
    right_pp.end = mid;
  else
    mid->next->prev = mid;

  return ptr_pair(left_pp.begin, right_pp.end);
  }


static tree_node *
fold(const list_node * head, unsigned size) {

  // Fold the given list of the given size into a tree, return a pointer to the
  // tree's root.

  if (size == 0)
    return tree_null;

  const unsigned h = size/2;
  const list_node * mid = head;
  for (unsigned i = h; i > 0; i--) {
    assert(mid);
    mid = mid->next;
    }
  assert(mid);

  tree_node * root = new tree_node(mid->val);

  if (size > 1) {
    root->left = fold(head, h);
    root->right = fold(mid->next, size - h - 1);
    }

  return root;
  }


static bool
list_same(const list_node * const lst1, const list_node * const lst2) {

  // Return the number of elements in the given list.

  if ((lst1 == list_null) and (lst2 == list_null))
    return true;
  if ((lst1 == list_null) or (lst2 == list_null))
    return false;

  return (lst1->val == lst2->val) and list_same(lst1->next, lst2->next);
  }


int 
main() {

  srandom(getpid());

  for (int i = 0; i < 10; i++)
    run_test(true);
  }


static list_node *
make_list(unsigned & size) {

  // Create and return a random list of integers.

  size = random() % 20;
  list_node head(0);
  list_node * tail = &head;

  for (unsigned i = 0; i < size; i++)
    tail = tail->next = new list_node(random() % 100, tail, list_null);
  if (head.next)
    head.next->prev = list_null;

  tail = head.next;
  head.next = list_null;

  return tail;
  }


static void
print_list(std::ostream & os, const list_node * head) {

  // Print the given list to the given output streaml.

  while (head) {
    os << head->val;
    os << " ";
    head = head->next;
    }
  os << "\n";
  }


static void
print_tree(std::ostream & os, const tree_node * root, std::string indent) {

  // Print the given tree to the given output stream, using the given indentation.

  if (root != tree_null) {
    os << indent << root->val << "\n";
    print_tree(os, root->left, indent + "  ");
    print_tree(os, root->right, indent + "  ");
    }
  }


static void
run_test(bool print) {

  // Run a folding-flattening test.

  unsigned size;
  const list_node * const lst = make_list(size);
  if (print) print_list(std::cout, lst);

  const tree_node * const tre = fold(lst, size);
  if (print) print_tree(std::cout, tre, "");

  const ptr_pair pp = flatten(tre);
  if (print) print_list(std::cout, pp.begin);

  assert(list_same(lst, pp.begin));
  }


// g++ -o tree-list -gstabs -ansi -pedantic -Wall tree-list.cc && ( ulimit -c 0 ; ./tree-list )


// $Log: tree-list.cc,v $
// Revision 1.1  2003/11/25 22:57:22  rclayton
// Initial revision
//