Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(161)

Side by Side Diff: sdk/lib/collection/splay_tree.dart

Issue 12298027: Revert "Make Comparable generic." (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 7 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « pkg/serialization/lib/src/basic_rule.dart ('k') | sdk/lib/core/comparable.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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 part of dart.collection; 5 part of dart.collection;
6 6
7 /** 7 /**
8 * A node in a splay tree. It holds the key, the value and the left 8 * A node in a splay tree. It holds the key, the value and the left
9 * and right children in the tree. 9 * and right children in the tree.
10 */ 10 */
11 class SplayTreeNode<K, V> { 11 class SplayTreeNode<K, V> {
12 final K key; 12 final K key;
13 V value; 13 V value;
14 SplayTreeNode<K, V> left; 14 SplayTreeNode<K, V> left;
15 SplayTreeNode<K, V> right; 15 SplayTreeNode<K, V> right;
16 16
17 SplayTreeNode(K this.key, V this.value); 17 SplayTreeNode(K this.key, V this.value);
18 } 18 }
19 19
20 /** 20 /**
21 * A splay tree is a self-balancing binary 21 * A splay tree is a self-balancing binary
22 * search tree with the additional property that recently accessed 22 * search tree with the additional property that recently accessed
23 * elements are quick to access again. It performs basic operations 23 * elements are quick to access again. It performs basic operations
24 * such as insertion, look-up and removal in O(log(n)) amortized time. 24 * such as insertion, look-up and removal in O(log(n)) amortized time.
25 * 25 *
26 * This implementation is a Dart version of the JavaScript 26 * This implementation is a Dart version of the JavaScript
27 * implementation in the V8 project. 27 * implementation in the V8 project.
28 */ 28 */
29 class SplayTreeMap<K extends Comparable<K>, V> implements Map<K, V> { 29 class SplayTreeMap<K extends Comparable, V> implements Map<K, V> {
30 30
31 // The root node of the splay tree. It will contain either the last 31 // The root node of the splay tree. It will contain either the last
32 // element inserted, or the last element looked up. 32 // element inserted, or the last element looked up.
33 SplayTreeNode<K, V> _root; 33 SplayTreeNode<K, V> _root;
34 34
35 // The dummy node used when performing a splay on the tree. It is a 35 // The dummy node used when performing a splay on the tree. It is a
36 // local field of the class to avoid allocating a node each time a 36 // local field of the class to avoid allocating a node each time a
37 // splay is performed. 37 // splay is performed.
38 SplayTreeNode<K, V> _dummy; 38 SplayTreeNode<K, V> _dummy;
39 39
(...skipping 414 matching lines...) Expand 10 before | Expand all | Expand 10 after
454 class _SplayTreeValueIterator<K, V> extends _SplayTreeIterator<V> { 454 class _SplayTreeValueIterator<K, V> extends _SplayTreeIterator<V> {
455 _SplayTreeValueIterator(SplayTreeMap<K, V> map): super(map); 455 _SplayTreeValueIterator(SplayTreeMap<K, V> map): super(map);
456 V _getValue(SplayTreeNode node) => node.value; 456 V _getValue(SplayTreeNode node) => node.value;
457 } 457 }
458 458
459 class _SplayTreeNodeIterator<K, V> 459 class _SplayTreeNodeIterator<K, V>
460 extends _SplayTreeIterator<SplayTreeNode<K, V>> { 460 extends _SplayTreeIterator<SplayTreeNode<K, V>> {
461 _SplayTreeNodeIterator(SplayTreeMap<K, V> map): super(map); 461 _SplayTreeNodeIterator(SplayTreeMap<K, V> map): super(map);
462 SplayTreeNode<K, V> _getValue(SplayTreeNode node) => node; 462 SplayTreeNode<K, V> _getValue(SplayTreeNode node) => node;
463 } 463 }
OLDNEW
« no previous file with comments | « pkg/serialization/lib/src/basic_rule.dart ('k') | sdk/lib/core/comparable.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698