%% From the end of lecture yesterday, here is the solution:

/*  [+,+,-]   
  remove(Itm,L,L1): L1 = L, but L1 has one copy of Itm removed.
    (Note that Itm *must* occur in L, to satisfy this.)
*/
remove(Target, [Target|L1], L1).
remove(Target, [F|L1], [F|L2]) :- remove(Target,L1,L2).



%%%%%%%%%%%%%%
% Sorting:
% We'll just provide the 'spec' for sorting:
% L2 is a sorted version of L1 if:
%  - L2 is in ascending order (er, non-decreasing).
%  - L1 is a permutation (re-arrangement) of L2, and

scrapSort(L1,L2) :- permutation(L1,L2), nondecreasing(L2).
 

% Here're the helper functions:
%
nondecreasing([]).
nondecreasing([_]).
nondecreasing([F,S|R]) :- F=<S, nondecreasing([S|R]).

/* permutation(L1,L2): L2 is a permutation of L1 */
permutation([],[]).
permutation(X,[F|R]) :- remove(F,X,Z), permutation(Z,R).
%
% `permutation` is actually kinda tricky to come up with.
% A couple of false-starts (and explanations) are at:
%   http://www.radford.edu/~itec380/2009fall-ibarland/Lectures/lect12c.P



% Reflecting on scrapSort:
%   Consider the *order* of solutions when we try:
%   permutation([3,4,5],X).
%   permutation([5,4,3],X).
% How *many* permutations does scrapSort([3,4,5],X) look at?
% How about scrapSort([5,4,3],X) ?
%
% Now, consider this problem amplified:
%     scrapSort([8,7,6,5,4,3,2,1],X).  runs okay. But
% But scrapSort([10,9,8,7,6,5,4,3,2,1],X).  takes a moment (~2.5s).
%     scrapSort([11,10,9,8,7,6,5,4,3,2,1],X).  takes too long (~27s).
% 
%
% The name "scrapSort" was chosen because its performance
% is a piece of scrap: O(n!).






% Ironically, 'quicksort' is more straightforward than 'scrapsort',
% even though we specify *how* to sort rather than *what sorted means*.
%

qsort([],[]).
qsort([F|R],L2) :- partition([F|R],F,Sm,Eq,Bg), 
                   qsort(Sm,SmSorted), 
                   qsort(Bg,BgSorted), 
                   append3(SmSorted,Eq,BgSorted,L2).

/* [+,+,-,-,-]
   partition(Lst,Pivot,Smalls,Equals,Larges) :
   partition Lst into those elements that are smaller, equal-to, and larger than Pivot.
   */
partition([],_,[],[],[]).
partition([F|R],Pivot,Smallers,Equals,Biggers) :- 
  F<Pivot,
  Smallers = [F|SmallerRest],
  partition(R,Pivot,SmallerRest,Equals,Biggers).
partition([F|R],Pivot,Smallers,Equals,Biggers) :- 
  F=Pivot, 
  Equals = [F|EqualRest],
  partition(R,Pivot,Smaller,EqualRest,Biggers).
partition([F|R],Pivot,Smallers,Equals,Biggers) :- 
  F>Pivot, 
  Biggers = [F|BiggerRest],
  partition(R,Pivot,Smallers,Equals,BiggerRest).

/* N.B. You can remove the '=' terms from the above lines,
   reducing the code by 4 lines.  Left in for clarity (?).
  */

% Note that we partition into *three* sections,
% so that we always *reduce* the size of a partition
% (even if our pivot is the maximum value).
% Study the sol'n above, to see how the Prolog
% makes sure we always recur on smaller lists (even
% when the pivot is the maximum (or minimum) value.






/* appendThree(L1,L2,L3,All) : All is the elements of L1 appended to L2 appended to L3. */
appendThree(L1,L2,L3,All) :- append(L1,L2,L1and2), append(L1and2,L3,All).

/* The following is the same as the append/3 included with [basics]. */
append([],L2,L2).
append([F|R],L2,[F|AllRest]) :- append(R,L2,AllRest).