| OLD | NEW |
| 1 # Copyright 2008 the V8 project authors. All rights reserved. | 1 # Copyright 2008 the V8 project authors. All rights reserved. |
| 2 # Redistribution and use in source and binary forms, with or without | 2 # Redistribution and use in source and binary forms, with or without |
| 3 # modification, are permitted provided that the following conditions are | 3 # modification, are permitted provided that the following conditions are |
| 4 # met: | 4 # met: |
| 5 # | 5 # |
| 6 # * Redistributions of source code must retain the above copyright | 6 # * Redistributions of source code must retain the above copyright |
| 7 # notice, this list of conditions and the following disclaimer. | 7 # notice, this list of conditions and the following disclaimer. |
| 8 # * Redistributions in binary form must reproduce the above | 8 # * Redistributions in binary form must reproduce the above |
| 9 # copyright notice, this list of conditions and the following | 9 # copyright notice, this list of conditions and the following |
| 10 # disclaimer in the documentation and/or other materials provided | 10 # disclaimer in the documentation and/or other materials provided |
| (...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 68 else: | 68 else: |
| 69 node.right = self.root | 69 node.right = self.root |
| 70 node.left = self.root.left | 70 node.left = self.root.left |
| 71 self.root.left = None | 71 self.root.left = None |
| 72 self.root = node | 72 self.root = node |
| 73 | 73 |
| 74 def Remove(self, key): | 74 def Remove(self, key): |
| 75 """Remove the node with the given key from the SplayTree.""" | 75 """Remove the node with the given key from the SplayTree.""" |
| 76 # Raise exception for key that is not found if the tree is empty. | 76 # Raise exception for key that is not found if the tree is empty. |
| 77 if self.IsEmpty(): | 77 if self.IsEmpty(): |
| 78 raise 'KeyNotFound' | 78 raise Exception('KeyNotFound') |
| 79 # Splay on the key to move the node with the given key to the top. | 79 # Splay on the key to move the node with the given key to the top. |
| 80 self.Splay(key) | 80 self.Splay(key) |
| 81 # Raise exception for key that is not found. | 81 # Raise exception for key that is not found. |
| 82 if self.root.key != key: | 82 if self.root.key != key: |
| 83 raise 'KeyNotFound' | 83 raise Exception('KeyNotFound') |
| 84 removed = self.root | 84 removed = self.root |
| 85 # Link out the root node. | 85 # Link out the root node. |
| 86 if not self.root.left: | 86 if not self.root.left: |
| 87 # No left child, so the new tree is just the right child. | 87 # No left child, so the new tree is just the right child. |
| 88 self.root = self.root.right | 88 self.root = self.root.right |
| 89 else: | 89 else: |
| 90 # Left child exists. | 90 # Left child exists. |
| 91 right = self.root.right | 91 right = self.root.right |
| 92 # Make the original left child the new root. | 92 # Make the original left child the new root. |
| 93 self.root = self.root.left | 93 self.root = self.root.left |
| (...skipping 116 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 210 left = current | 210 left = current |
| 211 current = current.right | 211 current = current.right |
| 212 else: | 212 else: |
| 213 break | 213 break |
| 214 # Assemble. | 214 # Assemble. |
| 215 left.right = current.left | 215 left.right = current.left |
| 216 right.left = current.right | 216 right.left = current.right |
| 217 current.left = dummy.right | 217 current.left = dummy.right |
| 218 current.right = dummy.left | 218 current.right = dummy.left |
| 219 self.root = current | 219 self.root = current |
| OLD | NEW |