1# This aims to test the various implementations of Sort. There are a few cases 2# we must cover: 3# 4# * We can choose if we pass a comparator 5# * We can do Sort or SortParallel 6# * We specialise for plain lists 7# Most of these checks are generate a whole bunch of random tests 8gap> START_TEST("sort.tst"); 9gap> lowAlpha := Immutable(SSortedList("abcdefghijklmnopqrstuvwxyz"));; 10gap> CheckIdObj := function (a,b) if IsIdenticalObj(a,b) then Error("Equal Obj!"); fi; end;; 11gap> CheckSort := function(list, sorted) 12> local listcpy, perm; 13> listcpy := DEEP_COPY_OBJ(list); Sort(listcpy); 14> if listcpy <> sorted then Print("Fail 1 : ", listcpy, list, sorted); fi; 15> listcpy := DEEP_COPY_OBJ(list); Sort(listcpy, function (a,b) CheckIdObj(a,b); return a < b; end); 16> if listcpy <> sorted then Print("Fail 2 : ", listcpy, list, sorted); fi; 17> listcpy := DEEP_COPY_OBJ(list); Sort(listcpy, function (a,b) CheckIdObj(a,b); return a <= b; end); 18> if listcpy <> sorted then Print("Fail 3 : ", listcpy, list, sorted); fi; 19> listcpy := DEEP_COPY_OBJ(list); Sort(listcpy, function (a,b) CheckIdObj(a,b); return a > b; end); 20> if listcpy <> Reversed(sorted) then Print("Fail 4 : ", listcpy, list, sorted); fi; 21> end;; 22gap> # Check filters are correctly set/unset with various sortings (and merge sortings) 23gap> CheckFiltersInner := function(list, isSort, isSSort, revisSort, revisSsort, sorter) 24> sorter(list); 25> if IsSortedList(list) <> isSort then 26> Print("fail isSorted : '", list, "'", isSort, "\n"); 27> fi; 28> if IsSSortedList(list) <> isSSort then 29> Print("fail isSSorted : ", list, "\n"); 30> fi; 31> sorter(list, function(x, y) return x < y; end); 32> if IsSortedList(list) <> isSort then 33> Print("fail isSorted 2 : '", list, "'", isSort, "\n"); 34> fi; 35> if IsSSortedList(list) <> isSSort then 36> Print("fail isSSorted 2 : ", list, "\n"); 37> fi; 38> sorter(list, function(x, y) return x > y; end); 39> if IsSortedList(list) <> revisSort then 40> Print("fail isSorted 3 : ", list, "\n"); 41> fi; 42> if IsSSortedList(list) <> revisSsort then 43> Print("fail isSSorted 3 : ", list, "\n"); 44> fi; 45> sorter(list, function(x, y) return x < y; end); 46> if IsSortedList(list) <> isSort then 47> Print("fail isSorted 4 : '", list, "'", isSort, "\n"); 48> fi; 49> if IsSSortedList(list) <> isSSort then 50> Print("fail isSSorted 4 : ", list, "\n"); 51> fi; 52> end;; 53gap> CheckFilters := function(list, isSort, isSSort, revisSort, revisSsort) 54> CheckFiltersInner(list, isSort, isSSort, revisSort, revisSsort, Sort); 55> CheckFiltersInner(list, isSort, isSSort, revisSort, revisSsort, StableSort); 56> end;; 57gap> for i in [0..500] do CheckSort([1..i],[1..i]); od; 58 59# Want to make sure GAP doesn't know the list is sorted 60gap> for i in [0..500] do CheckSort(List([1..i],x->x),[1..i]); od; 61gap> for i in [0..500] do CheckSort([-i..i],[-i..i]); od; 62gap> for i in [0..500] do CheckSort([i,i-1..-i],[-i..i]); od; 63gap> for i in [0..50] do 64> for j in [0..10] do 65> CheckSort(Shuffle([1..i]), [1..i]); 66> CheckFilters([1..i], true, true, i <= 1, i <= 1); 67> CheckFilters(Shuffle([1..i]), true, true, i <= 1, i <= 1); 68> od; 69> od; 70gap> for i in [0..100] do 71> for j in [0..10] do 72> l := Concatenation(List([0..j], x -> List([0..i], y -> x))); 73> l2 := Shuffle(List(l)); 74> CheckSort(l2, l); 75> CheckFilters(l, true, i = 0, j = 0, i = 0 and j = 0); 76> od; 77> od; 78 79# Need to test something which are not plists. Strings are a good choice. 80gap> for i in [0..50] do 81> for j in [0..10] do 82> l := ""; 83> for a in [1..j] do for b in [1..i] do 84> Add(l, CHARS_LALPHA[a]); 85> od; od; 86> l2 := Shuffle(List(l)); 87> if not(IsStringRep(l)) or not(IsStringRep(l2)) then 88> Print("StringFail"); 89> fi; 90> CheckSort(l2, l); 91> CheckFilters(l, true, i <= 1 or j <= 0, 92> i=0 or j<=1 or (i <= 1 and j <= 1), i=0 or j=0 or (i <= 1 and j <= 1)); 93> od; 94> od; 95 96# Let test bool lists too! 97gap> for i in [0..50] do 98> for j in [0..10] do 99> l := BlistList([1..i+j],[1..i]); 100> l2 := Shuffle(List(l)); 101> if not(IsBlistRep(l)) or not(IsBlistRep(l2)) then 102> Print("BlistFail"); 103> fi; 104> CheckSort(l2, l); 105> CheckFilters(l, true, i<=1 and j<=1, i = 0 or j = 0, i+j <= 1); 106> od; 107> od; 108 109# Test SortParallel 110gap> CheckSortParallel := function(sortedlist, perm, maxval) 111> local list1, list2, listcpy, list1orig; 112> # This slightly weird code is because I want to preserve 113> # The type of the input list 114> list1orig := DEEP_COPY_OBJ(sortedlist); 115> for i in [1..maxval] do 116> list1orig[i] := sortedlist[i^perm]; 117> od; 118> list1 := DEEP_COPY_OBJ(list1orig); 119> list2 := List([1..maxval], x -> Random(1, 100)); 120> listcpy := List(list2); 121> SortParallel(list1, list2); 122> if ForAny([1..maxval], x -> list2[x^perm] <> listcpy[x]) then 123> Print("failed SortParallel 1", perm, maxval, list2); 124> fi; 125> list1 := DEEP_COPY_OBJ(list1orig); 126> listcpy := List(list2); 127> SortParallel(list1, list2, function (a,b) return a <= b; end); 128> if ForAny([1..maxval], x -> list2[x^perm] <> listcpy[x]) then 129> Print("failed SortParallel 2", perm, maxval, list2); 130> fi; 131> end;; 132gap> for i in [0..100] do 133> for j in [0..10] do 134> CheckSortParallel([1..i],Random(SymmetricGroup([1..i])), i); 135> od; 136> od; 137 138# Just sanity check I really am making string reps 139gap> IsStringRep(lowAlpha{[1..0]}) and IsStringRep(lowAlpha{[1..10]}); 140true 141gap> for i in [0..26] do 142> for j in [0..10] do 143> CheckSortParallel(lowAlpha{[1..i]},Random(SymmetricGroup([1..i])), i); 144> od; 145> od; 146gap> # Pass two lists, where reverse-ordering x orders y 147gap> ParallelFilterCheckInner := function(x,y, strict, sorter) 148> sorter(x, y); 149> if not(IsSortedList(x) and IsSSortedList(x)=strict and 150> not(IsSortedList(y)) and not(IsSSortedList(y)) ) then 151> Print("ParFilter1 fail", x, y, strict); 152> fi; 153> sorter(x, y, function(x,y) return x > y; end); 154> if not(IsSortedList(y) and IsSSortedList(y)=strict and 155> not(IsSortedList(x)) and not(IsSSortedList(x)) ) then 156> Print("ParFilter2 fail", x, y, strict); 157> fi; 158> sorter(x, y, function(x,y) return x < y; end); 159> if not(IsSortedList(x) and IsSSortedList(x)=strict and 160> not(IsSortedList(y)) and not(IsSSortedList(y)) ) then 161> Print("ParFilter3 fail", x, y, strict); 162> fi; 163> sorter(x, y); 164> if not(IsSortedList(x) and IsSSortedList(x)=strict and 165> not(IsSortedList(y)) and not(IsSSortedList(y)) ) then 166> Print("ParFilter4 fail", x, y, strict); 167> fi; 168> end;; 169gap> ParallelFilterCheck := function(x,y,strict) 170> ParallelFilterCheckInner(x,y,strict, SortParallel); 171> ParallelFilterCheckInner(x,y,strict, StableSortParallel); 172> end;; 173gap> x := [1..10];; 174gap> y := [10,9..1];; 175gap> ParallelFilterCheck(x, y, true); 176gap> x := [1,1,1,2,2,2];; 177gap> y := [2,2,2,1,1,1];; 178gap> ParallelFilterCheck(x, y, false); 179gap> x := "abcdef";; 180gap> y := Reversed(x);; 181gap> ParallelFilterCheck(x, y, true); 182gap> y := [6,5..1];; 183gap> ParallelFilterCheck(x, y, true); 184gap> x := "aabbccddeeff";; 185gap> y := Reversed(x);; 186gap> ParallelFilterCheck(x, y, false); 187gap> y := [6,6,5,5,4,4,3,3,2,2,1,1];; 188gap> ParallelFilterCheck(x, y, false); 189gap> STOP_TEST("sort.tst", 1); 190