%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%      selection sort                   %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% min(L, Min).
% L is the list of numbers in which to find the min
% L must be provided
% Min is the minimum value of the provide list
% Min can be a variable.
min([Min], Min).
min([F|R], Min):- min(R, Min), Min < F.
min([F|R], F)  :- min(R, Min), Min > F.
min([F|R], F)  :- min(R, Min), Min = F.

% The following tests can be run by typing:
% run_tests(min)
:- begin_tests(min).
test(minT1) :- min([1, 2, 3], 1), !.
test(minT2) :- min([2, 1, 3], 1), !.
test(minT3) :- min([2, 3, 1], 1), !.
test(minT4) :- min([1, 1, 1], 1), !.
test(minT5) :- \+min([], _).
:- end_tests(min).

% remove(Item, ListBefore, ListAfter)
% Item is the item to be removed from ListBefore
% Item must be provided
% ListBefore is the list that contains the Item
% ListBefore should be provided
% ListAfter is the same as ListBefore with
%      the 1st instance of Item removed.
remove(X, [X|R], R).
remove(X, [F|R], [F|R2]):-
  X \= F,
  remove(X, R, R2).

% The following tests can be run by typing:
% run_tests(remove)
:- begin_tests(remove).
test(removeT1) :- remove(1, [1, 2, 3], [2, 3]), !.
test(removeT2) :- remove(1, [2, 1, 3], [2, 3]), !.
test(removeT3) :- remove(1, [2, 3, 1], [2, 3]), !.
test(removeT4) :- remove(1, [1, 1, 1], [1, 1]), !.
test(removeT5) :- remove(1, [1], []), !.
test(removeT6) :- \+remove(_, [], _).
:- end_tests(remove).

% selectionSort(Unsorted, Sorted).
% Unsorted is a list to be sorted
% Unsorted must be provided
% Sorted is a sorted version of elements in Unsorted
% Sorted can be a variable

% TODO write selectionSort

% The following tests can be run by typing:
% run_tests(selectionSort)
:- begin_tests(selectionSort).
test(selectionSortT1) :- selectionSort([1, 2, 3], [1, 2, 3]), !.
test(selectionSortT2) :- selectionSort([2, 1, 3], [1, 2, 3]), !.
test(selectionSortT3) :- selectionSort([2, 3, 1], [1, 2, 3]), !.
test(selectionSortT4) :- selectionSort([1, 1, 1], [1, 1, 1]), !.
test(selectionSortT5) :- selectionSort([1], [1]), !.
test(selectionSortT7) :- \+selectionSort([], [_|_]).
:- end_tests(selectionSort).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%      insertion sort             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% insert(Element, SortedList, SortedWithElement).
% Element is the item to add to the SortedList.
% Element should be provided.
% SortedList is a list of numbers in sorted order
% SortedList should be provided
% SortedWithElement is a sorted list of numbers
% SortedWithElement includes all items from SortedList
% SortedWithElement also includes Element.
insert(X, [], [X]).
insert(X, [F|R],  [X, F|R] ):- F >= X.
insert(X, [F|R],  [F|R2]) :- X > F, insert(X, R, R2).

% The following tests can be run by typing:
% run_tests(insert)
:- begin_tests(insert).
test(insertT1) :- insert(1, [2, 3], [1, 2, 3]), !.
test(insertT2) :- insert(2, [1, 3], [1, 2, 3]), !.
test(insertT3) :- insert(3, [1, 2], [1, 2, 3]), !.
test(insertT4) :- insert(1, [1, 1], [1, 1, 1]), !.
test(insertT5) :- insert(1, [], [1]), !.
test(insertT6) :- \+insert(_, _, []).
:- end_tests(insert).

%insertionSort(Unsorted, Sorted)
% Unsorted is a list to be sorted
% Unsorted must be provided
% Sorted is a sorted version of elements in Unsorted
% Sorted can be a variable

% TODO write insertionSort

% The following tests can be run by typing:
% run_tests(insertionSort)
:- begin_tests(insertionSort).
test(insertionSortT1) :- insertionSort([1, 2, 3], [1, 2, 3]), !.
test(insertionSortT2) :- insertionSort([2, 1, 3], [1, 2, 3]), !.
test(insertionSortT3) :- insertionSort([2, 3, 1], [1, 2, 3]), !.
test(insertionSortT4) :- insertionSort([1, 1, 1], [1, 1, 1]), !.
test(insertionSortT5) :- insertionSort([1], [1]), !.
:- end_tests(insertionSort).