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

#include "bfs.h"
#include "memory_man.h"

/* main function */
int main(int argc, char * argv[])
{  
  Graph graph;
  unsigned int root_id = 0;
  const char * filename = NULL;
  Node * root = NULL;

  if (argc < 3) {
    print_help(strrchr(argv[0], '/'));
    exit_error("Missing input file name!");
  }
  
  root_id = atoi(argv[1]);
  filename = argv[2];
  graph_init(&graph, filename);
  root = get_node_by_id(&graph, root_id);
  BFS(&graph, root);
  tree_print(root);
  graph_clear(&graph);
  mem_clear();
  return 0;
}

/* Prints an error message, deallocates resources if needed and exists
 * the program with error code -1.
 * \param err_msg is the text of the error msg
 */
void exit_error(char * err_msg)
{
  fprintf(stderr, "ERROR: %s\n", err_msg);
  mem_clear();
  exit(-1);
}

/* Reads a line from the input stream
 * \param stream the input stream that describes the graph
 * \param line the output line to fill
 * \paramm size the maximum nuber of characters in the line to fill
 */
int get_line(FILE * stream, char * line, int size)
{
  fgets(line, size, stream);  
  if (ferror(stream)) 
    exit_error("Failed reading input file!");
  if (feof(stream)) return EOF;
  else return 0;
}

/* Prints a concise message describing the command line
 * \param prog_name the name of the executable
 */
void print_help(char * prog_name)
{
  printf("Usage: %s root file\n\
  <root> \tbuild tree from node with id <root>\n",
  prog_name);
}

/* Prints a tree in a nicely formatted way.
 * Prints the id of the given node, then prints the ids of its children
 * recursively.
 */
void print_children(Node * node)
{
  Children_list list;
  static int level = -1; /* initialization only happens once! */
  ++level;  
  printf("\n%*.s(%u", level, "", node->id);  
  for (list = node->children; list != NULL; list = list->next) {
    print_children((Node *) list->node);
  }
  printf(")");
  --level;
}

/* Prints the tree
 * \param root the root of the tree
 */
void tree_print(Node *root)
{
  print_children(root);
  printf("\n");
}

/*! Reads a description of a graph from an input file and creates it.
 * Allocates an array if nodes, and adds arcs as necessary.
 * \param graph the output graph 
 * \param file_name the name of the input file that contains the graph
 * description.
 *
 * The file format follows. The number of nodes in the graph (must be greater
 * than 0) followed by bi-directional arcs. An id of a node is a number from 0
 * to n-1. Each arc is described by a pair of nodes embeded within parenthesis
 * and separated with a comma, for example (1, 2)
 *  
 * \return 0 upon success, and a negative number upon failure.
 *
 * Possible errors:
 * 1. The input file does not exist or it is not readable
 * 2. The number of nodes is 0
 * 3. An attempt to insert an arc that already exists. For example (a,b), (b,a)
 * 4. An attempt to insert a self loops (a, a)  
 */
void graph_init(Graph * graph, const char * file_name) 
{
  /* ADD YOUR CODE HERE */
}

/*! Clears a graph
 * Deallocates all data structures used by a graph
 * \param graph the graph to be cleared
 */
void graph_clear(Graph * graph)
{
  /* ADD YOUR CODE HERE */
}

/*! Obtains a graph node by its id.
 * If the id is invalid, generates an error
 */
Node * get_node_by_id(Graph * graph, unsigned int id)
{
  /* ADD YOUR CODE HERE */
}

/* Implements the Breath-First-Search algorithm
 * \param graph the graph to process
 * \param root the root node of the graph
 */
void BFS(Graph * graph, Node * root)
{
  /* ADD YOUR CODE HERE */
}