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 |