| OLD | NEW |
|---|
| (Empty) |
| 1 # Copyright 2008 the V8 project authors. All rights reserved. | |
| 2 # Redistribution and use in source and binary forms, with or without | |
| 3 # modification, are permitted provided that the following conditions are | |
| 4 # met: | |
| 5 # | |
| 6 # * Redistributions of source code must retain the above copyright | |
| 7 # notice, this list of conditions and the following disclaimer. | |
| 8 # * Redistributions in binary form must reproduce the above | |
| 9 # copyright notice, this list of conditions and the following | |
| 10 # disclaimer in the documentation and/or other materials provided | |
| 11 # with the distribution. | |
| 12 # * Neither the name of Google Inc. nor the names of its | |
| 13 # contributors may be used to endorse or promote products derived | |
| 14 # from this software without specific prior written permission. | |
| 15 # | |
| 16 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
| 17 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
| 18 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
| 19 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
| 20 # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
| 21 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
| 22 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
| 23 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
| 24 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
| 25 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
| 26 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
| 27 | |
| 28 | |
| 29 class Node(object): | |
| 30 """Nodes in the splay tree.""" | |
| 31 | |
| 32 def __init__(self, key, value): | |
| 33 self.key = key | |
| 34 self.value = value | |
| 35 self.left = None | |
| 36 self.right = None | |
| 37 | |
| 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 | |
| 46 class SplayTree(object): | |
| 47 """The splay tree itself is just a reference to the root of the tree.""" | |
| 48 | |
| 49 def __init__(self): | |
| 50 """Create a new SplayTree.""" | |
| 51 self.root = None | |
| 52 | |
| 53 def IsEmpty(self): | |
| 54 """Is the SplayTree empty?""" | |
| 55 return not self.root | |
| 56 | |
| 57 def Insert(self, key, value): | |
| 58 """Insert a new node in the SplayTree.""" | |
| 59 # If the tree is empty, insert the new node. | |
| 60 if self.IsEmpty(): | |
| 61 self.root = Node(key, value) | |
| 62 return | |
| 63 # Splay on the key to move the last node on the search path for | |
| 64 # the key to the root of the tree. | |
| 65 self.Splay(key) | |
| 66 # Ignore repeated insertions with the same key. | |
| 67 if self.root.key == key: | |
| 68 return | |
| 69 # Insert the new node. | |
| 70 node = Node(key, value) | |
| 71 if key > self.root.key: | |
| 72 node.left = self.root | |
| 73 node.right = self.root.right | |
| 74 self.root.right = None | |
| 75 else: | |
| 76 node.right = self.root | |
| 77 node.left = self.root.left | |
| 78 self.root.left = None | |
| 79 self.root = node | |
| 80 | |
| 81 def Remove(self, key): | |
| 82 """Remove the node with the given key from the SplayTree.""" | |
| 83 # Raise exception for key that is not found if the tree is empty. | |
| 84 if self.IsEmpty(): | |
| 85 raise KeyNotFoundError(key) | |
| 86 # Splay on the key to move the node with the given key to the top. | |
| 87 self.Splay(key) | |
| 88 # Raise exception for key that is not found. | |
| 89 if self.root.key != key: | |
| 90 raise KeyNotFoundError(key) | |
| 91 removed = self.root | |
| 92 # Link out the root node. | |
| 93 if not self.root.left: | |
| 94 # No left child, so the new tree is just the right child. | |
| 95 self.root = self.root.right | |
| 96 else: | |
| 97 # Left child exists. | |
| 98 right = self.root.right | |
| 99 # Make the original left child the new root. | |
| 100 self.root = self.root.left | |
| 101 # Splay to make sure that the new root has an empty right child. | |
| 102 self.Splay(key) | |
| 103 # Insert the original right child as the right child of the new | |
| 104 # root. | |
| 105 self.root.right = right | |
| 106 return removed | |
| 107 | |
| 108 def Find(self, key): | |
| 109 """Returns the node with the given key or None if no such node exists.""" | |
| 110 if self.IsEmpty(): | |
| 111 return None | |
| 112 self.Splay(key) | |
| 113 if self.root.key == key: | |
| 114 return self.root | |
| 115 return None | |
| 116 | |
| 117 def FindMax(self): | |
| 118 """Returns the node with the largest key value.""" | |
| 119 if self.IsEmpty(): | |
| 120 return None | |
| 121 current = self.root | |
| 122 while current.right != None: | |
| 123 current = current.right | |
| 124 return current | |
| 125 | |
| 126 # Returns the node with the smallest key value. | |
| 127 def FindMin(self): | |
| 128 if self.IsEmpty(): | |
| 129 return None | |
| 130 current = self.root | |
| 131 while current.left != None: | |
| 132 current = current.left | |
| 133 return current | |
| 134 | |
| 135 def FindGreatestsLessThan(self, key): | |
| 136 """Returns node with greatest key less than or equal to the given key.""" | |
| 137 if self.IsEmpty(): | |
| 138 return None | |
| 139 # Splay on the key to move the node with the given key or the last | |
| 140 # node on the search path to the top of the tree. | |
| 141 self.Splay(key) | |
| 142 # Now the result is either the root node or the greatest node in | |
| 143 # the left subtree. | |
| 144 if self.root.key <= key: | |
| 145 return self.root | |
| 146 else: | |
| 147 tmp = self.root | |
| 148 self.root = self.root.left | |
| 149 result = self.FindMax() | |
| 150 self.root = tmp | |
| 151 return result | |
| 152 | |
| 153 def ExportValueList(self): | |
| 154 """Returns a list containing all the values of the nodes in the tree.""" | |
| 155 result = [] | |
| 156 nodes_to_visit = [self.root] | |
| 157 while len(nodes_to_visit) > 0: | |
| 158 node = nodes_to_visit.pop() | |
| 159 if not node: | |
| 160 continue | |
| 161 result.append(node.value) | |
| 162 nodes_to_visit.append(node.left) | |
| 163 nodes_to_visit.append(node.right) | |
| 164 return result | |
| 165 | |
| 166 def Splay(self, key): | |
| 167 """Perform splay operation. | |
| 168 | |
| 169 Perform the splay operation for the given key. Moves the node with | |
| 170 the given key to the top of the tree. If no node has the given | |
| 171 key, the last node on the search path is moved to the top of the | |
| 172 tree. | |
| 173 | |
| 174 This uses the simplified top-down splaying algorithm from: | |
| 175 | |
| 176 "Self-adjusting Binary Search Trees" by Sleator and Tarjan | |
| 177 | |
| 178 """ | |
| 179 if self.IsEmpty(): | |
| 180 return | |
| 181 # Create a dummy node. The use of the dummy node is a bit | |
| 182 # counter-intuitive: The right child of the dummy node will hold | |
| 183 # the L tree of the algorithm. The left child of the dummy node | |
| 184 # will hold the R tree of the algorithm. Using a dummy node, left | |
| 185 # and right will always be nodes and we avoid special cases. | |
| 186 dummy = left = right = Node(None, None) | |
| 187 current = self.root | |
| 188 while True: | |
| 189 if key < current.key: | |
| 190 if not current.left: | |
| 191 break | |
| 192 if key < current.left.key: | |
| 193 # Rotate right. | |
| 194 tmp = current.left | |
| 195 current.left = tmp.right | |
| 196 tmp.right = current | |
| 197 current = tmp | |
| 198 if not current.left: | |
| 199 break | |
| 200 # Link right. | |
| 201 right.left = current | |
| 202 right = current | |
| 203 current = current.left | |
| 204 elif key > current.key: | |
| 205 if not current.right: | |
| 206 break | |
| 207 if key > current.right.key: | |
| 208 # Rotate left. | |
| 209 tmp = current.right | |
| 210 current.right = tmp.left | |
| 211 tmp.left = current | |
| 212 current = tmp | |
| 213 if not current.right: | |
| 214 break | |
| 215 # Link left. | |
| 216 left.right = current | |
| 217 left = current | |
| 218 current = current.right | |
| 219 else: | |
| 220 break | |
| 221 # Assemble. | |
| 222 left.right = current.left | |
| 223 right.left = current.right | |
| 224 current.left = dummy.right | |
| 225 current.right = dummy.left | |
| 226 self.root = current | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 6614010:
[Isolates] Merge 6700:7030 from bleeding_edge to isolates. (Closed)
Base URL: http://v8.googlecode.com/svn/branches/experimental/isolates/