Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 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 |