/**************************************************************/
/* ********************************************************** */
/* *                                                        * */
/* *                     LISTS                              * */
/* *                                                        * */
/* *  $Module:   LIST                                       * */ 
/* *                                                        * */
/* *  Copyright (C) 1996, 1997, 1998, 1999, 2000            * */
/* *  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$ */

#ifndef _LIST_
#define _LIST_

/**************************************************************/
/* Includes                                                   */
/**************************************************************/

#include "memory.h"
#include "misc.h"

/**************************************************************/
/* Structures                                                 */
/**************************************************************/

typedef struct LIST_HELP {
  struct LIST_HELP *cdr;
  POINTER           car;
} LIST_NODE;

typedef LIST_NODE *LIST;

/**************************************************************/
/* Macros                                                     */
/**************************************************************/

static __inline__ void list_Free(LIST L)
{
  memory_Free(L, sizeof(LIST_NODE));
}

static __inline__ LIST list_Nil(void)
{
  return NULL;
}

static __inline__ BOOL list_Empty(LIST L)
{
  return L == NULL;
}

static __inline__ BOOL list_Exist(LIST L)
{
  return L != NULL;
}

static __inline__ POINTER list_Car(LIST L)
{
  return L->car;
}

static __inline__ POINTER list_NCar(LIST *L)
{
  POINTER Result;
  LIST    Help;

  Result = (*L)->car;
  Help   = (*L)->cdr;
  list_Free(*L);
  *L     = Help;
  return Result;
}

static __inline__ LIST list_Cdr(LIST L)
{
  return L->cdr;
}

static __inline__ POINTER list_First(LIST L)
{
  return list_Car(L);
}

static __inline__ POINTER list_Second(LIST L)
{
  return list_Car(list_Cdr(L));
}

static __inline__ POINTER list_Third(LIST L)
{
  return list_Car(list_Cdr(list_Cdr(L)));
}

static __inline__ POINTER list_Fourth(LIST L) 
{
  return(list_Third(list_Cdr(L)));
}

static __inline__ POINTER list_Fifth(LIST L) 
{
  return(list_Fourth(list_Cdr(L)));
}

static __inline__ void list_Rplacd(LIST L1, LIST L2)
{
  L1->cdr = L2;
}

static __inline__ void list_Rplaca(LIST L, POINTER P)
{
  L->car = P;
}

static __inline__ void list_RplacSecond(LIST L, POINTER P)
{
  list_Rplaca(list_Cdr(L), P);
}


/**************************************************************/
/* Functions                                                  */
/**************************************************************/

LIST    list_Copy(const LIST);
LIST    list_CopyWithElement(const LIST, POINTER (*)(POINTER));
void    list_InsertNext(LIST, POINTER);

void    list_NMapCar(LIST, POINTER (*)(POINTER));
void    list_Apply(void (*)(POINTER), LIST);

LIST    list_Reverse(const LIST);
LIST    list_NReverse(LIST);

void    list_Split(LIST, LIST *, LIST *); 
LIST    list_PointerSort(LIST);
LIST    list_Merge(LIST, LIST, BOOL (*)(POINTER, POINTER));
LIST    list_MergeSort(LIST, BOOL (*)(POINTER, POINTER));
LIST    list_InsertionSort(LIST, BOOL (*)(POINTER, POINTER));
LIST    list_Sort(LIST, BOOL (*)(POINTER, POINTER));
BOOL    list_SortedInOrder(LIST, BOOL (*)(POINTER, POINTER));
LIST    list_NumberSort(LIST , NAT (*)(POINTER));
LIST    list_GreaterNumberSort(LIST , NAT (*)(POINTER));
LIST    list_NNumberMerge(LIST , LIST, NAT (*)(POINTER));

POINTER list_DequeueNext(LIST);
POINTER list_NthElement(LIST, NAT);
void    list_DeleteWithElement(LIST, void (*)(POINTER));
NAT     list_DeleteWithElementCount(LIST, void (*)(POINTER));
LIST    list_DeleteElement(LIST, POINTER, BOOL (*)(POINTER, POINTER));
LIST    list_DeleteElementIf(LIST, BOOL (*)(POINTER));
LIST    list_DeleteElementIfFree(LIST, BOOL (*)(POINTER), void (*)(POINTER));
LIST    list_DeleteElementFree(LIST, POINTER, BOOL (*)(POINTER, POINTER), void (*)(POINTER));
LIST    list_DeleteOneElement(LIST, POINTER, BOOL (*)(POINTER, POINTER));
LIST    list_PointerDeleteElement(LIST, POINTER);
LIST    list_PointerDeleteElementFree(LIST, POINTER, void (*)(POINTER));
LIST    list_PointerDeleteOneElement(LIST, POINTER);
BOOL    list_DeleteFromList(LIST*, POINTER);
BOOL    list_DeleteOneFromList(LIST*, POINTER);
LIST    list_DeleteDuplicates(LIST, BOOL (*)(POINTER, POINTER));
LIST    list_DeleteDuplicatesFree(LIST, BOOL (*)(POINTER, POINTER), void (*)(POINTER));
LIST    list_PointerDeleteDuplicates(LIST);

BOOL    list_IsSetOfPointers(LIST);
LIST    list_NPointerUnion(LIST, LIST);
LIST    list_NUnion(LIST, LIST, BOOL (*)(POINTER, POINTER));
LIST    list_NListTimes(LIST, LIST);
LIST    list_NIntersect(LIST, LIST, BOOL (*)(POINTER, POINTER));
void    list_NInsert(LIST, LIST);
LIST    list_NPointerIntersect(LIST, LIST);
BOOL    list_HasIntersection(LIST, LIST);
LIST    list_NPointerDifference(LIST, LIST);
LIST    list_NDifference(LIST, LIST, BOOL (*)(POINTER, POINTER));
LIST    list_NMultisetDifference(LIST, LIST, BOOL (*)(POINTER, POINTER));
BOOL    list_PointerReplaceMember(LIST, POINTER, POINTER);

void    list_DeleteAssocListWithValues(LIST, void (*)(POINTER));
POINTER list_AssocListValue(LIST, POINTER);
LIST    list_AssocListPair(LIST, POINTER);

LIST    list_MultisetDistribution(LIST);
int     list_CompareMultisetsByElementDistribution(LIST, LIST);

NAT     list_Length(LIST);
NAT     list_Bytes(LIST);

/**************************************************************/
/* Functional Inline Functions                                */
/**************************************************************/

static __inline__ LIST list_Cons(POINTER Ptr, const LIST List)
{
  LIST Cell;

  Cell = (LIST)memory_Malloc(sizeof(LIST_NODE));
  Cell->car = Ptr;
  Cell->cdr = List;
  return Cell;
}


static __inline__ LIST list_Nconc(LIST List1, LIST List2)
{
  LIST Result;

  if (list_Empty(List1))
    return List2;

  if (list_Empty(List2))
    return List1;

  Result = List1;
  for (List1 = Result; !list_Empty(list_Cdr(List1)); List1 = list_Cdr(List1))
    /* empty */;
  List1->cdr = List2;
  return Result;
}


static __inline__ LIST list_List(POINTER P)
{
  return list_Cons(P,list_Nil());
}


static __inline__ LIST list_Append(LIST List1, LIST List2)
{
  LIST Result;

  if (list_Empty(List1))
    return List2;
  if (list_Empty(List2))
    return list_Copy(List1);

  Result = list_Copy(List1);
  for (List1 = Result; !list_Empty(list_Cdr(List1)); List1 = list_Cdr(List1))
    /* empty */;
  List1->cdr = List2;
  return Result;
}


static __inline__ void list_Delete(LIST L)
{
  LIST Current;

  Current = L;
  while (!list_Empty(Current)) {
    L = list_Cdr(L);
    list_Free(Current);
    Current = L;
  }
}

static __inline__ BOOL list_Member(LIST List, POINTER Element,
				   BOOL (*Test)(POINTER, POINTER))
/**************************************************************
  INPUT:   A list and an element pointer and an equality test for two elements.
  RETURNS: TRUE iff Element is in List with respect to Test
***************************************************************/
{
  while (!list_Empty(List)) {
    if (Test(Element, list_Car(List)))
      return TRUE;
    List = list_Cdr(List);
  }
  
  return FALSE;
}


static __inline__ BOOL list_PointerMember(LIST List, POINTER Element)
/**************************************************************
  INPUT:   A list and an element pointer.
  RETURNS: TRUE iff Element is in List with respect to pointer equality.
***************************************************************/
{
  while (!list_Empty(List)) {
    if (Element == list_Car(List))
      return TRUE;
    List = list_Cdr(List);
  }
  
  return FALSE;
}

/**************************************************************/
/* Stack Macros                                               */
/**************************************************************/

static __inline__ LIST list_StackBottom(void)
{
  return list_Nil();
}


static __inline__ BOOL list_StackEmpty(LIST S)
{
  return list_Empty(S);
}


static __inline__ LIST list_Push(POINTER I, LIST L)
{
  return list_Cons(I, L);
}


static __inline__ POINTER list_Top(LIST L)
{
  return list_Car(L);
}


static __inline__ LIST list_Pop(LIST L)
{
  LIST Aux = L; 

  L = list_Cdr(L);
  list_Free(Aux);
  return L;
}


static __inline__ void list_RplacTop(LIST L, POINTER P)
{
  list_Rplaca(L, P);
}


static __inline__ LIST list_StackFree(LIST L)
{
  while (!list_StackEmpty(L))
    L = list_Pop(L);
  return list_Nil();
}


/**************************************************************/
/* Pair Macros                                                */
/**************************************************************/

static __inline__ LIST list_PairNull(void)
{
  return list_Nil();
}


static __inline__ LIST list_PairCreate(POINTER P1, POINTER P2)
{
  return list_Cons(P1, P2);
}


static __inline__ void list_PairFree(LIST L)
{
  list_Free(L);
}


static __inline__ POINTER list_PairFirst(LIST L)
{
  return list_Car(L);
}


static __inline__ POINTER list_PairSecond(LIST L)
{
  return (POINTER)list_Cdr(L);
}

static __inline__ void list_PairRplacSecond(LIST L, POINTER P)
{
  list_Rplacd(L,P);
}

static __inline__ void list_DeletePairList(LIST L)
  /* Delete a list of pairs */
{
  list_DeleteWithElement(L, (void (*)(POINTER))list_PairFree);
}

static __inline__ void list_DeleteDistribution(LIST L)
{
  list_DeletePairList(L);
}

/**************************************************************/
/* Assoc Lists                                                */
/**************************************************************/


static __inline__ LIST list_AssocCons(LIST L, POINTER Key, POINTER Value)
{
  return list_Cons(list_PairCreate(Key, Value), L);
} 

#endif