Checked in some new Tk demos that I wrote a while ago.

1 files changed, 634 insertions, 0 deletions

diff --git a/Demo/tkinter/guido/sortvisu.py b/Demo/tkinter/guido/sortvisu.py
new file mode 100644
index 0000000..6fe4002
--- /dev/null
+++ b/Demo/tkinter/guido/sortvisu.py
@@ -0,0 +1,634 @@
+#! /usr/bin/env python
+
+"""Sorting algorithms visualizer using Tkinter.
+
+This module is comprised of three ``components'':
+
+- an array visualizer with methods that implement basic sorting
+operations (compare, swap) as well as methods for ``annotating'' the
+sorting algorithm (e.g. to show the pivot element);
+
+- a number of sorting algorithms (currently quicksort, insertion sort,
+selection sort and bubble sort, as well as a randomization function),
+all using the array visualizer for its basic operations and with calls
+to its annotation methods;
+
+- and a ``driver'' class which can be used as a Grail applet or as a
+stand-alone application.
+
+"""
+
+
+from Tkinter import *
+from Canvas import Line, Rectangle
+import random
+
+
+XGRID = 10
+YGRID = 10
+WIDTH = 6
+
+
+class Array:
+
+    def __init__(self, master, data=None):
+	self.master = master
+	self.frame = Frame(self.master)
+	self.frame.pack(fill=X)
+	self.label = Label(self.frame)
+	self.label.pack()
+	self.canvas = Canvas(self.frame)
+	self.canvas.pack()
+	self.report = Label(self.frame)
+	self.report.pack()
+	self.left = Line(self.canvas, 0, 0, 0, 0)
+	self.right = Line(self.canvas, 0, 0, 0, 0)
+	self.pivot = Line(self.canvas, 0, 0, 0, 0)
+	self.items = []
+	self.size = self.maxvalue = 0
+	if data:
+	    self.setdata(data)
+
+    def setdata(self, data):
+	olditems = self.items
+	self.items = []
+	for item in olditems:
+	    item.delete()
+	self.size = len(data)
+	self.maxvalue = max(data)
+	self.canvas.config(width=(self.size+1)*XGRID,
+			   height=(self.maxvalue+1)*YGRID)
+	for i in range(self.size):
+	    self.items.append(ArrayItem(self, i, data[i]))
+	self.reset("Sort demo, size %d" % self.size)
+
+    speed = "normal"
+
+    def setspeed(self, speed):
+	self.speed = speed
+
+    def destroy(self):
+	self.frame.destroy()
+
+    in_mainloop = 0
+    stop_mainloop = 0
+
+    def cancel(self):
+	self.stop_mainloop = 1
+	if self.in_mainloop:
+	    self.master.quit()
+
+    def step(self):
+	if self.in_mainloop:
+	    self.master.quit()
+
+    Cancelled = "Array.Cancelled"	# Exception
+
+    def wait(self, msecs):
+	if self.speed == "fastest":
+	    msecs = 0
+	elif self.speed == "fast":
+	    msecs = msecs/10
+	elif self.speed == "single-step":
+	    msecs = 1000000000
+	if not self.stop_mainloop:
+	    self.master.update()
+	    id = self.master.after(msecs, self.master.quit)
+	    self.in_mainloop = 1
+	    self.master.mainloop()
+	    self.master.after_cancel(id)
+	    self.in_mainloop = 0
+	if self.stop_mainloop:
+	    self.stop_mainloop = 0
+	    self.message("Cancelled")
+	    raise Array.Cancelled
+
+    def getsize(self):
+	return self.size
+
+    def show_partition(self, first, last):
+	for i in range(self.size):
+	    item = self.items[i]
+	    if first <= i < last:
+		item.item.config(fill='red')
+	    else:
+		item.item.config(fill='orange')
+	self.hide_left_right_pivot()
+
+    def hide_partition(self):
+	for i in range(self.size):
+	    item = self.items[i]
+	    item.item.config(fill='red')
+	self.hide_left_right_pivot()
+
+    def show_left(self, left):
+	if not 0 <= left < self.size:
+	    self.hide_left()
+	    return
+	x1, y1, x2, y2 = self.items[left].position()
+##	top, bot = HIRO
+	self.left.coords([(x1-2, 0), (x1-2, 9999)])
+	self.master.update()
+
+    def show_right(self, right):
+	if not 0 <= right < self.size:
+	    self.hide_right()
+	    return
+	x1, y1, x2, y2 = self.items[right].position()
+	self.right.coords(((x2+2, 0), (x2+2, 9999)))
+	self.master.update()
+
+    def hide_left_right_pivot(self):
+	self.hide_left()
+	self.hide_right()
+	self.hide_pivot()
+
+    def hide_left(self):
+	self.left.coords(((0, 0), (0, 0)))
+
+    def hide_right(self):
+	self.right.coords(((0, 0), (0, 0)))
+
+    def show_pivot(self, pivot):
+	x1, y1, x2, y2 = self.items[pivot].position()
+	self.pivot.coords(((0, y1-2), (9999, y1-2)))
+
+    def hide_pivot(self):
+	self.pivot.coords(((0, 0), (0, 0)))
+
+    def swap(self, i, j):
+	if i == j: return
+	self.countswap()
+	item = self.items[i]
+	other = self.items[j]
+	self.items[i], self.items[j] = other, item
+	item.swapwith(other)
+
+    def compare(self, i, j):
+	self.countcompare()
+	item = self.items[i]
+	other = self.items[j]
+	return item.compareto(other)
+
+    def reset(self, msg):
+	self.ncompares = 0
+	self.nswaps = 0
+	self.message(msg)
+	self.updatereport()
+	self.hide_partition()
+
+    def message(self, msg):
+	self.label.config(text=msg)
+
+    def countswap(self):
+	self.nswaps = self.nswaps + 1
+	self.updatereport()
+
+    def countcompare(self):
+	self.ncompares = self.ncompares + 1
+	self.updatereport()
+
+    def updatereport(self):
+	text = "%d cmps, %d swaps" % (self.ncompares, self.nswaps)
+	self.report.config(text=text)
+
+
+class ArrayItem:
+
+    def __init__(self, array, index, value):
+	self.array = array
+	self.index = index
+	self.value = value
+	x1, y1, x2, y2 = self.position()
+	self.item = Rectangle(array.canvas, x1, y1, x2, y2,
+			      fill='red', outline='black', width=1)
+	self.item.bind('<Button-1>', self.mouse_down)
+	self.item.bind('<Button1-Motion>', self.mouse_move)
+	self.item.bind('<ButtonRelease-1>', self.mouse_up)
+
+    def delete(self):
+	item = self.item
+	self.array = None
+	self.item = None
+	item.delete()
+
+    def mouse_down(self, event):
+	self.lastx = event.x
+	self.lasty = event.y
+	self.origx = event.x
+	self.origy = event.y
+	self.item.tkraise()
+    	
+    def mouse_move(self, event):
+	self.item.move(event.x - self.lastx, event.y - self.lasty)
+	self.lastx = event.x
+	self.lasty = event.y
+
+    def mouse_up(self, event):
+	i = self.nearestindex(event.x)
+	if i >= self.array.getsize():
+	    i = self.array.getsize() - 1
+	if i < 0:
+	    i = 0
+	other = self.array.items[i]
+	here = self.index
+	self.array.items[here], self.array.items[i] = other, self
+	self.index = i
+	x1, y1, x2, y2 = self.position()
+	self.item.coords(((x1, y1), (x2, y2)))
+	other.setindex(here)
+
+    def setindex(self, index):
+	nsteps = steps(self.index, index)
+	if not nsteps: return
+	if self.array.speed == "fastest":
+	    nsteps = 0
+	oldpts = self.position()
+	self.index = index
+	newpts = self.position()
+	trajectory = interpolate(oldpts, newpts, nsteps)
+	self.item.tkraise()
+	for pts in trajectory:
+	    self.item.coords((pts[:2], pts[2:]))
+	    self.array.wait(50)
+
+    def swapwith(self, other):
+	nsteps = steps(self.index, other.index)
+	if not nsteps: return
+	if self.array.speed == "fastest":
+	    nsteps = 0
+	myoldpts = self.position()
+	otheroldpts = other.position()
+	self.index, other.index = other.index, self.index
+	mynewpts = self.position()
+	othernewpts = other.position()
+	myfill = self.item['fill']
+	otherfill = other.item['fill']
+	self.item.config(fill='green')
+	other.item.config(fill='yellow')
+	self.array.master.update()
+	if self.array.speed == "single-step":
+	    self.item.coords((mynewpts[:2], mynewpts[2:]))
+	    other.item.coords((othernewpts[:2], othernewpts[2:]))
+	    self.array.master.update()
+	    self.item.config(fill=myfill)
+	    other.item.config(fill=otherfill)
+	    self.array.wait(0)
+	    return
+	mytrajectory = interpolate(myoldpts, mynewpts, nsteps)
+	othertrajectory = interpolate(otheroldpts, othernewpts, nsteps)
+	if self.value > other.value:
+	    self.item.tkraise()
+	    other.item.tkraise()
+	else:
+	    other.item.tkraise()
+	    self.item.tkraise()
+	try:
+	    for i in range(len(mytrajectory)):
+		mypts = mytrajectory[i]
+		otherpts = othertrajectory[i]
+		self.item.coords((mypts[:2], mypts[2:]))
+		other.item.coords((otherpts[:2], otherpts[2:]))
+		self.array.wait(50)
+	finally:
+	    mypts = mytrajectory[-1]
+	    otherpts = othertrajectory[-1]
+	    self.item.coords((mypts[:2], mypts[2:]))
+	    other.item.coords((otherpts[:2], otherpts[2:]))
+	    self.item.config(fill=myfill)
+	    other.item.config(fill=otherfill)
+
+    def compareto(self, other):
+	myfill = self.item['fill']
+	otherfill = other.item['fill']
+	outcome = cmp(self.value, other.value)
+	if outcome < 0:
+	    myflash = 'white'
+	    otherflash = 'black'
+	elif outcome > 0:
+	    myflash = 'black'
+	    otherflash = 'white'
+	else:
+	    myflash = otherflash = 'grey'
+	try:
+	    self.item.config(fill=myflash)
+	    other.item.config(fill=otherflash)
+	    self.array.wait(500)
+	finally:
+	    self.item.config(fill=myfill)
+	    other.item.config(fill=otherfill)
+	return outcome
+
+    def position(self):
+	x1 = (self.index+1)*XGRID - WIDTH/2
+	x2 = x1+WIDTH
+	y2 = (self.array.maxvalue+1)*YGRID
+	y1 = y2 - (self.value)*YGRID
+	return x1, y1, x2, y2
+
+    def nearestindex(self, x):
+	return int(round(float(x)/XGRID)) - 1
+
+
+# Subroutines that don't need an object
+
+def steps(here, there):
+    nsteps = abs(here - there)
+    if nsteps <= 3:
+	nsteps = nsteps * 3
+    elif nsteps <= 5:
+	nsteps = nsteps * 2
+    elif nsteps > 10:
+	nsteps = 10
+    return nsteps
+
+def interpolate(oldpts, newpts, n):
+    if len(oldpts) != len(newpts):
+	raise ValueError, "can't interpolate arrays of different length"
+    pts = [0]*len(oldpts)
+    res = [tuple(oldpts)]
+    for i in range(1, n):
+	for k in range(len(pts)):
+	    pts[k] = oldpts[k] + (newpts[k] - oldpts[k])*i/n
+	res.append(tuple(pts))
+    res.append(tuple(newpts))
+    return res
+
+
+# Various (un)sorting algorithms
+
+def uniform(array):
+    size = array.getsize()
+    array.setdata([(size+1)/2] * size)
+    array.reset("Uniform data, size %d" % size)
+
+def distinct(array):
+    size = array.getsize()
+    array.setdata(range(1, size+1))
+    array.reset("Distinct data, size %d" % size)
+
+def randomize(array):
+    array.reset("Randomizing")
+    n = array.getsize()
+    for i in range(n):
+	j = random.randint(0, n-1)
+	array.swap(i, j)
+    array.message("Randomized")
+
+def insertionsort(array):
+    size = array.getsize()
+    array.reset("Insertion sort")
+    for i in range(1, size):
+	j = i-1
+	while j >= 0:
+	    if array.compare(j, j+1) <= 0:
+		break
+	    array.swap(j, j+1)
+	    j = j-1
+    array.message("Sorted")
+
+def selectionsort(array):
+    size = array.getsize()
+    array.reset("Selection sort")
+    try:
+	for i in range(size):
+	    array.show_partition(i, size)
+	    for j in range(i+1, size):
+		if array.compare(i, j) > 0:
+		    array.swap(i, j)
+	array.message("Sorted")
+    finally:
+	array.hide_partition()
+
+def bubblesort(array):
+    size = array.getsize()
+    array.reset("Bubble sort")
+    for i in range(size):
+	for j in range(1, size):
+	    if array.compare(j-1, j) > 0:
+		array.swap(j-1, j)
+    array.message("Sorted")
+
+def quicksort(array):
+    size = array.getsize()
+    array.reset("Quicksort")
+    try:
+	stack = [(0, size)]
+	while stack:
+	    first, last = stack[-1]
+	    del stack[-1]
+	    array.show_partition(first, last)
+	    if last-first < 5:
+		array.message("Insertion sort")
+		for i in range(first+1, last):
+		    j = i-1
+		    while j >= first:
+			if array.compare(j, j+1) <= 0:
+			    break
+			array.swap(j, j+1)
+			j = j-1
+		continue
+	    array.message("Choosing pivot")
+	    j, i, k = first, (first+last)/2, last-1
+	    if array.compare(k, i) < 0:
+		array.swap(k, i)
+	    if array.compare(k, j) < 0:
+		array.swap(k, j)
+	    if array.compare(j, i) < 0:
+		array.swap(j, i)
+	    pivot = j
+	    array.show_pivot(pivot)
+	    array.message("Pivot at left of partition")
+	    array.wait(1000)
+	    left = first
+	    right = last
+	    while 1:
+		array.message("Sweep right pointer")
+		right = right-1
+		array.show_right(right)
+		while right > first and array.compare(right, pivot) >= 0:
+		    right = right-1
+		    array.show_right(right)
+		array.message("Sweep left pointer")
+		left = left+1
+		array.show_left(left)
+		while left < last and array.compare(left, pivot) <= 0:
+		    left = left+1
+		    array.show_left(left)
+		if left > right:
+		    array.message("End of partition")
+		    break
+		array.message("Swap items")
+		array.swap(left, right)
+	    array.message("Swap pivot back")
+	    array.swap(pivot, right)
+	    n1 = right-first
+	    n2 = last-left
+	    if n1 > 1: stack.append((first, right))
+	    if n2 > 1: stack.append((left, last))
+	array.message("Sorted")
+    finally:
+	array.hide_partition()
+
+def demosort(array):
+    while 1:
+	for alg in [quicksort, insertionsort, selectionsort, bubblesort]:
+	    randomize(array)
+	    alg(array)
+
+
+# Sort demo class -- usable as a Grail applet
+
+class SortDemo:
+
+    def __init__(self, master, size=15):
+	self.master = master
+	self.size = size
+	self.busy = 0
+	self.array = Array(self.master)
+
+	self.botframe = Frame(master)
+	self.botframe.pack(side=BOTTOM)
+	self.botleftframe = Frame(self.botframe)
+	self.botleftframe.pack(side=LEFT, fill=Y)
+	self.botrightframe = Frame(self.botframe)
+	self.botrightframe.pack(side=RIGHT, fill=Y)
+
+	self.b_qsort = Button(self.botleftframe,
+			      text="Quicksort", command=self.c_qsort)
+	self.b_qsort.pack(fill=X)
+	self.b_isort = Button(self.botleftframe,
+			      text="Insertion sort", command=self.c_isort)
+	self.b_isort.pack(fill=X)
+	self.b_ssort = Button(self.botleftframe,
+			      text="Selection sort", command=self.c_ssort)
+	self.b_ssort.pack(fill=X)
+	self.b_bsort = Button(self.botleftframe,
+			      text="Bubble sort", command=self.c_bsort)
+	self.b_bsort.pack(fill=X)
+
+	# Terrible hack to overcome limitation of OptionMenu...
+	class MyIntVar(IntVar):
+	    def __init__(self, master, demo):
+		self.demo = demo
+		IntVar.__init__(self, master)
+	    def set(self, value):
+		IntVar.set(self, value)
+		if str(value) != '0':
+		    self.demo.resize(value)
+
+	self.v_size = MyIntVar(self.master, self)
+	self.v_size.set(size)
+	sizes = [1, 2, 3, 4] + range(5, 55, 5)
+	if self.size not in sizes:
+	    sizes.append(self.size)
+	    sizes.sort()
+	self.m_size = apply(OptionMenu,
+			    (self.botleftframe, self.v_size) + tuple(sizes))
+	self.m_size.pack(fill=X)
+	
+	self.v_speed = StringVar(self.master)
+	self.v_speed.set("normal")
+	self.m_speed = OptionMenu(self.botleftframe, self.v_speed,
+				  "single-step", "normal", "fast", "fastest")
+	self.m_speed.pack(fill=X)
+	
+	self.b_step = Button(self.botleftframe,
+			     text="Step", command=self.c_step)
+	self.b_step.pack(fill=X)
+	
+	self.b_randomize = Button(self.botrightframe,
+				  text="Randomize", command=self.c_randomize)
+	self.b_randomize.pack(fill=X)
+	self.b_uniform = Button(self.botrightframe,
+				  text="Uniform", command=self.c_uniform)
+	self.b_uniform.pack(fill=X)
+	self.b_distinct = Button(self.botrightframe,
+				  text="Distinct", command=self.c_distinct)
+	self.b_distinct.pack(fill=X)
+	self.b_demo = Button(self.botrightframe,
+			     text="Demo", command=self.c_demo)
+	self.b_demo.pack(fill=X)
+ 	self.b_cancel = Button(self.botrightframe,
+			       text="Cancel", command=self.c_cancel)
+ 	self.b_cancel.pack(fill=X)
+	self.b_cancel.config(state=DISABLED)
+	self.b_quit = Button(self.botrightframe,
+			     text="Quit", command=self.c_quit)
+	self.b_quit.pack(fill=X)
+
+    def resize(self, newsize):
+	if self.busy:
+	    self.master.bell()
+	    return
+	self.size = newsize
+	self.array.setdata(range(1, self.size+1))
+
+    def c_qsort(self):
+	self.run(quicksort)
+
+    def c_isort(self):
+	self.run(insertionsort)
+
+    def c_ssort(self):
+	self.run(selectionsort)
+
+    def c_bsort(self):
+	self.run(bubblesort)
+
+    def c_demo(self):
+	self.run(demosort)
+
+    def c_randomize(self):
+	self.run(randomize)
+
+    def c_uniform(self):
+	self.run(uniform)
+
+    def c_distinct(self):
+	self.run(distinct)
+
+    def run(self, func):
+	if self.busy:
+	    self.master.bell()
+	    return
+	self.busy = 1
+	self.array.setspeed(self.v_speed.get())
+	self.b_cancel.config(state=NORMAL)
+	try:
+	    func(self.array)
+	except Array.Cancelled:
+	    pass
+	self.b_cancel.config(state=DISABLED)
+	self.busy = 0
+
+    def c_cancel(self):
+	if not self.busy:
+	    self.master.bell()
+	    return
+	self.array.cancel()
+
+    def c_step(self):
+	if not self.busy:
+	    self.master.bell()
+	    return
+	self.v_speed.set("single-step")
+	self.array.setspeed("single-step")
+	self.array.step()
+
+    def c_quit(self):
+	if self.busy:
+	    self.array.cancel()
+	self.master.after_idle(self.master.quit)
+
+
+# Main program -- for stand-alone operation outside Grail
+
+def main():
+    root = Tk()
+    demo = SortDemo(root)
+    root.protocol('WM_DELETE_WINDOW', demo.c_quit)
+    root.mainloop()
+
+if __name__ == '__main__':
+    main()