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

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

Issue 451633003: Make Iterable.toSet say that it returns a Set with the same equality as the Iterable's contains met… (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 6 years, 4 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
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 typedef bool _Predicate<T>(T value); 7 typedef bool _Predicate<T>(T value);
8 8
9 /** 9 /**
10 * A node in a splay tree. It holds the sorting key and the left 10 * A node in a splay tree. It holds the sorting key and the left
(...skipping 579 matching lines...) Expand 10 before | Expand all | Expand 10 after
590 T _getValue(_SplayTreeNode node); 590 T _getValue(_SplayTreeNode node);
591 } 591 }
592 592
593 class _SplayTreeKeyIterable<K> extends IterableBase<K> 593 class _SplayTreeKeyIterable<K> extends IterableBase<K>
594 implements EfficientLength { 594 implements EfficientLength {
595 _SplayTree<K> _tree; 595 _SplayTree<K> _tree;
596 _SplayTreeKeyIterable(this._tree); 596 _SplayTreeKeyIterable(this._tree);
597 int get length => _tree._count; 597 int get length => _tree._count;
598 bool get isEmpty => _tree._count == 0; 598 bool get isEmpty => _tree._count == 0;
599 Iterator<K> get iterator => new _SplayTreeKeyIterator<K>(_tree); 599 Iterator<K> get iterator => new _SplayTreeKeyIterator<K>(_tree);
600 Set<K> toSet() {
601 SplayTreeSet<K> set =
602 new SplayTreeSet<K>(_tree._comparator, _tree._validKey);
603 set._count = _tree._count;
604 set._root = set._copyNode(_tree._root);
605 return set;
606 }
600 } 607 }
601 608
602 class _SplayTreeValueIterable<K, V> extends IterableBase<V> 609 class _SplayTreeValueIterable<K, V> extends IterableBase<V>
603 implements EfficientLength { 610 implements EfficientLength {
604 SplayTreeMap<K, V> _map; 611 SplayTreeMap<K, V> _map;
605 _SplayTreeValueIterable(this._map); 612 _SplayTreeValueIterable(this._map);
606 int get length => _map._count; 613 int get length => _map._count;
607 bool get isEmpty => _map._count == 0; 614 bool get isEmpty => _map._count == 0;
608 Iterator<V> get iterator => new _SplayTreeValueIterator<K, V>(_map); 615 Iterator<V> get iterator => new _SplayTreeValueIterator<K, V>(_map);
609 } 616 }
(...skipping 162 matching lines...) Expand 10 before | Expand all | Expand 10 after
772 return result; 779 return result;
773 } 780 }
774 781
775 Set<E> union(Set<E> other) { 782 Set<E> union(Set<E> other) {
776 return _clone()..addAll(other); 783 return _clone()..addAll(other);
777 } 784 }
778 785
779 SplayTreeSet<E> _clone() { 786 SplayTreeSet<E> _clone() {
780 var set = new SplayTreeSet<E>(_comparator, _validKey); 787 var set = new SplayTreeSet<E>(_comparator, _validKey);
781 set._count = _count; 788 set._count = _count;
782 set._root = _cloneNode(_root); 789 set._root = _copyNode(_root);
783 return set; 790 return set;
784 } 791 }
785 792
786 _SplayTreeNode<E> _cloneNode(_SplayTreeNode<E> node) { 793 // Copies the structure of a SplayTree into a new similar structure.
794 // Works on _SplayTreeMapNode as well, but only copies the keys,
795 _SplayTreeNode<E> _copyNode(_SplayTreeNode<E> node) {
787 if (node == null) return null; 796 if (node == null) return null;
788 return new _SplayTreeNode<E>(node.key)..left = _cloneNode(node.left) 797 return new _SplayTreeNode<E>(node.key)..left = _copyNode(node.left)
789 ..right = _cloneNode(node.right); 798 ..right = _copyNode(node.right);
790 } 799 }
791 800
792 void clear() { _clear(); } 801 void clear() { _clear(); }
793 802
794 Set<E> toSet() => _clone(); 803 Set<E> toSet() => _clone();
795 804
796 String toString() => IterableBase.iterableToFullString(this, '{', '}'); 805 String toString() => IterableBase.iterableToFullString(this, '{', '}');
797 } 806 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698