// Do not remove or rename the package
package lists

/*
* The following functions are helper functions that I am providing
*/

/*
* Extend the List class with a "tail" getter to get the tail of a list.
* Below is an example of how you would use tail
*    val a = listOf(1,2,3)
*    val t = a.tail
*    println("tail of $a is $t") // prints [2,3]
*/
val <T> List<T>.tail: List<T>
get() = drop(1)

/*
* Extend the List class with a "head" getter to get the head of a list.
* Below is an example of how you would use head
*    val a = listOf(1,2,3)
*    val h = a.head
*    println("head of $a is $h") // prints 1
*/
val <T> List<T>.head: T
get() = first()

/* 
* The isPrime function takes as input an Int
*      x : an Int object to test
* and returns a Boolean
*      true  if x is a prime
*      false if x is not a prime
*/
fun isPrime(x : Int) : Boolean {
    if (x == 1)
        return false
    for (i in 2..(x-1)) {
        if (x % i == 0) {
            return false
        }    
    }
    return true
}

/* The compose function takes as input
*     f - A function that takes as input a value of type T and returns a value of type T
*     g - A function that takes as input a value of type T and returns a value of type T
*  and returns as output the composition of the functions
*     f(g(x))
*/
fun<T> compose(f: (T)->T,  g:(T) -> T) : (T) -> T = { f(g(it)) }

/* Be sure to document 
   your functions
   describing inputs and outputs and what the function does
 */

/**
 * @param limit is the upper bound of the list of natural numbers
 * @return a list of natural numbers up to limit
 */
fun countingNumbers(limit : Int?) : List<Int>? {
    if (limit == null)
        return null
    return (1..limit).map { it }
}

/**
 * @param limit is the upper bound of the list of even numbers
 * @return a list of even numbers up to limit
 */
fun evenNumbers(limit : Int?) : List<Int>? {
    return countingNumbers(limit)?.filter( { it % 2 == 0 } )
}

/**
 * @param limit is the upper bound of the list of prime numbers
 * @return a list of prime numbers up to limit
 */
fun primeNumbers(limit : Int?) : List<Int>? {
    return countingNumbers(limit)?.filter( { isPrime(it) } )
}

/**
 * @param a is a null-safe list of elements of "Comparable" items
 * @param b is a null-safe list of elements of "Comparable" items
 * @return a sorted merge list of the elements of a and b
 */
fun<T: Comparable<T>> merge(a: List<T>?, b: List<T>?) : List<T>? {
    if (a == null || b == null)
    	  return null
    
    val merged = mutableListOf<T>()

    var aInd = 0
    var bInd = 0

    while (aInd < a.size && bInd < b.size) {
        if (a[aInd] < b[bInd]) {
            merged.add(a[aInd]);
            aInd++;
            continue;
        }
        merged.add(b[bInd]);
        bInd++;        
    }    

    if (aInd < a.size)
        merged += a.subList(aInd, a.size)
    
    else if (bInd < b.size)
        merged += b.subList(bInd, b.size)
    
    return merged
}

/**
 * @param a is a null-safe list of elements
 * @return a list of "sublists" where result[i] = a[0..i]
 */
fun <T> subLists(a: List<T>?) : List<List<T>>? {
    if (a == null)
        return null
    return (1..(a.size)).map( { a.subList(0, it) } )
}

/**
 * @param a is a null-safe list of lists of elements
 * @return the number of elements total in each sublist
 */
fun countElements(a: List<List<Any>? >?) : Int? {
    if (a == null)
        return a    
    return a.filter({ it != null }).fold(0, { acc, x -> acc + x!!.size })
}

/**
 * @param a is a null-safe list of lists of elements
 * @return the number of elements total in each sublist
 */
fun <T> listApply(f: (T, T) -> T, a: List<List<T>>?): List<T>? {
    if (a == null)
        return null
    return a.map( { l: List<T> -> l.foldIndexed( l[0], { index, acc, arg -> if (index > 0) f(acc, arg) else arg } ) } );
}

/**
 * @param a is a list of functions
 * @return a function that the composition of the list of functions (from right to left)
 */
fun <T> composeList(a: List<(T) -> T>): (T) -> T {
    return a.foldRight({ x -> x }, { acc, f: (T) -> T -> { x -> f(acc(x)) } });
}