-

(* Alejandro Salvador Vega Nogales
	801-13-7956
	Prof. Koutis
	CCOM-4029 *)

open List;



(* 1. Functions takes a list l and an int n ; Outputs l where the indexes are offset by n places 
    wrapper functions saves on calculations by making sure the list doesn't wrap around unnecessary
    times. *)

 fun rotN(nil, n) = []
   | rotN(l, 0) = l
   | rotN(h::t, n:int) = if (n > 0) then 
   							rotN([last(t)]@rev(tl(rev(h::t))),n-1)
                         else
                         	rotN(t@[h], n+1);

fun rotWrap(l, n) = rotN(l, (n mod length(l)));

(* 2.) function that takes a list l and an int k and returns
	   a tuple of 2 lists. the first list is the list with the first k elements of l 
       and the second list is the one with the remaining elements *)

fun splitList(nil, k) = (nil, nil)
  | splitList(l, k) = (take (l, k), drop (l, k));


(* 3.) wrapper function takes a list l and a number k.
	   sends l, k, nil list, and the starting index(0) to the 
	   function that actually does the work(posRemove) this function just adds
	   elements to the second list if the index isn't divisible with k and if the index is 0
	   and at the end it outputs the second list*)

fun posRemove (nil, k, l, count) = l
	| posRemove (h::t, k, l, count) = 
		if (count = 0) then 
			posRemove (t, k, l@[h], count+1)
		else if (count mod k <> 0) then 
			posRemove (t, k, l@[h], count+1)
		else
			posRemove(t, k, l, count+1);

fun posReWrap (l, k:int) = posRemove(l, k, nil, 0);


(* 4.) *)

(*function that find the nth fibonacci number: *)

fun fib n =
  if n < 3 then
    1
  else
    fib (n-1) + fib (n-2);

(* function that finds x number of fibonacci numbers where x is the length of the list, 
	but if the next fibonacci number is larger than the length of the list the function stops and 
	returns the list it has built up to that point *)

fun nFibs (~1, l, len) = l
	| nFibs (n, nil, len) = nFibs(n+1, [fib(n)], len)
	| nFibs (n, l, len) =  
		if (fib(n+1) > len andalso n <> len) then 
			nFibs(~1, l, len)
		else
			nFibs(n + 1, l@[fib(n)], len);

(* check if a number is in a list. very unefficient since worse
case scenario is that it compares each element of a list of length n 
n times.
could be made more efficient with binary search since
the fibonaci list is sorted? *)

fun inList (x, nil, inL) = inL
	| inList(x, h::t, inL) =
		if (x = h) then
			inList(x, nil, true)
		else 
			inList(x, t, inL);

(* function that takes a list and returns the elements of the list whose index is not a 
	fibonacci number *)

fun remFibIndex(nil, fibList, l, count) = l
	| remFibIndex (h::t, fibList, l, count) = 
		if (inList(count, fibList, false) = false) then
			remFibIndex (t, fibList, l@[h], count + 1)
		else
			remFibIndex (t, fibList, l, count + 1);

(* wrapper function that just takes the list as specified and returns the list with elements
	whose original index wasn't a fibonaci number: *)

fun noFibIndex (l) = remFibIndex(l, nFibs(0, [], List.length(l)), [], 0);

(* 5 *)

(* a declaration of a datatype that is a binary tree that ONLY holds values at its leaves*)

datatype 'a binTree = Leaf of 'a 
	| Node of 'a binTree * 'a binTree;

(* b a function that takes all the elements in a binary tree of the 
     sames type as above and outputs the elements from left to right in a list *)

fun leafList (Leaf c) = [c]
	| leafList(Node(left, right)) = leafList(left)@leafList(right); 

(* c *)

(* a function that finds the rightestmost leaf of a tree *)

fun findRightest (Leaf c) = c
    | findRightest(Node(l, r)) = findRightest(r);

(* a function that takes an ordered binary tree and a number n and outputs
   an ordered binary tree that includes n 
   i.e a function that inserts an element into an already ordered binary tree *)

fun leafInsert(Node(l, r), n) = 
                                if (findRightest(l) < n) then
                                    Node (l, leafInsert(r, n))
                                else
                                    Node(leafInsert(l, n), r)
    | leafInsert(Leaf c, n) = 
                            if (n > c) then 
                                Node(Leaf c, Leaf n)
                            else if (n < c) then 
                                Node(Leaf n, Leaf c)
                            else
                                Leaf n

(* d a function that takes a list and outputs an ordered version of the same list *)

fun whyDontYouMakeLikeATree(h::t, 1) = Leaf h  
    | whyDontYouMakeLikeATree(h::t, len) = leafInsert(whyDontYouMakeLikeATree(t, len - 1), h);

fun treeToList(l) = leafList(whyDontYouMakeLikeATree(l, length(l)));

(* not very happy with the implementation of c. very inefficient:

test out with this function as input for worst case scenario:

fun nSizeList (0, l) = l
    | nSizeList(n, l) = nSizeList(n - 1, l@[n]);
    
*)