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

#define LEFT     -1
#define RIGHT    1
#define NODE_NUM 1024   // 最大ノード数
#define START_ID 1      // intの初期値0とID=0と区別ができないので1から開始
#define NAME_MAX_LENGTH // タグ名の最大長

// ポインタ有りノード
typedef struct _node {
  struct _node* parent;
  struct _node* left;
  struct _node* right;
  int id;
  char name[NAME_MAX_LENGTH];
} node;

// ポインタ無しノード
typedef struct _array_node {
  int parent;
  int left;
  int right;
  char name[NAME_MAX_LENGTH];
} array_node;

// ポインタ有りノードの生成
node* create_node(char *name) {
  node* new_node;
  new_node = (node*)malloc( sizeof(node) );
  strcpy(new_node->name, name);
  return new_node;
}

// ポインタ無しノードの生成
array_node* create_array_node(char *name) {
  array_node* new_node;
  new_node = (array_node*)malloc( sizeof(array_node) );
  strcpy(new_node->name, name);
  return new_node;
}

// 任意のノードに対してノードを追加する
node* insert_node(node* parent, int pos, node* inserted_node) {
  inserted_node->parent = parent;
  if (pos == LEFT) parent->left  = inserted_node;
  else             parent->right = inserted_node;
}

// 与えられたノードを深さ優先で再帰的に下って順序を知る
// XXX idはcreate_node時に付与していけばeachする必要がなくなるかも
int each(node* target, int id, node** nodes) {
  nodes[id] = target;
  target->id = id;

  id++;
  if (target->left  != NULL) id = each(target->left,  id, nodes);
  if (target->right != NULL) id = each(target->right, id, nodes);
  return id;
}

// ポインタ有りノード集合から ポインタ無し集合を生成
map_to_array_node(node** nodes, array_node** array_nodes) {
  int i;
  for (i = START_ID; nodes[i] != NULL && i < NODE_NUM; i++) {
    array_nodes[i] = create_array_node(nodes[i]->name);
    if (nodes[i]->parent != NULL) array_nodes[i]->parent = nodes[i]->parent->id;
    if (nodes[i]->left   != NULL) array_nodes[i]->left   = nodes[i]->left->id;
    if (nodes[i]->right  != NULL) array_nodes[i]->right  = nodes[i]->right->id;
  }
}

/*
<root>
  <self>
    <child>
      <gchild></gchild>
    </child>
  </self>
  <sibling></sibling>
</root>
*/
int main(void) {
  node* root;
  node* self;
  node* child;
  node* gchild;
  node* sibling;
  node* nodes[NODE_NUM];
  array_node* array_nodes[NODE_NUM];

  root    = create_node("root");
  self    = create_node("self");
  child   = create_node("child");
  gchild  = create_node("gchild");
  sibling = create_node("sibling");

  insert_node(root,  LEFT,  self);
  insert_node(self,  LEFT,  child);
  insert_node(child, LEFT,  gchild);
  insert_node(self,  RIGHT, sibling);

  each(root, START_ID, nodes);
  map_to_array_node(nodes, array_nodes);

  // test
  printf("%d\n", array_nodes[START_ID + 0]->left); // 1->left  = 2 : self
  printf("%d\n", array_nodes[START_ID + 1]->left); // 2->left  = 3 : child
  printf("%d\n", array_nodes[START_ID + 2]->left); // 3->left  = 4 : gchild
  printf("%d\n", array_nodes[2]->right);           // 2->right = 5 : sibling

  return 0;
}