Demo/tkinter/guido/sortvisu.py

   1 #! /usr/bin/env python
   2
   3 """Sorting algorithms visualizer using Tkinter.
   4
   5 This module is comprised of three ``components'':
   6
   7 - an array visualizer with methods that implement basic sorting
   8 operations (compare, swap) as well as methods for ``annotating'' the
   9 sorting algorithm (e.g. to show the pivot element);
  10
  11 - a number of sorting algorithms (currently quicksort, insertion sort,
  12 selection sort and bubble sort, as well as a randomization function),
  13 all using the array visualizer for its basic operations and with calls
  14 to its annotation methods;
  15
  16 - and a ``driver'' class which can be used as a Grail applet or as a
  17 stand-alone application.
  18
  19 """
  20
  21
  22 from Tkinter import *
  23 from Canvas import Line, Rectangle
  24 import random
  25
  26
  27 XGRID = 10
  28 YGRID = 10
  29 WIDTH = 6
  30
  31
  32 class 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
 196 class 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
 335 def 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
 345 def 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
 360 def uniform(array):
 361     size = array.getsize()
 362     array.setdata([(size+1)//2] * size)
 363     array.reset("Uniform data, size %d" % size)
 364
 365 def distinct(array):
 366     size = array.getsize()
 367     array.setdata(range(1, size+1))
 368     array.reset("Distinct data, size %d" % size)
 369
 370 def 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
 378 def 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
 390 def 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
 403 def 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
 412 def 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
 473 def 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
 482 class 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
 627 def main():
 628     root = Tk()
 629     demo = SortDemo(root)
 630     root.protocol('WM_DELETE_WINDOW', demo.c_quit)
 631     root.mainloop()
 632
 633 if __name__ == '__main__':
 634     main()