home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pyos2bin.zip / Demo / tkinter / guido / sortvisu.py < prev    next >
Text File  |  1997-04-02  |  16KB  |  635 lines
  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()
  635.