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