from copy import *

#Rekursiv sortering

def sort(aList):
    '''sorts a list by means of recursion'''
    if len(aList) <= 1:
        #base case
        return aList
    else:
        #find the index of the smallest element of the list
        index = listIndexOfMin(aList)
        #recursive case
        sortedRest = concatente(aList[index],sort(remove(index,copy(aList))))
        #dump variables
        print str(aList[index]) + '+ sort:' + str(remove(index,copy(aList)))
        print 'Sorted rest: ' + str(sortedRest)
        return sortedRest

def listIndexOfMin(A):
    '''returns the index of the smallest element of A'''
    if A == []:
        print 'empty list'
        return -1
    n = len(A)-1
    i = 0
    currentMin = A[0]
    currentIndex = 0
    while i <= n:
        if currentMin > A[i]:
            currentMin = A[i]
            currentIndex = i
        i = i+1
    return currentIndex

def remove(index,aList):
    '''removes the ith element of a list'''
    del aList[index]
    return aList

def concatente(anElement,aList):
    '''concatenates an element to a list'''
    return [anElement]+ aList

#Fremfinding af største element i liste

def listMax(A,n):
    '''returns the largest element of the list A'''
    i = 0
    currentMax = A[i]
    while i <= n:
        if currentMax < A[i]:
            currentMax = A[i]
        i = i+1
    return currentMax

    

#Binær søgning i sorteret liste

def binSearch(x, nums):
    '''returns the index of x in nums of x is there, else -1'''
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = (low + high)/2
        item = nums[mid]
        #dump variables
        print nums, 'low:',low, 'mid:',mid, 'item:',item, 'high:',high
        if x == item:
            return mid
        elif x < item:
            high = mid - 1
        else:
            low = mid + 1
    return -1

def binSearchStart(x, nums):
    '''starts the recursive process with binSearchRec'''
    print 'binary recursive search after ' + str(x) + ' in ' + str(nums)
    return binSearchRec(x, nums, 0,len(nums)-1)
    
    
def binSearchRec(x, nums,low,high):
    '''returns the index of x in nums of x is there, else -1
    Resursive solution'''
    if low <= high:
        mid = (low + high)/2
        item = nums[mid]
        if x == item: #base case
            return mid
        elif x < item: #recursive case
            return binSearchRec(x, nums, low, mid - 1 )
        else: #recursive case
            return binSearchRec(x, nums, mid+1, high)
    else: #base case
        return -1


#Bankkonto

class Konto:
    '''represents a bank account'''
    def __init__(self,navn, indestaaende, rentesats):
        self.navn = navn
        self.indestaaende = indestaaende
        self.rentesats = rentesats

    def indsaet(self,beloeb):
        self.indestaaende += beloeb

    def haev(self,beloeb):
        self.indestaaende -= beloeb

    def tilSkrivRenter(self):
        self.indestaaende += self.indestaaende * self.rentesats/100

    def udSkrivSaldo(self):
        print 'Saldo for ' + self.navn
        print self.indestaaende


if __name__ ==  '__main__':
    print 'listMax'
    X = [1,4,3,5,7,9,10]
    print listMax(X,len(X)-1)
    print
    print 'binSearch 12'
    aList = [1,2,5,7,10, 12, 67, 100, 101,373]
    print binSearch(12,aList)
    print 'binSearch 234'
    print binSearch(234,aList)
    print
    print binSearchStart(12,aList)
    print
    print binSearchStart(234,aList)
    print
    print binSearchStart(373,aList)
    print
    print 'sorting [3,6,3,77,2,7,66,777]:'
    print sort([3,6,3,77,2,7,66,777])
    print
    print 'konto eksempel'

    minKonto = Konto('Peter Bøgh Andersen',1000,5)
    minKonto.udSkrivSaldo()
    print 'Indsæt penge'
    minKonto.indsaet(200)
    minKonto.udSkrivSaldo()
    print 'Hæv penge'
    minKonto.haev(100)
    minKonto.udSkrivSaldo()
    print 'Tilskriv renter'
    minKonto.tilSkrivRenter()
    minKonto.udSkrivSaldo()