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 18 matching lines...) Expand all Loading... |
29 class Node(object): | 29 class Node(object): |
30 """Nodes in the splay tree.""" | 30 """Nodes in the splay tree.""" |
31 | 31 |
32 def __init__(self, key, value): | 32 def __init__(self, key, value): |
33 self.key = key | 33 self.key = key |
34 self.value = value | 34 self.value = value |
35 self.left = None | 35 self.left = None |
36 self.right = None | 36 self.right = None |
37 | 37 |
38 | 38 |
| 39 class KeyNotFoundError(Exception): |
| 40 """KeyNotFoundError is raised when removing a non-existing node.""" |
| 41 |
| 42 def __init__(self, key): |
| 43 self.key = key |
| 44 |
| 45 |
39 class SplayTree(object): | 46 class SplayTree(object): |
40 """The splay tree itself is just a reference to the root of the tree.""" | 47 """The splay tree itself is just a reference to the root of the tree.""" |
41 | 48 |
42 def __init__(self): | 49 def __init__(self): |
43 """Create a new SplayTree.""" | 50 """Create a new SplayTree.""" |
44 self.root = None | 51 self.root = None |
45 | 52 |
46 def IsEmpty(self): | 53 def IsEmpty(self): |
47 """Is the SplayTree empty?""" | 54 """Is the SplayTree empty?""" |
48 return not self.root | 55 return not self.root |
(...skipping 19 matching lines...) Expand all Loading... |
68 else: | 75 else: |
69 node.right = self.root | 76 node.right = self.root |
70 node.left = self.root.left | 77 node.left = self.root.left |
71 self.root.left = None | 78 self.root.left = None |
72 self.root = node | 79 self.root = node |
73 | 80 |
74 def Remove(self, key): | 81 def Remove(self, key): |
75 """Remove the node with the given key from the SplayTree.""" | 82 """Remove the node with the given key from the SplayTree.""" |
76 # Raise exception for key that is not found if the tree is empty. | 83 # Raise exception for key that is not found if the tree is empty. |
77 if self.IsEmpty(): | 84 if self.IsEmpty(): |
78 raise Exception('KeyNotFound') | 85 raise KeyNotFoundError(key) |
79 # Splay on the key to move the node with the given key to the top. | 86 # Splay on the key to move the node with the given key to the top. |
80 self.Splay(key) | 87 self.Splay(key) |
81 # Raise exception for key that is not found. | 88 # Raise exception for key that is not found. |
82 if self.root.key != key: | 89 if self.root.key != key: |
83 raise Exception('KeyNotFound') | 90 raise KeyNotFoundError(key) |
84 removed = self.root | 91 removed = self.root |
85 # Link out the root node. | 92 # Link out the root node. |
86 if not self.root.left: | 93 if not self.root.left: |
87 # No left child, so the new tree is just the right child. | 94 # No left child, so the new tree is just the right child. |
88 self.root = self.root.right | 95 self.root = self.root.right |
89 else: | 96 else: |
90 # Left child exists. | 97 # Left child exists. |
91 right = self.root.right | 98 right = self.root.right |
92 # Make the original left child the new root. | 99 # Make the original left child the new root. |
93 self.root = self.root.left | 100 self.root = self.root.left |
(...skipping 116 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
210 left = current | 217 left = current |
211 current = current.right | 218 current = current.right |
212 else: | 219 else: |
213 break | 220 break |
214 # Assemble. | 221 # Assemble. |
215 left.right = current.left | 222 left.right = current.left |
216 right.left = current.right | 223 right.left = current.right |
217 current.left = dummy.right | 224 current.left = dummy.right |
218 current.right = dummy.left | 225 current.right = dummy.left |
219 self.root = current | 226 self.root = current |
OLD | NEW |