/**************************************************************/
/* ********************************************************** */
/* *                                                        * */
/* *                     LISTS                              * */
/* *                                                        * */
/* *  $Module:   LIST                                       * */ 
/* *                                                        * */
/* *  Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001      * */
/* *  MPI fuer Informatik                                   * */
/* *                                                        * */
/* *  This program is free software; you can redistribute   * */
/* *  it and/or modify it under the terms of the GNU        * */
/* *  General Public License as published by the Free       * */
/* *  Software Foundation; either version 2 of the License, * */
/* *  or (at your option) any later version.                * */
/* *                                                        * */
/* *  This program is distributed in the hope that it will  * */
/* *  be useful, but WITHOUT ANY WARRANTY; without even     * */
/* *  the implied warranty of MERCHANTABILITY or FITNESS    * */
/* *  FOR A PARTICULAR PURPOSE.  See the GNU General Public * */
/* *  License for more details.                             * */
/* *                                                        * */
/* *  You should have received a copy of the GNU General    * */
/* *  Public License along with this program; if not, write * */
/* *  to the Free Software Foundation, Inc., 59 Temple      * */
/* *  Place, Suite 330, Boston, MA  02111-1307  USA         * */
/* *                                                        * */
/* *                                                        * */
/* $Revision$                                        * */
/* $State$                                            * */
/* $Date$                             * */
/* $Author$                                       * */
/* *                                                        * */
/* *             Contact:                                   * */
/* *             Christoph Weidenbach                       * */
/* *             MPI fuer Informatik                        * */
/* *             Stuhlsatzenhausweg 85                      * */
/* *             66123 Saarbruecken                         * */
/* *             Email: weidenb@mpi-sb.mpg.de               * */
/* *             Germany                                    * */
/* *                                                        * */
/* ********************************************************** */
/**************************************************************/


/* $RCSfile$ */

#include "list.h"

/**************************************************************/
/* ********************************************************** */
/* *                                                        * */
/* *  MEMORY MANAGEMENT                                     * */
/* *                                                        * */
/* ********************************************************** */
/**************************************************************/

LIST list_Copy(const LIST List)
/**************************************************************
  INPUT:   A List.
  RETURNS: The copy of the list.
  CAUTION: The entries of the list are NOT copied !
           the function needs time O(n), where <n> is the length
	   of the list.
***************************************************************/
{
  LIST Copy;
  LIST Scan1,Scan2;

 
  if (list_Empty(List))
    return list_Nil();

  Copy  = list_List(list_Car(List));
  Scan1 = Copy;
  Scan2 = list_Cdr(List);

  while (!list_Empty(Scan2)) {
    list_Rplacd(Scan1, list_List(list_Car(Scan2)));
    Scan1 = list_Cdr(Scan1);
    Scan2 = list_Cdr(Scan2);
  }
  return Copy;
}


LIST list_CopyWithElement(const LIST List, POINTER (*CopyElement)(POINTER))
/**************************************************************
  INPUT:   A List and a copy function for the elements.
  RETURNS: The copy of the list.
  CAUTION: The entries of the list are NOT copied !
           The function needs time O(n*c), where <n> is the length
	   of the list and <c> is the time for a call of the
	   element copy function.
***************************************************************/
{
  LIST Copy;
  LIST Scan1,Scan2;

  if (list_Empty(List))
    return list_Nil();

  Copy  = list_List(CopyElement(list_Car(List)));
  Scan1 = Copy;
  Scan2 = list_Cdr(List);

  while (!list_Empty(Scan2)) {
    list_Rplacd(Scan1, list_List(CopyElement(list_Car(Scan2))));
    Scan1 = list_Cdr(Scan1);
    Scan2 = list_Cdr(Scan2);
  }
  return Copy;
}


void list_InsertNext(LIST List, POINTER Pointer)
/**************************************************************
  INPUT:   A list and a pointer to anything.
  RETURNS: A list with Pointer being added at the position that
           follows List.
  SUMMARY: We enqueue the element at position list_Cdr(List);
           The function needs time O(1).
***************************************************************/
{
#ifdef CHECK
  if (Pointer == NULL) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In list_InsertNext: NULL Pointer. ");
    misc_FinishErrorReport();
  }
#endif

  list_Rplacd(List, list_Cons(Pointer, list_Cdr(List)));
}


void list_NMapCar(LIST List, POINTER (*ElementFunc)(POINTER))
/**************************************************************
  INPUT:   A List and a function for the elements.
  RETURNS: The List where all elements are replaced by the result of 
           the function calls of <ElementFunc> to the elements
  CAUTION: The List is not copied !
           The function needs time O(n*f), where <n> is the length
	   of the list and <f> is the time for a call of the
	   element function.
***************************************************************/
{
  LIST Scan;

  for (Scan = List; !list_Empty(Scan); Scan = list_Cdr(Scan))
    list_Rplaca(Scan, ElementFunc(list_Car(Scan)));
}


void list_Apply(void (*Function)(POINTER),  LIST List)
/**************************************************************
  INPUT:   A non-resulting function and a list.
  SUMMARY: Apply the function to all members of the list.
           The function needs time O(n*f), where <n> is the length
	   of the list and <f> is the time for a call of the
	   element function.
***************************************************************/
{
  while (!list_Empty(List)) {
    Function(list_Car(List));
    List = list_Cdr(List);
  }
}


LIST list_Reverse(const LIST List)
/**************************************************************
  INPUT:   A list.
  RETURNS: A new list where the order of the elements is reversed.
  EFFECT:  The function needs time O(n), where <n> is the length
           of the list.
***************************************************************/
{
  LIST ReverseList;
  LIST Scan;
  
  ReverseList = list_Nil();

  for (Scan=List;!list_Empty(Scan);Scan=list_Cdr(Scan)) 
    ReverseList = list_Cons(list_Car(Scan), ReverseList);

  return ReverseList;
}


LIST list_NReverse(LIST List)
/**************************************************************
  INPUT:   A list
  RETURNS: The same list with reversed order of items.
  CAUTION: Destructive.
           The function needs time O(n), where <n> is the length
           of the list.
***************************************************************/
{
  LIST ReverseList;
  LIST Scan1;
  LIST Scan2;
  
  ReverseList = list_Nil();

  for (Scan1=List; !list_Empty(Scan1); Scan1=list_Cdr(Scan1)) 
    ReverseList = list_Cons(list_Car(Scan1),ReverseList);

  for (Scan1=List, Scan2=ReverseList;
       !list_Empty(Scan1);
       Scan1=list_Cdr(Scan1), Scan2=list_Cdr(Scan2)) 
    list_Rplaca(Scan1, list_Car(Scan2));

  list_Delete(ReverseList);
  return List;
}


static __inline__ BOOL list_PointerLower (POINTER A, POINTER B)
{
  return (NAT) A < (NAT) B;
}

LIST list_PointerSort(LIST List)
/**************************************************************
  INPUT:   A list
  RETURNS: The same list where the elements are sorted as pointers.
  EFFECT:  The function needs time O(n log n), where <n> is the length
           of the list.
  CAUTION: Destructive.
***************************************************************/
{
  return list_Sort(List, list_PointerLower);
}


BOOL list_SortedInOrder(LIST L, BOOL (*Test)(POINTER, POINTER)) 
/**************************************************************
  INPUT:   A list, and an ordering function.
  RETURNS: TRUE, if the list is ordered with respect to the
           ordering function, FALSE otherwise.
  EFFECT:  The function needs time O(n), where <n> is the 
           length of the list.
***************************************************************/
{
  LIST Scan1, Scan2;

  if (!(list_Empty(L) || list_Empty(list_Cdr(L)))) {
    Scan1 = L;
    Scan2 = list_Cdr(Scan1);

    /* Scan the list. */
    do {
      /* If all elements are ordered, then every element  */
      /* is <= its successor with respect to the ordering */
      /* function.                                        */
      /* We might have a strictly ordering Test function, */
      /* which implements < instead of <=, so let's test  */
      /* for equality first. */
      if (!Test(list_Car(Scan1), list_Car(Scan2)) &&
	  Test(list_Car(Scan2), list_Car(Scan1)))
	/* It is really strictly greater, so return FALSE. */
	return FALSE;

      Scan1 = list_Cdr(Scan1);
      Scan2 = list_Cdr(Scan1);
    } while (!list_Empty(Scan2));
  }

  return TRUE;
}


LIST list_Merge(LIST List1, LIST List2, BOOL (*Test)(POINTER, POINTER)) 
/**************************************************************
  INPUT:   Two sorted lists List1 and List2, and an ordering function.
  RETURNS: The merged list ordered with respect to the ordering function.
  EFFECT:  The function needs time O(n), where <n> is the length of the list.
***************************************************************/
{

  LIST Scan1, Scan2, Result, ResultStart;

#ifdef CHECK
  if (!list_SortedInOrder(List1, Test)) {
    /* print an error message and exit */
    misc_StartErrorReport();
    misc_ErrorReport("\n In list_Merge: First argument is not sorted.");
    misc_FinishErrorReport();
  }
  else if (!list_SortedInOrder (List2, Test)) {
    /* print an error message and exit */
    misc_StartErrorReport();
    misc_ErrorReport("\n In list_Merge: Second argument is not sorted.");
    misc_FinishErrorReport();
  }
#endif

  if (list_Empty(List1))
    return List2;

  if (list_Empty(List2))
    return List1;

  /* This version is derived from list_NNumberMerge, but it doesn't need */
  /* to allocate and deallocate memory, so it should be more efficient.  */

  /* Use the list with the least element as result list. */
  if (Test(list_Car(List1), list_Car(List2))) {
    ResultStart = List1;
    Scan1       = list_Cdr(List1);
    Scan2       = List2;
  }
  else {
    ResultStart = List2;
    Scan1       = List1;
    Scan2       = list_Cdr(List2);
  }

  /* Result is the last element of the merged list. */

  Result = ResultStart;

  while (!list_Empty(Scan1) && !list_Empty(Scan2)) {
    /* This function doesn't implement stable merging. */
    /* Add another test if you need it.                */

    if (Test(list_Car(Scan1), list_Car(Scan2))) {
      list_Rplacd(Result,Scan1);
      Scan1  = list_Cdr(Scan1);
    }
    else {
      list_Rplacd(Result,Scan2);
      Scan2  = list_Cdr(Scan2);
    }
    Result = list_Cdr(Result);
  }

  if (list_Empty(Scan1))
    list_Rplacd(Result, Scan2);
  else
    list_Rplacd(Result, Scan1);

  return ResultStart;
}


void list_Split(LIST L, LIST *Half1, LIST *Half2) 
/**************************************************************
  INPUT:   A list, and two pointers to lists.
  RETURNS: Nothing.
  EFFECT:  The input list is split in two. <Half1> and 
           <Half2> point to the resulting halves.
	   The input list is destructively changed!
	   If the list length is odd, <Half2> is assigned the
	   bigger part. 
	   The function needs time O(n), where <n> is the 
           length of the input list.
***************************************************************/
{
  /* Adapted code from proofcheck ... MergeSort. */

  LIST SingleStep, DoubleStep, Prev;

  if (list_Empty(L) || list_Empty(list_Cdr(L))) {
    *Half1 = list_Nil();
    *Half2 = L;
  }
  else {
    /* divide list in two halves */
    Prev = L;
    SingleStep = list_Cdr(L);
    DoubleStep = list_Cdr(SingleStep);
    
    while (!list_Empty(DoubleStep) && !list_Empty(list_Cdr(DoubleStep))) {
      Prev       = SingleStep;
      SingleStep = list_Cdr(SingleStep);
      DoubleStep = list_Cdr(list_Cdr(DoubleStep));
    }
    
    *Half1 = L;
    *Half2 = SingleStep;
    list_Rplacd(Prev, list_Nil());
  }
}


LIST list_MergeSort (LIST L, BOOL (*Test) (POINTER, POINTER)) 
/**************************************************************
  INPUT:   A list, and an ordering function.
  RETURNS: The list sorted with respect to the ordering function.
  EFFECT:  The function needs time O((n log n) * t), where 
	   <n> is the length of the input list and <t> is the
	   execution time of the ordering function.
***************************************************************/
{
  LIST Result; 
#ifdef CHECK
  NAT  originallength;

  originallength = list_Length(L);
#endif

  /* Only sort if list has more than one element */
  if (!list_Empty(L) && !list_Empty(list_Cdr(L))) {
    LIST  lowerhalf;
    LIST  greaterhalf;

    LIST *lowerhalfptr;
    LIST *greaterhalfptr;

    lowerhalfptr = &lowerhalf;
    greaterhalfptr = &greaterhalf;

    list_Split(L, lowerhalfptr, greaterhalfptr);

#ifdef CHECK
    if((list_Length(lowerhalf) + list_Length(greaterhalf)) 
       != originallength) {
      /* output an error message and exit */
      misc_StartErrorReport();
      misc_ErrorReport("\n In list_MergeSort: Split lists' total sizes");
      misc_ErrorReport("\n don't match original list's size.");
      misc_FinishErrorReport();
    }
#endif

    lowerhalf   = list_MergeSort(lowerhalf, Test);

    greaterhalf = list_MergeSort(greaterhalf, Test);

#ifdef CHECK
    if((list_Length(lowerhalf) + list_Length(greaterhalf)) 
       != originallength) {
      /* output an error message and exit */
      misc_StartErrorReport();
      misc_ErrorReport("\n In list_MergeSort: Mergesorted lists' total sizes");
      misc_ErrorReport("\n don't match original list's size.");
      misc_FinishErrorReport();
    }
#endif

    Result = list_Merge(lowerhalf, greaterhalf, Test);
    
#ifdef CHECK
    if(list_Length(Result) != originallength) {
      /* output an error message and exit */
      misc_StartErrorReport();
      misc_ErrorReport("\n In list_MergeSort: Merged list's size doesn't match ");
      misc_ErrorReport("\n original list's size.");
      misc_FinishErrorReport();
    }
#endif

  }
  else {
    Result = L;
  }

  return Result;
}


LIST list_InsertionSort(LIST List, BOOL (*Test)(POINTER, POINTER))
/**************************************************************
  INPUT:   A list and a 'less' function on the elements.
  RETURNS: The same list where the elements are sorted with
           respect to Test.
  EFFECT:  The function needs time O(n^2*t), where <n> is the
           length of the list and <t> is the time for the test
	   function.
  CAUTION: Destructive.
***************************************************************/
{
  LIST Scan1,Scan2,Min;
  POINTER Exchange;

  for (Scan1=List; !list_Empty(Scan1); Scan1=list_Cdr(Scan1)) {
    Min = Scan1;
    for (Scan2 = list_Cdr(Scan1); !list_Empty(Scan2); Scan2 = list_Cdr(Scan2))
      if (Test(list_Car(Scan2), list_Car(Min))) {
	Exchange = list_Car(Min);
	list_Rplaca(Min, list_Car(Scan2));
	list_Rplaca(Scan2, Exchange);
      }
  }

  return List;
}


LIST list_Sort(LIST List, BOOL (*Test)(POINTER, POINTER))
/**************************************************************
  INPUT:   A list and a 'less' function on the elements.
  RETURNS: The same list where the elements are sorted with
           respect to Test.
  EFFECT:  The function needs time O((n log n) *t), where <n> 
           is the length of the list and <t> is the time for 
	   the test function.
  CAUTION: Destructive.
***************************************************************/
{
  LIST Result;

#ifdef CHECK
  NAT  originallength;

  originallength = list_Length(List);
#endif

  Result = list_MergeSort(List, Test);

#ifdef CHECK
  if (!list_SortedInOrder(Result, Test)) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In list_Sort: list_MergeSort did not sort properly.");
    misc_FinishErrorReport();
  }
  if (list_Length(Result) != originallength) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In list_Sort: list_MergeSort lost elements. ");
    misc_FinishErrorReport();
  }
#endif

  return Result;
}


/* Help Variable used to store a pointer to the numbering function to use
   in element comparisons.
*/
static NAT (*NumberFunction)(POINTER) = NULL;

static __inline__ BOOL list_PointerNumberedLower(POINTER A, POINTER B) 
{
  return (BOOL) (NumberFunction(A) < NumberFunction(B));
}

static __inline__ BOOL list_PointerNumberedLowerOrEqual(POINTER A, POINTER B) 
{
  return (BOOL) (NumberFunction(A) <= NumberFunction(B));
}

static __inline__ BOOL list_PointerNumberedGreater(POINTER A, POINTER B) 
{
  return (BOOL) (NumberFunction(A) > NumberFunction(B));
}

LIST list_NumberSort(LIST List, NAT (*Number)(POINTER))
/**************************************************************
  INPUT:   A list and function mapping elements to numbers.
  RETURNS: The same list where the elements are sorted with
           respect to < and the Number function.
  EFFECT:  The function needs time O((n log n) * f), where <n> 
           is the length of the list and <f> is the time for a 
	   call of the <Number> function.
  CAUTION: Destructive.
***************************************************************/
{
  /* Use number function as temporary variable. It is used as 
     an implicit parameter in list_PointerLower.
     We can't make it an explicit parameter, because of the
     prototype of list_Sort.
  */

  NumberFunction = Number;

  return list_Sort(List, list_PointerNumberedLower);

}


LIST list_GreaterNumberSort(LIST List, NAT (*Number)(POINTER))
/**************************************************************
  INPUT:   A list and function mapping elements to numbers.
  RETURNS: The same list where the elements are sorted with 
           respect to > and the Number function.
  EFFECT:  The function needs time O((n log n) * f), where <n> 
           is the length of the list and <f> is the time for a 
	   call of the <Number> function.
  CAUTION: Destructive.
***************************************************************/
{
  /* Use number function as temporary variable. It is used as 
     an implicit parameter in list_PointerLower.
     We can't make it an explicit parameter, because of the
     prototype of list_Sort.
  */

  NumberFunction = Number;

  return list_Sort(List, list_PointerNumberedGreater);
}


LIST list_NNumberMerge(LIST List1, LIST List2, NAT (*Number)(POINTER))
/**************************************************************
  INPUT:   Two sorted lists and function mapping elements to
           numbers.
  RETURNS: The merge of the lists where the elements are sorted
           with respect to < and the Number function.
  CAUTION: Destructive on both lists.
***************************************************************/
{
  NumberFunction = Number;

  return list_Merge(List1, List2, list_PointerNumberedLowerOrEqual);
}
      

POINTER list_DequeueNext(LIST List)
/**************************************************************
  INPUT:   A list
  RETURNS: A pointer to a dequeued element.
  SUMMARY: We dequeue the element pointed to by list_Cdr(List).
           The function needs time O(1).
***************************************************************/
{
  POINTER Pointer;
  LIST    Memo;

  if (list_Empty(List))
    return NULL;

  Memo = list_Cdr(List);
  if (list_Empty(Memo))
    return NULL;
      
  Pointer = list_Car(Memo);
  list_Rplacd(List, Memo->cdr);
  list_Free(Memo);
  return Pointer;
}


POINTER list_NthElement(LIST List, NAT Number)
/**************************************************************
  INPUT:   A List and a natural number.
  RETURNS: The <Number>th element of the list, NULL otherwise.
  EFFECT:  The function needs time O(Number).
***************************************************************/
{
  while (!list_Empty(List) && --Number > 0)
    List = list_Cdr(List);
  
  if (list_Empty(List))
    return NULL;
  else
    return list_Car(List);
}


void list_DeleteWithElement(LIST List, void (*ElementDelete)(POINTER))
/**************************************************************
  INPUT:   A list and a delete function for the elements.
  RETURNS: Nothing.
  EFFECT:  The list and all its elements are deleted.
           The function needs time O(n*d), where <n> is the length
	   of the list and <d> is the time for the delete function.
***************************************************************/
{
  LIST Scan;

  while (!list_Empty(List)) {
    Scan = list_Cdr(List);
    ElementDelete(list_Car(List));
    list_Free(List);
    List = Scan;
  }
}


NAT list_DeleteWithElementCount(LIST List, void (*ElementDelete)(POINTER))
/**************************************************************
  INPUT:   A List and a delete function for the elements.
  RETURNS: The number of deleted elements.
  EFFECT:  The List and all its elements are deleted.
           The function needs time O(n*d), where <n> is the length
	   of the list and <d> is the time for the delete function.
***************************************************************/
{
  int  Result;
  LIST Scan;

  Result = 0;

  while (!list_Empty(List)) {
    Scan = list_Cdr(List);
    ElementDelete(list_Car(List));
    list_Free(List);
    List = Scan;
    Result++;
  }

  return Result;
}


LIST list_DeleteElement(LIST List, POINTER Element, BOOL (*Test)(POINTER, POINTER))
/**************************************************************
  INPUT:   A list, an element pointer, an equality test for 
           elements
  RETURNS: The list where Element is deleted from List with 
           respect to Test.
  EFFECTS: If List contains Element with respect to EqualityTest,
           Element is deleted from List
  CAUTION: Destructive. Be careful, the first element of a
           list cannot be changed destructively by call by
	   reference.
***************************************************************/
{
  LIST   Scan1,Scan2;

  while (!list_Empty(List) && Test(Element, list_Car(List))) {
    Scan1 = list_Cdr(List);
    list_Free(List);
    List = Scan1;
  }

  if (list_Empty(List))
    return list_Nil();
  
  Scan2 = List;
  Scan1 = list_Cdr(List);

  while (!list_Empty(Scan1)) {
    if (Test(Element, list_Car(Scan1))) {
      list_Rplacd(Scan2, list_Cdr(Scan1));
      list_Free(Scan1);
      Scan1 = list_Cdr(Scan2);
    }
    else {
      Scan2 = Scan1;
      Scan1 = list_Cdr(Scan1);
    }
  }
  return List;
}


LIST list_DeleteElementIf(LIST List, BOOL (*Test)(POINTER))
/**************************************************************
  INPUT:   A list and a test for elements.
  RETURNS: The list where an element is deleted if <Test> on it
           succeeds.
  CAUTION: Destructive. Be careful, the first element of a list
           cannot be changed destructively by call by
	   reference.
***************************************************************/
{
  LIST   Scan1,Scan2;

  while (!list_Empty(List) && Test(list_Car(List))) {
    Scan1 = list_Cdr(List);
    list_Free(List);
    List = Scan1;
  }

  if (list_Empty(List)) 
    return list_Nil();
  
  Scan2 = List;
  Scan1 = list_Cdr(List);

  while (!list_Empty(Scan1)) {
    if (Test(list_Car(Scan1))) {
      list_Rplacd(Scan2, list_Cdr(Scan1));
      list_Free(Scan1);
      Scan1 = list_Cdr(Scan2);
    }
    else {
      Scan2 = Scan1;
      Scan1 = list_Cdr(Scan1);
    }
  }
  return List;
}


LIST list_DeleteElementIfFree(LIST List, BOOL (*Test)(POINTER),
			      void (*Delete)(POINTER))
/**************************************************************
  INPUT:   A list, a test for elements and a delete function
           for elements.
  RETURNS: The list where an element is deleted if <Test> on it
           succeeds.
           The element is deleted with <Delete>.
  CAUTION: Destructive. Be careful, the first element of a list
           cannot be changed destructively by call by reference.
***************************************************************/
{
  LIST   Scan1,Scan2;

  while (!list_Empty(List) && Test(list_Car(List))) {
    Scan1 = list_Cdr(List);
    Delete(list_Car(List));
    list_Free(List);
    List = Scan1;
  }

  if (list_Empty(List))
    return list_Nil();
  
  Scan2 = List;
  Scan1 = list_Cdr(List);

  while (!list_Empty(Scan1)) {
    if (Test(list_Car(Scan1))) {
      Delete(list_Car(Scan1));
      list_Rplacd(Scan2, list_Cdr(Scan1));
      list_Free(Scan1);
      Scan1 = list_Cdr(Scan2);
    }
    else {
      Scan2 = Scan1;
      Scan1 = list_Cdr(Scan1);
    }
  }
  return List;
}


LIST list_DeleteElementFree(LIST List, POINTER Element,
			    BOOL (*Test)(POINTER, POINTER),
			    void (*Free)(POINTER))
/**************************************************************
  INPUT:   A list, an element pointer, an equality test for
           elements and a free function for elements.
  RETURNS: The list where Element is deleted from List with
           respect to Test.
  EFFECTS: If the list contains <Element> with respect to  <Test>,
           <Element> is deleted from the list and freed.
  CAUTION: Destructive. Be careful, the first element of a list
           cannot be changed destructively by call by reference.
***************************************************************/
{
  LIST   Scan1,Scan2;

  while (!list_Empty(List) && Test(Element, list_Car(List))) {
    Scan1 = list_Cdr(List);
    Free(list_Car(List));
    list_Free(List);
    List = Scan1;
  }

  if (list_Empty(List))
    return list_Nil();
  
  Scan2 = List;
  Scan1 = list_Cdr(List);

  while (!list_Empty(Scan1)) {
    if (Test(Element, list_Car(Scan1))) {
      list_Rplacd(Scan2, list_Cdr(Scan1));
      Free(list_Car(Scan1));
      list_Free(Scan1);
      Scan1 = list_Cdr(Scan2);
    }
    else {
      Scan2 = Scan1;
      Scan1 = list_Cdr(Scan1);
    }
  }
  return List;
}


LIST list_DeleteOneElement(LIST List, POINTER Element, BOOL (*Test)(POINTER, POINTER))
/**************************************************************
  INPUT:   A list, an element pointer and an equality test for
           elements.
  RETURNS: The list where at most one element was deleted from
           <List> if the Test between <Element> and the element
	   succeeds.
  EFFECT:  The function needs time O(n*t) in the worst case, and
           time O(t) in the best case, where <n> is the length of
	   the list and t is the time for a call of the test function.
  CAUTION: Destructive. Be careful, the first element of a list
           cannot be changed destructively by call by
	   reference.
	   The memory of the deleted element is not freed.
***************************************************************/
{
  LIST scan1, scan2;

  if (list_Empty(List))
    return List;
  else {
    if (Test(Element, list_Car(List)))
      return list_Pop(List);
  }
  
  for (scan2 = List, scan1 = list_Cdr(List); !list_Empty(scan1);
       scan2 = scan1, scan1 = list_Cdr(scan1)) {
    if (Test(Element, list_Car(scan1))) {
      list_Rplacd(scan2, list_Cdr(scan1));
      list_Free(scan1);
      scan1 = list_Cdr(scan2);
      return List;
    }
  }
  return List;
}


LIST list_PointerDeleteElement(LIST List, POINTER Element)
/**************************************************************
  INPUT:   A list and an element pointer
  RETURNS: The list where Element is deleted from List with respect to
           pointer equality.
  EFFECTS: If <List> contains <Element> with respect to pointer equality,
           <Element> is deleted from <List>.
	   This function needs time O(n), where <n> is the length of the list.
  CAUTION: Destructive. Be careful, the first element of a list cannot
           be changed destructively by call by reference.
***************************************************************/
{
  LIST   Scan1,Scan2;

  while (!list_Empty(List) && Element == list_Car(List)) {
    Scan1 = list_Cdr(List);
    list_Free(List);
    List = Scan1;
  }

  if (list_Empty(List))
    return list_Nil();
  
  Scan2 = List;
  Scan1 = list_Cdr(List);

  while (!list_Empty(Scan1)) {
    if (Element == list_Car(Scan1)) {
      list_Rplacd(Scan2, list_Cdr(Scan1));
      list_Free(Scan1);
      Scan1 = list_Cdr(Scan2);
    }
    else {
      Scan2 = Scan1;
      Scan1 = list_Cdr(Scan1);
    }
  }
  return List;
}

LIST list_PointerDeleteElementFree(LIST List, POINTER Element,
				   void (*Free)(POINTER))
/**************************************************************
  INPUT:   A list, an element pointer and a free function for
           elements.
  RETURNS: The list where Element is deleted from List with
           respect to pointer equality and freed.
  EFFECTS: If List contains Element with respect to pointer
           equality, Element is deleted from List
  CAUTION: Destructive. Be careful, the first element of a list
           cannot be changed destructively by call by 
	   reference.
***************************************************************/
{
  LIST   Scan1,Scan2;
  
  while (!list_Empty(List) && Element == list_Car(List)) {
    Scan1 = list_Cdr(List);
    Free(list_Car(List));
    list_Free(List);
    List = Scan1;
  }

  if (list_Empty(List))
    return list_Nil();
  
  Scan2 = List;
  Scan1 = list_Cdr(List);

  while (!list_Empty(Scan1)) {
    if (Element == list_Car(Scan1)) {
      list_Rplacd(Scan2, list_Cdr(Scan1));
      Free(list_Car(Scan1));
      list_Free(Scan1);
      Scan1 = list_Cdr(Scan2);
    }
    else {
      Scan2 = Scan1;
      Scan1 = list_Cdr(Scan1);
    }
  }
  return List;
}
 

LIST list_PointerDeleteOneElement(LIST List, POINTER Element)
/**************************************************************
  INPUT:   A list and an element pointer.
  RETURNS: The list where one occurrence of Element is deleted from List 
           with respect to pointer equality.
  EFFECTS: If List contains Element with respect to pointer equality,
           Element is deleted from List.
  CAUTION: Destructive. Be careful, the first element of a list cannot
           be changed destructively by call by reference.
***************************************************************/
{
  LIST   Scan1,Scan2;

  if (list_Empty(List))
    return List;
  else {
    if (Element == list_Car(List))
      return list_Pop(List);
  }
  
  Scan2 = List;
  Scan1 = list_Cdr(List);

  while (!list_Empty(Scan1)) {
    if (Element == list_Car(Scan1)) {
      list_Rplacd(Scan2, list_Cdr(Scan1));
      list_Free(Scan1);
      Scan1 = list_Cdr(Scan2);
      return List;
    }
    else {
      Scan2 = Scan1;
      Scan1 = list_Cdr(Scan1);
    }
  }
  return List;     
}


BOOL list_DeleteFromList(LIST* List, POINTER Element)
/**************************************************************
  INPUT:   A list and an element pointer
  RETURNS: TRUE, if Element was deleted; FALSE, otherwise.
  EFFECTS: If List contains Element with respect to pointer equality,
           all occurrences of Element are deleted from List.
  CAUTION: Destructive. Be careful, the first element of a list cannot
           be changed destructively by call by reference.
***************************************************************/
{
  BOOL Found;
  LIST Scan1;

  Found = FALSE;

  while (list_Exist(*List) && Element == list_Car(*List)) {
    Scan1 = list_Cdr(*List);
    list_Free(*List);
    *List = Scan1;
    Found = TRUE;
  }

  if (list_Exist(*List)) {
    LIST Scan2;

    Scan2 = *List;
    Scan1 = list_Cdr(*List);

    while (list_Exist(Scan1)) {
      if (Element == list_Car(Scan1)) {
	list_Rplacd(Scan2, list_Cdr(Scan1));
	list_Free(Scan1);
	Scan1 = list_Cdr(Scan2);
	Found = TRUE;
      } else {
	Scan2 = Scan1;
	Scan1 = list_Cdr(Scan1);
      }
    }
  }

  return Found;
}


BOOL list_DeleteOneFromList(LIST* List, POINTER Element)
/**************************************************************
  INPUT:   A list and an element pointer
  RETURNS: TRUE, if <Element> was deleted; FALSE, otherwise.
  EFFECTS: If <List> contains <Element> with respect to pointer equality,
           the first occurrence of <Element> is deleted from <List>.
  CAUTION: Destructive.
***************************************************************/
{
  if (list_Exist(*List)) {
    LIST Scan1;

    /* special treatment for the first element */
    if (Element == list_Car(*List)) {
      Scan1 = list_Cdr(*List);
      list_Free(*List);
      *List = Scan1;
      return TRUE;
    } else {
      LIST Scan2;

      for (Scan2 = *List, Scan1 = list_Cdr(*List); list_Exist(Scan1); ) {
	if (Element == list_Car(Scan1)) {
	  list_Rplacd(Scan2, list_Cdr(Scan1));
	  list_Free(Scan1);
	  Scan1 = list_Cdr(Scan2);
	  return TRUE;
	} else {
	  Scan2 = Scan1;
	  Scan1 = list_Cdr(Scan1);
	}
      }
    }
  }
  return FALSE;
}


BOOL list_IsSetOfPointers(LIST L)
/**************************************************************
  INPUT:   A list.
  RETURNS: TRUE, if <L> is a set of pointers (without duplicates),
           FALSE, otherwise.
  EFFECT:  The function needs n(n-1)/2 comparisons in the worst case,
           where n is the length of the list. So its time complexity
	   is O(n^2).
***************************************************************/
{
  for ( ; !list_Empty(L); L = list_Cdr(L)) {
    if (list_PointerMember(list_Cdr(L), list_Car(L)))
      return FALSE;
  }
  return TRUE;
}


LIST list_DeleteDuplicates(LIST List, BOOL (*Test)(POINTER, POINTER))
/**************************************************************
  INPUT:   A list, an equality test for elements
  RETURNS: The list where multiple occurrences are deleted.
  CAUTION: Destructive.
***************************************************************/
{
  LIST Scan;
  
  Scan = List;

  while (!list_Empty(Scan)) {
    list_Rplacd(Scan,
		list_DeleteElement(list_Cdr(Scan), list_Car(Scan), Test));
    Scan = list_Cdr(Scan);
  }
  return List;
}


LIST list_DeleteDuplicatesFree(LIST List, BOOL (*Test)(POINTER, POINTER), 
			       void (*Free)(POINTER))
/**************************************************************
  INPUT:   A list, an equality test for elements, and a free
           function for elements.
  RETURNS: The list where multiple occurrences are deleted.
  CAUTION: Destructive and frees all duplicates.
***************************************************************/
{
  LIST Scan;
  
  Scan = List;

  while (!list_Empty(Scan)) {
    list_Rplacd(Scan, list_DeleteElementFree(list_Cdr(Scan), list_Car(Scan), Test, Free));
    Scan = list_Cdr(Scan);
  }
  return List;
}


LIST list_PointerDeleteDuplicates(LIST List)
/**************************************************************
  INPUT:   A list
  RETURNS: The list where multiple occurrences are deleted.
  CAUTION: Destructive.
  EFFECT:  The function needs 
***************************************************************/
{
  LIST Scan;
  
  Scan = List;

  while (!list_Empty(Scan)) {
    list_Rplacd(Scan, list_PointerDeleteElement(list_Cdr(Scan),
						list_Car(Scan)));
    Scan = list_Cdr(Scan);
  }
  return List;
}


LIST list_NPointerUnion(LIST List1, LIST List2)
/**************************************************************
  INPUT:   Two lists.
  RETURNS: Regarding both lists as sets, the union of the sets.
  CAUTION: Destructive.
***************************************************************/
{
  return list_PointerDeleteDuplicates(list_Nconc(List1,List2));
}


LIST list_NUnion(LIST List1, LIST List2, BOOL (*Test)(POINTER, POINTER))
/**************************************************************
  INPUT:   Two lists and an equality test for the elements.
  RETURNS: Regarding both lists as sets, the union of the sets.
  CAUTION: Destructive.
***************************************************************/
{
  return list_DeleteDuplicates(list_Nconc(List1,List2), Test);
}


LIST list_NListTimes(LIST List1, LIST List2)
/**************************************************************
  INPUT:   Two lists of lists.
  RETURNS: The list of combinations of element lists.
  CAUTION: Destroys List1 and List2.
***************************************************************/
{
  LIST Result, Scan1, Scan2;

  Result = list_Nil();

  if (!list_Empty(List2)) {
    for (Scan1=List1; !list_Empty(Scan1); Scan1=list_Cdr(Scan1))
      for (Scan2=List2; !list_Empty(Scan2); Scan2=list_Cdr(Scan2))
	Result = list_Cons(list_Append(((LIST)list_Car(Scan1)),
				       list_Copy((LIST)list_Car(Scan2))),
			   Result);
  }
  list_DeleteWithElement(List1, (void (*)(POINTER))list_Delete);
  list_DeleteWithElement(List2, (void (*)(POINTER))list_Delete);

  return Result;
}


LIST list_NIntersect(LIST List1, LIST List2, BOOL (*Test)(POINTER, POINTER))
/**************************************************************
  INPUT:   Two lists and an equality test for the elements.
  RETURNS: Regarding both lists as sets, the intersection of the sets.
  CAUTION: Destructive on List1
***************************************************************/
{
  LIST Scan1, Scan2;
  
  while (!list_Empty(List1) && !list_Member(List2, list_Car(List1), Test)) {
    Scan1 = list_Cdr(List1);
    list_Free(List1);
    List1 = Scan1;
  }

  if (list_Empty(List1))
    return List1;

  Scan1 = List1;
  Scan2 = list_Cdr(List1);

  while (!list_Empty(Scan2)) {
    if (list_Member(List2, list_Car(Scan2), Test)) {
      Scan2 = list_Cdr(Scan2);
      Scan1 = list_Cdr(Scan1);
    }
    else {
      list_Rplacd(Scan1, list_Cdr(Scan2));
      list_Free(Scan2);
      Scan2 = list_Cdr(Scan1);
    }
  }
  return List1;
}


LIST list_NPointerIntersect(LIST List1, LIST List2)
/**************************************************************
  INPUT:   Two lists.
  RETURNS: Regarding both lists as sets, the intersection of the sets.
  CAUTION: Destructive on List1
***************************************************************/
{
  LIST Scan1, Scan2;
  
  while (!list_Empty(List1) && !list_PointerMember(List2, list_Car(List1))) {
    Scan1 = list_Cdr(List1);
    list_Free(List1);
    List1 = Scan1;
  }

  if (list_Empty(List1))
    return List1;

  Scan1 = List1;
  Scan2 = list_Cdr(List1);

  while (!list_Empty(Scan2)) {
    if (list_PointerMember(List2, list_Car(Scan2))) {
      Scan2 = list_Cdr(Scan2);
      Scan1 = list_Cdr(Scan1);
    }
    else {
      list_Rplacd(Scan1, list_Cdr(Scan2));
      list_Free(Scan2);
      Scan2 = list_Cdr(Scan1);
    }
  }
  return List1;
}


void list_NInsert(LIST List1, LIST List2)
/**************************************************************
  INPUT:   Two lists where <List1> must not be empty.
  EFFECT:  <List2> is destructively concatenated after
           the first element of <List1>.
  RETURNS: void.
  CAUTION: Destructive on List1 and List2.
***************************************************************/
{
  LIST Help;

#ifdef CHECK
  if (list_Empty(List1)) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In list_NInsert: Empty list argument.");
    misc_FinishErrorReport();
  }
#endif

  Help = list_Cdr(List1);
  list_Rplacd(List1,List2);
  List2 = List1;

  while (!list_Empty(list_Cdr(List2)))
    List2 = list_Cdr(List2);

  list_Rplacd(List2,Help);
}

      
BOOL list_HasIntersection(LIST List1, LIST List2)
/**************************************************************
  INPUT:   Two lists .
  RETURNS: TRUE iff List1 and List2 have a common element.
  EFFECT:  The function needs time O(n*m), where n and m are the
           lengths of the lists.
***************************************************************/
{ 
  LIST Scan;

  if (!list_Empty(List2)) {
    for (Scan=List1; !list_Empty(Scan); Scan=list_Cdr(Scan))
      if (list_PointerMember(List2, list_Car(Scan)))
	return TRUE;
  }
  return FALSE;
}


LIST list_NPointerDifference(LIST List1, LIST List2)
/**************************************************************
  INPUT:   Two lists.
  RETURNS: The list List1-List2.
  CAUTION: Destructive on List1.
***************************************************************/
{ 
  LIST Scan;

  if (!list_Empty(List1)) {
    for (Scan=List2; !list_Empty(Scan); Scan=list_Cdr(Scan))
      List1 = list_PointerDeleteElement(List1, list_Car(Scan));
  }
  return List1;
}


LIST list_NDifference(LIST List1, LIST List2, BOOL (*Test)(POINTER, POINTER))
/**************************************************************
  INPUT:   Two lists and an equality test for elements.
  RETURNS: The list List1-List2 wrt. <Test>.
  CAUTION: Destructive on List1.
***************************************************************/
{ 
  LIST Scan;
  
  if (!list_Empty(List1)) {
    for (Scan=List2; !list_Empty(Scan); Scan=list_Cdr(Scan))
      List1 = list_DeleteElement(List1, list_Car(Scan), Test);
  }
  return List1;
}


LIST list_NMultisetDifference(LIST List1, LIST List2, BOOL (*Test)(POINTER, POINTER))
/**************************************************************
  INPUT:   Two lists representing multisets and an equality
           test for elements.
  RETURNS: The multiset difference List1-List2 wrt. <Test>.
  CAUTION: Destructive on List1. The memory of deleted
           elements is not freed.
***************************************************************/
{
  LIST scan;
  /* Delete equal arguments */
  if (!list_Empty(List1)) {
    for (scan = List2; !list_Empty(scan); scan = list_Cdr(scan))
      /* Delete at most one element from List1 equal to */
      /* the actual element of List2. */
      List1 = list_DeleteOneElement(List1, list_Car(scan), Test);
  }
  return List1;
}

    
BOOL list_PointerReplaceMember(LIST List, POINTER Old, POINTER New)
/**************************************************************
  INPUT:   A list, a pointer to an old element, a pointer to a new element
  RETURNS: TRUE iff <Old> was replaced.
  EFFECT:  The first occurrence of <Old> in the list is replaced by <New>.
***************************************************************/
{
  while (!list_Empty(List)) {
    if (Old == list_Car(List)) {
      list_Rplaca(List, New);
      return TRUE;
    }
    List = list_Cdr(List);
  }
  return FALSE;
}   

  
void list_DeleteAssocListWithValues(LIST List, void (*ValueDelete)(POINTER))
/**************************************************************
  INPUT:   An association list and a delete function for the values.
  RETURNS: void.
  EFFECT:  The assoc list and its values are deleted.
***************************************************************/
{
  LIST Scan;

  for (Scan=List;!list_Empty(Scan);Scan = list_Cdr(Scan)) {
    ValueDelete(list_PairSecond(list_Car(Scan)));
    list_PairFree(list_Car(Scan));
  }

  list_Delete(List);
}


POINTER list_AssocListValue(LIST List, POINTER Key)
/**************************************************************
  INPUT:   An association list and a key.
  RETURNS: The value for <key> in the list. If <key> is not
           contained, NULL.
***************************************************************/
{
  LIST Scan;

  for (Scan=List;!list_Empty(Scan);Scan = list_Cdr(Scan))
    if (Key == list_PairFirst(list_Car(Scan)))
      return list_PairSecond(list_Car(Scan));

  return NULL;
}


LIST list_AssocListPair(LIST List, POINTER Key)
/**************************************************************
  INPUT:   An association list and a key.
  RETURNS: The  (<key>.<value) in the list. If <key> is not
           contained, the NULL pair.
***************************************************************/
{
  LIST Scan;

  for (Scan=List;!list_Empty(Scan);Scan = list_Cdr(Scan))
    if (Key == list_PairFirst(list_Car(Scan)))
      return list_Car(Scan);

  return list_PairNull();
}


LIST list_MultisetDistribution(LIST Multiset) 
/**************************************************************
  INPUT:   A list representing a multiset.
  RETURNS: The associative list of pairs (<element>.<occurrences>) 
           representing the distribution of elements in the list.
	   If the input multiset is empty, the NULL pair.
***************************************************************/
{
  LIST Distribution;
  LIST Scan;

  Distribution = list_PairNull();

  for (Scan = Multiset; !list_Empty(Scan); Scan = list_Cdr(Scan)) {
    LIST    Count;
    POINTER Element;
    int     Occurences;

    Element = list_Car(Scan);
    Count   = list_AssocListPair(Distribution, Element);

    if (Count != list_PairNull()) {
      Occurences = (int) list_PairSecond(Count);
      list_PairRplacSecond(Count, (POINTER) (Occurences + 1));
    }
    else {
      Distribution = list_AssocCons(Distribution, Element, (POINTER) 1);
    }
  }

  return Distribution;
}


int list_CompareElementDistribution(LIST LeftPair, LIST RightPair) 
/**************************************************************
  INPUT:   Two lists, representing single element frequency 
           counts.
  RETURNS: 1 if left > right, -1 if left < right, 0 otherwise.
  EFFECT:  Compares two element frequencies.
***************************************************************/
{
  if ((int) list_PairSecond(LeftPair) < (int) list_PairSecond(RightPair)) {
    return -1;
  }
  else if ((int) list_PairSecond(LeftPair) > (int) list_PairSecond(RightPair)) {
    return 1;
  }

  return 0;
}


BOOL list_CompareElementDistributionLEQ(LIST LeftPair, LIST RightPair) {
/**************************************************************
  INPUT:   Two lists, representing single element frequency 
           counts.
  RETURNS: TRUE if left <= right, FALSE otherwise.
  EFFECT:  Compares two element frequencies.
***************************************************************/
  return (list_CompareElementDistribution(LeftPair, RightPair) <= 0);
}


static int list_CompareDistributions(LIST Left, LIST Right) 
/**************************************************************
  INPUT:   Two lists, representing element distributions.
  RETURNS: 1 if left > right, -1 if left < right, 0 otherwise.
  EFFECT:  Compares the two distributions by comparing the 
           element frequencies from left to right.
  CAUTION: Expects the distributions to be sorted.
***************************************************************/
{
  LIST scan, scan2;
  int result;

  result = 0;

  scan  = Left;
  scan2 = Right;

  /* Compare distributions. */

  while ( !(list_Empty(scan) || list_Empty(scan2))) {
    result = list_CompareElementDistribution(list_Car(scan), list_Car(scan2));
    if (result != 0) {
      break;
    }
    
    scan  = list_Cdr(scan);
    scan2 = list_Cdr(scan2);
  }

  /* If the result is 0, and a distribution still
     has elements left, it is declared to be greater.
  */
  if (result == 0) {
    if (list_Empty(scan) && !list_Empty(scan2))
      result = -1;
    else if (!list_Empty(scan) && list_Empty(scan2))
      result = 1;
  }

  return result;
}


int list_CompareMultisetsByElementDistribution(LIST Left, LIST Right) 
/**************************************************************
  INPUT:   Two lists, representing multisets.
  RETURNS: 1 if left > right, -1 if left < right, 0 otherwise.
  EFFECT:  Compares two multisets by counting their element 
           frequencies, sorting them, and comparing the 
	   resulting multisets over natural numbers.
***************************************************************/
{
  LIST lmsd, rmsd; /* multiset distributions. */
  int result;

  /* Convert multiset of elements into a
     multiset of pairs (element, occurrences).
  */

  lmsd = list_MultisetDistribution(Left);
  rmsd = list_MultisetDistribution(Right);

  /* Sort multiset distributions in order 
     to make them comparable. 
   */

  lmsd = list_Sort(lmsd, (BOOL (*) (POINTER, POINTER)) list_CompareElementDistributionLEQ);
  rmsd = list_Sort(rmsd, (BOOL (*) (POINTER, POINTER)) list_CompareElementDistributionLEQ);

  result = list_CompareDistributions(lmsd, rmsd);

  list_DeleteDistribution(lmsd);
  list_DeleteDistribution(rmsd);

  return result;
}


NAT list_Length(LIST List)
/**************************************************************
  INPUT:   A List.
  RETURNS: The number of elements..
  EFFECT:  The function needs time O(n), where <n> is the length
           of the list.
***************************************************************/
{
  NAT Result;

  Result = 0;

  while (!list_Empty(List)) {
    Result++;
    List = list_Cdr(List);
  }

  return Result;
}


NAT list_Bytes(LIST List)
/**************************************************************
  INPUT:   A List.
  RETURNS: The number of Bytes occupied by the list structure of <List>
  EFFECT:  the function needs time O(n), where <n> is the length
           of the list.
***************************************************************/
{
  return (list_Length(List)*sizeof(LIST_NODE));
}