[python][algorithm] Sorting Animation

古いディスクを整理していたらすごーく懐かしいものが出てきた。
大学のころに友人が「sortアルゴリズムってたくさんありすぎてよーわからん」と言っていたのを聞いて説明用に書いたやつで、ありがちな sort中の配列の様子を可視化するプログラム。だけどちょっとだけ工夫した部分がある。元のプログラムはC++で書いてあるんだけど、oeperator =と operator []をオーバーロードしてあって、リードすると緑のラインが、ライトすると赤のラインが表示されて該当位置が変更される、というのを自動的にやってくれる。つまりは、アルゴリズム自体は教科書に載っているようなごく普通の書き方をすれば、可視化のことは考えなくても勝手にやってくれるようになっている。
今見ると、Xlibに依存していたり、わざわざオブジェクト版GetOptを使っていたり、と環境依存しまくりな見るに耐えない恥ずかしいコードなんだけど、なんだか懐かしくなったので Python+Tkinterで書き直してみた。

# SortingAnimation.py
import Tkinter as Tk
import array
import time

class DataArray(object):
        def __makeaccessbar__(self, color, tagname):
                self.canvas.create_rectangle( -self.grid+1, 0, 1, self.size*self.grid,
                                               outline = "", fill = color, tag = tagname)

        def __moveaccessbar__(self, tag, x):
                cur_x = self.canvas.coords(tag)[0]
                self.canvas.move(tag, (x+1)*self.grid - cur_x,0)

        def __makedot__(self, idx):
                grid = self.grid
                x = idx            *grid +1
                y = self.array[idx]*grid +1
                self.canvas.create_rectangle(x, y, x+grid, y+grid,
                                             outline = "", fill = "black", tag = "v"+str(idx))

        def __movedot__(self, idx, val):
                self.canvas.move("v"+str(idx), 0, (val - self.array[idx])*self.grid )

        def __init__(self, size = 256, wait = 0.01, grid=2, accessbar = True):
                self.size   = size
                self.max    = max
                self.grid   = grid
                self.wait   = wait
                self.accessbar = accessbar
                self.window = Tk.Tk()
                self.array  = array.array("i", xrange(size))

                import random
                random.shuffle(self.array)

                vis_size    = self.size * self.grid
                c = self.canvas = Tk.Canvas(self.window,  width = vis_size,
                                            height= vis_size)

                self.__makeaccessbar__("green",   "read")
                self.__makeaccessbar__("red",     "write")
#                self.__makeaccessbar__("magenta", "swap1") [T.B.D]
#                self.__makeaccessbar__("magenta", "swap2") [T.B.D]

                for i in xrange(size):
                        self.__makedot__(i)

		c.pack()

        def __len__(self):
                return len(self.array)

	def __getitem__(self, idx):
                if self.accessbar:
                        self.__moveaccessbar__("read",  idx)
                        self.window.update_idletasks()
		if self.wait: time.sleep(self.wait)
                return self.array[idx]

        def __setitem__(self, idx, val):
                if self.accessbar:
                        self.__moveaccessbar__("write", idx)
                self.__movedot__(idx, val)
		self.window.update_idletasks()
                if self.wait: time.sleep(self.wait)
                self.array[idx] = val
                return val

        def swap(self, idx1, idx2):
                t = self[idx1]
                self[idx1] = self[idx2]
                self[idx2] = t

...見るに耐えないコードを吐いてしまうのは昔も今も変わらないな。
こんな感じで使います。

# bubble.py
from SortingAnimation import DataArray

size = 100

xs = DataArray(size)

for i in xrange(size):
	for j in xrange(size-1, i, -1):
		if xs[j-1] > xs[j]:
			xs.swap(j-1, j)

しかしmainloop()を呼んでないのでウィンドウマネージ関連が死亡状態。おかげでLinuxではいいんだけどMacOSXのネイティブPythonだとウィンドウを前面に持ってくることすらできない（別アプリのため制御がいかない？)。さらに異様に遅い。せめてmainloop()だけでも動かそうと何も考えずにstart_new_thread()したら「違うアパートメントのTk呼ぶなゴラァ！」と怒られる。アルゴリズム終了すると即ウィンドウが消える(これは最後で明示的に止めればよいのですが）。修正すべきところだらけだけどとりあえず晒してみました。そのうち直す、、、、かな？