/**
  * 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 "Heap.h"

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

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

Heap
mkEmptyHeap (void)
{
  return (Heap) 0;
}

#if MACROS
#define mkEmptyHeap() ((Heap)0)
#endif

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

Heap
mkOneElemHeap (Element e)
{
  Heap res = malloc (sizeof (*res));

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

  return res;
}

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

int
isEmptyHeap (Heap s)
{
  return s == (Heap) 0;
}

#if MACROS
#define isEmptyHeap(s) ((s) == (Heap)0)
#endif

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

Element
minElem (Heap h)
{
  assert (!isEmptyHeap (h));

  return h->info;
}

#if MACROS
#define minElem(h) ((h)->info)
#endif

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

Heap
deleteMinElem (Heap h)
{
  assert (!isEmptyHeap (h));

  {
    Heap res = mergeHeaps (h->l, h->r);
    free(h);
    return res;
  }
}

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

Heap
insertElem (Element e, Heap h)
{
  return mergeHeaps (mkOneElemHeap (e), h);
}

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

static Heap
joinHeaps (Heap h1, Heap h2)
{
  Heap t;

  assert (!isEmptyHeap (h1));
  assert (!isEmptyHeap (h2));
  assert (compare (h1->info, h2->info) <= 0);

  t = mergeHeaps (h1->l, h2);
  h1->l = h1->r;
  h1->r = t;

  return h1;
}

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

Heap
mergeHeaps (Heap h1, Heap h2)
{
  if (isEmptyHeap (h1))
    return h2;

  if (isEmptyHeap (h2))
    return h1;

  if (compare (minElem (h1), minElem (h2)) <= 0)
    return joinHeaps (h1, h2);

  return joinHeaps (h2, h1);
}

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

static int
greaterThanOrEqual (Heap h, Element e)
{
  return
    isEmptyHeap (h)
    ||
    ( compare (h->info, e) >= 0 );
}

int
invHeap (Heap h)
{
  return
    isEmptyHeap (h)
    ||
    (greaterThanOrEqual (h->l, h->info)
     &&
     greaterThanOrEqual (h->r, h->info)
     &&
     invHeap(h->l)
     &&
     invHeap(h->r)
     );
}

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