Created
October 21, 2019 15:31
-
-
Save mhashim6/b26ddd219b024cf9b439a730ec9dabff to your computer and use it in GitHub Desktop.
Revisions
-
mhashim6 created this gist
Oct 21, 2019 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,213 @@ import struct import heapq import tkinter import itertools ###################################################################### # A function that mimics "enumerated datatypes" ###################################################################### def enum(*args): enums = dict(zip(args, range(len(args)))) return type('Enum', (), enums) ###################################################################### # A FIFO queue to keep track of the nodes at the frontier # Public functions: add, pop, isEmpty, find, size ###################################################################### class FifoQueue: # Initialize the queue def __init__(self): self.front = 0 self.back = 0 self.data = {} # Add an element at the back def add(self, value): self.data[self.back] = value self.back += 1 # Remove the element at the front def pop(self): value = self.data[self.front] del self.data[self.front] self.front += 1 return value # Check whether the queue is empty def isEmpty(self): return self.back==self.front # Find an element that satisfies a given criterion # i.e., return an element "e" where "f(e)" is true def find(self, predicate): for v in self.data.values(): if predicate(v): return True return False # Get the size of the queue def size(self): return len(self.data) ###################################################################### # A LIFO queue (stack) keeping track of the nodes at the frontier # Public functions: add, pop, isEmpty, find, size ###################################################################### class LifoQueue: # Initialize the stack def __init__(self): self.top = 0 self.data = {} # Push an element to the stack def add(self, value): self.data[self.top] = value self.top += 1 # Pop an element from the stack def pop(self): self.top -= 1 value = self.data[self.top] del self.data[self.top] return value # Check whether the stack is empty def isEmpty(self): return self.top==0 # Find an element that satisfies a given criterion # i.e., return an element "e" where "f(e)" is true def find(self, predicate): for v in self.data.values(): if predicate(v): return True return False # Get the size of the stack def size(self): return len(self.data) ###################################################################### # A priority queue keeping track of the nodes at the frontier # Public functions: add, remove, pop, isEmpty, find, size ###################################################################### class PriorityQueue: # Initialize the queue def __init__(self): self.pq = [] # list of entries arranged in a heap self.entry_finder = {} # mapping of tasks to entries self.REMOVED = '<removed-task>' # placeholder for a removed task self.counter = itertools.count()# unique sequence count # Add a new element or update the priority of an existing element def add(self,task, priority=0): if task in self.entry_finder: self.remove(task) count = next(self.counter) entry = [priority, count, task] self.entry_finder[task] = entry heapq.heappush(self.pq, entry) # Mark an element as REMOVED. Raise KeyError if not found def remove(self, task): entry = self.entry_finder.pop(task) entry[-1] = self.REMOVED # Remove and return the lowest priority element. Raise KeyError if empty def pop(self): while self.pq: priority, count, task = heapq.heappop(self.pq) if task is not self.REMOVED: del self.entry_finder[task] return task raise KeyError('pop from an empty priority queue') # Check whether the queue is empty def isEmpty(self): return self.entry_finder=={} # Find an element that satisfies a given criterion # i.e., return an element "e" where "f(e)" is true def find(self,f): for task in self.entry_finder: if f(task): return task return None def contains(self, e): return e in self.pq # Get the size of the queue def size(self): return len(self.entry_finder) ###################################################################### # A data structure to capture the set of explored states # Public functions: add, contains, isEmpty, size ###################################################################### class Set: # Initialize the set def __init__(self): self.elements = set() # Add an element to the set def add(self,element): self.elements.add(element) def find(self, f): for task in self.entry_finder: if f(task): return task return None # Find an element in the set def contains(self,element): return element in self.elements # Get the size of the set def size(self): return len(self.elements) ###################################################################### # A class for drawing objects (line, rectangle, ...) # Public functions: display, line, rectangle ###################################################################### class Window: # Initialize the graphics environment and create a window def __init__(self,title,s,h,w,rgb): (x,y) = s h *= 1.5 w *= 1.5 x *= 1.5 y *= 1.5 self.root = tkinter.Tk() self.root.title(title) self.root.geometry("%d"%(w+2*x)+"x"+"%d"%(h+2*y)) self.canvas = tkinter.Canvas(self.root, height=h+2*y, width=w+2*x) self.rectangle((x/1.5,y/1.5),h/1.5,w/1.5,rgb) # Display the drawings def display(self): # Display TK self.canvas.pack() self.root.mainloop() # Draw a line def line(self,s1,s2): (x1,y1) = s1 (x2,y2) = s2 x1 *= 1.5 y1 *= 1.5 x2 *= 1.5 y2 *= 1.5 self.canvas.create_line(x1,y1,x2,y2,fill="#000000") # Draw a rectangle def rectangle(self,s,h,w,rgb): (x,y) = s x *= 1.5 y *= 1.5 h *= 1.5 w *= 1.5 self.canvas.create_polygon(x,y,x+w,y,x+w,y+h,x,y+h,\ fill=rgb,outline="#000000")