/*         ______   ___    ___
 *        /\  _  \ /\_ \  /\_ \
 *        \ \ \L\ \\//\ \ \//\ \      __     __   _ __   ___
 *         \ \  __ \ \ \ \  \ \ \   /'__`\ /'_ `\/\`'__\/ __`\
 *          \ \ \/\ \ \_\ \_ \_\ \_/\  __//\ \L\ \ \ \//\ \L\ \
 *           \ \_\ \_\/\____\/\____\ \____\ \____ \ \_\\ \____/
 *            \/_/\/_/\/____/\/____/\/____/\/___L\ \/_/ \/___/
 *                                           /\____/
 *                                           \_/__/
 *
 *      AA tree, a type of self-balancing search tree.
 *
 *      By Peter Wang.
 */

/* prettier */
#define _AL_AATREE Aatree

#include "allegro5/allegro.h"
#include "allegro5/internal/aintern_aatree.h"

struct DelInfo
{
   const void *key;
   _al_cmp_t compare;
   Aatree *last;
   Aatree *deleted;
};

static Aatree nil = { 0, &nil, &nil, NULL, NULL };

static Aatree *skew(Aatree *T)
{
   if (T == &nil)
      return T;
   if (T->left->level == T->level) {
      Aatree *L = T->left;
      T->left = L->right;
      L->right = T;
      return L;
   }
   return T;
}

static Aatree *split(Aatree *T)
{
   if (T == &nil)
      return T;
   if (T->level == T->right->right->level) {
      Aatree *R = T->right;
      T->right = R->left;
      R->left = T;
      R->level = R->level + 1;
      return R;
   }
   return T;
}

static Aatree *singleton(const void *key, void *value)
{
   Aatree *T = al_malloc(sizeof(Aatree));
   T->level = 1;
   T->left = &nil;
   T->right = &nil;
   T->key = key;
   T->value = value;
   return T;
}

static Aatree *doinsert(Aatree *T, const void *key, void *value,
   _al_cmp_t compare)
{
   int cmp;
   if (T == &nil) {
      return singleton(key, value);
   }
   cmp = compare(key, T->key);
   if (cmp < 0) {
      T->left = doinsert(T->left, key, value, compare);
   }
   else if (cmp > 0) {
      T->right = doinsert(T->right, key, value, compare);
   }
   else {
      /* Already exists. We don't yet return any indication of this. */
      return T;
   }
   T = skew(T);
   T = split(T);
   return T;
}

Aatree *_al_aa_insert(Aatree *T, const void *key, void *value,
   _al_cmp_t compare)
{
   if (T == NULL)
      T = &nil;
   return doinsert(T, key, value, compare);
}

void *_al_aa_search(const Aatree *T, const void *key, _al_cmp_t compare)
{
   if (T == NULL)
      return NULL;
   while (T != &nil) {
      int cmp = compare(key, T->key);
      if (cmp == 0)
         return T->value;
      T = (cmp < 0) ? T->left : T->right;
   }
   return NULL;
}

static Aatree *dodelete(struct DelInfo *info, Aatree *T, void **ret_value)
{
   if (T == &nil)
      return T;

   /* Search down the tree and set pointers last and deleted. */
   info->last = T;
   if (info->compare(info->key, T->key) < 0) {
      T->left = dodelete(info, T->left, ret_value);
   }
   else {
      info->deleted = T;
      T->right = dodelete(info, T->right, ret_value);
   }

   /* At the bottom of the tree we remove the element if it is present. */
   if (T == info->last &&
      info->deleted != &nil &&
      info->compare(info->key, info->deleted->key) == 0)
   {
      Aatree *right = T->right;
      *ret_value = info->deleted->value;
      info->deleted->key = T->key;
      info->deleted->value = T->value;
      info->deleted = &nil;
      al_free(T);
      return right;
   }

   /* On the way back, we rebalance. */
   if (T->left->level < T->level - 1
      || T->right->level < T->level - 1)
   {
      T->level--;
      if (T->right->level > T->level) {
         T->right->level = T->level;
      }
      T = skew(T);
      T->right = skew(T->right);
      T->right->right = skew(T->right->right);
      T = split(T);
      T->right = split(T->right);
   }
   return T;
}

/* ret_value is only set if the item was found and deleted.
 * The caller should set it to some distinct value, e.g. NULL,
 * to detect if no item was found.
 */
Aatree *_al_aa_delete(Aatree *T, const void *key, _al_cmp_t compare,
   void **ret_value)
{
   struct DelInfo info;
   info.key = key;
   info.compare = compare;
   info.last = &nil;
   info.deleted = &nil;

   if (T) {
      T = dodelete(&info, T, ret_value);
      if (T == &nil)
         T = NULL;
   }
   return T;
}

void _al_aa_free(Aatree *T)
{
   if (T && T != &nil) {
      _al_aa_free(T->left);
      _al_aa_free(T->right);
      al_free(T);
   }
}

/* vim: set sts=3 sw=3 et: */
