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

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

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

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

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

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

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

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

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

List
tail (List l)
{
  List front;
  List front2;

  assert (!isEmptyList (l));

  front  = l->next;
  front2 = front->next;

  free (front);

  if (l == front)
      return mkEmptyList ();

  else
    {
      l->next = front2;
      return l;
    }
}

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

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

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

  res->info = e;
  res->next = res;		/* the smallest ring */

  return res;
}

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

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

  if (isEmptyList (l2))
    return l1;

  {
    List tmp = l1->next;
    l1->next = l2->next;
    l2->next = tmp;
    return l2;
  }
}

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

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

unsigned int
length (List l)
{
  if (isEmptyList (l))
    return 0;

  {
    unsigned int res = 1;
    List l1 = l->next;

    while (l1 != l)
      {
	l1 = l1->next;
	++res;
      }

    return res;
  }
}


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

Element
at (List l, unsigned int i)
{
  List l1;

  assert (!isEmptyList (l));

  l1 = l->next;

  while (i != 0)
    {
      assert (l1 != l);
      l1 = l1->next;
      --i;
    }

  return l1->info;
}

List
splitAt (List l, unsigned int i, List * rest)
{
  List l1;

  if (i == 0)
    {
      *rest = l;
      return mkEmptyList ();
    }

  l1 = l->next;
  while (i != 1)
    {
      assert (l1 != l);
      l1 = l1->next;
      --i;
    }

  if (l1 == l)
    {
      *rest = mkEmptyList ();
      return l;
    }
  else
    {
      List tmp = l1->next;
      l1->next = l->next;
      l->next = tmp;

      *rest = l;
      return l1;
    }
}

List
insertAt (List l, unsigned int i, Element e)
{
  List l1, l2;
  l1 = splitAt (l, i, &l2);

  return concat (concat (l1, mkOne (e)), l2);
}

List
removeAt (List l, unsigned int i)
{
  List l1, l2;
  l1 = splitAt (l, i, &l2);

  return concat (l1, tail (l2));
}

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