Python code coverage for Lib/turtledemo/sorting_animate.py

#	count	content
1	n/a	#!/usr/bin/env python3
2	n/a	"""
3	n/a
4	n/a	sorting_animation.py
5	n/a
6	n/a	A minimal sorting algorithm animation:
7	n/a	Sorts a shelf of 10 blocks using insertion
8	n/a	sort, selection sort and quicksort.
9	n/a
10	n/a	Shelfs are implemented using builtin lists.
11	n/a
12	n/a	Blocks are turtles with shape "square", but
13	n/a	stretched to rectangles by shapesize()
14	n/a	---------------------------------------
15	n/a	To exit press space button
16	n/a	---------------------------------------
17	n/a	"""
18	n/a	from turtle import *
19	n/a	import random
20	n/a
21	n/a
22	n/a	class Block(Turtle):
23	n/a
24	n/a	def __init__(self, size):
25	n/a	self.size = size
26	n/a	Turtle.__init__(self, shape="square", visible=False)
27	n/a	self.pu()
28	n/a	self.shapesize(size * 1.5, 1.5, 2) # square-->rectangle
29	n/a	self.fillcolor("black")
30	n/a	self.st()
31	n/a
32	n/a	def glow(self):
33	n/a	self.fillcolor("red")
34	n/a
35	n/a	def unglow(self):
36	n/a	self.fillcolor("black")
37	n/a
38	n/a	def __repr__(self):
39	n/a	return "Block size: {0}".format(self.size)
40	n/a
41	n/a
42	n/a	class Shelf(list):
43	n/a
44	n/a	def __init__(self, y):
45	n/a	"create a shelf. y is y-position of first block"
46	n/a	self.y = y
47	n/a	self.x = -150
48	n/a
49	n/a	def push(self, d):
50	n/a	width, _, _ = d.shapesize()
51	n/a	# align blocks by the bottom edge
52	n/a	y_offset = width / 2 * 20
53	n/a	d.sety(self.y + y_offset)
54	n/a	d.setx(self.x + 34 * len(self))
55	n/a	self.append(d)
56	n/a
57	n/a	def _close_gap_from_i(self, i):
58	n/a	for b in self[i:]:
59	n/a	xpos, _ = b.pos()
60	n/a	b.setx(xpos - 34)
61	n/a
62	n/a	def _open_gap_from_i(self, i):
63	n/a	for b in self[i:]:
64	n/a	xpos, _ = b.pos()
65	n/a	b.setx(xpos + 34)
66	n/a
67	n/a	def pop(self, key):
68	n/a	b = list.pop(self, key)
69	n/a	b.glow()
70	n/a	b.sety(200)
71	n/a	self._close_gap_from_i(key)
72	n/a	return b
73	n/a
74	n/a	def insert(self, key, b):
75	n/a	self._open_gap_from_i(key)
76	n/a	list.insert(self, key, b)
77	n/a	b.setx(self.x + 34 * key)
78	n/a	width, _, _ = b.shapesize()
79	n/a	# align blocks by the bottom edge
80	n/a	y_offset = width / 2 * 20
81	n/a	b.sety(self.y + y_offset)
82	n/a	b.unglow()
83	n/a
84	n/a	def isort(shelf):
85	n/a	length = len(shelf)
86	n/a	for i in range(1, length):
87	n/a	hole = i
88	n/a	while hole > 0 and shelf[i].size < shelf[hole - 1].size:
89	n/a	hole = hole - 1
90	n/a	shelf.insert(hole, shelf.pop(i))
91	n/a	return
92	n/a
93	n/a	def ssort(shelf):
94	n/a	length = len(shelf)
95	n/a	for j in range(0, length - 1):
96	n/a	imin = j
97	n/a	for i in range(j + 1, length):
98	n/a	if shelf[i].size < shelf[imin].size:
99	n/a	imin = i
100	n/a	if imin != j:
101	n/a	shelf.insert(j, shelf.pop(imin))
102	n/a
103	n/a	def partition(shelf, left, right, pivot_index):
104	n/a	pivot = shelf[pivot_index]
105	n/a	shelf.insert(right, shelf.pop(pivot_index))
106	n/a	store_index = left
107	n/a	for i in range(left, right): # range is non-inclusive of ending value
108	n/a	if shelf[i].size < pivot.size:
109	n/a	shelf.insert(store_index, shelf.pop(i))
110	n/a	store_index = store_index + 1
111	n/a	shelf.insert(store_index, shelf.pop(right)) # move pivot to correct position
112	n/a	return store_index
113	n/a
114	n/a	def qsort(shelf, left, right):
115	n/a	if left < right:
116	n/a	pivot_index = left
117	n/a	pivot_new_index = partition(shelf, left, right, pivot_index)
118	n/a	qsort(shelf, left, pivot_new_index - 1)
119	n/a	qsort(shelf, pivot_new_index + 1, right)
120	n/a
121	n/a	def randomize():
122	n/a	disable_keys()
123	n/a	clear()
124	n/a	target = list(range(10))
125	n/a	random.shuffle(target)
126	n/a	for i, t in enumerate(target):
127	n/a	for j in range(i, len(s)):
128	n/a	if s[j].size == t + 1:
129	n/a	s.insert(i, s.pop(j))
130	n/a	show_text(instructions1)
131	n/a	show_text(instructions2, line=1)
132	n/a	enable_keys()
133	n/a
134	n/a	def show_text(text, line=0):
135	n/a	line = 20 * line
136	n/a	goto(0,-250 - line)
137	n/a	write(text, align="center", font=("Courier", 16, "bold"))
138	n/a
139	n/a	def start_ssort():
140	n/a	disable_keys()
141	n/a	clear()
142	n/a	show_text("Selection Sort")
143	n/a	ssort(s)
144	n/a	clear()
145	n/a	show_text(instructions1)
146	n/a	show_text(instructions2, line=1)
147	n/a	enable_keys()
148	n/a
149	n/a	def start_isort():
150	n/a	disable_keys()
151	n/a	clear()
152	n/a	show_text("Insertion Sort")
153	n/a	isort(s)
154	n/a	clear()
155	n/a	show_text(instructions1)
156	n/a	show_text(instructions2, line=1)
157	n/a	enable_keys()
158	n/a
159	n/a	def start_qsort():
160	n/a	disable_keys()
161	n/a	clear()
162	n/a	show_text("Quicksort")
163	n/a	qsort(s, 0, len(s) - 1)
164	n/a	clear()
165	n/a	show_text(instructions1)
166	n/a	show_text(instructions2, line=1)
167	n/a	enable_keys()
168	n/a
169	n/a	def init_shelf():
170	n/a	global s
171	n/a	s = Shelf(-200)
172	n/a	vals = (4, 2, 8, 9, 1, 5, 10, 3, 7, 6)
173	n/a	for i in vals:
174	n/a	s.push(Block(i))
175	n/a
176	n/a	def disable_keys():
177	n/a	onkey(None, "s")
178	n/a	onkey(None, "i")
179	n/a	onkey(None, "q")
180	n/a	onkey(None, "r")
181	n/a
182	n/a	def enable_keys():
183	n/a	onkey(start_isort, "i")
184	n/a	onkey(start_ssort, "s")
185	n/a	onkey(start_qsort, "q")
186	n/a	onkey(randomize, "r")
187	n/a	onkey(bye, "space")
188	n/a
189	n/a	def main():
190	n/a	getscreen().clearscreen()
191	n/a	ht(); penup()
192	n/a	init_shelf()
193	n/a	show_text(instructions1)
194	n/a	show_text(instructions2, line=1)
195	n/a	enable_keys()
196	n/a	listen()
197	n/a	return "EVENTLOOP"
198	n/a
199	n/a	instructions1 = "press i for insertion sort, s for selection sort, q for quicksort"
200	n/a	instructions2 = "spacebar to quit, r to randomize"
201	n/a
202	n/a	if __name__=="__main__":
203	n/a	msg = main()
204	n/a	mainloop()