sortvisu.py

reduced python source for embedded apps

	    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()