« back to all changes in this revision
Viewing changes to SPASS/list.c
- browse files at revision 4
- compare with another revision
- download diff
- download tarball
- view history from revision 4
- Committer: Bazaar Package Importer
- Author(s): Roland Stigge
- Date: 2010-06-27 18:59:28 UTC
- mfrom: (1.1.1 upstream)
- Revision ID: james.westby@ubuntu.com-20100627185928-kdjuqghv04rxyqmc
Tags: 3.7-1
New upstream release
- files added:
- .pc
- .pc/debian-changes-3.7-1
- .pc/debian-changes-3.7-1/doc
- .pc/debian-changes-3.7-1/doc/man
- .pc/debian-changes-3.7-1/doc/texinfo
- SPASS
- debian/patches
- debian/source
- doc
- doc/handbook
- doc/html
- doc/man
- doc/syntax
- doc/texinfo
- doc/tutorial
- examples
- lib
- m4
- scripts
- files removed:
- debian/SPASS.1
- files modified:
- debian/changelog
added
removed
SPASS/list.c
1
/**************************************************************/
2
/* ********************************************************** */
3
/* * * */
4
/* * LISTS * */
5
/* * * */
6
/* * $Module: LIST * */
7
/* * * */
8
/* * Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001 * */
9
/* * MPI fuer Informatik * */
10
/* * * */
11
/* * This program is free software; you can redistribute * */
12
/* * it and/or modify it under the terms of the FreeBSD * */
13
/* * Licence. * */
14
/* * * */
15
/* * This program is distributed in the hope that it will * */
16
/* * be useful, but WITHOUT ANY WARRANTY; without even * */
17
/* * the implied warranty of MERCHANTABILITY or FITNESS * */
18
/* * FOR A PARTICULAR PURPOSE. See the LICENCE file * */
19
/* * for more details. * */
20
/* * * */
21
/* * * */
22
/* $Revision: 1.3 $ * */
23
/* $State: Exp $ * */
24
/* $Date: 2010-02-22 14:09:58 $ * */
25
/* $Author: weidenb $ * */
26
/* * * */
27
/* * Contact: * */
28
/* * Christoph Weidenbach * */
29
/* * MPI fuer Informatik * */
30
/* * Stuhlsatzenhausweg 85 * */
31
/* * 66123 Saarbruecken * */
32
/* * Email: spass@mpi-inf.mpg.de * */
33
/* * Germany * */
34
/* * * */
35
/* ********************************************************** */
36
/**************************************************************/
37
38
39
/* $RCSfile: list.c,v $ */
40
41
#include "list.h"
42
43
/**************************************************************/
44
/* ********************************************************** */
45
/* * * */
46
/* * MEMORY MANAGEMENT * */
47
/* * * */
48
/* ********************************************************** */
49
/**************************************************************/
50
51
LIST list_Copy(const LIST List)
52
/**************************************************************
53
INPUT: A List.
54
RETURNS: The copy of the list.
55
CAUTION: The entries of the list are NOT copied !
56
the function needs time O(n), where <n> is the length
57
of the list.
58
***************************************************************/
59
{
60
LIST Copy;
61
LIST Scan1,Scan2;
62
63
64
if (list_Empty(List))
65
return list_Nil();
66
67
Copy = list_List(list_Car(List));
68
Scan1 = Copy;
69
Scan2 = list_Cdr(List);
70
71
while (!list_Empty(Scan2)) {
72
list_Rplacd(Scan1, list_List(list_Car(Scan2)));
73
Scan1 = list_Cdr(Scan1);
74
Scan2 = list_Cdr(Scan2);
75
}
76
return Copy;
77
}
78
79
80
LIST list_CopyWithElement(const LIST List, POINTER (*CopyElement)(POINTER))
81
/**************************************************************
82
INPUT: A List and a copy function for the elements.
83
RETURNS: The copy of the list.
84
CAUTION: The entries of the list are NOT copied !
85
The function needs time O(n*c), where <n> is the length
86
of the list and <c> is the time for a call of the
87
element copy function.
88
***************************************************************/
89
{
90
LIST Copy;
91
LIST Scan1,Scan2;
92
93
if (list_Empty(List))
94
return list_Nil();
95
96
Copy = list_List(CopyElement(list_Car(List)));
97
Scan1 = Copy;
98
Scan2 = list_Cdr(List);
99
100
while (!list_Empty(Scan2)) {
101
list_Rplacd(Scan1, list_List(CopyElement(list_Car(Scan2))));
102
Scan1 = list_Cdr(Scan1);
103
Scan2 = list_Cdr(Scan2);
104
}
105
return Copy;
106
}
107
108
109
void list_InsertNext(LIST List, POINTER Pointer)
110
/**************************************************************
111
INPUT: A list and a pointer to anything.
112
RETURNS: A list with Pointer being added at the position that
113
follows List.
114
SUMMARY: We enqueue the element at position list_Cdr(List);
115
The function needs time O(1).
116
***************************************************************/
117
{
118
#ifdef CHECK
119
if (Pointer == NULL) {
120
misc_StartErrorReport();
121
misc_ErrorReport("\n In list_InsertNext: NULL Pointer. ");
122
misc_FinishErrorReport();
123
}
124
#endif
125
126
list_Rplacd(List, list_Cons(Pointer, list_Cdr(List)));
127
}
128
129
130
void list_NMapCar(LIST List, POINTER (*ElementFunc)(POINTER))
131
/**************************************************************
132
INPUT: A List and a function for the elements.
133
RETURNS: The List where all elements are replaced by the result of
134
the function calls of <ElementFunc> to the elements
135
CAUTION: The List is not copied !
136
The function needs time O(n*f), where <n> is the length
137
of the list and <f> is the time for a call of the
138
element function.
139
***************************************************************/
140
{
141
LIST Scan;
142
143
for (Scan = List; !list_Empty(Scan); Scan = list_Cdr(Scan))
144
list_Rplaca(Scan, ElementFunc(list_Car(Scan)));
145
}
146
147
148
void list_Apply(void (*Function)(POINTER), LIST List)
149
/**************************************************************
150
INPUT: A non-resulting function and a list.
151
SUMMARY: Apply the function to all members of the list.
152
The function needs time O(n*f), where <n> is the length
153
of the list and <f> is the time for a call of the
154
element function.
155
***************************************************************/
156
{
157
while (!list_Empty(List)) {
158
Function(list_Car(List));
159
List = list_Cdr(List);
160
}
161
}
162
163
164
LIST list_Reverse(const LIST List)
165
/**************************************************************
166
INPUT: A list.
167
RETURNS: A new list where the order of the elements is reversed.
168
EFFECT: The function needs time O(n), where <n> is the length
169
of the list.
170
***************************************************************/
171
{
172
LIST ReverseList;
173
LIST Scan;
174
175
ReverseList = list_Nil();
176
177
for (Scan=List;!list_Empty(Scan);Scan=list_Cdr(Scan))
178
ReverseList = list_Cons(list_Car(Scan), ReverseList);
179
180
return ReverseList;
181
}
182
183
184
LIST list_NReverse(LIST List)
185
/**************************************************************
186
INPUT: A list
187
RETURNS: The same list with reversed order of items.
188
CAUTION: Destructive but the pointer <List> is also the pointer
189
to the reverse list.
190
The function needs time and space O(n), where n is the length
191
of the list.
192
***************************************************************/
193
{
194
LIST ReverseList;
195
LIST Scan, Result;
196
197
if (list_Empty(List) || list_Empty(list_Cdr(List)))
198
return List;
199
200
Result = List;
201
List = list_List(list_Car(List));
202
list_Rplacd(List,list_Cdr(Result));
203
204
ReverseList = list_Nil();
205
206
while (!list_Empty(List)) {
207
Scan = list_Cdr(List);
208
list_Rplacd(List, ReverseList);
209
ReverseList = List;
210
List = Scan;
211
}
212
213
list_Rplaca(Result,list_Car(ReverseList));
214
list_Rplacd(Result,list_Cdr(ReverseList));
215
list_Free(ReverseList);
216
217
return Result;
218
}
219
220
221
static __inline__ BOOL list_PointerLower (POINTER A, POINTER B)
222
{
223
return (NAT) A < (NAT) B;
224
}
225
226
LIST list_PointerSort(LIST List)
227
/**************************************************************
228
INPUT: A list
229
RETURNS: The same list where the elements are sorted as pointers.
230
EFFECT: The function needs time O(n log n), where <n> is the length
231
of the list.
232
CAUTION: Destructive.
233
***************************************************************/
234
{
235
return list_Sort(List, list_PointerLower);
236
}
237
238
239
BOOL list_SortedInOrder(LIST L, BOOL (*Test)(POINTER, POINTER))
240
/**************************************************************
241
INPUT: A list, and an ordering function.
242
RETURNS: TRUE, if the list is ordered with respect to the
243
ordering function, FALSE otherwise.
244
EFFECT: The function needs time O(n), where <n> is the
245
length of the list.
246
***************************************************************/
247
{
248
LIST Scan1, Scan2;
249
250
if (!(list_Empty(L) || list_Empty(list_Cdr(L)))) {
251
Scan1 = L;
252
Scan2 = list_Cdr(Scan1);
253
254
/* Scan the list. */
255
do {
256
/* If all elements are ordered, then every element */
257
/* is <= its successor with respect to the ordering */
258
/* function. */
259
/* We might have a strictly ordering Test function, */
260
/* which implements < instead of <=, so let's test */
261
/* for equality first. */
262
if (!Test(list_Car(Scan1), list_Car(Scan2)) &&
263
Test(list_Car(Scan2), list_Car(Scan1)))
264
/* It is really strictly greater, so return FALSE. */
265
return FALSE;
266
267
Scan1 = list_Cdr(Scan1);
268
Scan2 = list_Cdr(Scan1);
269
} while (!list_Empty(Scan2));
270
}
271
272
return TRUE;
273
}
274
275
276
LIST list_Merge(LIST List1, LIST List2, BOOL (*Test)(POINTER, POINTER))
277
/**************************************************************
278
INPUT: Two sorted lists List1 and List2, and an ordering function.
279
RETURNS: The merged list ordered with respect to the ordering function.
280
EFFECT: The function needs time O(n), where <n> is the length of the list.
281
***************************************************************/
282
{
283
284
LIST Scan1, Scan2, Result, ResultStart;
285
286
#ifdef CHECK
287
if (!list_SortedInOrder(List1, Test)) {
288
/* print an error message and exit */
289
misc_StartErrorReport();
290
misc_ErrorReport("\n In list_Merge: First argument is not sorted.");
291
misc_FinishErrorReport();
292
}
293
else if (!list_SortedInOrder (List2, Test)) {
294
/* print an error message and exit */
295
misc_StartErrorReport();
296
misc_ErrorReport("\n In list_Merge: Second argument is not sorted.");
297
misc_FinishErrorReport();
298
}
299
#endif
300
301
if (list_Empty(List1))
302
return List2;
303
304
if (list_Empty(List2))
305
return List1;
306
307
/* This version is derived from list_NNumberMerge, but it doesn't need */
308
/* to allocate and deallocate memory, so it should be more efficient. */
309
310
/* Use the list with the least element as result list. */
311
if (Test(list_Car(List1), list_Car(List2))) {
312
ResultStart = List1;
313
Scan1 = list_Cdr(List1);
314
Scan2 = List2;
315
}
316
else {
317
ResultStart = List2;
318
Scan1 = List1;
319
Scan2 = list_Cdr(List2);
320
}
321
322
/* Result is the last element of the merged list. */
323
324
Result = ResultStart;
325
326
while (!list_Empty(Scan1) && !list_Empty(Scan2)) {
327
/* This function doesn't implement stable merging. */
328
/* Add another test if you need it. */
329
330
if (Test(list_Car(Scan1), list_Car(Scan2))) {
331
list_Rplacd(Result,Scan1);
332
Scan1 = list_Cdr(Scan1);
333
}
334
else {
335
list_Rplacd(Result,Scan2);
336
Scan2 = list_Cdr(Scan2);
337
}
338
Result = list_Cdr(Result);
339
}
340
341
if (list_Empty(Scan1))
342
list_Rplacd(Result, Scan2);
343
else
344
list_Rplacd(Result, Scan1);
345
346
return ResultStart;
347
}
348
349
350
void list_Split(LIST L, LIST *Half1, LIST *Half2)
351
/**************************************************************
352
INPUT: A list, and two pointers to lists.
353
RETURNS: Nothing.
354
EFFECT: The input list is split in two. <Half1> and
355
<Half2> point to the resulting halves.
356
The input list is destructively changed!
357
If the list length is odd, <Half2> is assigned the
358
bigger part.
359
The function needs time O(n), where <n> is the
360
length of the input list.
361
***************************************************************/
362
{
363
/* Adapted code from proofcheck ... MergeSort. */
364
365
LIST SingleStep, DoubleStep, Prev;
366
367
if (list_Empty(L) || list_Empty(list_Cdr(L))) {
368
*Half1 = list_Nil();
369
*Half2 = L;
370
}
371
else {
372
/* divide list in two halves */
373
Prev = L;
374
SingleStep = list_Cdr(L);
375
DoubleStep = list_Cdr(SingleStep);
376
377
while (!list_Empty(DoubleStep) && !list_Empty(list_Cdr(DoubleStep))) {
378
Prev = SingleStep;
379
SingleStep = list_Cdr(SingleStep);
380
DoubleStep = list_Cdr(list_Cdr(DoubleStep));
381
}
382
383
*Half1 = L;
384
*Half2 = SingleStep;
385
list_Rplacd(Prev, list_Nil());
386
}
387
}
388
389
390
LIST list_MergeSort (LIST L, BOOL (*Test) (POINTER, POINTER))
391
/**************************************************************
392
INPUT: A list, and an ordering function.
393
RETURNS: The list sorted with respect to the ordering function.
394
EFFECT: The function needs time O((n log n) * t), where
395
<n> is the length of the input list and <t> is the
396
execution time of the ordering function.
397
***************************************************************/
398
{
399
LIST Result;
400
#ifdef CHECK
401
NAT originallength;
402
403
originallength = list_Length(L);
404
#endif
405
406
/* Only sort if list has more than one element */
407
if (!list_Empty(L) && !list_Empty(list_Cdr(L))) {
408
LIST lowerhalf;
409
LIST greaterhalf;
410
411
LIST *lowerhalfptr;
412
LIST *greaterhalfptr;
413
414
lowerhalfptr = &lowerhalf;
415
greaterhalfptr = &greaterhalf;
416
417
list_Split(L, lowerhalfptr, greaterhalfptr);
418
419
#ifdef CHECK
420
if((list_Length(lowerhalf) + list_Length(greaterhalf))
421
!= originallength) {
422
/* output an error message and exit */
423
misc_StartErrorReport();
424
misc_ErrorReport("\n In list_MergeSort: Split lists' total sizes");
425
misc_ErrorReport("\n don't match original list's size.");
426
misc_FinishErrorReport();
427
}
428
#endif
429
430
lowerhalf = list_MergeSort(lowerhalf, Test);
431
432
greaterhalf = list_MergeSort(greaterhalf, Test);
433
434
#ifdef CHECK
435
if((list_Length(lowerhalf) + list_Length(greaterhalf))
436
!= originallength) {
437
/* output an error message and exit */
438
misc_StartErrorReport();
439
misc_ErrorReport("\n In list_MergeSort: Mergesorted lists' total sizes");
440
misc_ErrorReport("\n don't match original list's size.");
441
misc_FinishErrorReport();
442
}
443
#endif
444
445
Result = list_Merge(lowerhalf, greaterhalf, Test);
446
447
#ifdef CHECK
448
if(list_Length(Result) != originallength) {
449
/* output an error message and exit */
450
misc_StartErrorReport();
451
misc_ErrorReport("\n In list_MergeSort: Merged list's size doesn't match ");
452
misc_ErrorReport("\n original list's size.");
453
misc_FinishErrorReport();
454
}
455
#endif
456
457
}
458
else {
459
Result = L;
460
}
461
462
return Result;
463
}
464
465
466
LIST list_InsertionSort(LIST List, BOOL (*Test)(POINTER, POINTER))
467
/**************************************************************
468
INPUT: A list and a 'less' function on the elements.
469
RETURNS: The same list where the elements are sorted with
470
respect to Test.
471
EFFECT: The function needs time O(n^2*t), where <n> is the
472
length of the list and <t> is the time for the test
473
function.
474
CAUTION: Destructive.
475
***************************************************************/
476
{
477
LIST Scan1,Scan2,Min;
478
POINTER Exchange;
479
480
for (Scan1=List; !list_Empty(Scan1); Scan1=list_Cdr(Scan1)) {
481
Min = Scan1;
482
for (Scan2 = list_Cdr(Scan1); !list_Empty(Scan2); Scan2 = list_Cdr(Scan2))
483
if (Test(list_Car(Scan2), list_Car(Min))) {
484
Exchange = list_Car(Min);
485
list_Rplaca(Min, list_Car(Scan2));
486
list_Rplaca(Scan2, Exchange);
487
}
488
}
489
490
return List;
491
}
492
493
494
LIST list_Sort(LIST List, BOOL (*Test)(POINTER, POINTER))
495
/**************************************************************
496
INPUT: A list and a 'less' function on the elements.
497
RETURNS: The same list where the elements are sorted with
498
respect to Test.
499
EFFECT: The function needs time O((n log n) *t), where <n>
500
is the length of the list and <t> is the time for
501
the test function.
502
CAUTION: Destructive.
503
***************************************************************/
504
{
505
LIST Result;
506
507
#ifdef CHECK
508
NAT originallength;
509
510
originallength = list_Length(List);
511
#endif
512
513
Result = list_MergeSort(List, Test);
514
515
#ifdef CHECK
516
if (!list_SortedInOrder(Result, Test)) {
517
misc_StartErrorReport();
518
misc_ErrorReport("\n In list_Sort: list_MergeSort did not sort properly.");
519
misc_FinishErrorReport();
520
}
521
if (list_Length(Result) != originallength) {
522
misc_StartErrorReport();
523
misc_ErrorReport("\n In list_Sort: list_MergeSort lost elements. ");
524
misc_FinishErrorReport();
525
}
526
#endif
527
528
return Result;
529
}
530
531
532
/* Help Variable used to store a pointer to the numbering function to use
533
in element comparisons.
534
*/
535
static NAT (*NumberFunction)(POINTER) = NULL;
536
537
static __inline__ BOOL list_PointerNumberedLower(POINTER A, POINTER B)
538
{
539
return (BOOL) (NumberFunction(A) < NumberFunction(B));
540
}
541
542
static __inline__ BOOL list_PointerNumberedLowerOrEqual(POINTER A, POINTER B)
543
{
544
return (BOOL) (NumberFunction(A) <= NumberFunction(B));
545
}
546
547
static __inline__ BOOL list_PointerNumberedGreater(POINTER A, POINTER B)
548
{
549
return (BOOL) (NumberFunction(A) > NumberFunction(B));
550
}
551
552
LIST list_NumberSort(LIST List, NAT (*Number)(POINTER))
553
/**************************************************************
554
INPUT: A list and function mapping elements to numbers.
555
RETURNS: The same list where the elements are sorted with
556
respect to < and the Number function.
557
EFFECT: The function needs time O((n log n) * f), where <n>
558
is the length of the list and <f> is the time for a
559
call of the <Number> function.
560
CAUTION: Destructive.
561
***************************************************************/
562
{
563
/* Use number function as temporary variable. It is used as
564
an implicit parameter in list_PointerLower.
565
We can't make it an explicit parameter, because of the
566
prototype of list_Sort.
567
*/
568
569
NumberFunction = Number;
570
571
return list_Sort(List, list_PointerNumberedLower);
572
573
}
574
575
576
LIST list_GreaterNumberSort(LIST List, NAT (*Number)(POINTER))
577
/**************************************************************
578
INPUT: A list and function mapping elements to numbers.
579
RETURNS: The same list where the elements are sorted with
580
respect to > and the Number function.
581
EFFECT: The function needs time O((n log n) * f), where <n>
582
is the length of the list and <f> is the time for a
583
call of the <Number> function.
584
CAUTION: Destructive.
585
***************************************************************/
586
{
587
/* Use number function as temporary variable. It is used as
588
an implicit parameter in list_PointerLower.
589
We can't make it an explicit parameter, because of the
590
prototype of list_Sort.
591
*/
592
593
NumberFunction = Number;
594
595
return list_Sort(List, list_PointerNumberedGreater);
596
}
597
598
599
LIST list_NNumberMerge(LIST List1, LIST List2, NAT (*Number)(POINTER))
600
/**************************************************************
601
INPUT: Two sorted lists and function mapping elements to
602
numbers.
603
RETURNS: The merge of the lists where the elements are sorted
604
with respect to < and the Number function.
605
CAUTION: Destructive on both lists.
606
***************************************************************/
607
{
608
NumberFunction = Number;
609
610
return list_Merge(List1, List2, list_PointerNumberedLowerOrEqual);
611
}
612
613
614
POINTER list_DequeueNext(LIST List)
615
/**************************************************************
616
INPUT: A list
617
RETURNS: A pointer to a dequeued element.
618
SUMMARY: We dequeue the element pointed to by list_Cdr(List).
619
The function needs time O(1).
620
***************************************************************/
621
{
622
POINTER Pointer;
623
LIST Memo;
624
625
if (list_Empty(List))
626
return NULL;
627
628
Memo = list_Cdr(List);
629
if (list_Empty(Memo))
630
return NULL;
631
632
Pointer = list_Car(Memo);
633
list_Rplacd(List, Memo->cdr);
634
list_Free(Memo);
635
return Pointer;
636
}
637
638
639
POINTER list_NthElement(LIST List, NAT Number)
640
/**************************************************************
641
INPUT: A List and a natural number.
642
RETURNS: The <Number>th element of the list, NULL otherwise.
643
EFFECT: The function needs time O(Number).
644
***************************************************************/
645
{
646
while (!list_Empty(List) && --Number > 0)
647
List = list_Cdr(List);
648
649
if (list_Empty(List))
650
return NULL;
651
else
652
return list_Car(List);
653
}
654
655
656
void list_DeleteWithElement(LIST List, void (*ElementDelete)(POINTER))
657
/**************************************************************
658
INPUT: A list and a delete function for the elements.
659
RETURNS: Nothing.
660
EFFECT: The list and all its elements are deleted.
661
The function needs time O(n*d), where <n> is the length
662
of the list and <d> is the time for the delete function.
663
***************************************************************/
664
{
665
LIST Scan;
666
667
while (!list_Empty(List)) {
668
Scan = list_Cdr(List);
669
ElementDelete(list_Car(List));
670
list_Free(List);
671
List = Scan;
672
}
673
}
674
675
676
NAT list_DeleteWithElementCount(LIST List, void (*ElementDelete)(POINTER))
677
/**************************************************************
678
INPUT: A List and a delete function for the elements.
679
RETURNS: The number of deleted elements.
680
EFFECT: The List and all its elements are deleted.
681
The function needs time O(n*d), where <n> is the length
682
of the list and <d> is the time for the delete function.
683
***************************************************************/
684
{
685
int Result;
686
LIST Scan;
687
688
Result = 0;
689
690
while (!list_Empty(List)) {
691
Scan = list_Cdr(List);
692
ElementDelete(list_Car(List));
693
list_Free(List);
694
List = Scan;
695
Result++;
696
}
697
698
return Result;
699
}
700
701
702
LIST list_DeleteElement(LIST List, POINTER Element, BOOL (*Test)(POINTER, POINTER))
703
/**************************************************************
704
INPUT: A list, an element pointer, an equality test for
705
elements
706
RETURNS: The list where Element is deleted from List with
707
respect to Test.
708
EFFECTS: If List contains Element with respect to EqualityTest,
709
Element is deleted from List
710
CAUTION: Destructive. Be careful, the first element of a
711
list cannot be changed destructively by call by
712
reference.
713
***************************************************************/
714
{
715
LIST Scan1,Scan2;
716
717
while (!list_Empty(List) && Test(Element, list_Car(List))) {
718
Scan1 = list_Cdr(List);
719
list_Free(List);
720
List = Scan1;
721
}
722
723
if (list_Empty(List))
724
return list_Nil();
725
726
Scan2 = List;
727
Scan1 = list_Cdr(List);
728
729
while (!list_Empty(Scan1)) {
730
if (Test(Element, list_Car(Scan1))) {
731
list_Rplacd(Scan2, list_Cdr(Scan1));
732
list_Free(Scan1);
733
Scan1 = list_Cdr(Scan2);
734
}
735
else {
736
Scan2 = Scan1;
737
Scan1 = list_Cdr(Scan1);
738
}
739
}
740
return List;
741
}
742
743
744
LIST list_DeleteElementIf(LIST List, BOOL (*Test)(POINTER))
745
/**************************************************************
746
INPUT: A list and a test for elements.
747
RETURNS: The list where an element is deleted if <Test> on it
748
succeeds.
749
CAUTION: Destructive. Be careful, the first element of a list
750
cannot be changed destructively by call by
751
reference.
752
***************************************************************/
753
{
754
LIST Scan1,Scan2;
755
756
while (!list_Empty(List) && Test(list_Car(List))) {
757
Scan1 = list_Cdr(List);
758
list_Free(List);
759
List = Scan1;
760
}
761
762
if (list_Empty(List))
763
return list_Nil();
764
765
Scan2 = List;
766
Scan1 = list_Cdr(List);
767
768
while (!list_Empty(Scan1)) {
769
if (Test(list_Car(Scan1))) {
770
list_Rplacd(Scan2, list_Cdr(Scan1));
771
list_Free(Scan1);
772
Scan1 = list_Cdr(Scan2);
773
}
774
else {
775
Scan2 = Scan1;
776
Scan1 = list_Cdr(Scan1);
777
}
778
}
779
return List;
780
}
781
782
783
LIST list_DeleteElementIfFree(LIST List, BOOL (*Test)(POINTER),
784
void (*Delete)(POINTER))
785
/**************************************************************
786
INPUT: A list, a test for elements and a delete function
787
for elements.
788
RETURNS: The list where an element is deleted if <Test> on it
789
succeeds.
790
The element is deleted with <Delete>.
791
CAUTION: Destructive. Be careful, the first element of a list
792
cannot be changed destructively by call by reference.
793
***************************************************************/
794
{
795
LIST Scan1,Scan2;
796
797
while (!list_Empty(List) && Test(list_Car(List))) {
798
Scan1 = list_Cdr(List);
799
Delete(list_Car(List));
800
list_Free(List);
801
List = Scan1;
802
}
803
804
if (list_Empty(List))
805
return list_Nil();
806
807
Scan2 = List;
808
Scan1 = list_Cdr(List);
809
810
while (!list_Empty(Scan1)) {
811
if (Test(list_Car(Scan1))) {
812
Delete(list_Car(Scan1));
813
list_Rplacd(Scan2, list_Cdr(Scan1));
814
list_Free(Scan1);
815
Scan1 = list_Cdr(Scan2);
816
}
817
else {
818
Scan2 = Scan1;
819
Scan1 = list_Cdr(Scan1);
820
}
821
}
822
return List;
823
}
824
825
826
827
LIST list_DeleteElementFree(LIST List, POINTER Element,
828
BOOL (*Test)(POINTER, POINTER),
829
void (*Free)(POINTER))
830
/**************************************************************
831
INPUT: A list, an element pointer, an equality test for
832
elements and a free function for elements.
833
RETURNS: The list where Element is deleted from List with
834
respect to Test.
835
EFFECTS: If the list contains <Element> with respect to <Test>,
836
<Element> is deleted from the list and freed.
837
CAUTION: Destructive. Be careful, the first element of a list
838
cannot be changed destructively by call by reference.
839
***************************************************************/
840
{
841
LIST Scan1,Scan2;
842
843
while (!list_Empty(List) && Test(Element, list_Car(List))) {
844
Scan1 = list_Cdr(List);
845
Free(list_Car(List));
846
list_Free(List);
847
List = Scan1;
848
}
849
850
if (list_Empty(List))
851
return list_Nil();
852
853
Scan2 = List;
854
Scan1 = list_Cdr(List);
855
856
while (!list_Empty(Scan1)) {
857
if (Test(Element, list_Car(Scan1))) {
858
list_Rplacd(Scan2, list_Cdr(Scan1));
859
Free(list_Car(Scan1));
860
list_Free(Scan1);
861
Scan1 = list_Cdr(Scan2);
862
}
863
else {
864
Scan2 = Scan1;
865
Scan1 = list_Cdr(Scan1);
866
}
867
}
868
return List;
869
}
870
871
872
LIST list_DeleteOneElement(LIST List, POINTER Element, BOOL (*Test)(POINTER, POINTER))
873
/**************************************************************
874
INPUT: A list, an element pointer and an equality test for
875
elements.
876
RETURNS: The list where at most one element was deleted from
877
<List> if the Test between <Element> and the element
878
succeeds.
879
EFFECT: The function needs time O(n*t) in the worst case, and
880
time O(t) in the best case, where <n> is the length of
881
the list and t is the time for a call of the test function.
882
CAUTION: Destructive. Be careful, the first element of a list
883
cannot be changed destructively by call by
884
reference.
885
The memory of the deleted element is not freed.
886
***************************************************************/
887
{
888
LIST scan1, scan2;
889
890
if (list_Empty(List))
891
return List;
892
else {
893
if (Test(Element, list_Car(List)))
894
return list_Pop(List);
895
}
896
897
for (scan2 = List, scan1 = list_Cdr(List); !list_Empty(scan1);
898
scan2 = scan1, scan1 = list_Cdr(scan1)) {
899
if (Test(Element, list_Car(scan1))) {
900
list_Rplacd(scan2, list_Cdr(scan1));
901
list_Free(scan1);
902
scan1 = list_Cdr(scan2);
903
return List;
904
}
905
}
906
return List;
907
}
908
909
910
LIST list_PointerDeleteElement(LIST List, POINTER Element)
911
/**************************************************************
912
INPUT: A list and an element pointer
913
RETURNS: The list where Element is deleted from List with respect to
914
pointer equality.
915
EFFECTS: If <List> contains <Element> with respect to pointer equality,
916
<Element> is deleted from <List>.
917
This function needs time O(n), where <n> is the length of the list.
918
CAUTION: Destructive. Be careful, the first element of a list cannot
919
be changed destructively by call by reference.
920
***************************************************************/
921
{
922
LIST Scan1,Scan2;
923
924
while (!list_Empty(List) && Element == list_Car(List)) {
925
Scan1 = list_Cdr(List);
926
list_Free(List);
927
List = Scan1;
928
}
929
930
if (list_Empty(List))
931
return list_Nil();
932
933
Scan2 = List;
934
Scan1 = list_Cdr(List);
935
936
while (!list_Empty(Scan1)) {
937
if (Element == list_Car(Scan1)) {
938
list_Rplacd(Scan2, list_Cdr(Scan1));
939
list_Free(Scan1);
940
Scan1 = list_Cdr(Scan2);
941
}
942
else {
943
Scan2 = Scan1;
944
Scan1 = list_Cdr(Scan1);
945
}
946
}
947
return List;
948
}
949
950
LIST list_PointerDeleteElementFree(LIST List, POINTER Element,
951
void (*Free)(POINTER))
952
/**************************************************************
953
INPUT: A list, an element pointer and a free function for
954
elements.
955
RETURNS: The list where Element is deleted from List with
956
respect to pointer equality and freed.
957
EFFECTS: If List contains Element with respect to pointer
958
equality, Element is deleted from List
959
CAUTION: Destructive. Be careful, the first element of a list
960
cannot be changed destructively by call by
961
reference.
962
***************************************************************/
963
{
964
LIST Scan1,Scan2;
965
966
while (!list_Empty(List) && Element == list_Car(List)) {
967
Scan1 = list_Cdr(List);
968
Free(list_Car(List));
969
list_Free(List);
970
List = Scan1;
971
}
972
973
if (list_Empty(List))
974
return list_Nil();
975
976
Scan2 = List;
977
Scan1 = list_Cdr(List);
978
979
while (!list_Empty(Scan1)) {
980
if (Element == list_Car(Scan1)) {
981
list_Rplacd(Scan2, list_Cdr(Scan1));
982
Free(list_Car(Scan1));
983
list_Free(Scan1);
984
Scan1 = list_Cdr(Scan2);
985
}
986
else {
987
Scan2 = Scan1;
988
Scan1 = list_Cdr(Scan1);
989
}
990
}
991
return List;
992
}
993
994
995
LIST list_PointerDeleteOneElement(LIST List, POINTER Element)
996
/**************************************************************
997
INPUT: A list and an element pointer.
998
RETURNS: The list where one occurrence of Element is deleted from List
999
with respect to pointer equality.
1000
EFFECTS: If List contains Element with respect to pointer equality,
1001
Element is deleted from List.
1002
CAUTION: Destructive. Be careful, the first element of a list cannot
1003
be changed destructively by call by reference.
1004
***************************************************************/
1005
{
1006
LIST Scan1,Scan2;
1007
1008
if (list_Empty(List))
1009
return List;
1010
else {
1011
if (Element == list_Car(List))
1012
return list_Pop(List);
1013
}
1014
1015
Scan2 = List;
1016
Scan1 = list_Cdr(List);
1017
1018
while (!list_Empty(Scan1)) {
1019
if (Element == list_Car(Scan1)) {
1020
list_Rplacd(Scan2, list_Cdr(Scan1));
1021
list_Free(Scan1);
1022
Scan1 = list_Cdr(Scan2);
1023
return List;
1024
}
1025
else {
1026
Scan2 = Scan1;
1027
Scan1 = list_Cdr(Scan1);
1028
}
1029
}
1030
return List;
1031
}
1032
1033
1034
BOOL list_DeleteFromList(LIST* List, POINTER Element)
1035
/**************************************************************
1036
INPUT: A list and an element pointer
1037
RETURNS: TRUE, if Element was deleted; FALSE, otherwise.
1038
EFFECTS: If List contains Element with respect to pointer equality,
1039
all occurrences of Element are deleted from List.
1040
CAUTION: Destructive. Be careful, the first element of a list cannot
1041
be changed destructively by call by reference.
1042
***************************************************************/
1043
{
1044
BOOL Found;
1045
LIST Scan1;
1046
1047
Found = FALSE;
1048
1049
while (list_Exist(*List) && Element == list_Car(*List)) {
1050
Scan1 = list_Cdr(*List);
1051
list_Free(*List);
1052
*List = Scan1;
1053
Found = TRUE;
1054
}
1055
1056
if (list_Exist(*List)) {
1057
LIST Scan2;
1058
1059
Scan2 = *List;
1060
Scan1 = list_Cdr(*List);
1061
1062
while (list_Exist(Scan1)) {
1063
if (Element == list_Car(Scan1)) {
1064
list_Rplacd(Scan2, list_Cdr(Scan1));
1065
list_Free(Scan1);
1066
Scan1 = list_Cdr(Scan2);
1067
Found = TRUE;
1068
} else {
1069
Scan2 = Scan1;
1070
Scan1 = list_Cdr(Scan1);
1071
}
1072
}
1073
}
1074
1075
return Found;
1076
}
1077
1078
1079
BOOL list_DeleteOneFromList(LIST* List, POINTER Element)
1080
/**************************************************************
1081
INPUT: A list and an element pointer
1082
RETURNS: TRUE, if <Element> was deleted; FALSE, otherwise.
1083
EFFECTS: If <List> contains <Element> with respect to pointer equality,
1084
the first occurrence of <Element> is deleted from <List>.
1085
CAUTION: Destructive.
1086
***************************************************************/
1087
{
1088
if (list_Exist(*List)) {
1089
LIST Scan1;
1090
1091
/* special treatment for the first element */
1092
if (Element == list_Car(*List)) {
1093
Scan1 = list_Cdr(*List);
1094
list_Free(*List);
1095
*List = Scan1;
1096
return TRUE;
1097
} else {
1098
LIST Scan2;
1099
1100
for (Scan2 = *List, Scan1 = list_Cdr(*List); list_Exist(Scan1); ) {
1101
if (Element == list_Car(Scan1)) {
1102
list_Rplacd(Scan2, list_Cdr(Scan1));
1103
list_Free(Scan1);
1104
Scan1 = list_Cdr(Scan2);
1105
return TRUE;
1106
} else {
1107
Scan2 = Scan1;
1108
Scan1 = list_Cdr(Scan1);
1109
}
1110
}
1111
}
1112
}
1113
return FALSE;
1114
}
1115
1116
1117
BOOL list_IsSetOfPointers(LIST L)
1118
/**************************************************************
1119
INPUT: A list.
1120
RETURNS: TRUE, if <L> is a set of pointers (without duplicates),
1121
FALSE, otherwise.
1122
EFFECT: The function needs n(n-1)/2 comparisons in the worst case,
1123
where n is the length of the list. So its time complexity
1124
is O(n^2).
1125
***************************************************************/
1126
{
1127
for ( ; !list_Empty(L); L = list_Cdr(L)) {
1128
if (list_PointerMember(list_Cdr(L), list_Car(L)))
1129
return FALSE;
1130
}
1131
return TRUE;
1132
}
1133
1134
1135
LIST list_DeleteDuplicates(LIST List, BOOL (*Test)(POINTER, POINTER))
1136
/**************************************************************
1137
INPUT: A list, an equality test for elements
1138
RETURNS: The list where multiple occurrences are deleted.
1139
CAUTION: Destructive.
1140
***************************************************************/
1141
{
1142
LIST Scan;
1143
1144
Scan = List;
1145
1146
while (!list_Empty(Scan)) {
1147
list_Rplacd(Scan,
1148
list_DeleteElement(list_Cdr(Scan), list_Car(Scan), Test));
1149
Scan = list_Cdr(Scan);
1150
}
1151
return List;
1152
}
1153
1154
1155
LIST list_DeleteDuplicatesFree(LIST List, BOOL (*Test)(POINTER, POINTER),
1156
void (*Free)(POINTER))
1157
/**************************************************************
1158
INPUT: A list, an equality test for elements, and a free
1159
function for elements.
1160
RETURNS: The list where multiple occurrences are deleted.
1161
CAUTION: Destructive and frees all duplicates.
1162
***************************************************************/
1163
{
1164
LIST Scan;
1165
1166
Scan = List;
1167
1168
while (!list_Empty(Scan)) {
1169
list_Rplacd(Scan, list_DeleteElementFree(list_Cdr(Scan), list_Car(Scan), Test, Free));
1170
Scan = list_Cdr(Scan);
1171
}
1172
return List;
1173
}
1174
1175
1176
LIST list_PointerDeleteDuplicates(LIST List)
1177
/**************************************************************
1178
INPUT: A list
1179
RETURNS: The list where multiple occurrences are deleted.
1180
CAUTION: Destructive.
1181
EFFECT: The function needs
1182
***************************************************************/
1183
{
1184
LIST Scan;
1185
1186
Scan = List;
1187
1188
while (!list_Empty(Scan)) {
1189
list_Rplacd(Scan, list_PointerDeleteElement(list_Cdr(Scan),
1190
list_Car(Scan)));
1191
Scan = list_Cdr(Scan);
1192
}
1193
return List;
1194
}
1195
1196
1197
LIST list_NPointerUnion(LIST List1, LIST List2)
1198
/**************************************************************
1199
INPUT: Two lists.
1200
RETURNS: Regarding both lists as sets, the union of the sets.
1201
CAUTION: Destructive.
1202
***************************************************************/
1203
{
1204
return list_PointerDeleteDuplicates(list_Nconc(List1,List2));
1205
}
1206
1207
1208
LIST list_NUnion(LIST List1, LIST List2, BOOL (*Test)(POINTER, POINTER))
1209
/**************************************************************
1210
INPUT: Two lists and an equality test for the elements.
1211
RETURNS: Regarding both lists as sets, the union of the sets.
1212
CAUTION: Destructive.
1213
***************************************************************/
1214
{
1215
return list_DeleteDuplicates(list_Nconc(List1,List2), Test);
1216
}
1217
1218
1219
LIST list_NListTimes(LIST List1, LIST List2)
1220
/**************************************************************
1221
INPUT: Two lists of lists.
1222
RETURNS: The list of combinations of element lists.
1223
CAUTION: Destroys List1 and List2.
1224
***************************************************************/
1225
{
1226
LIST Result, Scan1, Scan2;
1227
1228
Result = list_Nil();
1229
1230
if (!list_Empty(List2)) {
1231
for (Scan1=List1; !list_Empty(Scan1); Scan1=list_Cdr(Scan1))
1232
for (Scan2=List2; !list_Empty(Scan2); Scan2=list_Cdr(Scan2))
1233
Result = list_Cons(list_Append(((LIST)list_Car(Scan1)),
1234
list_Copy((LIST)list_Car(Scan2))),
1235
Result);
1236
}
1237
list_DeleteWithElement(List1, (void (*)(POINTER))list_Delete);
1238
list_DeleteWithElement(List2, (void (*)(POINTER))list_Delete);
1239
1240
return Result;
1241
}
1242
1243
1244
LIST list_NIntersect(LIST List1, LIST List2, BOOL (*Test)(POINTER, POINTER))
1245
/**************************************************************
1246
INPUT: Two lists and an equality test for the elements.
1247
RETURNS: Regarding both lists as sets, the intersection of the sets.
1248
CAUTION: Destructive on List1
1249
***************************************************************/
1250
{
1251
LIST Scan1, Scan2;
1252
1253
while (!list_Empty(List1) && !list_Member(List2, list_Car(List1), Test)) {
1254
Scan1 = list_Cdr(List1);
1255
list_Free(List1);
1256
List1 = Scan1;
1257
}
1258
1259
if (list_Empty(List1))
1260
return List1;
1261
1262
Scan1 = List1;
1263
Scan2 = list_Cdr(List1);
1264
1265
while (!list_Empty(Scan2)) {
1266
if (list_Member(List2, list_Car(Scan2), Test)) {
1267
Scan2 = list_Cdr(Scan2);
1268
Scan1 = list_Cdr(Scan1);
1269
}
1270
else {
1271
list_Rplacd(Scan1, list_Cdr(Scan2));
1272
list_Free(Scan2);
1273
Scan2 = list_Cdr(Scan1);
1274
}
1275
}
1276
return List1;
1277
}
1278
1279
1280
LIST list_NPointerIntersect(LIST List1, LIST List2)
1281
/**************************************************************
1282
INPUT: Two lists.
1283
RETURNS: Regarding both lists as sets, the intersection of the sets.
1284
CAUTION: Destructive on List1
1285
***************************************************************/
1286
{
1287
LIST Scan1, Scan2;
1288
1289
while (!list_Empty(List1) && !list_PointerMember(List2, list_Car(List1))) {
1290
Scan1 = list_Cdr(List1);
1291
list_Free(List1);
1292
List1 = Scan1;
1293
}
1294
1295
if (list_Empty(List1))
1296
return List1;
1297
1298
Scan1 = List1;
1299
Scan2 = list_Cdr(List1);
1300
1301
while (!list_Empty(Scan2)) {
1302
if (list_PointerMember(List2, list_Car(Scan2))) {
1303
Scan2 = list_Cdr(Scan2);
1304
Scan1 = list_Cdr(Scan1);
1305
}
1306
else {
1307
list_Rplacd(Scan1, list_Cdr(Scan2));
1308
list_Free(Scan2);
1309
Scan2 = list_Cdr(Scan1);
1310
}
1311
}
1312
return List1;
1313
}
1314
1315
/**************************************************************
1316
INPUT: Two lists.
1317
EFFECT: <List2> is concatenated after
1318
the last element of <List1>.
1319
RETURNS: Concatenated list.
1320
CAUTION: Destructive on List1.
1321
***************************************************************/
1322
LIST list_Nconc(LIST List1, LIST List2)
1323
{
1324
LIST Result;
1325
1326
if (list_Empty(List1))
1327
return List2;
1328
1329
if (list_Empty(List2))
1330
return List1;
1331
1332
Result = List1;
1333
for (List1 = Result; !list_Empty(list_Cdr(List1)); List1 = list_Cdr(List1))
1334
/* empty */;
1335
List1->cdr = List2;
1336
return Result;
1337
}
1338
1339
void list_NInsert(LIST List1, LIST List2)
1340
/**************************************************************
1341
INPUT: Two lists where <List1> must not be empty.
1342
EFFECT: <List2> is destructively concatenated after
1343
the first element of <List1>.
1344
RETURNS: void.
1345
CAUTION: Destructive on List1 and List2.
1346
***************************************************************/
1347
{
1348
LIST Help;
1349
1350
#ifdef CHECK
1351
if (list_Empty(List1)) {
1352
misc_StartErrorReport();
1353
misc_ErrorReport("\n In list_NInsert: Empty list argument.");
1354
misc_FinishErrorReport();
1355
}
1356
#endif
1357
1358
Help = list_Cdr(List1);
1359
list_Rplacd(List1,List2);
1360
List2 = List1;
1361
1362
while (!list_Empty(list_Cdr(List2)))
1363
List2 = list_Cdr(List2);
1364
1365
list_Rplacd(List2,Help);
1366
}
1367
1368
1369
BOOL list_HasIntersection(LIST List1, LIST List2)
1370
/**************************************************************
1371
INPUT: Two lists .
1372
RETURNS: TRUE iff List1 and List2 have a common element.
1373
EFFECT: The function needs time O(n*m), where n and m are the
1374
lengths of the lists.
1375
***************************************************************/
1376
{
1377
LIST Scan;
1378
1379
if (!list_Empty(List2)) {
1380
for (Scan=List1; !list_Empty(Scan); Scan=list_Cdr(Scan))
1381
if (list_PointerMember(List2, list_Car(Scan)))
1382
return TRUE;
1383
}
1384
return FALSE;
1385
}
1386
1387
1388
LIST list_NPointerDifference(LIST List1, LIST List2)
1389
/**************************************************************
1390
INPUT: Two lists.
1391
RETURNS: The list List1-List2.
1392
CAUTION: Destructive on List1.
1393
***************************************************************/
1394
{
1395
LIST Scan;
1396
1397
if (!list_Empty(List1)) {
1398
for (Scan=List2; !list_Empty(Scan); Scan=list_Cdr(Scan))
1399
List1 = list_PointerDeleteElement(List1, list_Car(Scan));
1400
}
1401
return List1;
1402
}
1403
1404
1405
LIST list_NDifference(LIST List1, LIST List2, BOOL (*Test)(POINTER, POINTER))
1406
/**************************************************************
1407
INPUT: Two lists and an equality test for elements.
1408
RETURNS: The list List1-List2 wrt. <Test>.
1409
CAUTION: Destructive on List1.
1410
***************************************************************/
1411
{
1412
LIST Scan;
1413
1414
if (!list_Empty(List1)) {
1415
for (Scan=List2; !list_Empty(Scan); Scan=list_Cdr(Scan))
1416
List1 = list_DeleteElement(List1, list_Car(Scan), Test);
1417
}
1418
return List1;
1419
}
1420
1421
1422
LIST list_NMultisetDifference(LIST List1, LIST List2, BOOL (*Test)(POINTER, POINTER))
1423
/**************************************************************
1424
INPUT: Two lists representing multisets and an equality
1425
test for elements.
1426
RETURNS: The multiset difference List1-List2 wrt. <Test>.
1427
CAUTION: Destructive on List1. The memory of deleted
1428
elements is not freed.
1429
***************************************************************/
1430
{
1431
LIST scan;
1432
/* Delete equal arguments */
1433
if (!list_Empty(List1)) {
1434
for (scan = List2; !list_Empty(scan); scan = list_Cdr(scan))
1435
/* Delete at most one element from List1 equal to */
1436
/* the actual element of List2. */
1437
List1 = list_DeleteOneElement(List1, list_Car(scan), Test);
1438
}
1439
return List1;
1440
}
1441
1442
1443
BOOL list_PointerReplaceMember(LIST List, POINTER Old, POINTER New)
1444
/**************************************************************
1445
INPUT: A list, a pointer to an old element, a pointer to a new element
1446
RETURNS: TRUE iff <Old> was replaced.
1447
EFFECT: The first occurrence of <Old> in the list is replaced by <New>.
1448
***************************************************************/
1449
{
1450
while (!list_Empty(List)) {
1451
if (Old == list_Car(List)) {
1452
list_Rplaca(List, New);
1453
return TRUE;
1454
}
1455
List = list_Cdr(List);
1456
}
1457
return FALSE;
1458
}
1459
1460
1461
void list_DeleteAssocListWithValues(LIST List, void (*ValueDelete)(POINTER))
1462
/**************************************************************
1463
INPUT: An association list and a delete function for the values.
1464
RETURNS: void.
1465
EFFECT: The assoc list and its values are deleted.
1466
***************************************************************/
1467
{
1468
LIST Scan;
1469
1470
for (Scan=List;!list_Empty(Scan);Scan = list_Cdr(Scan)) {
1471
ValueDelete(list_PairSecond(list_Car(Scan)));
1472
list_PairFree(list_Car(Scan));
1473
}
1474
1475
list_Delete(List);
1476
}
1477
1478
1479
POINTER list_AssocListValue(LIST List, POINTER Key)
1480
/**************************************************************
1481
INPUT: An association list and a key.
1482
RETURNS: The value for <key> in the list. If <key> is not
1483
contained, NULL.
1484
***************************************************************/
1485
{
1486
LIST Scan;
1487
1488
for (Scan=List;!list_Empty(Scan);Scan = list_Cdr(Scan))
1489
if (Key == list_PairFirst(list_Car(Scan)))
1490
return list_PairSecond(list_Car(Scan));
1491
1492
return NULL;
1493
}
1494
1495
1496
LIST list_AssocListPair(LIST List, POINTER Key)
1497
/**************************************************************
1498
INPUT: An association list and a key.
1499
RETURNS: The (<key>.<value) in the list. If <key> is not
1500
contained, the NULL pair.
1501
***************************************************************/
1502
{
1503
LIST Scan;
1504
1505
for (Scan=List;!list_Empty(Scan);Scan = list_Cdr(Scan))
1506
if (Key == list_PairFirst(list_Car(Scan)))
1507
return list_Car(Scan);
1508
1509
return list_PairNull();
1510
}
1511
1512
1513
LIST list_MultisetDistribution(LIST Multiset)
1514
/**************************************************************
1515
INPUT: A list representing a multiset.
1516
RETURNS: The associative list of pairs (<element>.<occurrences>)
1517
representing the distribution of elements in the list.
1518
If the input multiset is empty, the NULL pair.
1519
***************************************************************/
1520
{
1521
LIST Distribution;
1522
LIST Scan;
1523
1524
Distribution = list_PairNull();
1525
1526
for (Scan = Multiset; !list_Empty(Scan); Scan = list_Cdr(Scan)) {
1527
LIST Count;
1528
POINTER Element;
1529
int Occurences;
1530
1531
Element = list_Car(Scan);
1532
Count = list_AssocListPair(Distribution, Element);
1533
1534
if (Count != list_PairNull()) {
1535
Occurences = (int) list_PairSecond(Count);
1536
list_PairRplacSecond(Count, (POINTER) (Occurences + 1));
1537
}
1538
else {
1539
Distribution = list_AssocCons(Distribution, Element, (POINTER) 1);
1540
}
1541
}
1542
1543
return Distribution;
1544
}
1545
1546
1547
int list_CompareElementDistribution(LIST LeftPair, LIST RightPair)
1548
/**************************************************************
1549
INPUT: Two lists, representing single element frequency
1550
counts.
1551
RETURNS: 1 if left > right, -1 if left < right, 0 otherwise.
1552
EFFECT: Compares two element frequencies.
1553
***************************************************************/
1554
{
1555
if ((int) list_PairSecond(LeftPair) < (int) list_PairSecond(RightPair)) {
1556
return -1;
1557
}
1558
else if ((int) list_PairSecond(LeftPair) > (int) list_PairSecond(RightPair)) {
1559
return 1;
1560
}
1561
1562
return 0;
1563
}
1564
1565
1566
BOOL list_CompareElementDistributionLEQ(LIST LeftPair, LIST RightPair) {
1567
/**************************************************************
1568
INPUT: Two lists, representing single element frequency
1569
counts.
1570
RETURNS: TRUE if left <= right, FALSE otherwise.
1571
EFFECT: Compares two element frequencies.
1572
***************************************************************/
1573
return (list_CompareElementDistribution(LeftPair, RightPair) <= 0);
1574
}
1575
1576
1577
static int list_CompareDistributions(LIST Left, LIST Right)
1578
/**************************************************************
1579
INPUT: Two lists, representing element distributions.
1580
RETURNS: 1 if left > right, -1 if left < right, 0 otherwise.
1581
EFFECT: Compares the two distributions by comparing the
1582
element frequencies from left to right.
1583
CAUTION: Expects the distributions to be sorted.
1584
***************************************************************/
1585
{
1586
LIST scan, scan2;
1587
int result;
1588
1589
result = 0;
1590
1591
scan = Left;
1592
scan2 = Right;
1593
1594
/* Compare distributions. */
1595
1596
while ( !(list_Empty(scan) || list_Empty(scan2))) {
1597
result = list_CompareElementDistribution(list_Car(scan), list_Car(scan2));
1598
if (result != 0) {
1599
break;
1600
}
1601
1602
scan = list_Cdr(scan);
1603
scan2 = list_Cdr(scan2);
1604
}
1605
1606
/* If the result is 0, and a distribution still
1607
has elements left, it is declared to be greater.
1608
*/
1609
if (result == 0) {
1610
if (list_Empty(scan) && !list_Empty(scan2))
1611
result = -1;
1612
else if (!list_Empty(scan) && list_Empty(scan2))
1613
result = 1;
1614
}
1615
1616
return result;
1617
}
1618
1619
1620
int list_CompareMultisetsByElementDistribution(LIST Left, LIST Right)
1621
/**************************************************************
1622
INPUT: Two lists, representing multisets.
1623
RETURNS: 1 if left > right, -1 if left < right, 0 otherwise.
1624
EFFECT: Compares two multisets by counting their element
1625
frequencies, sorting them, and comparing the
1626
resulting multisets over natural numbers.
1627
***************************************************************/
1628
{
1629
LIST lmsd, rmsd; /* multiset distributions. */
1630
int result;
1631
1632
/* Convert multiset of elements into a
1633
multiset of pairs (element, occurrences).
1634
*/
1635
1636
lmsd = list_MultisetDistribution(Left);
1637
rmsd = list_MultisetDistribution(Right);
1638
1639
/* Sort multiset distributions in order
1640
to make them comparable.
1641
*/
1642
1643
lmsd = list_Sort(lmsd, (BOOL (*) (POINTER, POINTER)) list_CompareElementDistributionLEQ);
1644
rmsd = list_Sort(rmsd, (BOOL (*) (POINTER, POINTER)) list_CompareElementDistributionLEQ);
1645
1646
result = list_CompareDistributions(lmsd, rmsd);
1647
1648
list_DeleteDistribution(lmsd);
1649
list_DeleteDistribution(rmsd);
1650
1651
return result;
1652
}
1653
1654
1655
NAT list_Length(LIST List)
1656
/**************************************************************
1657
INPUT: A List.
1658
RETURNS: The number of elements..
1659
EFFECT: The function needs time O(n), where <n> is the length
1660
of the list.
1661
***************************************************************/
1662
{
1663
NAT Result;
1664
1665
Result = 0;
1666
1667
while (!list_Empty(List)) {
1668
Result++;
1669
List = list_Cdr(List);
1670
}
1671
1672
return Result;
1673
}
1674
1675
1676
NAT list_Bytes(LIST List)
1677
/**************************************************************
1678
INPUT: A List.
1679
RETURNS: The number of Bytes occupied by the list structure of <List>
1680
EFFECT: the function needs time O(n), where <n> is the length
1681
of the list.
1682
***************************************************************/
1683
{
1684
return (list_Length(List)*sizeof(LIST_NODE));
1685
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1