'''
20211021

Robin Dawes

Display a tkinter animation of binary search

'''
import tkinter as tk

import random

window = tk.Tk()
window.geometry("1800x800")
window.title("Binary Search Demonstration")

delay = 2400               # time in milliseconds between moves



 
values = sorted(list(random.sample(range(1,100),15)))

value_labels = []

mid_marker_labels = []

def build_axes():
   '''The display of the values is done with the grid() placement.  The
      rows and columns of the display are established with the Labels defined here.  
   '''
   for i in range(12):
      blank_label = tk.Label(window, text = "       ", font = (None, 20))
      blank_label.grid(row = i, column = 0)
   for p in range(len(values)):
      p_label = tk.Label(window, text = "    "+str(p)+"    ", font = (None, 22), bg = "black", fg = "white", width = 5, border = 1)
      p_label.grid(row = 2, column = p + 1)
      

   
def display_values():  
   '''Show the values in the positions that have not yet been eliminated
      from the search
   '''
   global value_labels      # we make this an assignable global variable so
                                         # that we can reset it with "value_labels = []"
   for vl in value_labels:
       vl.destroy()
   value_labels = []
   for v in range(len(values)): 
       if values[v] == None:
          text = "          "        # print a string of blanks instead of the value
       else:
          text = "    "+str(values[v])+"    "
       place = tk.Label(window, text = text , font = (None, 20))
       value_labels.append(place)
       place.grid(row = 4, column = v + 1)
       
      
def bin_search(a_list, target):
   '''Set up and initiate the recursive search'''
   return bin_search_rec(a_list, target, 0, len(a_list) - 1)
   
def bin_search_rec(a_list, target, first, last):
   '''Perform the recursive search.
      first and last are the indices that define the portion of the
      list to be searched.
   '''
   global mid_marker_labels
   if first > last:
      return -1
   else:
      mid = (first + last) // 2
      # delete everything in the row that displays "MID"
      for mml in mid_marker_labels:
         mml.destroy()
      # place "MID" on the appropriate label
      for i in range(len(a_list)):
         if i == mid:
            show_text = "MID"
         else:
            show_text = "       "     # this makes sure the previous "MID" is overwritten with blanks
         mml = tk.Label(window, text = show_text, font = (None, 20))
         mml.grid(row = 1, column = i+1)
      window.update()               # show the changes
      if a_list[mid] == target:
         window.after(delay)       # wait a bit
         display_values()             # put the values on the labels
         window.update()            # show the changes
         return mid
      elif a_list[mid] > target:
         for v in range(mid, last + 1):
            a_list[v] = None
         window.after(delay)
         display_values()
         window.update()
         return bin_search_rec(a_list, target, first, mid - 1)
      else:
         for v in range(first, mid + 1):
            a_list[v] = None
         window.after(delay)
         display_values()
         window.update()
         return bin_search_rec(a_list, target, mid + 1, last)

# randomly select one of the values in the list as the target 
target = values[random.randint(0,len(values) - 1)]
# use this line to randomly selet a target that may or may not be in the list
#target = random.randint(0,100)

l1 = tk.Label(window, text = "Target : ", font=(None, 20))
l1.grid(row = 8, column = 1, columnspan = 2)

l2 = tk.Label(window, text = str(target), font = (None, 20))
l2.grid(row = 8, column = 3)

build_axes()                  # create the axes
display_values()

window.update()            # update the screen
window.after(delay*2)   # wait a bit



posit = bin_search(values, target)     # this generates a lot of tkinter operations
                                                          
                                                          
# show the information about the success or failure of the search
if posit == -1:
   final_text = "Not found"
else:
   final_text = "Found " + str( target) + " in position " + str( posit)

l_final = tk.Label(window, text = final_text, font = (None, 20))
l_final.grid(row = 10, column = 1, columnspan = 3)     # columnspan centres the label across the width of several columns

window.mainloop()      # start mainloop - this keeps the final display on the screen