# -*- coding: utf-8 -*-
#argparse allows the parsing of command line arguments
import argparse
#utility functions for cs 6515 projects
import GA_ProjectUtils as util

"""

findX.py - Intro to Graduate Algorithms, Summer 2020

Solve the findX in an Infinite array problem using a Divide & Conqueor method
Your runtime must be O(log n)

The array of values is indexed A[1..n] inclusive

Your code MUST NOT directly reference any variables in findX.  The following methods are available:
    
    findX.start(seed) -- returns the value (x) to search for within the array
    findX.lookup(i) -- returns A[i] or None if i>n
    findX.lookups() -- returns the number of calls to lookup

""" 
def findXinA(x, findX):

    #TODO Your Code Begins Here, DO NOT MODIFY ANY CODE ABOVE THIS LINE

    theIndex = None # replace None with the index of x
    numLookups = 0

    def BinarySearch(x, l, r):
        while (l <= r):
            m = int(l + (r - l) / 2)
            temp = findX.lookup(m)
            if temp == None:
                r = m - 1
            else :
                if temp > x:
                    r = m - 1
                if temp < x:
                    l = m + 1
                if temp == x:
                    return m


    # base case
    if x == findX.lookup(0):
        theIndex = 0
        numLookups = 1

    #recursion
    i = 1
    #print(findX.lookup(24402))

    while findX.lookup(i)!= None:
        if findX.lookup(i) == x:
            theIndex = i
        else:
            i = i * 32
    theIndex = BinarySearch(x,0,i)

    #TODOne Your code Ends here, DO NOT MOIDFY ANYTHING BELOW THIS LINE

    numLookups = findX.lookups() #return the number of calls to findX.lookup()

    return theIndex, numLookups

def main():
    """
    main - DO NOT CHANGE ANYTHING BELOW THIS LINE
    """
    # DO NOT REMOVE ANY ARGUMENTS FROM THE ARGPARSER BELOW
    parser = argparse.ArgumentParser(description='Find X Coding Quiz')

    #args for autograder, DO NOT MODIFY ANY OF THESE
    parser.add_argument('-n', '--sName',  help='Student name, used for autograder', default='GT', dest='studentName')
    parser.add_argument('-a', '--autograde',  help='Autograder-called (2) or not (1=default)', type=int, choices=[1, 2], default=1, dest='autograde')
    parser.add_argument('-s', '--seed', help='seed value for random function', type=int, default=8, dest='seed')
    parser.add_argument('-l', '--nLower', help='lower bound for N', type=int, default=10, dest='nLower')
    parser.add_argument('-u', '--nUpper', help='upper bound for N', type=int, default=100000, dest='nUpper')

    args = parser.parse_args()

    #DO NOT MODIFY ANY OF THE FOLLOWING CODE

    findX = util.findX()
    x = findX.start(args.seed, args.nLower, args.nUpper) #initialize the problem space and return the value x
    index, calls = findXinA(x, findX)
    print('findX result: x found at index {} in {} calls'.format(index, calls))

    return

if __name__ == '__main__':
    main()