diff options
Diffstat (limited to 'test/spass/list.c')
| -rw-r--r-- | test/spass/list.c | 1660 |
1 files changed, 1660 insertions, 0 deletions
diff --git a/test/spass/list.c b/test/spass/list.c new file mode 100644 index 00000000..c956e1e1 --- /dev/null +++ b/test/spass/list.c @@ -0,0 +1,1660 @@ +/**************************************************************/ +/* ********************************************************** */ +/* * * */ +/* * 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: 21527 $ * */ +/* $State$ * */ +/* $Date: 2005-04-24 21:10:28 -0700 (Sun, 24 Apr 2005) $ * */ +/* $Author: duraid $ * */ +/* * * */ +/* * 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)); +} |