| 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 | 
|---|