OLD | NEW |
---|---|
1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2011, 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.core; | 5 part of dart.core; |
6 | 6 |
7 /** | 7 /** |
8 * This class is the public interface of a set. A set is a collection | 8 * This class is the public interface of a set. A set is a collection |
9 * without duplicates. | 9 * without duplicates. |
10 */ | 10 */ |
(...skipping 14 matching lines...) Expand all Loading... | |
25 * Adds [value] into the set. The method has no effect if | 25 * Adds [value] into the set. The method has no effect if |
26 * [value] was already in the set. | 26 * [value] was already in the set. |
27 */ | 27 */ |
28 void add(E value); | 28 void add(E value); |
29 | 29 |
30 /** | 30 /** |
31 * Removes [value] from the set. Returns true if [value] was | 31 * Removes [value] from the set. Returns true if [value] was |
32 * in the set. Returns false otherwise. The method has no effect | 32 * in the set. Returns false otherwise. The method has no effect |
33 * if [value] value was not in the set. | 33 * if [value] value was not in the set. |
34 */ | 34 */ |
35 bool remove(E value); | 35 bool remove(Object value); |
floitsch
2013/01/17 13:36:58
make it "var" ?
Lasse Reichstein Nielsen
2013/01/18 11:41:48
Object is correct here. We only use ==, possibly h
| |
36 | 36 |
37 /** | 37 /** |
38 * Adds all the elements of the given [iterable] to the set. | 38 * Adds all the elements of the given [iterable] to the set. |
39 */ | 39 */ |
40 void addAll(Iterable<E> iterable); | 40 void addAll(Iterable<E> iterable); |
41 | 41 |
42 /** | 42 /** |
43 * Removes all the elements of the given collection from the set. | |
44 */ | |
45 void removeAll(Iterable<E> iterable); | |
46 | |
47 /** | |
48 * Returns true if [collection] contains all the elements of this | 43 * Returns true if [collection] contains all the elements of this |
49 * collection. | 44 * collection. |
50 */ | 45 */ |
51 bool isSubsetOf(Collection<E> collection); | 46 bool isSubsetOf(Collection<E> collection); |
52 | 47 |
53 /** | 48 /** |
54 * Returns true if this collection contains all the elements of | 49 * Returns true if this collection contains all the elements of |
55 * [collection]. | 50 * [collection]. |
56 */ | 51 */ |
57 bool containsAll(Collection<E> collection); | 52 bool containsAll(Collection<E> collection); |
58 | 53 |
59 /** | 54 /** |
60 * Returns a new set which is the intersection between this set and | 55 * Returns a new set which is the intersection between this set and |
61 * the given collection. | 56 * the given collection. |
62 */ | 57 */ |
63 Set<E> intersection(Collection<E> other); | 58 Set<E> intersection(Collection<E> other); |
64 | 59 |
65 /** | 60 /** |
66 * Removes all elements in the set. | 61 * Removes all elements in the set. |
67 */ | 62 */ |
68 void clear(); | 63 void clear(); |
64 } | |
69 | 65 |
70 } | |
71 | 66 |
72 abstract class HashSet<E> extends Set<E> { | 67 abstract class HashSet<E> extends Set<E> { |
73 factory HashSet() => new _HashSetImpl<E>(); | 68 factory HashSet() => new _HashSetImpl<E>(); |
74 | 69 |
75 /** | 70 /** |
76 * Creates a [Set] that contains all elements of [other]. | 71 * Creates a [Set] that contains all elements of [other]. |
77 */ | 72 */ |
78 factory HashSet.from(Iterable<E> other) => new _HashSetImpl<E>.from(other); | 73 factory HashSet.from(Iterable<E> other) => new _HashSetImpl<E>.from(other); |
79 } | 74 } |
80 | 75 |
81 | 76 |
82 class _HashSetImpl<E> extends Iterable<E> implements HashSet<E> { | 77 class _HashSetImpl<E> extends Iterable<E> implements HashSet<E> { |
floitsch
2013/01/17 13:36:58
extends Collection
or even
extends HashSet<E>
?
Lasse Reichstein Nielsen
2013/01/18 11:41:48
Must be Collection, HashSet doesn't have a generat
| |
83 | 78 |
84 _HashSetImpl() { | 79 _HashSetImpl() { |
85 _backingMap = new _HashMapImpl<E, E>(); | 80 _backingMap = new _HashMapImpl<E, E>(); |
86 } | 81 } |
87 | 82 |
88 factory _HashSetImpl.from(Iterable<E> other) { | 83 factory _HashSetImpl.from(Iterable<E> other) { |
89 Set<E> set = new _HashSetImpl<E>(); | 84 Set<E> set = new _HashSetImpl<E>(); |
90 for (final e in other) { | 85 for (final e in other) { |
91 set.add(e); | 86 set.add(e); |
92 } | 87 } |
93 return set; | 88 return set; |
94 } | 89 } |
95 | 90 |
96 void clear() { | 91 void clear() { |
97 _backingMap.clear(); | 92 _backingMap.clear(); |
98 } | 93 } |
99 | 94 |
100 void add(E value) { | 95 void add(E value) { |
101 _backingMap[value] = value; | 96 _backingMap[value] = value; |
102 } | 97 } |
103 | 98 |
104 bool contains(E value) { | 99 bool contains(E value) { |
105 return _backingMap.containsKey(value); | 100 return _backingMap.containsKey(value); |
106 } | 101 } |
107 | 102 |
108 bool remove(E value) { | 103 bool remove(Object value) { |
109 if (!_backingMap.containsKey(value)) return false; | 104 if (!_backingMap.containsKey(value)) return false; |
110 _backingMap.remove(value); | 105 _backingMap.remove(value); |
111 return true; | 106 return true; |
112 } | 107 } |
113 | 108 |
109 void removeAll(Iterable elements) { | |
floitsch
2013/01/17 13:36:58
should not be necessary if Collection provides def
Lasse Reichstein Nielsen
2013/01/18 11:41:48
Done.
| |
110 for (var element in elements) { | |
111 remove(element); | |
112 } | |
113 } | |
114 | |
115 void retainAll(Iterable elements) { | |
116 Set other; | |
117 if (elements is Set) { | |
118 other = elements | |
119 } else { | |
120 other = new Set.from(elements); | |
121 } | |
122 removeMatching((E e) => !set.contains(e)); | |
123 } | |
124 | |
125 void removeMatching(bool test(E element)) { | |
126 List<E> toRemove = <E>[]; | |
127 // TODO(lrn): Consider making HashSet able to handle remove | |
128 // during iteration. | |
129 for (E element in this) { | |
130 if (test(element)) { | |
131 toRemove.add(element); | |
132 } | |
133 } | |
134 for (E element in toRemove) { | |
135 remove(element); | |
136 } | |
137 } | |
138 | |
114 void addAll(Iterable<E> iterable) { | 139 void addAll(Iterable<E> iterable) { |
115 for (E element in iterable) { | 140 for (E element in iterable) { |
116 add(element); | 141 add(element); |
117 } | 142 } |
118 } | 143 } |
119 | 144 |
120 Set<E> intersection(Collection<E> collection) { | 145 Set<E> intersection(Collection<E> collection) { |
121 Set<E> result = new Set<E>(); | 146 Set<E> result = new Set<E>(); |
122 collection.forEach((E value) { | 147 collection.forEach((E value) { |
123 if (contains(value)) result.add(value); | 148 if (contains(value)) result.add(value); |
124 }); | 149 }); |
125 return result; | 150 return result; |
126 } | 151 } |
127 | 152 |
128 bool isSubsetOf(Collection<E> other) { | 153 bool isSubsetOf(Collection<E> other) { |
129 return new Set<E>.from(other).containsAll(this); | 154 return new Set<E>.from(other).containsAll(this); |
130 } | 155 } |
131 | 156 |
132 void removeAll(Iterable<E> iterable) { | |
133 for (E value in iterable) { | |
134 remove(value); | |
135 } | |
136 } | |
137 | |
138 bool containsAll(Collection<E> collection) { | 157 bool containsAll(Collection<E> collection) { |
139 return collection.every((E value) { | 158 return collection.every((E value) { |
140 return contains(value); | 159 return contains(value); |
141 }); | 160 }); |
142 } | 161 } |
143 | 162 |
144 void forEach(void f(E element)) { | 163 void forEach(void f(E element)) { |
145 _backingMap.forEach((E key, E value) { | 164 _backingMap.forEach((E key, E value) { |
146 f(key); | 165 f(key); |
147 }); | 166 }); |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
186 do { | 205 do { |
187 result = _keysIterator.moveNext(); | 206 result = _keysIterator.moveNext(); |
188 } while (result && | 207 } while (result && |
189 (_keysIterator.current == null || | 208 (_keysIterator.current == null || |
190 identical(_keysIterator.current, _HashMapImpl._DELETED_KEY))); | 209 identical(_keysIterator.current, _HashMapImpl._DELETED_KEY))); |
191 return result; | 210 return result; |
192 } | 211 } |
193 | 212 |
194 Iterator _keysIterator; | 213 Iterator _keysIterator; |
195 } | 214 } |
OLD | NEW |