/**
  * 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>

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

/* special empty node, marked as black */

static struct Node finalNode = { BLACK };

Set
mkEmptySet(void)
{
  return &finalNode;
}

/* local optimization */

#define mkEmptySet() (&finalNode)

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

int
isEmptySet(Set s)
{
  return s == &finalNode;
}

/* local optimization */

#define isEmptySet(s) ((s) == &finalNode)

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

/* auxiliary function: file scope */

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

  if (!res)
    {
      perror
        ("mkNewNode: malloc failed");
      exit(1);
    }

  res->color = RED;             /* every new node is red */
  res->info = e;
  res->l = mkEmptySet();
  res->r = mkEmptySet();

  return res;
}

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

Set
mkOneElemSet(Element e)
{
  return insertElem(e, mkEmptySet());
}

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

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;
}

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

/* color predicates */

#define isBlackNode(s) ((s)->color == BLACK)
#define isRedNode(s) (! isBlackNode(s))

static int
hasRedChild(Set s)
{
  return
    ! isEmptySet(s)
    && (isRedNode(s->l)
        ||
	isRedNode(s->r));
}

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

/* reorganize tree */

static Set
balanceTrees(Set x, Set y, Set z,
	     Set b, Set c)
{
  x->r = b;
  z->l = c;

  y->l = x;
  y->r = z;

  x->color = BLACK;
  z->color = BLACK;
  y->color = RED;

  return y;
}

/* check invariant */

/* check balance in left subtree */

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

  /* no balancing of trees with red root */

  if (isRedNode(s))
    return s;

  if (isRedNode(s->l)
      && isRedNode(s->l->l))
    return balanceTrees(s->l->l,
			s->l,
                        s,
			s->l->l->r,
                        s->l->r);

  if (isRedNode(s->l)
      && isRedNode(s->l->r))
    return balanceTrees(s->l,
			s->l->r,
                        s,
			s->l->r->l,
                        s->l->r->r);

  return s;
}

/* check balance in right subtree */

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

  /* no balancing of trees with red root */

  if (isRedNode(s))
    return s;

  if (isRedNode(s->r)
      && isRedNode(s->r->l))
    return balanceTrees(s,
			s->r->l,
                        s->r,
                        s->r->l->l,
                        s->r->l->r);

  if (isRedNode(s->r)
      && isRedNode(s->r->r))
    return balanceTrees(s,
			s->r,
                        s->r->r,
                        s->r->l,
                        s->r->r->l);

  return s;
}

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

static Set
insertElem1(Element e, Set s)
{
  if (isEmptySet(s))
    return mkNewRedNode(e);

  switch (compare(e, s->info))
    {
    case -1:
      s->l = insertElem1(e, s->l);

      /* invariant is checked with left subtree */
      return checkBalanceLeft(s);

    case 0:
      break;

    case +1:
      s->r = insertElem1(e, s->r);

      /* invariant is checked with right subtree */
      return checkBalanceRight(s);
    }

  return s;
}

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

Set
insertElem(Element e, Set s)
{
  Set res = insertElem1(e, s);

  /* the root is always black */

  res->color = BLACK;

  assert(invSetAsRedBlackTree(res));

  return res;
}

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

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

}

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

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

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

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

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

static int
invNoRedNodeHasRedChild(Set s)
{
  if (isEmptySet(s))
    return 1;

  return
    (isBlackNode(s)
     ||
     ! hasRedChild(s)
    )
    &&
    invNoRedNodeHasRedChild(s->l)
    &&
    invNoRedNodeHasRedChild(s->r);
}

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

static int
noOfBlackNodes(Set s)
{
  if (isEmptySet(s))
    return 1;

  {
    int nl = noOfBlackNodes(s->l);
    int nr = noOfBlackNodes(s->r);

    if (nl == nr && nl != -1)
      return nl + isBlackNode(s);

    /* invariant does not hold */
    return -1;
  }
}

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

int
invSetAsRedBlackTree(Set s)
{
  return
    invSetAsBinTree(s)
    &&
    invNoRedNodeHasRedChild(s)
    &&
    noOfBlackNodes(s) != -1;
}

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

unsigned int
card(Set s)
{
  if (isEmptySet(s))
    return 0;

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

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

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

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

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

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

unsigned int
maxPathLength(Set s)
{
  if (isEmptySet(s))
    return 0;

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

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

unsigned int
minPathLength(Set s)
{
  if (isEmptySet(s))
    return 0;

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

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