OLD | NEW |
| (Empty) |
1 // Copyright 2013 Google Inc. All Rights Reserved. | |
2 // | |
3 // Licensed under the Apache License, Version 2.0 (the "License"); | |
4 // you may not use this file except in compliance with the License. | |
5 // You may obtain a copy of the License at | |
6 // | |
7 // http://www.apache.org/licenses/LICENSE-2.0 | |
8 // | |
9 // Unless required by applicable law or agreed to in writing, software | |
10 // distributed under the License is distributed on an "AS IS" BASIS, | |
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
12 // See the License for the specific language governing permissions and | |
13 // limitations under the License. | |
14 | |
15 part of quiver.iterables; | |
16 | |
17 /// Returns the result of merging an [Iterable] of [Iterable]s, according to | |
18 /// the order specified by the [compare] function. This function assumes the | |
19 /// provided iterables are already sorted according to the provided [compare] | |
20 /// function. It will not check for this condition or sort the iterables. | |
21 /// | |
22 /// The compare function must act as a [Comparator]. If [compare] is omitted, | |
23 /// [Comparable.compare] is used. | |
24 /// | |
25 /// If any of the [iterables] contain null elements, an exception will be | |
26 /// thrown. | |
27 Iterable merge(Iterable<Iterable> iterables, | |
28 [Comparator compare = Comparable.compare]) => | |
29 (iterables.isEmpty) ? const [] : new _Merge(iterables, compare); | |
30 | |
31 class _Merge extends IterableBase { | |
32 final Iterable<Iterable> _iterables; | |
33 final Comparator _compare; | |
34 | |
35 _Merge(this._iterables, this._compare); | |
36 | |
37 Iterator get iterator => new _MergeIterator( | |
38 _iterables.map((i) => i.iterator).toList(growable: false), _compare); | |
39 | |
40 String toString() => this.toList().toString(); | |
41 } | |
42 | |
43 /// Like [Iterator] but one element ahead. | |
44 class _IteratorPeeker { | |
45 final Iterator _iterator; | |
46 bool _hasCurrent; | |
47 | |
48 _IteratorPeeker(Iterator iterator) | |
49 : _iterator = iterator, | |
50 _hasCurrent = iterator.moveNext(); | |
51 | |
52 moveNext() { | |
53 _hasCurrent = _iterator.moveNext(); | |
54 } | |
55 | |
56 get current => _iterator.current; | |
57 } | |
58 | |
59 class _MergeIterator implements Iterator { | |
60 final List<_IteratorPeeker> _peekers; | |
61 final Comparator _compare; | |
62 var _current; | |
63 | |
64 _MergeIterator(List<Iterator> iterators, this._compare) | |
65 : _peekers = iterators.map((i) => new _IteratorPeeker(i)).toList(); | |
66 | |
67 bool moveNext() { | |
68 // Pick the peeker that's peeking at the puniest piece | |
69 _IteratorPeeker minIter = null; | |
70 for (var p in _peekers) { | |
71 if (p._hasCurrent) { | |
72 if (minIter == null || _compare(p.current, minIter.current) < 0) { | |
73 minIter = p; | |
74 } | |
75 } | |
76 } | |
77 | |
78 if (minIter == null) { | |
79 return false; | |
80 } | |
81 _current = minIter.current; | |
82 minIter.moveNext(); | |
83 return true; | |
84 } | |
85 | |
86 get current => _current; | |
87 } | |
OLD | NEW |