Download code

Jump to: navigation, search

Back to Binary_search_tree_(Python)

Download for Windows: zip

Download for UNIX: zip, tar.gz, tar.bz2

Bst.py

  1 # The authors of this work have released all rights to it and placed it
  2 # in the public domain under the Creative Commons CC0 1.0 waiver
  3 # (http://creativecommons.org/publicdomain/zero/1.0/).
  4 # 
  5 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 # 
 13 # Retrieved from: http://en.literateprograms.org/Binary_search_tree_(Python)?oldid=18769
 14 
 15 class Node( object ) :
 16 	def __init__( self, key, left=None, right=None ) :
 17 		self.val = key
 18 		self.less = left
 19 		self.more = right	
 20 	def __init__( self, first=None ) :
 21 		self.root = None
 22 		if first is None :
 23 			return
 24 		elif isinstance( first, list ) :
 25 			self._add_multiple( first )
 26 		else :
 27 			self.add( first )
 28 	def g_less( self ) :
 29 		return self.less
 30 	def g_more( self ) :
 31 		return self.more
 32 	def change_less( self, another ) :
 33 		self.less = another
 34 	def change_more( self, another ) :
 35 		self.more = another
 36 	def g_val( self ) :
 37 		return self.val
 38 
 39 	def change_val( self, new_key ) :
 40 		self.val = new_key
 41 	def __eq__( self, another ) :
 42 		return self.val == another.val
 43 
 44 	def __gt__( self, another ) :
 45 		return self.val > another.val
 46 
 47 	def __lt__( self, another ) :
 48 		return self.val < another.val
 49 	def am_leaf( self ) :
 50 		return self.less is None and self.more is None
 51 
 52 	def less_is_empty( self ) :
 53 		return self.less is None
 54 
 55 	def more_is_empty( self ) :
 56 		return self.more is None
 57 class Bst( object ) :
 58 	def __init__( self, key, left=None, right=None ) :
 59 		self.val = key
 60 		self.less = left
 61 		self.more = right	
 62 	def __init__( self, first=None ) :
 63 		self.root = None
 64 		if first is None :
 65 			return
 66 		elif isinstance( first, list ) :
 67 			self._add_multiple( first )
 68 		else :
 69 			self.add( first )
 70 	def add( self, wanted ) :
 71 		if isinstance( wanted, list ) :
 72 			self._add_multiple( wanted )
 73 		elif self.is_empty() :
 74 			self.root = Node( wanted )
 75 		else :
 76 			insertion = Node( wanted )
 77 			self._add_leaf( self.root, insertion )
 78 	def _add_multiple( self, wanted_vals ) :
 79 		for val in wanted_vals :
 80 			self.add( val )
 81 	def _add_leaf( self, comparison, new_node ) : 
 82 		'currently, not checking until I enter'
 83 		if comparison == new_node :
 84 			return # no duplicates
 85 		elif comparison > new_node :
 86 			if comparison.less_is_empty( ) :
 87 				comparison.change_less( new_node )
 88 			else :
 89 				self._add_leaf( comparison.g_less( ), new_node )
 90 		else :
 91 			if comparison.more_is_empty( ) :
 92 				comparison.change_more( new_node )
 93 			else :
 94 				self._add_leaf( comparison.g_more( ), new_node )
 95 	def confirm( self, desire ) :
 96 		if self.is_empty() :
 97 			return False
 98 		elif self.root.g_val() == desire :
 99 			return True
100 		else :
101 			fake = Node( desire )
102 			result = self._find( self.root, fake )
103 			if result is None :
104 				return False
105 			else : # found
106 				return True	
107 	def _find( self, maybe, unconfirmed ) :
108 		if maybe < unconfirmed :
109 			maybe = maybe.g_more()
110 			if maybe is None :
111 				return maybe # failure
112 			elif maybe == unconfirmed :
113 				return maybe # success
114 			else :
115 				return self._find( maybe, unconfirmed )
116 		else : # maybe > unconfirmed
117 			maybe = maybe.g_less()
118 			if maybe == unconfirmed or maybe is None :
119 				return maybe
120 			else :
121 				return self._find( maybe, unconfirmed )
122 	def delete( self, unwanted_val ) :
123 		if self.is_empty() :
124 			return
125 		elif self.root.g_val() == unwanted_val :
126 			self._delete_root()
127 		else :
128 			obsolete = Node( unwanted_val )
129 			ancestor_stack = [ ]
130 			ancestor_stack = self._path_to_obsolete( obsolete, self.root, ancestor_stack )
131 			if ancestor_stack[ -1 ] is None :
132 				return
133 			else :
134 				self._perform_delete( ancestor_stack )
135 	def _perform_delete( self, ancestor_stack ) :
136 		o_less_Leaf = True
137 		obsolete = ancestor_stack.pop( )
138 		parent = ancestor_stack.pop( )
139 		o_was_less = obsolete < parent
140 			def _delete_root( self ) :
141 				fake = Node( self.root.g_val() + self.root.g_val() )
142 				fake_stack = [fake, self.root]
143 				self._perform_delete( fake_stack )
144 				if fake.less_is_empty() :
145 					self.root = fake.g_more()
146 				else :
147 					self.root = fake.g_less()
148 		if obsolete.am_leaf() :
149 			self._update_parent( parent_of_o, None, o_was_less )
150 		elif obsolete.less_is_empty() :
151 			self._replace_with_solo( parent, o_was_less, obsolete, o_less_Leaf )
152 		elif obsolete.more_is_empty() :
153 			self._replace_with_solo( parent, o_was_less, obsolete, not o_less_Leaf )
154 		else : # two children
155 			self._replace_with_two_children( parent, o_was_less, obsolete )
156 	def _update_parent( self, parent, replacer, from_less ) :
157 		if from_less :
158 			parent.change_less( replacer )
159 		else :
160 			parent.change_more( replacer )
161 	def _replace_with_solo( self, parent, from_less, obsolete, o_less_Leaf ) :
162 		if o_less_Leaf :
163 			self._update_parent( parent_of_o, obsolete.g_more(), from_less )
164 		else : # more is empty
165 			self._update_parent( parent_of_o, obsolete.g_less(), from_less )
166 	def _replace_with_two_children( self, parent, from_less, obsolete ) :
167 		left_replace = obsolete.g_val() % 2 == 0 # magic, or use rand_bool( )
168 		if left_replace :
169 			replacer, reps_parent = self._max_and_parent( obsolete.g_less(), obsolete )
170 			self._less_replace_2_kid( parent, from_less, obsolete, replacer, reps_parent )
171 		else : # right_replace
172 			replacer, reps_parent = self._min_and_parent( obsolete.g_more( ), obsolete )
173 			self._more_replace_2_kid( parent, from_less, obsolete, replacer, reps_parent )
174 	def _less_replace_2_kid( self, parent, from_less, obsolete, replacer, reps_parent ) :
175 		if reps_parent is obsolete :
176 			replacer.change_more( obsolete.g_more() )
177 			o_less_Leaf = True
178 			self._replace_with_solo( parent, from_less, obsolete, not o_less_Leaf )
179 		else :
180 			self._update_parent( parent, replacer, from_less )
181 			replacer.change_more( obsolete.g_more() )
182 			reps_parent.change_more( replacer.g_less() )
183 			replacer.change_less( obsolete.g_less() )
184 	def _more_replace_2_kid( self, parent, from_less, obsolete, replacer, reps_parent ) :
185 		if reps_parent is obsolete :
186 			replacer.change_less( obsolete.g_less() )
187 			o_less_Leaf = True
188 			self._replace_with_solo( parent, from_less, obsolete, o_less_Leaf )
189 		else :
190 			self._update_parent( parent, replacer, from_less )
191 			replacer.change_less( obsolete.g_less() )
192 			reps_parent.change_less( replacer.g_more() ) # is this right?
193 			replacer.change_more( obsolete.g_more() )
194 	def _path_to_obsolete( self, obsolete, focus, ancestorStack ) :
195 		ancestorStack.append( focus )
196 		if focus is None or focus == obsolete :
197 			return ancestorStack
198 		else :
199 			if focus < obsolete :
200 				return self._path_to_obsolete( obsolete, focus.g_more( ), ancestorStack )
201 			else :
202 				return self._path_to_obsolete( obsolete, focus.g_less( ), ancestorStack )
203 
204 	def _max_and_parent( self, a_child, a_root ) :
205 		if a_child.more_is_empty() :
206 			return a_child, a_root
207 		else :
208 			return self._max_and_parent( a_child.g_more(), a_child )
209 
210 	def _min_and_parent( self, a_child, a_root ) :
211 		if a_child.less_is_empty() :
212 			return a_child, a_root
213 		# else :
214 		while not a_child.less_is_empty() :
215 			a_root = a_child
216 			a_child = a_child.g_less()
217 		return a_child, a_root
218 	def g_all_elements( self ) :
219 		everything = []
220 		if self.root is None :
221 			return everything
222 		else :
223 			everything = self._traverse( self.root, everything )
224 			return everything
225 
226 	def _traverse( self, focus, container ) :
227 		'in order, obviously'
228 		if focus is None :
229 			return container
230 		else :
231 			container = self._traverse( focus.g_less(), container )
232 			container.push( focus.g_val() )
233 			container = self._traverse( focus.g_more(), container )
234 			return container
235 
236 	def is_empty( self ) :
237 		return self.root is None
238 
239 	def erase( self ) :
240 		self.root = None
241 	def pr_hV( self ) :
242 		if tree.is_empty() :
243 			print ">--"
244 		else :
245 			print "v"
246 			self._pr_90( [ self.root ] )
247 
248 	def _pr_hV( self, pr_stack ) :
249 		vert = pr_stack.__len__() - 1
250 		if vert >= 0 :
251 			self._pr_90_links( pr_stack, vert + 1 )
252 			print
253 			self._pr_90_links( pr_stack, vert )
254 			pr_stack = self._pr_90_row( pr_stack )
255 			self._pr_90( pr_stack )
256 
257 	def _pr_hV_links( self, pr_stack, vert ) : # test this addition
258 		for ind in range( 0, vert ) :
259 			nn = pr_stack[ ind ]
260 			if nn is None :
261 				print "  ",
262 			else :
263 				print "| ",
264 
265 	def _pr_hV_row( self, pr_stack ) :
266 		## python print \n suppression substitutes a space
267 		row_str = []
268 		focus = pr_stack.pop()
269 		while not focus is None :
270 			row_str.append( str( focus.g_val() ) )
271 			if not focus.less_is_empty() :
272 				pr_stack.append( focus.g_less() )
273 			elif not focus.more_is_empty() :
274 				pr_stack.append( None ),		
275 			if not focus.more_is_empty() :
276 				row_str.append( "-" )
277 			focus = focus.g_more()
278 		row_str = ''.join( row_str ) # turn list to string.
279 		print row_str
280 		#self._pr_node_stack( pr_stack )
281 		pr_stack = self._strip_placeholders( pr_stack )
282 		return pr_stack
283 
284 	def _strip_placeholders( self, pr_stack ) :
285 		'ie None'
286 		focus = None
287 		while pr_stack.__len__() > 0 :
288 			focus = pr_stack.pop()
289 			if not focus is None :
290 				pr_stack.append( focus )
291 				break
292 		return pr_stack
293 
294 tree = Bst()
295 something_wrong = True
296 seems_okay = not something_wrong
297 status = seems_okay # at least initially
298 print "\n\t PROBLEMS"
299 status = node_should_work() or status
300 status = should_erase()  or status
301 status = should_insert( tree ) or status # propagates truth
302 status = should_confirm( tree ) or status
303 status = should_delete( tree ) or status
304 status = should_traverse( tree ) or status
305 if seems_okay :
306 	print "> Silent test run"
307 else :
308 	print "\n<> so go fix that"
309 #check_by_eye( tree )
310 
311 def should_insert( tree ) :
312 	flag = should_add_to_empty( tree )
313 	flag = should_add_to_root_leaf( tree ) or flag
314 	flag = should_add_multiple( tree ) or flag
315 	flag = should_not_add_copy( tree ) or flag
316 	return flag
317 def should_add_to_empty( tree ) :
318 	if not tree.is_empty( ) :
319 		tree.erase( )
320 	root_v = 'aa'
321 	tree.add( root_v )
322 	if not tree.root.g_val() == root_v :
323 		print "I> didn't add val to empty tree"
324 		return something_wrong
325 	tree.erase( )
326 	return seems_okay
327 def should_add_to_root_leaf( tree ) :
328 	root_v = -12
329 	new_val = 21
330 	tree.add( root_v )
331 	tree.add( new_val )
332 	if tree.root.am_leaf( ) :
333 		print "I> didn't add val to a node"
334 		return something_wrong
335 	elif tree.root.more_is_empty() :
336 		print "I> added new node to opposite side"
337 		return something_wrong
338 	elif tree.root.g_more( ).g_val() != new_val :
339 		print "I> added to right side, wrong value"
340 		return something_wrong
341 	return seems_okay
342 
343 def should_add_multiple( tree ) :
344 	#print "I> doesn't test multiple yet"
345 	tree.erase()
346 	root_val = .5
347 	l_child = .25
348 	lis = [root_val, l_child]
349 	tree.add(lis)
350 	if not tree.root.g_val() == root_val :
351 		print "I> multiple didn't deposit first val"
352 		return something_wrong
353 	elif not tree.root.g_less().g_val() == l_child :
354 		print "I> multiple didn't add second val"
355 		return something_wrong
356 	return seems_okay
357 def should_not_add_copy( tree ) :
358 	tree.erase()
359 	root_v = 'do'
360 	child = 're'
361 	tree.add( root_v )
362 	tree.add( root_v )
363 	if not tree.root.am_leaf() :
364 		print "I> added a second copy of a val"
365 		return something_wrong
366 	tree.add( child )
367 	tree.add( child )
368 	if not tree.root.g_more().am_leaf() :
369 		print "I> added redundant node to interior"
370 		return something_wrong
371 	tree.add( root_v )
372 	root_okay = tree.root.less_is_empty()
373 	child_okay = tree.root.g_more().am_leaf()
374 	if not root_okay or not child_okay :
375 		print "I> added redundant on second try"
376 		return something_wrong
377 	return seems_okay
378 def should_confirm( tree ) :
379 	tree.erase()
380 	root_v = 4
381 	val_yes = 5
382 	val_no = val_yes + val_yes
383 	bunch = [ root_v, 3, 6, val_yes]
384 	if tree.confirm( val_no ) :
385 		print "C> confirmed value when tree empty"
386 		return something_wrong
387 	tree.add( bunch )
388 	if not tree.confirm( root_v ) :
389 		print "C> didn't confirm root's value"
390 		return something_wrong
391 	elif not tree.confirm( val_yes ) :
392 		print "C> didn't find key in subtree"
393 		return something_wrong
394 	elif tree.confirm( val_no ) :
395 		print "C> tree thinks it contains an uninserted value"
396 		return something_wrong
397 	else :
398 		return seems_okay
399 
400 def should_traverse( tree ) :
401 	tree.erase()
402 	bunch = [ 4, 2, 1, 3, 7, 5, 8 ]
403 	tree.add( bunch )
404 	bundle = tree.g_all_elements()
405 	bunch.sort()
406 	for elem in range( 0, bunch.__len__() - 1 )	:
407 		if not bundle[ elem ] == bunch[ elem ] :
408 			print "T> ret " + str( bundle[ elem ] ) + " is not supp " + str( bunch[ elem ] )
409 			print bundle
410 			return something_wrong
411 	tree.erase
412 	return seems_okay
413 
414 


hijacker
hijacker
hijacker
hijacker

input.nw

  1 <<Bst.py>>=
  2 <<node>>
  3 <<bst>>
  4 <<tests>>
  5 
  6 @ text
  7 
  8 <<node>>=
  9 class Node( object ) :
 10 <<constructor>>
 11 <<child get-set>>
 12 <<key get-set>>
 13 <<value comparisons>>
 14 <<query children>>
 15 @ text
 16 
 17 <<child get-set>>=
 18 	def g_less( self ) :
 19 		return self.less
 20 	def g_more( self ) :
 21 		return self.more
 22 	def change_less( self, another ) :
 23 		self.less = another
 24 	def change_more( self, another ) :
 25 		self.more = another
 26 @ text
 27 
 28 <<key get-set>>=
 29 	def g_val( self ) :
 30 		return self.val
 31 
 32 	def change_val( self, new_key ) :
 33 		self.val = new_key
 34 @ text
 35 
 36 <<constructor>>=
 37 	def __init__( self, key, left=None, right=None ) :
 38 		self.val = key
 39 		self.less = left
 40 		self.more = right	
 41 @ text
 42 
 43 <<value comparisons>>=
 44 	def __eq__( self, another ) :
 45 		return self.val == another.val
 46 
 47 	def __gt__( self, another ) :
 48 		return self.val > another.val
 49 
 50 	def __lt__( self, another ) :
 51 		return self.val < another.val
 52 @ text
 53 
 54 <<query children>>=
 55 	def am_leaf( self ) :
 56 		return self.less is None and self.more is None
 57 
 58 	def less_is_empty( self ) :
 59 		return self.less is None
 60 
 61 	def more_is_empty( self ) :
 62 		return self.more is None
 63 @ text
 64 
 65 <<bst>>=
 66 class Bst( object ) :
 67 <<constructor>>
 68 <<insertion>>
 69 <<search>>
 70 <<deletion>>
 71 <<enumerate>>
 72 <<print>>
 73 <<advanced interfaces>>
 74 @ text
 75 
 76 <<constructor>>=
 77 	def __init__( self, first=None ) :
 78 		self.root = None
 79 		if first is None :
 80 			return
 81 		elif isinstance( first, list ) :
 82 			self._add_multiple( first )
 83 		else :
 84 			self.add( first )
 85 @ text
 86 
 87 <<insertion>>=
 88 <<client add>>
 89 <<add multiple>>
 90 <<add single>>
 91 @ text
 92 
 93 <<client add>>=
 94 	def add( self, wanted ) :
 95 		if isinstance( wanted, list ) :
 96 			self._add_multiple( wanted )
 97 		elif self.is_empty() :
 98 			self.root = Node( wanted )
 99 		else :
100 			insertion = Node( wanted )
101 			self._add_leaf( self.root, insertion )
102 @ text
103 
104 <<add multiple>>=
105 	def _add_multiple( self, wanted_vals ) :
106 		for val in wanted_vals :
107 			self.add( val )
108 @ text
109 
110 <<add single>>=
111 	def _add_leaf( self, comparison, new_node ) : 
112 		'currently, not checking until I enter'
113 		if comparison == new_node :
114 			return # no duplicates
115 		elif comparison > new_node :
116 			if comparison.less_is_empty( ) :
117 				comparison.change_less( new_node )
118 			else :
119 				self._add_leaf( comparison.g_less( ), new_node )
120 		else :
121 			if comparison.more_is_empty( ) :
122 				comparison.change_more( new_node )
123 			else :
124 				self._add_leaf( comparison.g_more( ), new_node )
125 @ text
126 
127 <<insert tests>>=
128 def should_insert( tree ) :
129 	flag = should_add_to_empty( tree )
130 	flag = should_add_to_root_leaf( tree ) or flag
131 	flag = should_add_multiple( tree ) or flag
132 	flag = should_not_add_copy( tree ) or flag
133 	return flag
134 <<T I empty tree>>
135 <<T I to root>>
136 <<T I to a child>>
137 <<T I multiple>>
138 <<T I redundant>>
139 @ text
140 
141 <<T I empty tree>>=
142 def should_add_to_empty( tree ) :
143 	if not tree.is_empty( ) :
144 		tree.erase( )
145 	root_v = 'aa'
146 	tree.add( root_v )
147 	if not tree.root.g_val() == root_v :
148 		print "I> didn't add val to empty tree"
149 		return something_wrong
150 	tree.erase( )
151 	return seems_okay
152 @ text
153 
154 <<T I to root>>=
155 def should_add_to_root_leaf( tree ) :
156 	root_v = -12
157 	new_val = 21
158 	tree.add( root_v )
159 	tree.add( new_val )
160 	if tree.root.am_leaf( ) :
161 		print "I> didn't add val to a node"
162 		return something_wrong
163 	elif tree.root.more_is_empty() :
164 		print "I> added new node to opposite side"
165 		return something_wrong
166 	elif tree.root.g_more( ).g_val() != new_val :
167 		print "I> added to right side, wrong value"
168 		return something_wrong
169 	return seems_okay
170 @ text
171 
172 <<T I multiple>>=
173 def should_add_multiple( tree ) :
174 	#print "I> doesn't test multiple yet"
175 	tree.erase()
176 	root_val = .5
177 	l_child = .25
178 	lis = [root_val, l_child]
179 	tree.add(lis)
180 	if not tree.root.g_val() == root_val :
181 		print "I> multiple didn't deposit first val"
182 		return something_wrong
183 	elif not tree.root.g_less().g_val() == l_child :
184 		print "I> multiple didn't add second val"
185 		return something_wrong
186 	return seems_okay
187 @ text
188 
189 <<T I redundant>>=
190 def should_not_add_copy( tree ) :
191 	tree.erase()
192 	root_v = 'do'
193 	child = 're'
194 	tree.add( root_v )
195 	tree.add( root_v )
196 	if not tree.root.am_leaf() :
197 		print "I> added a second copy of a val"
198 		return something_wrong
199 	tree.add( child )
200 	tree.add( child )
201 	if not tree.root.g_more().am_leaf() :
202 		print "I> added redundant node to interior"
203 		return something_wrong
204 	tree.add( root_v )
205 	root_okay = tree.root.less_is_empty()
206 	child_okay = tree.root.g_more().am_leaf()
207 	if not root_okay or not child_okay :
208 		print "I> added redundant on second try"
209 		return something_wrong
210 	return seems_okay
211 @ text
212 
213 <<search>>=
214 <<client find>>
215 <<find node>>
216 @ text
217 
218 <<client find>>=
219 	def confirm( self, desire ) :
220 		if self.is_empty() :
221 			return False
222 		elif self.root.g_val() == desire :
223 			return True
224 		else :
225 			fake = Node( desire )
226 			result = self._find( self.root, fake )
227 			if result is None :
228 				return False
229 			else : # found
230 				return True	
231 @ text
232 
233 <<find node>>=
234 	def _find( self, maybe, unconfirmed ) :
235 		if maybe < unconfirmed :
236 			maybe = maybe.g_more()
237 			if maybe is None :
238 				return maybe # failure
239 			elif maybe == unconfirmed :
240 				return maybe # success
241 			else :
242 				return self._find( maybe, unconfirmed )
243 		else : # maybe > unconfirmed
244 			maybe = maybe.g_less()
245 			if maybe == unconfirmed or maybe is None :
246 				return maybe
247 			else :
248 				return self._find( maybe, unconfirmed )
249 @ text
250 
251 <<search tests>>=
252 def should_confirm( tree ) :
253 	tree.erase()
254 	root_v = 4
255 	val_yes = 5
256 	val_no = val_yes + val_yes
257 	bunch = [ root_v, 3, 6, val_yes]
258 	if tree.confirm( val_no ) :
259 		print "C> confirmed value when tree empty"
260 		return something_wrong
261 	tree.add( bunch )
262 	if not tree.confirm( root_v ) :
263 		print "C> didn't confirm root's value"
264 		return something_wrong
265 	elif not tree.confirm( val_yes ) :
266 		print "C> didn't find key in subtree"
267 		return something_wrong
268 	elif tree.confirm( val_no ) :
269 		print "C> tree thinks it contains an uninserted value"
270 		return something_wrong
271 	else :
272 		return seems_okay
273 @ text
274 
275 <<deletion>>=
276 <<perform delete>>
277 <<deletion cases>>
278 <<deletion utilities>>
279 @ text
280 
281 <<perform delete>>=
282 	def delete( self, unwanted_val ) :
283 		if self.is_empty() :
284 			return
285 		elif self.root.g_val() == unwanted_val :
286 			self._delete_root()
287 		else :
288 			obsolete = Node( unwanted_val )
289 			ancestor_stack = [ ]
290 			ancestor_stack = self._path_to_obsolete( obsolete, self.root, ancestor_stack )
291 			if ancestor_stack[ -1 ] is None :
292 				return
293 			else :
294 				self._perform_delete( ancestor_stack )
295 <<select case>>
296 @ text
297 
298 <<prep delete>>=
299 o_less_Leaf = True
300 obsolete = ancestor_stack.pop( )
301 parent = ancestor_stack.pop( )
302 o_was_less = obsolete < parent
303 <<cleanup root>>
304 @ text
305 
306 <<select case>>=
307 	def _perform_delete( self, ancestor_stack ) :
308 		<<prep delete>>
309 		if obsolete.am_leaf() :
310 			self._update_parent( parent_of_o, None, o_was_less )
311 		elif obsolete.less_is_empty() :
312 			self._replace_with_solo( parent, o_was_less, obsolete, o_less_Leaf )
313 		elif obsolete.more_is_empty() :
314 			self._replace_with_solo( parent, o_was_less, obsolete, not o_less_Leaf )
315 		else : # two children
316 			self._replace_with_two_children( parent, o_was_less, obsolete )
317 @ text
318 
319 <<cleanup root>>=
320 	def _delete_root( self ) :
321 		fake = Node( self.root.g_val() + self.root.g_val() )
322 		fake_stack = [fake, self.root]
323 		self._perform_delete( fake_stack )
324 		if fake.less_is_empty() :
325 			self.root = fake.g_more()
326 		else :
327 			self.root = fake.g_less()
328 @ text
329 
330 <<deletion cases>>=
331 <<update parent>>
332 <<single child replaces>>
333 <<resolve parent of two>>
334 @ text
335 
336 <<update parent>>=
337 	def _update_parent( self, parent, replacer, from_less ) :
338 		if from_less :
339 			parent.change_less( replacer )
340 		else :
341 			parent.change_more( replacer )
342 @ text
343 
344 <<single child replaces>>=
345 	def _replace_with_solo( self, parent, from_less, obsolete, o_less_Leaf ) :
346 		if o_less_Leaf :
347 			self._update_parent( parent_of_o, obsolete.g_more(), from_less )
348 		else : # more is empty
349 			self._update_parent( parent_of_o, obsolete.g_less(), from_less )
350 @ text
351 
352 <<resolve parent of two>>=
353 	def _replace_with_two_children( self, parent, from_less, obsolete ) :
354 		left_replace = obsolete.g_val() % 2 == 0 # magic, or use rand_bool( )
355 		if left_replace :
356 			replacer, reps_parent = self._max_and_parent( obsolete.g_less(), obsolete )
357 			self._less_replace_2_kid( parent, from_less, obsolete, replacer, reps_parent )
358 		else : # right_replace
359 			replacer, reps_parent = self._min_and_parent( obsolete.g_more( ), obsolete )
360 			self._more_replace_2_kid( parent, from_less, obsolete, replacer, reps_parent )
361 <<del 2, less>>
362 <<del 2, more>>
363 @ text
364 
365 <<del 2, less>>=
366 	def _less_replace_2_kid( self, parent, from_less, obsolete, replacer, reps_parent ) :
367 		if reps_parent is obsolete :
368 			replacer.change_more( obsolete.g_more() )
369 			o_less_Leaf = True
370 			self._replace_with_solo( parent, from_less, obsolete, not o_less_Leaf )
371 		else :
372 			self._update_parent( parent, replacer, from_less )
373 			replacer.change_more( obsolete.g_more() )
374 			reps_parent.change_more( replacer.g_less() )
375 			replacer.change_less( obsolete.g_less() )
376 @ text
377 
378 <<del 2, more>>=
379 	def _more_replace_2_kid( self, parent, from_less, obsolete, replacer, reps_parent ) :
380 		if reps_parent is obsolete :
381 			replacer.change_less( obsolete.g_less() )
382 			o_less_Leaf = True
383 			self._replace_with_solo( parent, from_less, obsolete, o_less_Leaf )
384 		else :
385 			self._update_parent( parent, replacer, from_less )
386 			replacer.change_less( obsolete.g_less() )
387 			reps_parent.change_less( replacer.g_more() ) # is this right?
388 			replacer.change_more( obsolete.g_more() )
389 @ text
390 
391 <<deletion utilities>>=
392 	def _path_to_obsolete( self, obsolete, focus, ancestorStack ) :
393 		ancestorStack.append( focus )
394 		if focus is None or focus == obsolete :
395 			return ancestorStack
396 		else :
397 			if focus < obsolete :
398 				return self._path_to_obsolete( obsolete, focus.g_more( ), ancestorStack )
399 			else :
400 				return self._path_to_obsolete( obsolete, focus.g_less( ), ancestorStack )
401 
402 	def _max_and_parent( self, a_child, a_root ) :
403 		if a_child.more_is_empty() :
404 			return a_child, a_root
405 		else :
406 			return self._max_and_parent( a_child.g_more(), a_child )
407 
408 	def _min_and_parent( self, a_child, a_root ) :
409 		if a_child.less_is_empty() :
410 			return a_child, a_root
411 		# else :
412 		while not a_child.less_is_empty() :
413 			a_root = a_child
414 			a_child = a_child.g_less()
415 		return a_child, a_root
416 @ text
417 
418 <<delete tests>>=
419 def should_delete( tree ) :
420 	print "D> doesn't test deletion AT ALL"
421 	flag = test_deletion_cases( tree )
422 	flag = test_deletion_utilities( tree ) or flag
423 	return something_wrong
424 
425 def test_deletion_cases( tree ) :
426 	flag = should_D_leaf_root( tree )
427 	flag = should_D_only_child( tree ) or flag
428 	flag = should_D_replace_w_sole( tree ) or flag
429 	flag = should_D_with_2( tree ) or flag
430 	#flag = ( tree ) or flag
431 	return flag
432 
433 def should_D_leaf_root( tree ) :
434 	tree.erase()
435 	val = 5
436 	tree.add( val )
437 	tree.delete( val )
438 	if not tree.is_empty() :
439 		print "D> solitary root didn't delete"
440 		return something_wrong
441 	else :
442 		return seems_okay
443 
444 def should_D_only_child( tree ) :
445 	ro = 4
446 	l_ch = 3
447 	r_ch = 5
448 	tree.add( ro )
449 	tree.add( l_ch )
450 	tree.delete( l_ch )
451 	if not tree.root.am_leaf() :
452 		print "D> didn't cut solitary less child"
453 		return something_wrong
454 	tree.add( r_ch )
455 	tree.delete( r_ch )
456 	if not tree.root.am_leaf() :
457 		print "D> didn't cut solitary more child"
458 		return something_wrong
459 	tree.erase()
460 	return seems_okay
461 
462 def should_D_replace_w_sole( tree ) :
463 	tree.erase()
464 	mid_v = 'm'
465 	l_ch = 'd'
466 	r_ch = 'r'
467 	tree.add( [ mid_v, l_ch ] )
468 	tree.delete( mid_v )
469 	# from root
470 	if not tree.root.g_val() == l_ch :
471 		print "D> root not replaced by sole (less) child"
472 		return something_wrong
473 	# from interior
474 	tree.add( [ mid_v, r_ch ] )
475 	tree.delete( mid_v )
476 	if not tree.root.g_more().g_val() != r_ch :
477 		print "D> "
478 		return something_wrong
479 	else :
480 		return seems_okay
481 
482 def should_D_with_2( tree ) : # fill
483 	print "D> doesn't test deleting with two children"
484 	return
485 
486 def test_deletion_utilities( tree ) : # verify
487 	flag = should_get_parent( tree ) # get that hotkey thing
488 	flag = should_get_min_max( tree ) or flag
489 	return flag
490 
491 def should_get_parent( tree ) : # verify
492 	left_val = 3
493 	root_val = 5
494 	between_val = 6
495 	parent_val = 7
496 	outer_val = 8
497 	from_left = True
498 	tree.add( root_val )
499 	tree.add( left_val )
500 	tree.add( parent_val )
501 	tree.add( between_val )
502 	tree.add( outer_val )
503 	print "D> does not Test get_path()"
504 	return something_wrong
505 
506 def should_get_min_max( tree ) : # verify
507 	left_val = 3
508 	root_val = 5
509 	between_val = 6
510 	parent_val = 7
511 	outer_val = 8
512 	from_left = True
513 	tree.add( root_val )
514 	tree.add( left_val )
515 	tree.add( parent_val )
516 	tree.add( between_val )
517 	tree.add( outer_val )
518 	print "D> DOESN'T TEST MIN/MAX"
519 	return something_wrong
520 @ text
521 
522 <<enumerate>>=
523 	def g_all_elements( self ) :
524 		everything = []
525 		if self.root is None :
526 			return everything
527 		else :
528 			everything = self._traverse( self.root, everything )
529 			return everything
530 
531 	def _traverse( self, focus, container ) :
532 		'in order, obviously'
533 		if focus is None :
534 			return container
535 		else :
536 			container = self._traverse( focus.g_less(), container )
537 			container.push( focus.g_val() )
538 			container = self._traverse( focus.g_more(), container )
539 			return container
540 
541 	def is_empty( self ) :
542 		return self.root is None
543 
544 	def erase( self ) :
545 		self.root = None
546 @ text
547 
548 <<enumeration tests>>=
549 def should_traverse( tree ) :
550 	tree.erase()
551 	bunch = [ 4, 2, 1, 3, 7, 5, 8 ]
552 	tree.add( bunch )
553 	bundle = tree.g_all_elements()
554 	bunch.sort()
555 	for elem in range( 0, bunch.__len__() - 1 )	:
556 		if not bundle[ elem ] == bunch[ elem ] :
557 			print "T> ret " + str( bundle[ elem ] ) + " is not supp " + str( bunch[ elem ] )
558 			print bundle
559 			return something_wrong
560 	tree.erase
561 	return seems_okay
562 @ text
563 
564 <<print>>=
565 	def pr_hV( self ) :
566 		if tree.is_empty() :
567 			print ">--"
568 		else :
569 			print "v"
570 			self._pr_90( [ self.root ] )
571 
572 	def _pr_hV( self, pr_stack ) :
573 		vert = pr_stack.__len__() - 1
574 		if vert >= 0 :
575 			self._pr_90_links( pr_stack, vert + 1 )
576 			print
577 			self._pr_90_links( pr_stack, vert )
578 			pr_stack = self._pr_90_row( pr_stack )
579 			self._pr_90( pr_stack )
580 
581 	def _pr_hV_links( self, pr_stack, vert ) : # test this addition
582 		for ind in range( 0, vert ) :
583 			nn = pr_stack[ ind ]
584 			if nn is None :
585 				print "  ",
586 			else :
587 				print "| ",
588 
589 	def _pr_hV_row( self, pr_stack ) :
590 		## python print \n suppression substitutes a space
591 		row_str = []
592 		focus = pr_stack.pop()
593 		while not focus is None :
594 			row_str.append( str( focus.g_val() ) )
595 			if not focus.less_is_empty() :
596 				pr_stack.append( focus.g_less() )
597 			elif not focus.more_is_empty() :
598 				pr_stack.append( None ),		
599 			if not focus.more_is_empty() :
600 				row_str.append( "-" )
601 			focus = focus.g_more()
602 		row_str = ''.join( row_str ) # turn list to string.
603 		print row_str
604 		#self._pr_node_stack( pr_stack )
605 		pr_stack = self._strip_placeholders( pr_stack )
606 		return pr_stack
607 
608 	def _strip_placeholders( self, pr_stack ) :
609 		'ie None'
610 		focus = None
611 		while pr_stack.__len__() > 0 :
612 			focus = pr_stack.pop()
613 			if not focus is None :
614 				pr_stack.append( focus )
615 				break
616 		return pr_stack
617 @ text
618 
619 <<tests>>=
620 <<test framework>>
621 <<node tests>>
622 <<insert tests>>
623 <<search tests>>
624 <<deletion tests>>
625 <<enumeration tests>>
626 <<advanced tests>>
627 @ text
628 
629 <<test framework>>=
630 tree = Bst()
631 something_wrong = True
632 seems_okay = not something_wrong
633 status = seems_okay # at least initially
634 print "\n\t PROBLEMS"
635 status = node_should_work() or status
636 status = should_erase()  or status
637 status = should_insert( tree ) or status # propagates truth
638 status = should_confirm( tree ) or status
639 status = should_delete( tree ) or status
640 status = should_traverse( tree ) or status
641 if seems_okay :
642 	print "> Silent test run"
643 else :
644 	print "\n<> so go fix that"
645 #check_by_eye( tree )
646 @ text
647 


hijacker
hijacker
hijacker
hijacker

build.log

1 Sorry: IndentationError: ('unexpected indent', ('/tmp/litprog3241555/Bst.py', 140, 3, '\t\t\tdef _delete_root( self ) :\n'))


noweb.log

1 undefined chunk name: <<advanced interfaces>>
2 undefined chunk name: <<node tests>>
3 undefined chunk name: <<T I to a child>>
4 undefined chunk name: <<deletion tests>>
5 undefined chunk name: <<advanced tests>>