#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
/* to help you solve the kata, a queue implementation has been
preloaded for you */

typedef struct Queue Queue;

// the queue elements are pointers

// creates a new queue
extern Queue *new_queue (void);
// returns the number of elements in the queue
extern size_t queue_size (const Queue *queue);
// adds an element at the back of the queue and returns the queue
extern Queue *queue_enqueue (Queue *queue, const void *data);
// removes the element at the front of the queue and returns it
extern void *queue_dequeue (Queue *queue);
// frees the queue, do not forget to call it !
extern void free_queue (Queue *queue);
/* ==================================================== */

typedef struct Tree {
	struct Tree *left, *right;
	int value;
} Tree;

Queue* q;

int task;

void proceed_childs(const Tree *ptr, int depth, char c) {

  if(depth>3) return;
    char tab[depth+1];
    for(int i=0;i<depth;i++) {
      tab[i] = '\t';
    }
    tab[depth] = '\0';


    printf("\n%s#%d %c (node %p)\n", tab, depth, c, ptr);

    if(ptr->left != NULL) {
      queue_enqueue(q, ptr->left);
      /*if(depth<2) {
        queue_enqueue(q, &ptr->left->value);
        printf("%sLeft [%d]\n",tab,ptr->left->value);
      } else {
        queue_enqueue(q, &ptr->left->value);
        printf("%s!!! Left [%d] %p\n",tab,ptr->left->value, &ptr->left);
      } */
    }
    if(ptr->right != NULL) {
      queue_enqueue(q, ptr->right);
      /*if(depth<2) {
        queue_enqueue(q, &ptr->right->value);
        printf("%sRight [%d]\n",tab,ptr->right->value);
      } else {
        printf("%s!!! Right [%d] %p\n",tab,ptr->right->value, &ptr->right);
      }*/
    }

    ++depth;
    printf("\n%s>>Next depth %d\n", tab, depth);


    if(ptr->left != NULL) {
      //printf("%sCall left %p from %p (new depth %d):\n", tab,ptr->left, ptr, depth);
      proceed_childs(ptr->left, depth, 'l');
    }

    if(ptr->right!=NULL) {
      //printf("%sCall right %p from %p (new depth %d):\n", tab, ptr->right, ptr, depth);
      proceed_childs(ptr->right, depth, 'r');
    }
}

int *tree_by_levels (const Tree *tree, size_t *tree_size)
{
  task++;
  if(task>1) return NULL;
  printf("\nTask #%d\n", task);
  q = new_queue();
  queue_enqueue(q, tree);
  proceed_childs(tree, 0, '-');
  *tree_size = queue_size(q);
  printf("\nTotal: %zu\n",*tree_size);

  int* result = malloc(sizeof(int)*(*tree_size));

  for(size_t i=0; i<*tree_size; i++) {
    result[i] = -1;
    if(queue_size(q)==0) continue;
    void* e = queue_dequeue(q);
    if(e==NULL) {
      printf("Error");
    } else {

      Tree* node = (Tree*)e;
      int value = node->value;
      printf("%d %p %p %d\n", i, e, node, node->value);
      result[i] = value;
    }
  }

  printf("\n\n");
  free_queue(q);

  for(int i=0;i<*tree_size;i++) {
    printf("%d=%d\n", i, result[i]);
  }

  return result; // return a heap-allocated array, it will be freed
}