/* 宿題メール裏版 2004/05/26 ソフ開 */

#ifndef STDIO_HEADER_INCLUDED
#define STDIO_HEADER_INCLUDED
#include <stdio.h>
#endif

#ifndef STDLIB_HEADER_INCLUDED
#define STDLIB_HEADER_INCLUDED
#include <stdlib.h>
#endif

/* ---------------------------------------------------------
 *  ノードを表す構造体
 * --------------------------------------------------------- */
typedef struct mc_node Node;
struct mc_node {
  int index; /* 何番目の子か */
  struct mc_node *Parent;
  struct mc_node *FirstChild;
  struct mc_node *NextBrother;
};

/* ---------------------------------------------------------
 *  プロトタイプ宣言
 * --------------------------------------------------------- */
struct mc_node *mc_node_init( struct mc_node *root, int num ) ;
void mc_node_destroy( struct mc_node *root, int num ) ;
void mc_node_append( struct mc_node *node, struct mc_node *parent ) ;
struct mc_node *mc_node_lastBrother( struct mc_node *brother ) ;
char *mc_node_getId( char *id, struct mc_node *node ) ;
void mc_node_clean( struct mc_node *node ) ;
char *mc_node_reverseChars( char *c ) ;

void printBrothers( char *id, Node *tmp ) ;

/* ---------------------------------------------------------
 *  メイン
 * --------------------------------------------------------- */
int main( int argc, char *argv[] ) {

  int id_len = 1024;
  int childs = 5;
  int node_len = 1 + childs + (childs * childs);
  int i,j;

  Node *root;
  Node *tmp, *depth1, *depth2;
  
  /* id表示と二分木のメモリ確保 */
  char *id = (char *)calloc(id_len, sizeof(char));
  root = mc_node_init( root, node_len );

  if ( id == NULL || root == NULL ) {
    return 1;
  }

  /*
   * ルート直下に childs 個の子ノード
   * そのそれぞれに childs 個の子ノード
   * 
   *                    root
   *                  ／/|\＼
   * depth1          0 1 2 3 4 ..
   *              ／/|\＼ 
   * depth2      0 1 2 3 4 ..
   *
   * 二分木用に確保した領域に次のように格納される
   * 
   * node[0]   root
   * node[1]   rootの 0番目の子
   * node[2]   rootの 0番目の子 の 0番目の子
   * node[3]   rootの 0番目の子 の 1番目の子
   *                :
   * node[6]   rootの 0番目の子 の 4番目の子
   * node[7]   rootの 1番目の子
   * node[8]   rootの 1番目の子 の 0番目の子
   *                :
   *
   * 分かりにくくてごめんなさいm(__;)m
   *
   */
  for( i=0 ; i < childs ; i++ ) {
    depth1 = (root + 1) + (i * (childs + 1));
    depth2 = depth1;
    mc_node_append( depth1, root );

    for( j=0 ; j < childs ; j++ ) {
      mc_node_append( ++depth2, depth1 ) ;
    }
  }

  /* depth1それぞれの i 番目の子の全ての兄弟を出力 */
  for( i=0 ; i < childs ; i++ ) {
    tmp = (root + 1) + (i * (childs + 1));
    tmp = (tmp + 1) + i;
    printf( "-- %sの兄弟は\n", mc_node_getId( id, tmp ) );
    printBrothers( id, tmp );
  }

  /* 確保した領域の開放 */
  mc_node_destroy( root, node_len );
  free( id );

  return 0;
}

/**
 * node の全ての兄弟を出力する
 *  id : id取得のための文字列領域を指すポインタ
 *  node : 任意のノード
 */
void printBrothers( char *id, Node *node ) {
  Node *tmp = node->Parent->FirstChild;
  while( tmp != NULL ) {
    printf( "%s\n", mc_node_getId( id, tmp ) );
    tmp = tmp->NextBrother;
  }
}


/* ===========================================================
 *  簡易二分木構築
 * =========================================================== */

/* -----------------------------------------------------------
 *  二分木を格納する領域の確保と初期化
 *  領域確保に失敗した場合NULLを返す
 *
 *    root : 二分木の根
 *    num : ノードの総数
 * ----------------------------------------------------------- */

struct mc_node *mc_node_init( struct mc_node *root, int num ) {

  int i;
  struct mc_node *tmp;

  root = (struct mc_node *)malloc(sizeof(struct mc_node) * num);
  if ( root == NULL ) { 
    return NULL;
  }

  /* ノードの初期化 */

  tmp = root;
  for ( i=0 ; i < num ; i++ ) {
    mc_node_clean( tmp++ );
  }

  return root;
}

/* -----------------------------------------------------------
 *  確保した領域の初期化と開放
 *
 *    root : 二分木の根
 *    num : ノードの総数
 * ----------------------------------------------------------- */
void mc_node_destroy( struct mc_node *root, int num ) {

  int i;
  struct mc_node *tmp = root;

  for ( i=0 ; i < num ; i++ ) {
    mc_node_clean( tmp++ );
  }

  free( root );

}

/* -----------------------------------------------------------
 *  ノードの追加
 *  子が存在しない場合,最初に, それ意外は最後に追加する
 * 
 *    node : 追加するノード
 *    parent : 親ノード
 * ----------------------------------------------------------- */
void mc_node_append( struct mc_node *node, struct mc_node *parent ) {
  int index;
  struct mc_node *tmp;
  if( parent->FirstChild == NULL ) {
    parent->FirstChild = node;
    index = 0;
  }
  else {
    tmp = mc_node_lastBrother( parent->FirstChild );
    tmp->NextBrother = node;
    index = tmp->index + 1;
  }
  node->Parent = parent;
  node->index = index;
}

/* -----------------------------------------------------------
 *  引数で与えたノードの属する木の, 最後の兄弟を返す
 * 
 *    brother : 兄弟の任意のノード
 * ----------------------------------------------------------- */
struct mc_node *mc_node_lastBrother( struct mc_node *brother ) {
  while( brother->NextBrother != NULL ) {
    brother = brother->NextBrother;
  }
  return brother;
}

/* -----------------------------------------------------------
 *  ノードのインデックスを根まで辿り,一意な文字列に整形して返す
 *  ルートの3番目の子の4番目の子は "r_3_4"
 *
 *    id : 文字列格納用の領域
 *    node : IDを取得するノード
 * ----------------------------------------------------------- */
char *mc_node_getId( char *id, struct mc_node *node ) {
  *id = '\0';
  while( node->Parent != NULL ) {
    sprintf( id, "%s%d_%c", id, node->index, '\0' );
    node = node->Parent;
  }
  sprintf( id, "%sr%c", id, '\0' );
  mc_node_reverseChars( id );
  return id;
}

/* -----------------------------------------------------------
 *  ノードの初期化
 * 
 *     node : 初期化するノード
 * ----------------------------------------------------------- */
void mc_node_clean( struct mc_node *node ) {
  node->index = 0;
  node->Parent = NULL;
  node->FirstChild = NULL;
  node->NextBrother = NULL;
}

/* -----------------------------------------------------------
 *  文字列を逆順に並べかえる
 *
 *    c : 並べかえる文字列の先頭を指すポインタ
 * ----------------------------------------------------------- */
char *mc_node_reverseChars( char *c ) {
  char *s, *e;
  char w;
  s = e = c;
  while( *e++ != '\0' )
    ;
  e = e - 2;
  do {
    w = *e;
    *e = *s;
    *s = w;
  }
  while ( ++s <= --e ) ;
  return c;
}