1 | // Copyright 2014 The Flutter Authors. All rights reserved. |
---|---|

2 | // Use of this source code is governed by a BSD-style license that can be |

3 | // found in the LICENSE file. |

4 | |

5 | // TODO(ianh): These should be on the Set and List classes themselves. |

6 | |

7 | /// Compares two sets for element-by-element equality. |

8 | /// |

9 | /// Returns true if the sets are both null, or if they are both non-null, have |

10 | /// the same length, and contain the same members. Returns false otherwise. |

11 | /// Order is not compared. |

12 | /// |

13 | /// If the elements are maps, lists, sets, or other collections/composite |

14 | /// objects, then the contents of those elements are not compared element by |

15 | /// element unless their equality operators ([Object.==]) do so. For checking |

16 | /// deep equality, consider using the [DeepCollectionEquality] class. |

17 | /// |

18 | /// See also: |

19 | /// |

20 | /// * [listEquals], which does something similar for lists. |

21 | /// * [mapEquals], which does something similar for maps. |

22 | bool setEquals<T>(Set<T>? a, Set<T>? b) { |

23 | if (a == null) { |

24 | return b == null; |

25 | } |

26 | if (b == null || a.length != b.length) { |

27 | return false; |

28 | } |

29 | if (identical(a, b)) { |

30 | return true; |

31 | } |

32 | for (final T value in a) { |

33 | if (!b.contains(value)) { |

34 | return false; |

35 | } |

36 | } |

37 | return true; |

38 | } |

39 | |

40 | /// Compares two lists for element-by-element equality. |

41 | /// |

42 | /// Returns true if the lists are both null, or if they are both non-null, have |

43 | /// the same length, and contain the same members in the same order. Returns |

44 | /// false otherwise. |

45 | /// |

46 | /// If the elements are maps, lists, sets, or other collections/composite |

47 | /// objects, then the contents of those elements are not compared element by |

48 | /// element unless their equality operators ([Object.==]) do so. For checking |

49 | /// deep equality, consider using the [DeepCollectionEquality] class. |

50 | /// |

51 | /// See also: |

52 | /// |

53 | /// * [setEquals], which does something similar for sets. |

54 | /// * [mapEquals], which does something similar for maps. |

55 | bool listEquals<T>(List<T>? a, List<T>? b) { |

56 | if (a == null) { |

57 | return b == null; |

58 | } |

59 | if (b == null || a.length != b.length) { |

60 | return false; |

61 | } |

62 | if (identical(a, b)) { |

63 | return true; |

64 | } |

65 | for (int index = 0; index < a.length; index += 1) { |

66 | if (a[index] != b[index]) { |

67 | return false; |

68 | } |

69 | } |

70 | return true; |

71 | } |

72 | |

73 | /// Compares two maps for element-by-element equality. |

74 | /// |

75 | /// Returns true if the maps are both null, or if they are both non-null, have |

76 | /// the same length, and contain the same keys associated with the same values. |

77 | /// Returns false otherwise. |

78 | /// |

79 | /// If the elements are maps, lists, sets, or other collections/composite |

80 | /// objects, then the contents of those elements are not compared element by |

81 | /// element unless their equality operators ([Object.==]) do so. For checking |

82 | /// deep equality, consider using the [DeepCollectionEquality] class. |

83 | /// |

84 | /// See also: |

85 | /// |

86 | /// * [setEquals], which does something similar for sets. |

87 | /// * [listEquals], which does something similar for lists. |

88 | bool mapEquals<T, U>(Map<T, U>? a, Map<T, U>? b) { |

89 | if (a == null) { |

90 | return b == null; |

91 | } |

92 | if (b == null || a.length != b.length) { |

93 | return false; |

94 | } |

95 | if (identical(a, b)) { |

96 | return true; |

97 | } |

98 | for (final T key in a.keys) { |

99 | if (!b.containsKey(key) || b[key] != a[key]) { |

100 | return false; |

101 | } |

102 | } |

103 | return true; |

104 | } |

105 | |

106 | /// Returns the position of `value` in the `sortedList`, if it exists. |

107 | /// |

108 | /// Returns `-1` if the `value` is not in the list. Requires the list items |

109 | /// to implement [Comparable] and the `sortedList` to already be ordered. |

110 | int binarySearch<T extends Comparable<Object>>(List<T> sortedList, T value) { |

111 | int min = 0; |

112 | int max = sortedList.length; |

113 | while (min < max) { |

114 | final int mid = min + ((max - min) >> 1); |

115 | final T element = sortedList[mid]; |

116 | final int comp = element.compareTo(value); |

117 | if (comp == 0) { |

118 | return mid; |

119 | } |

120 | if (comp < 0) { |

121 | min = mid + 1; |

122 | } else { |

123 | max = mid; |

124 | } |

125 | } |

126 | return -1; |

127 | } |

128 | |

129 | /// Limit below which merge sort defaults to insertion sort. |

130 | const int _kMergeSortLimit = 32; |

131 | |

132 | /// Sorts a list between `start` (inclusive) and `end` (exclusive) using the |

133 | /// merge sort algorithm. |

134 | /// |

135 | /// If `compare` is omitted, this defaults to calling [Comparable.compareTo] on |

136 | /// the objects. If any object is not [Comparable], this throws a [TypeError] |

137 | /// (The stack trace may call it `_CastError` or `_TypeError`, but to catch it, |

138 | /// use [TypeError]). |

139 | /// |

140 | /// Merge-sorting works by splitting the job into two parts, sorting each |

141 | /// recursively, and then merging the two sorted parts. |

142 | /// |

143 | /// This takes on the order of `n * log(n)` comparisons and moves to sort `n` |

144 | /// elements, but requires extra space of about the same size as the list being |

145 | /// sorted. |

146 | /// |

147 | /// This merge sort is stable: Equal elements end up in the same order as they |

148 | /// started in. |

149 | /// |

150 | /// For small lists (less than 32 elements), [mergeSort] automatically uses an |

151 | /// insertion sort instead, as that is more efficient for small lists. The |

152 | /// insertion sort is also stable. |

153 | void mergeSort<T>( |

154 | List<T> list, { |

155 | int start = 0, |

156 | int? end, |

157 | int Function(T, T)? compare, |

158 | }) { |

159 | end ??= list.length; |

160 | compare ??= _defaultCompare<T>(); |

161 | |

162 | final int length = end - start; |

163 | if (length < 2) { |

164 | return; |

165 | } |

166 | if (length < _kMergeSortLimit) { |

167 | _insertionSort<T>(list, compare: compare, start: start, end: end); |

168 | return; |

169 | } |

170 | // Special case the first split instead of directly calling _mergeSort, |

171 | // because the _mergeSort requires its target to be different from its source, |

172 | // and it requires extra space of the same size as the list to sort. This |

173 | // split allows us to have only half as much extra space, and it ends up in |

174 | // the original place. |

175 | final int middle = start + ((end - start) >> 1); |

176 | final int firstLength = middle - start; |

177 | final int secondLength = end - middle; |

178 | // secondLength is always the same as firstLength, or one greater. |

179 | final List<T> scratchSpace = List<T>.filled(secondLength, list[start]); |

180 | _mergeSort<T>(list, compare, middle, end, scratchSpace, 0); |

181 | final int firstTarget = end - firstLength; |

182 | _mergeSort<T>(list, compare, start, middle, list, firstTarget); |

183 | _merge<T>(compare, list, firstTarget, end, scratchSpace, 0, secondLength, list, start); |

184 | } |

185 | |

186 | /// Returns a [Comparator] that asserts that its first argument is comparable. |

187 | Comparator<T> _defaultCompare<T>() { |

188 | // If we specify Comparable |

189 | // int isn't a subtype of comparable. Leaving out the type implicitly converts |

190 | // it to a num, which is a comparable. |

191 | return (T value1, T value2) => (value1 as Comparable<dynamic>).compareTo(value2); |

192 | } |

193 | |

194 | /// Sort a list between `start` (inclusive) and `end` (exclusive) using |

195 | /// insertion sort. |

196 | /// |

197 | /// If `compare` is omitted, this defaults to calling [Comparable.compareTo] on |

198 | /// the objects. If any object is not [Comparable], this throws a [TypeError] |

199 | /// (The stack trace may call it `_CastError` or `_TypeError`, but to catch it, |

200 | /// use [TypeError]). |

201 | /// |

202 | /// Insertion sort is a simple sorting algorithm. For `n` elements it does on |

203 | /// the order of `n * log(n)` comparisons but up to `n` squared moves. The |

204 | /// sorting is performed in-place, without using extra memory. |

205 | /// |

206 | /// For short lists the many moves have less impact than the simple algorithm, |

207 | /// and it is often the favored sorting algorithm for short lists. |

208 | /// |

209 | /// This insertion sort is stable: Equal elements end up in the same order as |

210 | /// they started in. |

211 | void _insertionSort<T>( |

212 | List<T> list, { |

213 | int Function(T, T)? compare, |

214 | int start = 0, |

215 | int? end, |

216 | }) { |

217 | // If the same method could have both positional and named optional |

218 | // parameters, this should be (list, [start, end], {compare}). |

219 | compare ??= _defaultCompare<T>(); |

220 | end ??= list.length; |

221 | |

222 | for (int pos = start + 1; pos < end; pos++) { |

223 | int min = start; |

224 | int max = pos; |

225 | final T element = list[pos]; |

226 | while (min < max) { |

227 | final int mid = min + ((max - min) >> 1); |

228 | final int comparison = compare(element, list[mid]); |

229 | if (comparison < 0) { |

230 | max = mid; |

231 | } else { |

232 | min = mid + 1; |

233 | } |

234 | } |

235 | list.setRange(min + 1, pos + 1, list, min); |

236 | list[min] = element; |

237 | } |

238 | } |

239 | |

240 | /// Performs an insertion sort into a potentially different list than the one |

241 | /// containing the original values. |

242 | /// |

243 | /// It will work in-place as well. |

244 | void _movingInsertionSort<T>( |

245 | List<T> list, |

246 | int Function(T, T) compare, |

247 | int start, |

248 | int end, |

249 | List<T> target, |

250 | int targetOffset, |

251 | ) { |

252 | final int length = end - start; |

253 | if (length == 0) { |

254 | return; |

255 | } |

256 | target[targetOffset] = list[start]; |

257 | for (int i = 1; i < length; i++) { |

258 | final T element = list[start + i]; |

259 | int min = targetOffset; |

260 | int max = targetOffset + i; |

261 | while (min < max) { |

262 | final int mid = min + ((max - min) >> 1); |

263 | if (compare(element, target[mid]) < 0) { |

264 | max = mid; |

265 | } else { |

266 | min = mid + 1; |

267 | } |

268 | } |

269 | target.setRange(min + 1, targetOffset + i + 1, target, min); |

270 | target[min] = element; |

271 | } |

272 | } |

273 | |

274 | /// Sorts `list` from `start` to `end` into `target` at `targetOffset`. |

275 | /// |

276 | /// The `target` list must be able to contain the range from `start` to `end` |

277 | /// after `targetOffset`. |

278 | /// |

279 | /// Allows target to be the same list as `list`, as long as it's not overlapping |

280 | /// the `start..end` range. |

281 | void _mergeSort<T>( |

282 | List<T> list, |

283 | int Function(T, T) compare, |

284 | int start, |

285 | int end, |

286 | List<T> target, |

287 | int targetOffset, |

288 | ) { |

289 | final int length = end - start; |

290 | if (length < _kMergeSortLimit) { |

291 | _movingInsertionSort<T>(list, compare, start, end, target, targetOffset); |

292 | return; |

293 | } |

294 | final int middle = start + (length >> 1); |

295 | final int firstLength = middle - start; |

296 | final int secondLength = end - middle; |

297 | // Here secondLength >= firstLength (differs by at most one). |

298 | final int targetMiddle = targetOffset + firstLength; |

299 | // Sort the second half into the end of the target area. |

300 | _mergeSort<T>(list, compare, middle, end, target, targetMiddle); |

301 | // Sort the first half into the end of the source area. |

302 | _mergeSort<T>(list, compare, start, middle, list, middle); |

303 | // Merge the two parts into the target area. |

304 | _merge<T>( |

305 | compare, |

306 | list, |

307 | middle, |

308 | middle + firstLength, |

309 | target, |

310 | targetMiddle, |

311 | targetMiddle + secondLength, |

312 | target, |

313 | targetOffset, |

314 | ); |

315 | } |

316 | |

317 | /// Merges two lists into a target list. |

318 | /// |

319 | /// One of the input lists may be positioned at the end of the target list. |

320 | /// |

321 | /// For equal object, elements from `firstList` are always preferred. This |

322 | /// allows the merge to be stable if the first list contains elements that |

323 | /// started out earlier than the ones in `secondList`. |

324 | void _merge<T>( |

325 | int Function(T, T) compare, |

326 | List<T> firstList, |

327 | int firstStart, |

328 | int firstEnd, |

329 | List<T> secondList, |

330 | int secondStart, |

331 | int secondEnd, |

332 | List<T> target, |

333 | int targetOffset, |

334 | ) { |

335 | // No empty lists reaches here. |

336 | assert(firstStart < firstEnd); |

337 | assert(secondStart < secondEnd); |

338 | int cursor1 = firstStart; |

339 | int cursor2 = secondStart; |

340 | T firstElement = firstList[cursor1++]; |

341 | T secondElement = secondList[cursor2++]; |

342 | while (true) { |

343 | if (compare(firstElement, secondElement) <= 0) { |

344 | target[targetOffset++] = firstElement; |

345 | if (cursor1 == firstEnd) { |

346 | // Flushing second list after loop. |

347 | break; |

348 | } |

349 | firstElement = firstList[cursor1++]; |

350 | } else { |

351 | target[targetOffset++] = secondElement; |

352 | if (cursor2 != secondEnd) { |

353 | secondElement = secondList[cursor2++]; |

354 | continue; |

355 | } |

356 | // Second list empties first. Flushing first list here. |

357 | target[targetOffset++] = firstElement; |

358 | target.setRange(targetOffset, targetOffset + (firstEnd - cursor1), firstList, cursor1); |

359 | return; |

360 | } |

361 | } |

362 | // First list empties first. Reached by break above. |

363 | target[targetOffset++] = secondElement; |

364 | target.setRange(targetOffset, targetOffset + (secondEnd - cursor2), secondList, cursor2); |

365 | } |

366 |