Random week 5 stuff

class hash_table:
    def __init__(self,size):
        self.data = [None for i in range (size)]
        self.size = size
        self.num_items = 0

    def resize(self):
        temp = hash_table(self.size*2)
        for i in self.data:
            if i is not None:
                temp.insert(i)
        self.data = temp.data
        self.size = temp.size

    def insert(self,input):
        if self.num_items / self.size > 0.5:
            self.resize()
        hashed_location = self.hash(input)
        if self.data[hashed_location] is None: #if the location is empty, insert there
            self.data[hashed_location] = input
            self.num_items +=1
        else:
            starting_point = hashed_location+1
            end_point = self.size
            found = self.find_replace_empty(input,starting_point,end_point) #otherwise, go from that point to the end of the list looking for an empty slot
            if not found:
                starting_point = 0
                end_point = hashed_location
                found = self.find_replace_empty(input,starting_point,hashed_location) #if there is still no more empty slots, start from the beginning of the list
            if not found:
                raise Exception("Something went wrong my dude") #oh fuck the list is full

    def find_replace_empty(self,input,lower,upper):
        found = False
        i = lower
        while i < upper and not found:
            if self.data[i] is None:
                self.data[i] = input
                self.num_items += 1
                found = True
            i += 1
        return found

    def __contains__(self, item):
        return self.search(item)

    def delete(self, item): #note that the special case if this were chained is that you would need to shift items on the chain if one got deleted anywhere but the end
        item_location = self.get_loc(item)
        if item_location is not False:
            self.data[item_location] = None


    def get_loc(self,input):
        if self.data[self.hash(input)] is None:
            return False
        elif self.data[self.hash(input)] == input:
            return self.hash(input)
        else:
            found = False
            i = self.hash(input)+1
            while not found and i < self.size: #fringe case, refactor?
                if self.data[i] is None:
                    return False
                elif self.data[i] == input:
                    return i
                i += 1
            i = 0
            while not found and i < self.hash(input): #fringe case, refactor?
                if self.data[i] is None:
                    return False
                elif self.data[i] == input:
                    return i
                i += 1
            raise Exception("Oh fuck somehow the hash table is full")

    def search(self,input):
        if self.data[self.hash(input)] is None:
            return False
        elif self.data[self.hash(input)] == input:
            return True
        else:
            found = False
            i = self.hash(input)+1
            while not found and i < self.size: #fringe case, refactor?
                if self.data[i] is None:
                    return False
                elif self.data[i] == input:
                    return True
                i += 1
            i = 0
            while not found and i < self.hash(input): #fringe case, refactor?
                if self.data[i] is None:
                    return False
                elif self.data[i] == input:
                    return True
                i += 1
            raise Exception("Oh fuck somehow the hash table is full")

    def hash(self,input):
        nums = [ord(char) for char in input]
        result = 0
        for i in range(len(nums)):
            result += (i+1) * nums[i]
        return result % self.size
        return 4

x = hash_table(20)
for i in range(15):
    x.insert("penis")
print(x.data)
print(x.size)


import random
import time
#print(random.sample(range(1000),5))

def binary_prototype(a_list,item):
    return binary_search_recursive(a_list,item,0,len(a_list)-1)

def binary_search_recursive(a_list,item,start,end):
    midpoint = start + (end - start) // 2
    if a_list[midpoint] == item:
        return True
    if end - start == 0:
        return False
    if a_list[midpoint] > item:
        return binary_search_recursive(a_list,item,start,midpoint-1)
    if a_list[midpoint] < item:
       return binary_search_recursive(a_list,item,midpoint+1,end)


start_time = time.time()
x = [i for i in range(10000000)]
print(binary_prototype(x,102))
print("Time to run binary search recursive no slice = ", time.time()-start_time)

#15 and 16 todo...