/* -*- c++ -*- */
 
#ifndef _LLIST_R_H_
#define _LLIST_R_H_

#include "llist.h"
#include <cassert>

#define generic template <class T>

/* Forward decls for functions that are most commonly used. */
generic bool can_move_to_front(T const &x, const llist<T>* l,
			       bool equal(T const & x, T const & y),
			       bool canSwap(T const & x, T const & y));
generic bool can_reorder(const llist<T>* l1, const llist<T>* l2,
			 bool equal(T const & x, T const & y),
			 bool canSwap(T const & x, T const & y));



/* Destructive delete on the first matching element found. Returns -1 
   if the element was not found. */
generic llist<T>* remove(T const & x, llist<T>* l,
			 bool equal(T const & x, T const & y)) 
{
  llist<T> *orig_l = l;
  if (equal(l->front(), x))
    return l->free();

  while (l->tail()) {
    if (equal(l->tail()->front(), x)) {
      l->tail() = l->tail()->free();
      return orig_l;
    }
    l = l->tail();
  }
  return (llist<T>*)-1;
}

/* The list l must contain x.  Return true iff it is possible to move
   x to the front of l by swapping adjacent list elements.  For a swap
   of list elements y and x to be considered, can_swap(y, x) must be
   true.  The list and its contents are not modified. */
generic bool can_move_to_front(T const &x, const llist<T> *l,
			       bool equal(T const & x, T const & y),
			       bool can_swap(T const & x, T const & y))
{
  int i = 0;
  if (l == NULL)
    return false;
  for (const llist<T> *k = l; !equal(k->front(), x); i++)
    if ((k = k->tail()) == NULL)
      return false;
  while (i > 0)
    if (!can_swap((*l)[--i], x))
      return false;
  return true;
}

/* Same as can_reorder(), below, except that lists l1 and l2 are freed
   before returning. */
generic bool can_reorder_c(llist<T> *l1, llist<T> *l2,
			   bool equal(T const & x, T const & y),
			   bool can_swap(T const & x, T const & y))
{
  if (l1 == NULL) {
    assert(l2 == NULL);
    return true;
  }
  T const &l1f = l1->front();
  T const &l2f = l2->front();
  if (equal(l1f, l2f))
    return can_reorder_c(l1->free(), l2->free(), equal, can_swap);
  else if (can_move_to_front(l1f, l2, equal, can_swap)) {
    l2 = remove(l1f, l2, equal);
    return can_reorder_c(l1->free(), l2, equal, can_swap);
  }
  else {
    free_all(l1);
    free_all(l2);
    return false;
  }
}

/* The list l1 should be a permutation of the list l2.  Return true
   iff it is possible to transform l1 into l2 by swapping adjacent
   pairs of elements.  For a swap of list elements x and y to be
   considered, can_swap(x, y) must be true.  The lists and their
   contents are not modified. */
generic bool can_reorder(const llist<T> *l1, const llist<T> *l2,
			 bool equal(T const & x, T const & y),
			 bool can_swap(T const & x, T const & y))
{
  if (l1 == NULL) {
    assert(l2 == NULL);
    return true;
  }
  return can_reorder_c(copylist(l1), copylist(l2), equal, can_swap);
}

#undef generic

#endif