Chromium Code Reviews| OLD | NEW |
|---|---|
| 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, 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 class HashSet<E> extends Collection<E> implements Set<E> { | 7 class HashSet<E> extends Collection<E> with _SetMixin<E> implements Set<E> { |
|
floitsch
2013/04/05 12:38:17
I would prefer a common super-class (_SetBase ?) i
| |
| 8 static const int _INITIAL_CAPACITY = 8; | 8 static const int _INITIAL_CAPACITY = 8; |
| 9 final _HashTable<E> _table; | 9 final _HashTable<E> _table; |
| 10 | 10 |
| 11 HashSet() : _table = new _HashTable(_INITIAL_CAPACITY) { | 11 HashSet() : _table = new _HashTable(_INITIAL_CAPACITY) { |
| 12 _table._container = this; | 12 _table._container = this; |
| 13 } | 13 } |
| 14 | 14 |
| 15 factory HashSet.from(Iterable<E> iterable) { | 15 factory HashSet.from(Iterable<E> iterable) { |
| 16 return new HashSet<E>()..addAll(iterable); | 16 return new HashSet<E>()..addAll(iterable); |
| 17 } | 17 } |
| (...skipping 26 matching lines...) Expand all Loading... | |
| 44 return offset >= 0; | 44 return offset >= 0; |
| 45 } | 45 } |
| 46 | 46 |
| 47 void removeAll(Iterable objectsToRemove) { | 47 void removeAll(Iterable objectsToRemove) { |
| 48 for (Object object in objectsToRemove) { | 48 for (Object object in objectsToRemove) { |
| 49 _table._remove(object); | 49 _table._remove(object); |
| 50 _table._checkCapacity(); | 50 _table._checkCapacity(); |
| 51 } | 51 } |
| 52 } | 52 } |
| 53 | 53 |
| 54 void retainAll(Iterable objectsToRetain) { | |
| 55 IterableMixinWorkaround.retainAll(this, objectsToRetain); | |
| 56 } | |
| 57 | |
| 58 void _filterWhere(bool test(E element), bool removeMatching) { | 54 void _filterWhere(bool test(E element), bool removeMatching) { |
| 59 int entrySize = _table._entrySize; | 55 int entrySize = _table._entrySize; |
| 60 int length = _table._table.length; | 56 int length = _table._table.length; |
| 61 for (int offset = 0; offset < length; offset += entrySize) { | 57 for (int offset = 0; offset < length; offset += entrySize) { |
| 62 Object entry = _table._table[offset]; | 58 Object entry = _table._table[offset]; |
| 63 if (!_table._isFree(entry)) { | 59 if (!_table._isFree(entry)) { |
| 64 E key = identical(entry, _NULL) ? null : entry; | 60 E key = identical(entry, _NULL) ? null : entry; |
| 65 int modificationCount = _table._modificationCount; | 61 int modificationCount = _table._modificationCount; |
| 66 bool shouldRemove = (removeMatching == test(key)); | 62 bool shouldRemove = (removeMatching == test(key)); |
| 67 _table._checkModification(modificationCount); | 63 _table._checkModification(modificationCount); |
| (...skipping 10 matching lines...) Expand all Loading... | |
| 78 } | 74 } |
| 79 | 75 |
| 80 void retainWhere(bool test(E element)) { | 76 void retainWhere(bool test(E element)) { |
| 81 _filterWhere(test, false); | 77 _filterWhere(test, false); |
| 82 } | 78 } |
| 83 | 79 |
| 84 void clear() { | 80 void clear() { |
| 85 _table._clear(); | 81 _table._clear(); |
| 86 } | 82 } |
| 87 | 83 |
| 84 Set<E> _newSet() => new HashSet<E>(); | |
| 85 | |
| 86 String toString() => Collections.collectionToString(this); | |
|
floitsch
2013/04/05 12:38:17
move to _SetMixin.
| |
| 87 } | |
| 88 | |
| 89 // Implementation of Set methods shared by Set implementations. | |
| 90 abstract class _SetMixin<E> { | |
| 91 Set<E> _newSet(); | |
| 92 | |
| 88 // Set. | 93 // Set. |
| 89 bool isSubsetOf(Collection<E> other) { | 94 bool isSubsetOf(Collection<E> other) { |
| 90 // Deprecated, and using old signature. | 95 // Deprecated, and using old signature. |
| 91 Set otherSet; | 96 Set otherSet; |
| 92 if (other is Set) { | 97 if (other is Set) { |
| 93 otherSet = other; | 98 otherSet = other; |
| 94 } else { | 99 } else { |
| 95 otherSet = other.toSet(); | 100 otherSet = other.toSet(); |
| 96 } | 101 } |
| 97 return IterableMixinWorkaround.setContainsAll(otherSet, this); | 102 return otherSet.containsAll(this); |
| 98 } | 103 } |
| 99 | 104 |
| 100 bool containsAll(Iterable<E> other) { | 105 bool containsAll(Iterable<E> other) { |
| 101 return IterableMixinWorkaround.setContainsAll(this, other); | 106 for (E object in other) { |
| 107 if (_table._get(object) < 0) return false; | |
| 108 } | |
| 109 return true; | |
| 102 } | 110 } |
| 103 | 111 |
| 104 Set<E> intersection(Set<E> other) { | 112 Set<E> intersection(Set<E> other) { |
| 105 return IterableMixinWorkaround.setIntersection( | 113 Set<E> result = _newSet(); |
| 106 this, other, new HashSet<E>()); | 114 if (other.length < this.length) { |
| 115 for (E element in other) { | |
| 116 if (this.contains(element)) result.add(element); | |
| 117 } | |
| 118 } else { | |
| 119 for (E element in this) { | |
| 120 if (other.contains(element)) result.add(element); | |
| 121 } | |
| 122 } | |
| 123 return result; | |
| 107 } | 124 } |
| 108 | 125 |
| 109 Set<E> union(Set<E> other) { | 126 Set<E> union(Set<E> other) { |
| 110 return IterableMixinWorkaround.setUnion(this, other, new HashSet<E>()); | 127 return _newSet()..addAll(this)..addAll(other); |
| 111 } | 128 } |
| 112 | 129 |
| 113 Set<E> difference(Set<E> other) { | 130 Set<E> difference(Set<E> other) { |
| 114 return IterableMixinWorkaround.setDifference(this, other, new HashSet<E>()); | 131 HashSet<E> result = _newSet(); |
| 132 for (E element in this) { | |
| 133 if (!other.contains(element)) result.add(element); | |
| 134 } | |
| 135 return result; | |
| 115 } | 136 } |
| 116 | |
| 117 String toString() => Collections.collectionToString(this); | |
| 118 } | 137 } |
| OLD | NEW |