/* Linked list type */

/* User should #define:
   T
   list
   cons
   head
   tail
   length
   freecell
   set_head
   set_tail
   dreverse
   dreverse_and_extend
*/

typedef struct list {
  T head;
  struct list *tail;
} list;

TI_INLINE(cons) list *cons(T head, list *tail) {
  list *result = ALLOC(list, 1);
  result->head = head;
  result->tail = tail;
  return result;
}

TI_INLINE(head) T head(list *l) { return l->head; }
TI_INLINE(tail) list *tail(list *l) { return l->tail; }

TI_INLINE(freecell) list *freecell(list *l)
{ list *r = l->tail; FREE(l); return r; }

TI_INLINE(set_head) void set_head(list *l, T h)
{ l->head = h; }
TI_INLINE(set_tail) void set_tail(list *l, list *t)
{ l->tail = t; }
  
TI_INLINE(length) int length(list *l)
{
  int i = 0;
  while (l != NULL) {
    i++;
    l = l->tail;
  }
  return i;
}

/* Destructively reverse l and destructively append p to the result. */
TI_INLINE(dreverse_and_extend) list *dreverse_and_extend(list *l, list *p)
{
  if (l == NULL)
    return p;
  while (l->tail != NULL) {
    list *next = l->tail;
    l->tail = p;
    p = l;
    l = next;
  }
  l->tail = p;
  return l;
}

TI_INLINE(dreverse) list *dreverse(list *l)
{
  return dreverse_and_extend(l, NULL);
}