/**
  * Copyright (c): Uwe Schmidt, FH Wedel
  *
  * You may study, modify and distribute this source code
  * FOR NON-COMMERCIAL PURPOSES ONLY.
  * This copyright message has to remain unchanged.
  *
  * Note that this document is provided 'as is',
  * WITHOUT WARRANTY of any kind either expressed or implied.
  */

#include "Set.h"

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

/*--------------------*/

#if ! MACROS

Set
mkEmptySet(void)
{
  return (Set) 0;
}

/*--------------------*/

int
isEmptySet(Set s)
{
  return s == (Set) 0;
}

#endif

/*--------------------*/

Set
mkOneElemSet(Element e)
{
  Set res = malloc(sizeof(*res));

  if (!res)
    {
      perror("mkOneElemSet: malloc failed");
      exit(1);
    }
  res->info = e;
  res->l = mkEmptySet();
  res->r = mkEmptySet();

  return res;
}

/*--------------------*/

int
isInSet(Element e, Set s)
{
  if (isEmptySet(s))
    return 0;

  switch (compare(e, s->info))
    {
    case -1:
      return isInSet(e, s->l);
    case 0:
      return 1;
    case +1:
      return isInSet(e, s->r);
    }

  assert(0);
  return 0;
}

/*--------------------*/

Set
insertElem(Element e, Set s)
{
  if (isEmptySet(s))
    return mkOneElemSet(e);

  switch (compare(e, s->info))
    {
    case -1:
      s->l = insertElem(e, s->l);
      break;
    case 0:
      break;
    case +1:
      s->r = insertElem(e, s->r);
      break;
    }

  return s;
}

/*--------------------*/

static int
lessThan(Set s, Element e)
{
  return
    (isEmptySet(s)
     || (compare(s->info, e) == -1
         &&
         lessThan(s->r, e)
         /*
         &&
         lessThan(s->l, e) is redundant */
	 )
    );

}

/*--------------------*/

static int
greaterThan(Set s, Element e)
{
  return
    (isEmptySet(s)
     || (compare(s->info, e) == +1
         &&
         greaterThan(s->l, e)
         /*
         &&
         greaterThan(s->r, e) is redundant */
        )
    );
}

/*--------------------*/

int
invSetAsBintree(Set s)
{
  return
    isEmptySet(s)
    || (lessThan(s->l, s->info)
        &&
        greaterThan(s->r, s->info)
        &&
        invSetAsBintree(s->l)
        &&
        invSetAsBintree(s->r));
}

/*--------------------*/

Nat0
card(Set s)
{
  if (isEmptySet(s))
    return 0;

  return card(s->l) + 1 + card(s->r);
}

/*--------------------*/

static Nat0
max(Nat0 i, Nat0 j)
{
  return i > j ? i : j;
}

/*--------------------*/

static Nat0
min(Nat0 i, Nat0 j)
{
  return i < j ? i : j;
}

/*--------------------*/

Nat0
maxPathLength(Set s)
{
  if (isEmptySet(s))
    return 0;

  return
    1 + max(maxPathLength(s->l),
            maxPathLength(s->r));
}

/*--------------------*/

Nat0
minPathLength(Set s)
{
  if (isEmptySet(s))
    return 0;

  return
    1 + min(minPathLength(s->l),
            minPathLength(s->r));
}

/*--------------------*/

static Element
maxElem(Set s)
{
  assert(!isEmptySet(s));

  if (isEmptySet(s->r))
    return s->info;

  return maxElem(s->r);
}

/*--------------------*/

static Set
removeRoot(Set s)
{
  assert(!isEmptySet(s));

  if (isEmptySet(s->l)
      || isEmptySet(s->r))
    {
      Set res =
        isEmptySet(s->l) ? s->r : s->l;
      free(s);
      return res;
    }

  assert(!isEmptySet(s->l));
  assert(!isEmptySet(s->r));

  s->info = maxElem(s->l);
  s->l = removeElem(s->info, s->l);

  return s;
}

/*--------------------*/

Set
removeElem(Element e, Set s)
{
  if (isEmptySet(s))
    return s;

  switch (compare(e, s->info))
    {
    case -1:
      s->l = removeElem(e, s->l);
      break;
    case 0:
      s = removeRoot(s);
      break;
    case +1:
      s->r = removeElem(e, s->r);
      break;
    }

  return s;
}

/*--------------------*/

static Set
flat(Set s, Set res)
{
  if (isEmptySet(s))
    return res;

  s->r = flat(s->r, res);

  return flat(s->l, s);
}

/*--------------------*/

static Set
balance(Set s, Nat0 length)
{
  if (length == 0)
    return mkEmptySet();

  {
    Nat0 rootPos = length / 2;
    Set root = s;

    while (rootPos--)
      root = root->r;

    root->l = balance(s, length / 2);
    root->r = balance(root->r,
                      length -
                      length / 2 - 1);
    return root;
  }
}

/*--------------------*/

int
isBalancedBintree(Set t) {
  return
    maxPathLength(t) -
    minPathLength(t) <= 1;
}

Set
balanceBintree(Set t)
{
  Nat0 length = card(t);

  Set res = balance(flat(t,
                         mkEmptySet()),
                    length);

  assert(isBalancedBintree(res));

  assert(card(res) == length);

  assert(invSetAsBintree(res));

  return res;
}

/*--------------------*/