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 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
50 * Returns a new set which is the intersection between this set and | 50 * Returns a new set which is the intersection between this set and |
51 * the given collection. | 51 * the given collection. |
52 */ | 52 */ |
53 Set<E> intersection(Collection<E> other); | 53 Set<E> intersection(Collection<E> other); |
54 | 54 |
55 /** | 55 /** |
56 * Removes all elements in the set. | 56 * Removes all elements in the set. |
57 */ | 57 */ |
58 void clear(); | 58 void clear(); |
59 } | 59 } |
60 | |
61 | |
62 class HashSet<E> extends Collection<E> implements Set<E> { | |
63 // The map backing this set. The associations in this map are all | |
64 // of the form element -> element. If a value is not in the map, | |
65 // then it is not in the set. | |
66 final _HashMapImpl<E, E> _backingMap; | |
67 | |
68 HashSet() : _backingMap = new _HashMapImpl<E, E>(); | |
69 | |
70 /** | |
71 * Creates a [Set] that contains all elements of [other]. | |
72 */ | |
73 factory HashSet.from(Iterable<E> other) { | |
74 Set<E> set = new HashSet<E>(); | |
75 for (final e in other) { | |
76 set.add(e); | |
77 } | |
78 return set; | |
79 } | |
80 | |
81 void clear() { | |
82 _backingMap.clear(); | |
83 } | |
84 | |
85 void add(E value) { | |
86 _backingMap[value] = value; | |
87 } | |
88 | |
89 bool remove(Object value) { | |
90 if (!_backingMap.containsKey(value)) return false; | |
91 _backingMap.remove(value); | |
92 return true; | |
93 } | |
94 | |
95 bool contains(E value) { | |
96 return _backingMap.containsKey(value); | |
97 } | |
98 | |
99 Set<E> intersection(Collection<E> collection) { | |
100 Set<E> result = new Set<E>(); | |
101 collection.forEach((E value) { | |
102 if (contains(value)) result.add(value); | |
103 }); | |
104 return result; | |
105 } | |
106 | |
107 bool isSubsetOf(Collection<E> other) { | |
108 return new Set<E>.from(other).containsAll(this); | |
109 } | |
110 | |
111 bool containsAll(Collection<E> collection) { | |
112 return collection.every((E value) { | |
113 return contains(value); | |
114 }); | |
115 } | |
116 | |
117 void forEach(void f(E element)) { | |
118 _backingMap.forEach((E key, E value) { | |
119 f(key); | |
120 }); | |
121 } | |
122 | |
123 bool get isEmpty { | |
124 return _backingMap.isEmpty; | |
125 } | |
126 | |
127 int get length { | |
128 return _backingMap.length; | |
129 } | |
130 | |
131 Iterator<E> get iterator => new _HashSetIterator<E>(this); | |
132 | |
133 String toString() { | |
134 return Collections.collectionToString(this); | |
135 } | |
136 } | |
137 | |
138 class _HashSetIterator<E> implements Iterator<E> { | |
139 | |
140 _HashSetIterator(HashSet<E> set) | |
141 : _keysIterator = set._backingMap._keys.iterator; | |
142 | |
143 E get current { | |
144 var result = _keysIterator.current; | |
145 if (identical(result, _HashMapImpl._DELETED_KEY)) { | |
146 // TODO(floitsch): improve the error reporting. | |
147 throw new StateError("Concurrent modification."); | |
148 } | |
149 return result; | |
150 } | |
151 | |
152 bool moveNext() { | |
153 bool result; | |
154 do { | |
155 result = _keysIterator.moveNext(); | |
156 } while (result && | |
157 (_keysIterator.current == null || | |
158 identical(_keysIterator.current, _HashMapImpl._DELETED_KEY))); | |
159 return result; | |
160 } | |
161 | |
162 Iterator _keysIterator; | |
163 } | |
OLD | NEW |