import java.util.ArrayList;
import java.util.Random;


/**
 * Using recursion over arrays
 * Soemtimes this is a good idea. Usually it involves private recursive functions
 * to hold the array index. 
 * 
 * @author gtowell
 * Created: August 11, 2021
 */
public class RArray {

    /**
     * Make an array with increasing elements but the gaps are random
     * @param size the size of the array to make
     * @param maxgap the max space between successive items int he array
     * @return the array
     */
    public ArrayList<Integer> makeIncrArray(int size, int maxgap) {
        return makeIncrArrayUtil(size, maxgap, 0, new Random());
    }

/**
 * The private recursive fun that actually does the work
 * @param arr the array to be filled
 * @param maxgap the max space between items
 * @param loc the location of the item being worked (the loop index)
 * @param r a random number generator
 * @return the resulting array
 */
    private ArrayList<Integer> makeIncrArrayUtil(int size, int maxgap, int loc, Random r) {
        if (loc >= size)
            return new ArrayList<Integer>();
        ArrayList<Integer> ai = makeIncrArrayUtil(size, maxgap, loc + 1, r);
        if (ai.size()>0)
            ai.add(ai.get(ai.size() - 1) + r.nextInt(maxgap)+1);
        else
            ai.add(r.nextInt(maxgap));
        return ai;
    }


     /**
     * Find a number in an array of numbers
     * @param arr the array
     * @param num the number ot be found
     * @return the location in the array, or -1 if the number is not i the array
     */
    public int find(ArrayList<Integer> arr, int num, boolean useA) {
        if (useA)
            return findUtil(arr, num, 0);
        return findUtilB(arr, num, 0, arr.size()-1);
    }

    /**
     * Find be looking at each item.  The array may be in any order
     * @param arr the array to be searched
     * @param num the number to be found
     * @param loc the location to consider next
     * @return the location of num in arr, or -1 if not in arr
     */
    private int findUtil(ArrayList<Integer> arr, int num, int loc) {
        if (loc >= arr.size())
            return -1;
        if (arr.get(loc) == num)
            return loc;
        return findUtil(arr, num, loc + 1);
    }

    /**
     * An alternate version of finding number in an array
     * This version requires that the array be sorted
     * @param arr the arraylist - it must be sorted
     * @param num the number to be found
     * @param minPos the lowest position that the item to be found could be at
     * @param maxPos the highest possible location
     * @return the location, or -1 if not found
     */
    private int findUtilB(ArrayList<Integer> arr, int num, int minPos, int maxPos) {
        if (minPos > maxPos)
            return -1;
        int loc = (minPos + maxPos) / 2;
        if (arr.get(loc) == num)
            return loc;
        if (num > arr.get(loc))
            return findUtilB(arr, num, loc + 1, maxPos);
        else
            return findUtilB(arr, num, minPos, loc - 1);
    }


    public static void main(String[] args) {
        RArray rar = new RArray();
        ArrayList<Integer> rrr = rar.makeIncrArray(200, 2);
        System.out.println(rrr);
        System.out.println("The location of " + rrr.get(16) + " is " + rar.find(rrr, rrr.get(16), true));
        System.out.println("The location of " + 103 + " is " + rar.find(rrr, 103, true));
        System.out.println("The location of " + 103 + " is " + rar.find(rrr, 103, false));

    }
}