//STRING TO ARRAY
function split(S) {
    let i = 0;
    let result = [];
    
    while(char_at(S, i) !== undefined){
        result[i] = char_at(S,i);
        i = i + 1;
    }
    
    return result;
}

//String to stream:
// your helper functions go here
function split(s) {
    let i = 0;
    let result = [];
    
    while(char_at(s, i) !== undefined){
        result[i] = char_at(s,i);
        i = i + 1;
    }
    
    return result;
}

//Alternatively:
//ARRAYS TO LIST AND LISTS TO ARRAYS
function array_to_list(arr){
    let res = null;
    const len = array_length(arr);
    for (let i = 1; i <= len; i = i + 1){
        res = pair(arr[len - i], res);
    }
    return res;
}

function string_to_list (s){
        const new_list = array_to_list(split(s));
        return new_list;
    }
function list_to_stream(lst){
        return is_null(lst)
               ? null 
               : pair(head(lst), ()=> list_to_stream(tail(lst)));
    }
function char_stream(s) {
    return list_to_stream(string_to_list(s));
}

//Searching 2 arrays for matching elements
function contains(B, A_i) {
    const len = array_length(B);
    
    for (let j = 0; j < len; j = j + 1){
    if (B[j] === A_i){
        return true;
      }
    }
    return false;
}

function num_characters_from(A, B) {
    let result = 0;
    for (let i = 0; i < array_length(A); i = i + 1){
        if (contains(B, A[i])){
            result = result + 1;
        }
    }
    return result;
}

//ARRAYS TO LIST AND LISTS TO ARRAYS
function runlength_decode(R) {
    const RA = list_to_array(R);
    const res = [];
    for (let i = 0; i < array_length(RA); i = i + 1){
    if (is_number(RA[i])){
        res[array_length(res)] = RA[i];
    } else {
        //RA[i] is a pair
        const item = head(RA[i]);
        const quantity = tail(RA[i]);
        for (let j = 0; j < quantity; j = j + 1){
            res[array_length(res)] = item;
        }
      }
    }
    return array_to_list(res);
}

function list_to_array(xs){
    const res = [];
    let current_pair = xs;
    while (!is_null(current_pair)){
        res[array_length(res)] = head(current_pair);
        current_pair = tail(current_pair);
    }
    return res;
}

function array_to_list(arr){
    let res = null;
    const len = array_length(arr);
    for (let i = 1; i <= len; i = i + 1){
        res = pair(arr[len - i], res);
    }
    return res;
}






//SEARCHING
//1. Generalised Search
function search_cond(A, cond) {
    const len = array_length(A);
    
    for (let i = 0; i < len; i = i + 1){
        if (cond(A[i])){
            return i;
        } 
    }
    return -1;
}
/*
Approach:
1. Loop through each element of array
2. Check is predicate condition returns true
3. If true, return i of A[i]
4. If no element in loop returns true, then return -1 instead.

Other case: empty array --> -1
*/


//2. INSERTION
function insert(A, pos, x){
    let len = array_length(A);
    len = len + 1;
    for (let i = len - 2; i >= pos; i = i-1){
        A[i + 1] = A[i];
    }
    A[pos] = x;
}

/*
inputs: Array, position and element

Input validity: 
- Position needs to be within array length

output: function should return inserted array, with array length modified

code structure:
1. Expand array: increase length by 1 to make space
2. Shifting: Start from last element, shift each element one spot to the right 
   until you reach position, leaving an empty space at position
3. Insert x into empty space

Loop condition: i > = pos
*/

//3. Insertion Sort
function insertion_sort(A) {
    let sorted_array = [];
    let len = array_length(A);
    
    for ( let i = 0; i < len; i=i+1){
        let x = A[i];
        let pos = search_cond(sorted_array, y => y > x);
        
        if (pos === -1) {
            pos = array_length(sorted_array);
        }
        
        insert(sorted_array, pos, x);
    }
    
    return sorted_array;
}

/*
1. Create a new array: sorted_array
2. Iterate over elements of original array
3. Use search_cond to find validity to insert into sorterd_array
*/