/**
  * 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 <stdlib.h>
#include <stdio.h>
#include <assert.h>

#include "List.h"

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

/* simple ops as functions */

#if ! MACROS

List
mkEmptyList(void)
{
  return (List) 0;
}

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

int
isEmptyList(List l)
{
  return l == (List) 0;
}

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

Element
head(List l)
{
  assert(! isEmptyList(l));
  return l->info;
}

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

List
tail(List l)
{
  assert(! isEmptyList(l));
  return l->next;
}

#endif

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

List
removeHead(List l)
{
  assert(! isEmptyList(l));
  {
    List res = l->next;
    free(l);
    return res;
  }
}

List
cons(Element e, List l)
{
  /* the only call of malloc */
  List res = malloc(sizeof(*l));

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

  return res;
}

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

#if ! ITERATIVE

unsigned int
length(List l)
{
  return isEmptyList(l)
    ? 0
    : 1 + length(tail(l));
}

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

#else

unsigned int
length(List l)
{
  unsigned int res;

  for (res = 0; ! isEmptyList(l);
       l = l->next)
    ++res;

  return res;
}

#endif

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

#if ! ITERATIVE

Element
at(List l, unsigned int i)
{
  return i == 0
    ? head(l)
    : at(tail(l), i - 1);
}

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

#else

Element
at(List l, unsigned int i)
{
  while (i != 0)
    {
      l = tail(l);
      --i;
    }
  return head(l);
}

#endif

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

#if ! ITERATIVE

int
isInList(Element e, List l)
{
  if (isEmptyList(l))
    return 0;

  if (eqElement(e, l->info))
    return 1;

#if SORTED
  if (! geElement(e, l->info))
    return 0;
#endif

  return isInList(e, l->next);
}

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

#else

int
isInList(Element e, List l)
{
  while (! isEmptyList(l)
#if SORTED
         &&
         geElement(e, l->info)
#endif
    )
    {
      if (eqElement(e, l->info))
        return 1;
      l = l->next;
    }
  return 0;
}

#endif

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

#if ! SORTED

List
insertElem(Element e, List l)
{
#if DUPLICATES
  return cons(e, l);

#else

  return isInList(e, l)
    ? l
    : cons(e, l);
#endif
}

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

#else
/* sorted list */

#if ! ITERATIVE

List
insertElem(Element e, List l)
{
  if (isEmptyList(l)
      ||
      ! geElement(e, l->info))
    return cons(e, l);

#if ! DUPLICATES
  if (eqElement(e, l->info))
    return l;
#endif

  l->next = insertElem(e, l->next);
  return l;
}

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

#else

List
insertElem(Element e, List l)
{
  List *pl = &l;

  while (! isEmptyList(*pl)
         &&
         ! geElement((*pl)->info, e))
    {
      pl = &((*pl)->next);
    }

#if ! DUPLICATES
  if (! isEmptyList(*pl)
      && eqElement(e, (*pl)->info))
    return l;
#endif

  *pl = cons(e, *pl);
  return l;
}
#endif

#endif

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

static List
removeElem1(Element e, List l)
{
  if (isEmptyList(l))
    return l;

#if SORTED
  if (! geElement(e, l->info))
    return l;
#endif

  if (eqElement(e, l->info))
    {
      return
	removeHead(l);
    }

  l->next = removeElem1(e, l->next);
  return l;
}

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

/* a save version of removeElem */

List
removeElem(Element e, List l)
{
  List res = removeElem1(e, l);

  assert(invList(res));
  return res;
}

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

static List
removeAllElems1(Element e, List l)
{
  if (isEmptyList(l))
    return l;

#if SORTED
  if (! geElement(e, l->info))
    return l;
#endif

  if (eqElement(e, l->info))
    {
      return
	removeAllElems1(e, removeHead(l));
    }

  l->next = removeAllElems1(e, l->next);
  return l;
}

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

/* a save version of removeAllElems */

List
removeAllElems(Element e, List l)
{
  List res = removeAllElems1(e, l);

  assert(invList(res));
  assert(! isInList(e, res));
  return res;
}

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

List
concat(List l1, List l2) {
  if ( isEmptyList(l1) )
    return l2;

  l1->next = concat(l1->next, l2);
  return l1;
}

List
append(List l, Element e) {
  return
    concat(l,
	   cons(e, mkEmptyList()));
}

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

List
splitAt(List l,
	unsigned int i,
	List * rest) {
  if (i == 0) {
    * rest = l;
    return mkEmptyList();
  }
  l->next = splitAt(tail(l),
		    i-1,
		    rest);
  return l;
}

List
removeAt(List l,
	 unsigned int i) {
  if (i == 0) {
    return removeHead(l);
  }
  l->next = removeAt(tail(l),
		     i-1);
  return l;
}

List
insertAt(List l,
	 unsigned int i,
	 Element e) {
  if (i == 0) {
    return cons(e, l);
  }
  l->next = insertAt(tail(l),
		     i-1,
		     e);
  return l;
}

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

List
Union(List l1, List l2) {
#if ! SORTED

#if ! DUPLICATES

  if ( isEmptyList(l1) )
    return l2;
  l2 = insertElem(l1->info, l2);
  return Union(removeHead(l1), l2);

#else

  return concat(l1, l2);

#endif

#else

  if ( isEmptyList(l1) )
    return l2;

  if ( isEmptyList(l2) )
    return l1;

#if ! DUPLICATES
  if ( eqElement(l1->info, l2->info) )
    return Union(removeHead(l1), l2);
#endif

  if ( geElement(l1->info, l2->info) ) {
    l2->next = Union(l1, l2->next);
    return l2;
  } else {
    l1->next = Union(l1->next, l2);
    return l1;
  }

#endif
}

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

/* Invariant for sorted lists */

#if SORTED

int
invList(List l)
{
  if (isEmptyList(l))
    return 1;

  if (isEmptyList(l->next))
    return 1;

#if ! DUPLICATES
  if (eqElement(l->info, l->next->info))
    return 0;
#endif

  return
    geElement(l->next->info, l->info)
    &&
    invList(l->next);
}

#else

#if DUPLICATES

int
invList(List l)
{
  if (isEmptyList(l))
    return 1;

  return
    ! isInList(l->info, l->next)
    &&
    invList(l->next);
}


#endif

#endif

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

unsigned spaceUsed(List l)
{
  return length(l) * sizeof (*l);
}

unsigned spaceNecc(List l)
{
  return length(l) * sizeof (l->info);
}

double spaceOverhead(List l)
{
  return
    (double)spaceUsed(l) /
    (double)spaceNecc(l);
}

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