#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#include <limits.h>

#include "iset.h"

typedef struct _iset_node
{
  int data;
  struct _iset_node *parent;
  struct _iset_node *left;
  struct _iset_node *right;
} iset_node;

/**
 * Information resulting from a search for the node containing a value:
 * the node (or NULL if not found);
 * the parent or would-be parent (or NULL if n is or would be the root);
 * a pointer to the pointer to the node or would-be node;
 * whether it was found (redundant: can determine from whether n is NULL); and
 * the direction parent to n (undefined if n is or would be the root).
 */
typedef struct
{
  iset_node *parent;
  iset_node *n;
  iset_node **incoming;
  bool found;
  int dir;
} iset_search_result;

struct iset
{
  iset_node *root;
  int size;
};

/**
 * Returns a pointer to a new node containing the item.
 *
 * @param item an integer
 * @return a pointer to a new node containing the item
 */
iset_node *iset_create_node(int item);

/**
 * Deletes the given node in the given BST.
 *
 * @param s a pointer to a set, non-NULL
 * @param node a node in that set's tree
 */
void iset_delete_node(iset* s, const iset_search_result *result);

/**
 * Finds the node containing the given integer in the given set's tree,
 * or, if the integer is not there, determines where it would be added.
 *
 * @param s a pointer to a set, non-NULL
 * @param item an integer
 * @param return a pointer to the struct in which to record the results
 * of the search
 */
void iset_find_node(iset *s, int item, iset_search_result *result);

/**
 * Deletes all of the nodes in the tree rooted at the given node.
 * There is no effect if given pointer is NULL.
 *
 * @param n a pointer to a node
 */
void iset_destroy_subtree(iset_node *n);

void iset_for_each_range_subtree(iset_node *n, void (*f)(int, void *), void *a, int min, int max, int subtree_min, int subtree_max);

/**
 * Prints the contents of the subtree rooted at the given node,
 * or "null" if the given pointer is NULL.
 *
 * @param node a pointer to a node
 * @param level the depth of that node
 */
void iset_print_subtree(const iset_node *node, int level);

/**
 * Processes the contents of the subtree rooted at the given node.
 * All items (along with their levels in the tree) will be passed to
 * the given function.
 *
 * @param node a pointer to a node
 * @param level the depth of that node
 */
void iset_for_each_subtree(iset_node *n, void (*f)(int, int, void *), void *a, int level);

iset *iset_create()
{
  iset *s = malloc(sizeof(iset));

  if (s != NULL)
    {
      s->root = NULL;
      s->size = 0;
    }

  return s;
}

int iset_size(const iset *s)
{
  if (s != NULL)
    {
      return s->size;
    }
  else
    {
      return 0;
    }
}

bool iset_contains(const iset *s, int item)
{
  if (s == NULL)
    {
      return false;
    }
  else
    {
      iset_search_result result;
      iset_find_node((iset *)s, item, &result); // remove const via cast
      
      return result.found;
    }
}

void iset_find_node(iset *s, int item, iset_search_result *result)
{
  // start at root
  iset_node *parent = NULL;
  iset_node *curr = s->root;
  iset_node **incoming = &s->root;
  int dir = 0;

  // keep going while not out of places to look and not at what we want
  while (curr != NULL && (dir = item - curr->data) != 0)
    {
      parent = curr;
      if (dir < 0)
	{
	  // item is < value in current node; go left
	  incoming = &curr->left;
	  curr = curr->left;
	}
      else
	{
	  // item is > value in current node; go right
	  incoming = &curr->right;
	  curr = curr->right;
	}
    }

  // save results in struct
  result->parent = parent;
  result->n = curr;
  result->incoming = incoming;
  result->dir = dir;
  result->found = (curr != NULL);
}

bool iset_add(iset *s, int item)
{
  if (s == NULL)
    {
      return false;
    }
  
  // check if item is already in the set
  iset_search_result result;
  iset_find_node(s, item, &result);
  if (result.found)
    {
      // in the set already; nothing more to do
      return false;
    }

  // create new node and link parent to it
  iset_node *new_node = iset_create_node(item);
  *result.incoming = new_node;

  // link new node back to parent
  if (new_node != NULL)
    {
      new_node->parent = result.parent;
      s->size++;
  
      return true;
    }
  else
    {
      return false;
    }
}

iset_node *iset_create_node(int item)
{
  iset_node *result = (iset_node *)malloc(sizeof(iset_node));

  if (result != NULL)
    {
      result->right = NULL;
      result->left = NULL;
      result->data = item;
    }

  return result;
}

bool iset_remove(iset *s, int item)
{
  if (s == NULL)
    {
      return false;
    }

  // find node containing item
  iset_search_result result;
  iset_find_node(s, item, &result);
  if (!result.found)
    {
      return false;
    }

  // delete it
  iset_delete_node(s, &result);
  return true;
}

void iset_delete_node(iset *s, const iset_search_result *result)
{
  iset_node *node = result->n;

  if (node->left == NULL && node->right == NULL)
    {
      // no children: just remove node
      *result->incoming = NULL;
      s->size--;
    }
  else if (node->left == NULL)
    {
      // only a right child: move it up to replace deleted
      *result->incoming = node->right;
      node->right->parent = node->parent;
      s->size--;
    }
  else if (node->right == NULL)
    {
      // only a left child: move it up to replace deleted
      *result->incoming = node->left;
      node->left->parent = node->parent;
    }
  else
    {
      // TWO CHILDREN CASE

      // find replacement node (smallest [leftmost] in right subtree
      // or largest [rightmost] in left subtree)

      // link parent of replacement to replacement's right child
      // link replacement to deleted's children
      // link parent of deleted to replacement
    }

  // free space for node
  free(node);
}

void iset_for_each(iset *s, void (*f)(int, int, void *), void *a)
{
  if (s != NULL && f != NULL)
    {
      iset_for_each_subtree(s->root, f, a, 0);
    }
}

void iset_for_each_subtree(iset_node *n, void (*f)(int, int, void *), void *a, int level)
{
  if (n != NULL)
    {
      // inorder traversal: left subtree, then node, then right subtree
      // (processes data in sorted order!)
      iset_for_each_subtree(n->left, f, a, level + 1);
      f(n->data, level, a);
      iset_for_each_subtree(n->right, f, a, level + 1);
    }
}

void iset_for_each_range(iset *s, void (*f)(int, void *), void *a, int min, int max)
{
  if (s != NULL && f != NULL)
    {
      iset_for_each_range_subtree(s->root, f, a, min, max, INT_MIN, INT_MAX);
    }
}

void iset_for_each_range_subtree(iset_node *n, void (*f)(int, void *), void *a, int min, int max, int subtree_min, int subtree_max)
{
  // base cases: empty tree or no overlap between range of values
  // in current subtree and range we're interested in
  if (n == NULL || subtree_min > max || subtree_max < min)
    {
      return;
    }
  else
    {
      iset_for_each_range_subtree(n->left, f, a, min, max, subtree_min, n->data - 1);

      if (n->data >= min && n->data <= max)
	{
	  f(n->data, a);
	}

      iset_for_each_range_subtree(n->right, f, a, min, max, n->data + 1, subtree_max);
    }
}

void iset_destroy(iset *s)
{
  iset_destroy_subtree(s->root);
  s->size = 0;
  s->root = NULL;
  free(s);
}

void iset_destroy_subtree(iset_node *n)
{
  if (n != NULL)
    {
      // postorder traversal to delete nodes
      iset_destroy_subtree(n->left);
      iset_destroy_subtree(n->right);
      free(n);
    }
}

void iset_print_subtree(const iset_node *node, int level)
{
  // don't need this any more since we have for_each, but maybe useful
  // for debugging?
  for (int i = 0; i < level; i++)
    {
      printf(" ");
    }
  if (node != NULL)
    {
      printf("level %d: %d\n", level, node->data);
      iset_print_subtree(node->left, level + 1);
      iset_print_subtree(node->right, level + 1);
    }
  else
    {
      printf("null\n");
    }
}