1#! /usr/bin/env python
2
3"""Sorting algorithms visualizer using Tkinter.
4
5This module is comprised of three ``components'':
6
7- an array visualizer with methods that implement basic sorting
8operations (compare, swap) as well as methods for ``annotating'' the
9sorting algorithm (e.g. to show the pivot element);
10
11- a number of sorting algorithms (currently quicksort, insertion sort,
12selection sort and bubble sort, as well as a randomization function),
13all using the array visualizer for its basic operations and with calls
14to its annotation methods;
15
16- and a ``driver'' class which can be used as a Grail applet or as a
17stand-alone application.
18
19"""
20
21
22from Tkinter import *
23from Canvas import Line, Rectangle
24import random
25
26
27XGRID = 10
28YGRID = 10
29WIDTH = 6
30
31
32class Array:
33
34    def __init__(self, master, data=None):
35        self.master = master
36        self.frame = Frame(self.master)
37        self.frame.pack(fill=X)
38        self.label = Label(self.frame)
39        self.label.pack()
40        self.canvas = Canvas(self.frame)
41        self.canvas.pack()
42        self.report = Label(self.frame)
43        self.report.pack()
44        self.left = Line(self.canvas, 0, 0, 0, 0)
45        self.right = Line(self.canvas, 0, 0, 0, 0)
46        self.pivot = Line(self.canvas, 0, 0, 0, 0)
47        self.items = []
48        self.size = self.maxvalue = 0
49        if data:
50            self.setdata(data)
51
52    def setdata(self, data):
53        olditems = self.items
54        self.items = []
55        for item in olditems:
56            item.delete()
57        self.size = len(data)
58        self.maxvalue = max(data)
59        self.canvas.config(width=(self.size+1)*XGRID,
60                           height=(self.maxvalue+1)*YGRID)
61        for i in range(self.size):
62            self.items.append(ArrayItem(self, i, data[i]))
63        self.reset("Sort demo, size %d" % self.size)
64
65    speed = "normal"
66
67    def setspeed(self, speed):
68        self.speed = speed
69
70    def destroy(self):
71        self.frame.destroy()
72
73    in_mainloop = 0
74    stop_mainloop = 0
75
76    def cancel(self):
77        self.stop_mainloop = 1
78        if self.in_mainloop:
79            self.master.quit()
80
81    def step(self):
82        if self.in_mainloop:
83            self.master.quit()
84
85    Cancelled = "Array.Cancelled"       # Exception
86
87    def wait(self, msecs):
88        if self.speed == "fastest":
89            msecs = 0
90        elif self.speed == "fast":
91            msecs = msecs//10
92        elif self.speed == "single-step":
93            msecs = 1000000000
94        if not self.stop_mainloop:
95            self.master.update()
96            id = self.master.after(msecs, self.master.quit)
97            self.in_mainloop = 1
98            self.master.mainloop()
99            self.master.after_cancel(id)
100            self.in_mainloop = 0
101        if self.stop_mainloop:
102            self.stop_mainloop = 0
103            self.message("Cancelled")
104            raise Array.Cancelled
105
106    def getsize(self):
107        return self.size
108
109    def show_partition(self, first, last):
110        for i in range(self.size):
111            item = self.items[i]
112            if first <= i < last:
113                item.item.config(fill='red')
114            else:
115                item.item.config(fill='orange')
116        self.hide_left_right_pivot()
117
118    def hide_partition(self):
119        for i in range(self.size):
120            item = self.items[i]
121            item.item.config(fill='red')
122        self.hide_left_right_pivot()
123
124    def show_left(self, left):
125        if not 0 <= left < self.size:
126            self.hide_left()
127            return
128        x1, y1, x2, y2 = self.items[left].position()
129##      top, bot = HIRO
130        self.left.coords([(x1-2, 0), (x1-2, 9999)])
131        self.master.update()
132
133    def show_right(self, right):
134        if not 0 <= right < self.size:
135            self.hide_right()
136            return
137        x1, y1, x2, y2 = self.items[right].position()
138        self.right.coords(((x2+2, 0), (x2+2, 9999)))
139        self.master.update()
140
141    def hide_left_right_pivot(self):
142        self.hide_left()
143        self.hide_right()
144        self.hide_pivot()
145
146    def hide_left(self):
147        self.left.coords(((0, 0), (0, 0)))
148
149    def hide_right(self):
150        self.right.coords(((0, 0), (0, 0)))
151
152    def show_pivot(self, pivot):
153        x1, y1, x2, y2 = self.items[pivot].position()
154        self.pivot.coords(((0, y1-2), (9999, y1-2)))
155
156    def hide_pivot(self):
157        self.pivot.coords(((0, 0), (0, 0)))
158
159    def swap(self, i, j):
160        if i == j: return
161        self.countswap()
162        item = self.items[i]
163        other = self.items[j]
164        self.items[i], self.items[j] = other, item
165        item.swapwith(other)
166
167    def compare(self, i, j):
168        self.countcompare()
169        item = self.items[i]
170        other = self.items[j]
171        return item.compareto(other)
172
173    def reset(self, msg):
174        self.ncompares = 0
175        self.nswaps = 0
176        self.message(msg)
177        self.updatereport()
178        self.hide_partition()
179
180    def message(self, msg):
181        self.label.config(text=msg)
182
183    def countswap(self):
184        self.nswaps = self.nswaps + 1
185        self.updatereport()
186
187    def countcompare(self):
188        self.ncompares = self.ncompares + 1
189        self.updatereport()
190
191    def updatereport(self):
192        text = "%d cmps, %d swaps" % (self.ncompares, self.nswaps)
193        self.report.config(text=text)
194
195
196class ArrayItem:
197
198    def __init__(self, array, index, value):
199        self.array = array
200        self.index = index
201        self.value = value
202        x1, y1, x2, y2 = self.position()
203        self.item = Rectangle(array.canvas, x1, y1, x2, y2,
204                              fill='red', outline='black', width=1)
205        self.item.bind('<Button-1>', self.mouse_down)
206        self.item.bind('<Button1-Motion>', self.mouse_move)
207        self.item.bind('<ButtonRelease-1>', self.mouse_up)
208
209    def delete(self):
210        item = self.item
211        self.array = None
212        self.item = None
213        item.delete()
214
215    def mouse_down(self, event):
216        self.lastx = event.x
217        self.lasty = event.y
218        self.origx = event.x
219        self.origy = event.y
220        self.item.tkraise()
221
222    def mouse_move(self, event):
223        self.item.move(event.x - self.lastx, event.y - self.lasty)
224        self.lastx = event.x
225        self.lasty = event.y
226
227    def mouse_up(self, event):
228        i = self.nearestindex(event.x)
229        if i >= self.array.getsize():
230            i = self.array.getsize() - 1
231        if i < 0:
232            i = 0
233        other = self.array.items[i]
234        here = self.index
235        self.array.items[here], self.array.items[i] = other, self
236        self.index = i
237        x1, y1, x2, y2 = self.position()
238        self.item.coords(((x1, y1), (x2, y2)))
239        other.setindex(here)
240
241    def setindex(self, index):
242        nsteps = steps(self.index, index)
243        if not nsteps: return
244        if self.array.speed == "fastest":
245            nsteps = 0
246        oldpts = self.position()
247        self.index = index
248        newpts = self.position()
249        trajectory = interpolate(oldpts, newpts, nsteps)
250        self.item.tkraise()
251        for pts in trajectory:
252            self.item.coords((pts[:2], pts[2:]))
253            self.array.wait(50)
254
255    def swapwith(self, other):
256        nsteps = steps(self.index, other.index)
257        if not nsteps: return
258        if self.array.speed == "fastest":
259            nsteps = 0
260        myoldpts = self.position()
261        otheroldpts = other.position()
262        self.index, other.index = other.index, self.index
263        mynewpts = self.position()
264        othernewpts = other.position()
265        myfill = self.item['fill']
266        otherfill = other.item['fill']
267        self.item.config(fill='green')
268        other.item.config(fill='yellow')
269        self.array.master.update()
270        if self.array.speed == "single-step":
271            self.item.coords((mynewpts[:2], mynewpts[2:]))
272            other.item.coords((othernewpts[:2], othernewpts[2:]))
273            self.array.master.update()
274            self.item.config(fill=myfill)
275            other.item.config(fill=otherfill)
276            self.array.wait(0)
277            return
278        mytrajectory = interpolate(myoldpts, mynewpts, nsteps)
279        othertrajectory = interpolate(otheroldpts, othernewpts, nsteps)
280        if self.value > other.value:
281            self.item.tkraise()
282            other.item.tkraise()
283        else:
284            other.item.tkraise()
285            self.item.tkraise()
286        try:
287            for i in range(len(mytrajectory)):
288                mypts = mytrajectory[i]
289                otherpts = othertrajectory[i]
290                self.item.coords((mypts[:2], mypts[2:]))
291                other.item.coords((otherpts[:2], otherpts[2:]))
292                self.array.wait(50)
293        finally:
294            mypts = mytrajectory[-1]
295            otherpts = othertrajectory[-1]
296            self.item.coords((mypts[:2], mypts[2:]))
297            other.item.coords((otherpts[:2], otherpts[2:]))
298            self.item.config(fill=myfill)
299            other.item.config(fill=otherfill)
300
301    def compareto(self, other):
302        myfill = self.item['fill']
303        otherfill = other.item['fill']
304        outcome = cmp(self.value, other.value)
305        if outcome < 0:
306            myflash = 'white'
307            otherflash = 'black'
308        elif outcome > 0:
309            myflash = 'black'
310            otherflash = 'white'
311        else:
312            myflash = otherflash = 'grey'
313        try:
314            self.item.config(fill=myflash)
315            other.item.config(fill=otherflash)
316            self.array.wait(500)
317        finally:
318            self.item.config(fill=myfill)
319            other.item.config(fill=otherfill)
320        return outcome
321
322    def position(self):
323        x1 = (self.index+1)*XGRID - WIDTH//2
324        x2 = x1+WIDTH
325        y2 = (self.array.maxvalue+1)*YGRID
326        y1 = y2 - (self.value)*YGRID
327        return x1, y1, x2, y2
328
329    def nearestindex(self, x):
330        return int(round(float(x)/XGRID)) - 1
331
332
333# Subroutines that don't need an object
334
335def steps(here, there):
336    nsteps = abs(here - there)
337    if nsteps <= 3:
338        nsteps = nsteps * 3
339    elif nsteps <= 5:
340        nsteps = nsteps * 2
341    elif nsteps > 10:
342        nsteps = 10
343    return nsteps
344
345def interpolate(oldpts, newpts, n):
346    if len(oldpts) != len(newpts):
347        raise ValueError, "can't interpolate arrays of different length"
348    pts = [0]*len(oldpts)
349    res = [tuple(oldpts)]
350    for i in range(1, n):
351        for k in range(len(pts)):
352            pts[k] = oldpts[k] + (newpts[k] - oldpts[k])*i//n
353        res.append(tuple(pts))
354    res.append(tuple(newpts))
355    return res
356
357
358# Various (un)sorting algorithms
359
360def uniform(array):
361    size = array.getsize()
362    array.setdata([(size+1)//2] * size)
363    array.reset("Uniform data, size %d" % size)
364
365def distinct(array):
366    size = array.getsize()
367    array.setdata(range(1, size+1))
368    array.reset("Distinct data, size %d" % size)
369
370def randomize(array):
371    array.reset("Randomizing")
372    n = array.getsize()
373    for i in range(n):
374        j = random.randint(0, n-1)
375        array.swap(i, j)
376    array.message("Randomized")
377
378def insertionsort(array):
379    size = array.getsize()
380    array.reset("Insertion sort")
381    for i in range(1, size):
382        j = i-1
383        while j >= 0:
384            if array.compare(j, j+1) <= 0:
385                break
386            array.swap(j, j+1)
387            j = j-1
388    array.message("Sorted")
389
390def selectionsort(array):
391    size = array.getsize()
392    array.reset("Selection sort")
393    try:
394        for i in range(size):
395            array.show_partition(i, size)
396            for j in range(i+1, size):
397                if array.compare(i, j) > 0:
398                    array.swap(i, j)
399        array.message("Sorted")
400    finally:
401        array.hide_partition()
402
403def bubblesort(array):
404    size = array.getsize()
405    array.reset("Bubble sort")
406    for i in range(size):
407        for j in range(1, size):
408            if array.compare(j-1, j) > 0:
409                array.swap(j-1, j)
410    array.message("Sorted")
411
412def quicksort(array):
413    size = array.getsize()
414    array.reset("Quicksort")
415    try:
416        stack = [(0, size)]
417        while stack:
418            first, last = stack[-1]
419            del stack[-1]
420            array.show_partition(first, last)
421            if last-first < 5:
422                array.message("Insertion sort")
423                for i in range(first+1, last):
424                    j = i-1
425                    while j >= first:
426                        if array.compare(j, j+1) <= 0:
427                            break
428                        array.swap(j, j+1)
429                        j = j-1
430                continue
431            array.message("Choosing pivot")
432            j, i, k = first, (first+last)//2, last-1
433            if array.compare(k, i) < 0:
434                array.swap(k, i)
435            if array.compare(k, j) < 0:
436                array.swap(k, j)
437            if array.compare(j, i) < 0:
438                array.swap(j, i)
439            pivot = j
440            array.show_pivot(pivot)
441            array.message("Pivot at left of partition")
442            array.wait(1000)
443            left = first
444            right = last
445            while 1:
446                array.message("Sweep right pointer")
447                right = right-1
448                array.show_right(right)
449                while right > first and array.compare(right, pivot) >= 0:
450                    right = right-1
451                    array.show_right(right)
452                array.message("Sweep left pointer")
453                left = left+1
454                array.show_left(left)
455                while left < last and array.compare(left, pivot) <= 0:
456                    left = left+1
457                    array.show_left(left)
458                if left > right:
459                    array.message("End of partition")
460                    break
461                array.message("Swap items")
462                array.swap(left, right)
463            array.message("Swap pivot back")
464            array.swap(pivot, right)
465            n1 = right-first
466            n2 = last-left
467            if n1 > 1: stack.append((first, right))
468            if n2 > 1: stack.append((left, last))
469        array.message("Sorted")
470    finally:
471        array.hide_partition()
472
473def demosort(array):
474    while 1:
475        for alg in [quicksort, insertionsort, selectionsort, bubblesort]:
476            randomize(array)
477            alg(array)
478
479
480# Sort demo class -- usable as a Grail applet
481
482class SortDemo:
483
484    def __init__(self, master, size=15):
485        self.master = master
486        self.size = size
487        self.busy = 0
488        self.array = Array(self.master)
489
490        self.botframe = Frame(master)
491        self.botframe.pack(side=BOTTOM)
492        self.botleftframe = Frame(self.botframe)
493        self.botleftframe.pack(side=LEFT, fill=Y)
494        self.botrightframe = Frame(self.botframe)
495        self.botrightframe.pack(side=RIGHT, fill=Y)
496
497        self.b_qsort = Button(self.botleftframe,
498                              text="Quicksort", command=self.c_qsort)
499        self.b_qsort.pack(fill=X)
500        self.b_isort = Button(self.botleftframe,
501                              text="Insertion sort", command=self.c_isort)
502        self.b_isort.pack(fill=X)
503        self.b_ssort = Button(self.botleftframe,
504                              text="Selection sort", command=self.c_ssort)
505        self.b_ssort.pack(fill=X)
506        self.b_bsort = Button(self.botleftframe,
507                              text="Bubble sort", command=self.c_bsort)
508        self.b_bsort.pack(fill=X)
509
510        # Terrible hack to overcome limitation of OptionMenu...
511        class MyIntVar(IntVar):
512            def __init__(self, master, demo):
513                self.demo = demo
514                IntVar.__init__(self, master)
515            def set(self, value):
516                IntVar.set(self, value)
517                if str(value) != '0':
518                    self.demo.resize(value)
519
520        self.v_size = MyIntVar(self.master, self)
521        self.v_size.set(size)
522        sizes = [1, 2, 3, 4] + range(5, 55, 5)
523        if self.size not in sizes:
524            sizes.append(self.size)
525            sizes.sort()
526        self.m_size = apply(OptionMenu,
527                            (self.botleftframe, self.v_size) + tuple(sizes))
528        self.m_size.pack(fill=X)
529
530        self.v_speed = StringVar(self.master)
531        self.v_speed.set("normal")
532        self.m_speed = OptionMenu(self.botleftframe, self.v_speed,
533                                  "single-step", "normal", "fast", "fastest")
534        self.m_speed.pack(fill=X)
535
536        self.b_step = Button(self.botleftframe,
537                             text="Step", command=self.c_step)
538        self.b_step.pack(fill=X)
539
540        self.b_randomize = Button(self.botrightframe,
541                                  text="Randomize", command=self.c_randomize)
542        self.b_randomize.pack(fill=X)
543        self.b_uniform = Button(self.botrightframe,
544                                  text="Uniform", command=self.c_uniform)
545        self.b_uniform.pack(fill=X)
546        self.b_distinct = Button(self.botrightframe,
547                                  text="Distinct", command=self.c_distinct)
548        self.b_distinct.pack(fill=X)
549        self.b_demo = Button(self.botrightframe,
550                             text="Demo", command=self.c_demo)
551        self.b_demo.pack(fill=X)
552        self.b_cancel = Button(self.botrightframe,
553                               text="Cancel", command=self.c_cancel)
554        self.b_cancel.pack(fill=X)
555        self.b_cancel.config(state=DISABLED)
556        self.b_quit = Button(self.botrightframe,
557                             text="Quit", command=self.c_quit)
558        self.b_quit.pack(fill=X)
559
560    def resize(self, newsize):
561        if self.busy:
562            self.master.bell()
563            return
564        self.size = newsize
565        self.array.setdata(range(1, self.size+1))
566
567    def c_qsort(self):
568        self.run(quicksort)
569
570    def c_isort(self):
571        self.run(insertionsort)
572
573    def c_ssort(self):
574        self.run(selectionsort)
575
576    def c_bsort(self):
577        self.run(bubblesort)
578
579    def c_demo(self):
580        self.run(demosort)
581
582    def c_randomize(self):
583        self.run(randomize)
584
585    def c_uniform(self):
586        self.run(uniform)
587
588    def c_distinct(self):
589        self.run(distinct)
590
591    def run(self, func):
592        if self.busy:
593            self.master.bell()
594            return
595        self.busy = 1
596        self.array.setspeed(self.v_speed.get())
597        self.b_cancel.config(state=NORMAL)
598        try:
599            func(self.array)
600        except Array.Cancelled:
601            pass
602        self.b_cancel.config(state=DISABLED)
603        self.busy = 0
604
605    def c_cancel(self):
606        if not self.busy:
607            self.master.bell()
608            return
609        self.array.cancel()
610
611    def c_step(self):
612        if not self.busy:
613            self.master.bell()
614            return
615        self.v_speed.set("single-step")
616        self.array.setspeed("single-step")
617        self.array.step()
618
619    def c_quit(self):
620        if self.busy:
621            self.array.cancel()
622        self.master.after_idle(self.master.quit)
623
624
625# Main program -- for stand-alone operation outside Grail
626
627def main():
628    root = Tk()
629    demo = SortDemo(root)
630    root.protocol('WM_DELETE_WINDOW', demo.c_quit)
631    root.mainloop()
632
633if __name__ == '__main__':
634    main()
635