| OLD | NEW |
| 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 /** | 5 /** |
| 6 * A node in a splay tree. It holds the key, the value and the left | 6 * A node in a splay tree. It holds the key, the value and the left |
| 7 * and right children in the tree. | 7 * and right children in the tree. |
| 8 */ | 8 */ |
| 9 class SplayTreeNode<K, V> { | 9 class SplayTreeNode<K, V> { |
| 10 SplayTreeNode(K this.key, V this.value); | 10 SplayTreeNode(K this.key, V this.value); |
| (...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 44 } | 44 } |
| 45 | 45 |
| 46 /** | 46 /** |
| 47 * Perform the splay operation for the given key. Moves the node with | 47 * Perform the splay operation for the given key. Moves the node with |
| 48 * the given key to the top of the tree. If no node has the given | 48 * the given key to the top of the tree. If no node has the given |
| 49 * key, the last node on the search path is moved to the top of the | 49 * key, the last node on the search path is moved to the top of the |
| 50 * tree. This is the simplified top-down splaying algorithm from: | 50 * tree. This is the simplified top-down splaying algorithm from: |
| 51 * "Self-adjusting Binary Search Trees" by Sleator and Tarjan. | 51 * "Self-adjusting Binary Search Trees" by Sleator and Tarjan. |
| 52 */ | 52 */ |
| 53 void splay_(K key) { | 53 void splay_(K key) { |
| 54 if (isEmpty()) return; | 54 if (isEmpty) return; |
| 55 | 55 |
| 56 // The right child of the dummy node will hold | 56 // The right child of the dummy node will hold |
| 57 // the L tree of the algorithm. The left child of the dummy node | 57 // the L tree of the algorithm. The left child of the dummy node |
| 58 // will hold the R tree of the algorithm. Using a dummy node, left | 58 // will hold the R tree of the algorithm. Using a dummy node, left |
| 59 // and right will always be nodes and we avoid special cases. | 59 // and right will always be nodes and we avoid special cases. |
| 60 SplayTreeNode<K, V> left = _dummy; | 60 SplayTreeNode<K, V> left = _dummy; |
| 61 SplayTreeNode<K, V> right = _dummy; | 61 SplayTreeNode<K, V> right = _dummy; |
| 62 SplayTreeNode<K, V> current = _root; | 62 SplayTreeNode<K, V> current = _root; |
| 63 while (true) { | 63 while (true) { |
| 64 int comp = key.compareTo(current.key); | 64 int comp = key.compareTo(current.key); |
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 99 right.left = current.right; | 99 right.left = current.right; |
| 100 current.left = _dummy.right; | 100 current.left = _dummy.right; |
| 101 current.right = _dummy.left; | 101 current.right = _dummy.left; |
| 102 _root = current; | 102 _root = current; |
| 103 | 103 |
| 104 _dummy.right = null; | 104 _dummy.right = null; |
| 105 _dummy.left = null; | 105 _dummy.left = null; |
| 106 } | 106 } |
| 107 | 107 |
| 108 V operator [](K key) { | 108 V operator [](K key) { |
| 109 if (!isEmpty()) { | 109 if (!isEmpty) { |
| 110 splay_(key); | 110 splay_(key); |
| 111 if (_root.key.compareTo(key) == 0) return _root.value; | 111 if (_root.key.compareTo(key) == 0) return _root.value; |
| 112 } | 112 } |
| 113 return null; | 113 return null; |
| 114 } | 114 } |
| 115 | 115 |
| 116 V remove(K key) { | 116 V remove(K key) { |
| 117 if (isEmpty()) return null; | 117 if (isEmpty) return null; |
| 118 splay_(key); | 118 splay_(key); |
| 119 if (_root.key.compareTo(key) != 0) return null; | 119 if (_root.key.compareTo(key) != 0) return null; |
| 120 V value = _root.value; | 120 V value = _root.value; |
| 121 | 121 |
| 122 _count--; | 122 _count--; |
| 123 // assert(_count >= 0); | 123 // assert(_count >= 0); |
| 124 if (_root.left === null) { | 124 if (_root.left === null) { |
| 125 _root = _root.right; | 125 _root = _root.right; |
| 126 } else { | 126 } else { |
| 127 SplayTreeNode<K, V> right = _root.right; | 127 SplayTreeNode<K, V> right = _root.right; |
| 128 _root = _root.left; | 128 _root = _root.left; |
| 129 // Splay to make sure that the new root has an empty right child. | 129 // Splay to make sure that the new root has an empty right child. |
| 130 splay_(key); | 130 splay_(key); |
| 131 // Insert the original right child as the right child of the new | 131 // Insert the original right child as the right child of the new |
| 132 // root. | 132 // root. |
| 133 _root.right = right; | 133 _root.right = right; |
| 134 } | 134 } |
| 135 return value; | 135 return value; |
| 136 } | 136 } |
| 137 | 137 |
| 138 void operator []=(K key, V value) { | 138 void operator []=(K key, V value) { |
| 139 if (isEmpty()) { | 139 if (isEmpty) { |
| 140 _count++; | 140 _count++; |
| 141 _root = new SplayTreeNode(key, value); | 141 _root = new SplayTreeNode(key, value); |
| 142 return; | 142 return; |
| 143 } | 143 } |
| 144 // Splay on the key to move the last node on the search path for | 144 // Splay on the key to move the last node on the search path for |
| 145 // the key to the root of the tree. | 145 // the key to the root of the tree. |
| 146 splay_(key); | 146 splay_(key); |
| 147 if (_root.key.compareTo(key) == 0) { | 147 if (_root.key.compareTo(key) == 0) { |
| 148 _root.value = value; | 148 _root.value = value; |
| 149 return; | 149 return; |
| (...skipping 13 matching lines...) Expand all Loading... |
| 163 _root = node; | 163 _root = node; |
| 164 } | 164 } |
| 165 | 165 |
| 166 V putIfAbsent(K key, V ifAbsent()) { | 166 V putIfAbsent(K key, V ifAbsent()) { |
| 167 if (containsKey(key)) return this[key]; | 167 if (containsKey(key)) return this[key]; |
| 168 V value = ifAbsent(); | 168 V value = ifAbsent(); |
| 169 this[key] = value; | 169 this[key] = value; |
| 170 return value; | 170 return value; |
| 171 } | 171 } |
| 172 | 172 |
| 173 bool isEmpty() { | 173 bool get isEmpty { |
| 174 // assert(!((_root === null) && (_count != 0))); | 174 // assert(!((_root === null) && (_count != 0))); |
| 175 // assert(!((_count == 0) && (_root !== null))); | 175 // assert(!((_count == 0) && (_root !== null))); |
| 176 return (_root === null); | 176 return (_root === null); |
| 177 } | 177 } |
| 178 | 178 |
| 179 void forEach(void f(K key, V value)) { | 179 void forEach(void f(K key, V value)) { |
| 180 List<SplayTreeNode<K, V>> list = new List<SplayTreeNode<K, V>>(); | 180 List<SplayTreeNode<K, V>> list = new List<SplayTreeNode<K, V>>(); |
| 181 SplayTreeNode<K, V> current = _root; | 181 SplayTreeNode<K, V> current = _root; |
| 182 while (current !== null) { | 182 while (current !== null) { |
| 183 if (current.left !== null) { | 183 if (current.left !== null) { |
| 184 list.add(current); | 184 list.add(current); |
| 185 current = current.left; | 185 current = current.left; |
| 186 } else { | 186 } else { |
| 187 f(current.key, current.value); | 187 f(current.key, current.value); |
| 188 while (current.right === null) { | 188 while (current.right === null) { |
| 189 if (list.isEmpty()) return; | 189 if (list.isEmpty) return; |
| 190 current = list.removeLast(); | 190 current = list.removeLast(); |
| 191 f(current.key, current.value); | 191 f(current.key, current.value); |
| 192 } | 192 } |
| 193 current = current.right; | 193 current = current.right; |
| 194 } | 194 } |
| 195 } | 195 } |
| 196 } | 196 } |
| 197 | 197 |
| 198 int get length { | 198 int get length { |
| 199 return _count; | 199 return _count; |
| 200 } | 200 } |
| 201 | 201 |
| 202 void clear() { | 202 void clear() { |
| 203 _root = null; | 203 _root = null; |
| 204 _count = 0; | 204 _count = 0; |
| 205 } | 205 } |
| 206 | 206 |
| 207 bool containsKey(K key) { | 207 bool containsKey(K key) { |
| 208 if (!isEmpty()) { | 208 if (!isEmpty) { |
| 209 splay_(key); | 209 splay_(key); |
| 210 if (_root.key.compareTo(key) == 0) return true; | 210 if (_root.key.compareTo(key) == 0) return true; |
| 211 } | 211 } |
| 212 return false; | 212 return false; |
| 213 } | 213 } |
| 214 | 214 |
| 215 bool containsValue(V value) { | 215 bool containsValue(V value) { |
| 216 bool found = false; | 216 bool found = false; |
| 217 bool visit(SplayTreeNode node) { | 217 bool visit(SplayTreeNode node) { |
| 218 if (node === null) return false; | 218 if (node === null) return false; |
| (...skipping 78 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 297 if (node.key.compareTo(key) > 0) { | 297 if (node.key.compareTo(key) > 0) { |
| 298 return visit(node.left, node.key); | 298 return visit(node.left, node.key); |
| 299 } | 299 } |
| 300 if (node.key.compareTo(key) <= 0) { | 300 if (node.key.compareTo(key) <= 0) { |
| 301 return visit(node.right, ifEmpty); | 301 return visit(node.right, ifEmpty); |
| 302 } | 302 } |
| 303 } | 303 } |
| 304 return visit(_root, null); | 304 return visit(_root, null); |
| 305 } | 305 } |
| 306 } | 306 } |
| OLD | NEW |