| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 library dart2js.util.setlet; | |
| 6 | |
| 7 import 'dart:collection' show IterableBase; | |
| 8 | |
| 9 class Setlet<E> extends IterableBase<E> implements Set<E> { | |
| 10 static const _MARKER = const _SetletMarker(); | |
| 11 static const CAPACITY = 8; | |
| 12 | |
| 13 // The setlet can be in one of four states: | |
| 14 // | |
| 15 // * Empty (extra: null, contents: marker) | |
| 16 // * Single element (extra: null, contents: element) | |
| 17 // * List-backed (extra: length, contents: list) | |
| 18 // * Set-backed (extra: marker, contents: set) | |
| 19 // | |
| 20 // When the setlet is list-backed, the list in the contents field | |
| 21 // may have empty slots filled with the marker value. | |
| 22 var _contents = _MARKER; | |
| 23 var _extra; | |
| 24 | |
| 25 Setlet(); | |
| 26 Setlet.from(Iterable<E> elements) { | |
| 27 addAll(elements); | |
| 28 } | |
| 29 | |
| 30 Iterator<E> get iterator { | |
| 31 if (_extra == null) { | |
| 32 return new _SetletSingleIterator<E>(_contents); | |
| 33 } else if (_MARKER == _extra) { | |
| 34 return _contents.iterator; | |
| 35 } else { | |
| 36 return new _SetletListIterator<E>(_contents, _extra); | |
| 37 } | |
| 38 } | |
| 39 | |
| 40 int get length { | |
| 41 if (_extra == null) { | |
| 42 return (_MARKER == _contents) ? 0 : 1; | |
| 43 } else if (_MARKER == _extra) { | |
| 44 return _contents.length; | |
| 45 } else { | |
| 46 return _extra; | |
| 47 } | |
| 48 } | |
| 49 | |
| 50 bool get isEmpty { | |
| 51 if (_extra == null) { | |
| 52 return _MARKER == _contents; | |
| 53 } else if (_MARKER == _extra) { | |
| 54 return _contents.isEmpty; | |
| 55 } else { | |
| 56 return _extra == 0; | |
| 57 } | |
| 58 } | |
| 59 | |
| 60 bool contains(E element) { | |
| 61 if (_extra == null) { | |
| 62 return _contents == element; | |
| 63 } else if (_MARKER == _extra) { | |
| 64 return _contents.contains(element); | |
| 65 } else { | |
| 66 for (int remaining = _extra, i = 0; remaining > 0 && i < CAPACITY; i++) { | |
| 67 var candidate = _contents[i]; | |
| 68 if (_MARKER == candidate) continue; | |
| 69 if (candidate == element) return true; | |
| 70 remaining--; | |
| 71 } | |
| 72 return false; | |
| 73 } | |
| 74 } | |
| 75 | |
| 76 bool add(E element) { | |
| 77 if (_extra == null) { | |
| 78 if (_MARKER == _contents) { | |
| 79 _contents = element; | |
| 80 return true; | |
| 81 } else if (_contents == element) { | |
| 82 // Do nothing. | |
| 83 return false; | |
| 84 } else { | |
| 85 List list = new List(CAPACITY); | |
| 86 list[0] = _contents; | |
| 87 list[1] = element; | |
| 88 _contents = list; | |
| 89 _extra = 2; // Two elements. | |
| 90 return true; | |
| 91 } | |
| 92 } else if (_MARKER == _extra) { | |
| 93 return _contents.add(element); | |
| 94 } else { | |
| 95 int remaining = _extra; | |
| 96 int index = 0; | |
| 97 int copyTo, copyFrom; | |
| 98 while (remaining > 0 && index < CAPACITY) { | |
| 99 var candidate = _contents[index++]; | |
| 100 if (_MARKER == candidate) { | |
| 101 // Keep track of the last range of empty slots in the | |
| 102 // list. When we're done we'll move all the elements | |
| 103 // after those empty slots down, so that adding an element | |
| 104 // after that will preserve the insertion order. | |
| 105 if (copyFrom == index - 1) { | |
| 106 copyFrom++; | |
| 107 } else { | |
| 108 copyTo = index - 1; | |
| 109 copyFrom = index; | |
| 110 } | |
| 111 continue; | |
| 112 } else if (candidate == element) { | |
| 113 return false; | |
| 114 } | |
| 115 remaining--; | |
| 116 } | |
| 117 if (index < CAPACITY) { | |
| 118 _contents[index] = element; | |
| 119 _extra++; | |
| 120 } else if (_extra < CAPACITY) { | |
| 121 // Move the last elements down into the last empty slots | |
| 122 // so that we have empty slots after the last element. | |
| 123 while (copyFrom < CAPACITY) { | |
| 124 _contents[copyTo++] = _contents[copyFrom++]; | |
| 125 } | |
| 126 // Insert the new element as the last element. | |
| 127 _contents[copyTo++] = element; | |
| 128 _extra++; | |
| 129 // Clear all elements after the new last elements to | |
| 130 // make sure we don't keep extra stuff alive. | |
| 131 while (copyTo < CAPACITY) _contents[copyTo++] = null; | |
| 132 } else { | |
| 133 _contents = new Set<E>()..addAll(_contents)..add(element); | |
| 134 _extra = _MARKER; | |
| 135 } | |
| 136 return true; | |
| 137 } | |
| 138 } | |
| 139 | |
| 140 void addAll(Iterable<E> elements) { | |
| 141 elements.forEach((each) => add(each)); | |
| 142 } | |
| 143 | |
| 144 E lookup(Object element) { | |
| 145 if (_extra == null) { | |
| 146 return _contents == element ? _contents : null; | |
| 147 } else if (_MARKER == _extra) { | |
| 148 return _contents.lookup(element); | |
| 149 } else { | |
| 150 for (int remaining = _extra, i = 0; remaining > 0 && i < CAPACITY; i++) { | |
| 151 var candidate = _contents[i]; | |
| 152 if (_MARKER == candidate) continue; | |
| 153 if (candidate == element) return candidate; | |
| 154 remaining--; | |
| 155 } | |
| 156 return null; | |
| 157 } | |
| 158 } | |
| 159 | |
| 160 bool remove(E element) { | |
| 161 if (_extra == null) { | |
| 162 if (_contents == element) { | |
| 163 _contents = _MARKER; | |
| 164 return true; | |
| 165 } else { | |
| 166 return false; | |
| 167 } | |
| 168 } else if (_MARKER == _extra) { | |
| 169 return _contents.remove(element); | |
| 170 } else { | |
| 171 for (int remaining = _extra, i = 0; remaining > 0 && i < CAPACITY; i++) { | |
| 172 var candidate = _contents[i]; | |
| 173 if (_MARKER == candidate) continue; | |
| 174 if (candidate == element) { | |
| 175 _contents[i] = _MARKER; | |
| 176 _extra--; | |
| 177 return true; | |
| 178 } | |
| 179 remaining--; | |
| 180 } | |
| 181 return false; | |
| 182 } | |
| 183 } | |
| 184 | |
| 185 void removeAll(Iterable<Object> other) { | |
| 186 other.forEach(remove); | |
| 187 } | |
| 188 | |
| 189 void removeWhere(bool test(E element)) { | |
| 190 if (_extra == null) { | |
| 191 if (test(_contents)) { | |
| 192 _contents = _MARKER; | |
| 193 } | |
| 194 } else if (_MARKER == _extra) { | |
| 195 _contents.removeWhere(test); | |
| 196 } else { | |
| 197 for (int remaining = _extra, i = 0; remaining > 0 && i < CAPACITY; i++) { | |
| 198 var candidate = _contents[i]; | |
| 199 if (_MARKER == candidate) continue; | |
| 200 if (test(candidate)) { | |
| 201 _contents[i] = _MARKER; | |
| 202 _extra--; | |
| 203 } | |
| 204 remaining--; | |
| 205 } | |
| 206 } | |
| 207 } | |
| 208 | |
| 209 void retainWhere(bool test(E element)) { | |
| 210 removeWhere((E element) => !test(element)); | |
| 211 } | |
| 212 | |
| 213 void retainAll(Iterable<Object> elements) { | |
| 214 Set set = elements is Set ? elements : elements.toSet(); | |
| 215 removeWhere((E element) => !set.contains(element)); | |
| 216 } | |
| 217 | |
| 218 void forEach(void action(E element)) { | |
| 219 if (_extra == null) { | |
| 220 if (_MARKER != _contents) action(_contents); | |
| 221 } else if (_MARKER == _extra) { | |
| 222 _contents.forEach(action); | |
| 223 } else { | |
| 224 for (int remaining = _extra, i = 0; remaining > 0 && i < CAPACITY; i++) { | |
| 225 var element = _contents[i]; | |
| 226 if (_MARKER == element) continue; | |
| 227 action(element); | |
| 228 remaining--; | |
| 229 } | |
| 230 } | |
| 231 } | |
| 232 | |
| 233 bool containsAll(Iterable<E> other) { | |
| 234 for (E e in other) { | |
| 235 if (!this.contains(e)) return false; | |
| 236 }; | |
| 237 return true; | |
| 238 } | |
| 239 | |
| 240 clear() { | |
| 241 _contents = _MARKER; | |
| 242 _extra = null; | |
| 243 } | |
| 244 | |
| 245 Set<E> union(Set<E> other) => new Set<E>.from(this)..addAll(other); | |
| 246 | |
| 247 Setlet<E> intersection(Set<E> other) => | |
| 248 new Setlet<E>.from(this.where((e) => other.contains(e))); | |
| 249 | |
| 250 Setlet<E> difference(Set<E> other) => | |
| 251 new Setlet<E>.from(this.where((e) => !other.contains(e))); | |
| 252 | |
| 253 Setlet<E> toSet() { | |
| 254 Setlet<E> result = new Setlet<E>(); | |
| 255 if (_extra == null) { | |
| 256 result._contents = _contents; | |
| 257 } else if (_extra == _MARKER) { | |
| 258 result._extra = _MARKER; | |
| 259 result._contents = _contents.toSet(); | |
| 260 } else { | |
| 261 result._extra = _extra; | |
| 262 result._contents = _contents.toList(); | |
| 263 } | |
| 264 return result; | |
| 265 } | |
| 266 } | |
| 267 | |
| 268 class _SetletMarker { | |
| 269 const _SetletMarker(); | |
| 270 toString() => "-"; | |
| 271 } | |
| 272 | |
| 273 class _SetletSingleIterator<E> implements Iterator<E> { | |
| 274 var _element; | |
| 275 E _current; | |
| 276 _SetletSingleIterator(this._element); | |
| 277 | |
| 278 E get current => _current; | |
| 279 | |
| 280 bool moveNext() { | |
| 281 if (Setlet._MARKER == _element) { | |
| 282 _current = null; | |
| 283 return false; | |
| 284 } | |
| 285 _current = _element; | |
| 286 _element = Setlet._MARKER; | |
| 287 return true; | |
| 288 } | |
| 289 } | |
| 290 | |
| 291 class _SetletListIterator<E> implements Iterator<E> { | |
| 292 final List _list; | |
| 293 int _remaining; | |
| 294 int _index = 0; | |
| 295 E _current; | |
| 296 _SetletListIterator(this._list, this._remaining); | |
| 297 | |
| 298 E get current => _current; | |
| 299 | |
| 300 bool moveNext() { | |
| 301 while (_remaining > 0) { | |
| 302 var candidate = _list[_index++]; | |
| 303 if (Setlet._MARKER != candidate) { | |
| 304 _current = candidate; | |
| 305 _remaining--; | |
| 306 return true; | |
| 307 } | |
| 308 } | |
| 309 _current = null; | |
| 310 return false; | |
| 311 } | |
| 312 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 694353007:
Move dart2js from sdk/lib/_internal/compiler to pkg/compiler (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart