#include <stdlib.h>
#include <stdio.h>
#include "map.h"

struct node {
  int key;
  void* value;
  struct node* left;
  struct node* right;
};

struct map {
  struct node* root;
};

struct map* map_init() {
  struct map* map = malloc(sizeof(struct map));
  map->root = NULL;
  return map;
}

void free_node(struct node*n) {
  if(!n)
    return;
  free_node(n->left);
  free_node(n->right);
  free(n);
}

void map_free(struct map*map) {
  free_node(map->root);
  free(map);
}

/* return the node of key or NULL if not found */
static struct node* map_find_key(struct node* node, int key) {
  if(!node)
    return NULL;

  if(node->key == key)
    return node;
  if(node->key < key)
    return map_find_key(node->right, key);
  return map_find_key(node->left, key);
}

struct node* new_node(int key, void*val) {
  struct node* n = malloc(sizeof(struct node));
  n->left=NULL;
  n->right=NULL;
  n->key=key;
  n->value=val;
  return n;
}

/* insert n in a tree */
struct node* insert(struct node* tree, struct node*n) {
  if(!tree)
    return n;

  if(n->key > tree->key) {
    /* insert  */
    tree->right = insert(tree->right, n);
  } else {
    tree->left = insert(tree->left, n);
  }
  return tree;
}

void print_tab(int depth) {
  for(int i=0; i<depth; i++)
    printf("  ");
}

void print_node(struct node* n, int depth) {
  print_tab(depth);
  if(!n) {
    printf("NULL\n");
    return;
  }
  printf("<%d>\n", n->key);
  print_tab(depth);
  printf("Left of %d: \n", n->key);
  print_node(n->left, depth+1);
  printf("Right of %d: \n", n->key);
  print_node(n->right, depth+1);
}

void print_tree(struct map* map){
  if(map)
    print_node(map->root, 0);
}

void map_put(struct map* map, int key, void* val) {
  printf("\n\nInsert (%d, %p)\n", key, val);
  struct node*n = map_find_key(map->root, key);
  if(!n) {
    /* key was not found. expend the array */
    n = new_node(key, val);
    map->root = insert(map->root, n);
  } else {
    n->value = val;
  }
  print_tree(map);
}

void*  map_get(struct map* map, int key) {
  struct node*n = map_find_key(map->root, key);
  if(n)
    return n->value;
  return NULL;
}