ยปCore Development>Code coverage>Tools/demo/sortvisu.py

Python code coverage for Tools/demo/sortvisu.py

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