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

#include "treeMgt.h"

typedef struct _ListNode {
  struct _TreeNode * treeNodeP;
  struct _ListNode * nextP;
} ListNode;

typedef struct _List {
  ListNode * headP;
  ListNode * tailP;
} List;

List * newList( );

int addTreeNodeToList( TreeNode * newTreeNodeP, List * lP );


//  ----------------------------------------------------------------------------
// Functions for managing the tree nodes proper

TreeNode * newTreeNode( char * s )
{
  TreeNode * tnP = malloc( sizeof(TreeNode) );
  if( tnP == NULL ) { fprintf( stderr, "TreeNode malloc failed\n" ); return NULL; }

  tnP->extName = malloc(strlen(s));

  if( tnP->extName == NULL ) {
    fprintf( stderr, "TreeNode.extName alloc failed\n" );
    return NULL;
  }
  strcpy( tnP->extName, s );

  tnP->childListP = newList();
  if( tnP->childListP  == NULL ) 
  { fprintf( stderr, "TreeNode.childListP alloc failed\n" ); return NULL; }

  return tnP;
}

//  --------------------------------------
Tree  * newTree( TreeNode * tnP )
{
  Tree * tp = malloc( sizeof(Tree) );
  tp->root = tnP;
  return tp;
}

//  --------------------------------------

void printTreeNodePOnFP( TreeNode * P, FILE * fp )
{
  fprintf( fp, "%s\n", P->extName );
}

void genTabs( int n, FILE * fp )
{
  while( n-- > 0 ) fprintf( fp, "  " );
}

//  --------------------------------------
//  Recursive function for listing the node names in a tree
//  in Depth First Search order

void dfsTraversalOn( TreeNode * tnP )
{
  List * childListP = tnP->childListP;
  if( childListP == NULL ) {
	fprintf(stderr, "childListP empty\n");
	return;
  }
  ListNode * childListNodeP = childListP->headP;

  while( childListNodeP != NULL )
  {
    TreeNode * childTreeNodeP = childListNodeP->treeNodeP;
    fprintf( stderr, "%s ", childTreeNodeP->extName );

    dfsTraversalOn( childTreeNodeP );

    childListNodeP = childListNodeP->nextP;
  }
}

//  --------------------------------------

void addChildToParentNode( TreeNode * parentP, 
                                   TreeNode * childP )
{
  addTreeNodeToList( childP, parentP->childListP );
}

//  --------------------------------------
//  Produce an HTML coding for the tree rooted at the 'tnP' TreeNode
//  *** NOT TO BE PROVIDED TO STUDENTS ***

void dfsCodeGenForNodeOnFile( int level, TreeNode * tnP, FILE * fp )
{
  List * childListP;

  genTabs( level, fp );
  fprintf( fp, "<li> " );
  fprintf( fp, "%s ", tnP->extName );

  childListP = tnP->childListP;

  if( childListP->tailP == NULL )  //  we arranged so that childListP never null
  {
    fprintf( fp, " </li>\n" );    
    return;
  }

  fprintf( fp, "\n" );
  genTabs( level+1, fp );
  fprintf( fp, "<ul>\n" );  

  ListNode * childListNodeP = childListP->headP;

  while( childListNodeP != NULL )
  {
    TreeNode * childTreeNodeP = childListNodeP->treeNodeP;

    dfsCodeGenForNodeOnFile( level+2, childTreeNodeP, fp );

    childListNodeP = childListNodeP->nextP;
  }

  genTabs( level+1, fp );
  fprintf( fp, "</ul>\n" );    
  genTabs( level, fp );
  fprintf( fp, "</li>\n" );
}

//  ===================================================================-
//  Functions for managing lists of children of tree nodes
//  Most don't need to be exposed outside

//  ----------------------------------------------------------------------------

List * newList( )
{
  List * lP = malloc(sizeof(List) );
  return lP;
}

//  --------------------------------------

int addTreeNodeToList( TreeNode * newTreeNodeP, List * lP )
{
  ListNode * lnP = malloc(sizeof(ListNode));
  if( lnP == NULL )
  {
    fprintf(stderr,"addTreeNodeToList(): malloc failed\n");
    return 0;
  }

  lnP->treeNodeP = newTreeNodeP;
  // fprintf( stderr, "new list node assigned tree node ptr" ); getALine( " ? " );

  if( lP->tailP == NULL )
  {
    lP->headP = lP->tailP = lnP;
    // fprintf( stderr, "added as 1st child" ); getALine( " ? " );
    return 1;
  }

  (lP->tailP)->nextP = lnP;
  lP->tailP = lnP;
  // fprintf( stderr, "appended" ); getALine( " ? " );
  return 1;
}

//  --------------------------------------

void printNodesInList( List * lP )
{
  ListNode * lnP = lP->headP;

  while( lnP != NULL ) {
    TreeNode * tnP = lnP->treeNodeP;
    printTreeNodePOnFP( tnP,  stderr );
    lnP = lnP->nextP;
  }
}

TreeNode * getNodeFromRoot(Tree *t)
{
	return t->root;
}

#ifdef TEST
#include <assert.h>
int main( int argc, char *argv[] )
{
  TreeNode * tnRoot;
  TreeNode * r    = newTreeNode( "Root" );

  Tree * t = newTree(r);
  TreeNode * tnP1 = newTreeNode( "P1" );
  TreeNode * tnP2 = newTreeNode( "P2" );
  TreeNode * tnP3 = newTreeNode( "C1" );
  TreeNode * tnP4 = newTreeNode( "C2" );

  fprintf( stderr, "nodes created\n" );

  addChildToParentNode(r, tnP1);	
  addChildToParentNode(r, tnP2);	
  addChildToParentNode(r, tnP3);	
  addChildToParentNode(r, tnP4);	
  
  fprintf( stderr, "4th child added\n" );

  tnRoot = getNodeFromRoot(t);
  assert(tnRoot == r);
  fprintf(stderr,  "DFS traversal :\n");
  dfsTraversalOn( tnRoot );
  fprintf(stderr, "\n");

  dfsCodeGenForNodeOnFile( 0, tnRoot, stderr );
}
#endif