www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Sorted ranges in combined sorted order?

reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
Given a range of ranges where individual ranges are already sorted, is 
there anything in Phobos that can visit the combined range in sorted order?

Although the range elements are not necessarily arrays, e.g.

     [ [ 3, 10, 20 ]
       [ 1, 2, 7 ]
       [ 5, 6 ] ]

The elements should appear without any copying as

     [ 1, 2, 3, 5, 6, 7, 10, 20 ]

The outer range may be unsorted but luckily it has very few elements so 
a linear search should be fine.

Ali
Oct 20 2016
parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Thursday, 20 October 2016 at 20:49:38 UTC, Ali Çehreli wrote:
 Given a range of ranges where individual ranges are already 
 sorted, is there anything in Phobos that can visit the combined 
 range in sorted order?

 Although the range elements are not necessarily arrays, e.g.

     [ [ 3, 10, 20 ]
       [ 1, 2, 7 ]
       [ 5, 6 ] ]

 The elements should appear without any copying as

     [ 1, 2, 3, 5, 6, 7, 10, 20 ]

 The outer range may be unsorted but luckily it has very few 
 elements so a linear search should be fine.

 Ali
I have a variadic implemention of `std.algorithm.merge` lying around that does this. It includes all the D bells and whistles of lazy range including infiniteness propagation when possible. Maybe it's time to get it in: https://github.com/dlang/phobos/pull/3315#issuecomment-243089368 Note that it was first merged and then reverted by Andrei because he thought the existing `setUnion` at https://dlang.org/phobos/std_algorithm_setops.html#setUnion is a superset of `merge`. But wilzbach and others want it merged :) anyway. I'll do another try. In the meantime you can use setUnion. I also recall a discussion about uniqueness handling, but have forgotten the details.
Oct 20 2016
parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Thursday, 20 October 2016 at 21:14:14 UTC, Nordlöw wrote:
 Given a range of ranges where individual ranges are already
Ahh, my mistake. It's https://dlang.org/phobos/std_algorithm_setops.html#.NWayUnion you're looking for, right?
Oct 20 2016
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 10/20/2016 02:15 PM, Nordlöw wrote:
 On Thursday, 20 October 2016 at 21:14:14 UTC, Nordlöw wrote:
 Given a range of ranges where individual ranges are already
Ahh, my mistake. It's https://dlang.org/phobos/std_algorithm_setops.html#.NWayUnion you're looking for, right?
Thanks! That's exactly what I needed... I consider my "wasted" effort of writing such a range just now, as valuable experience. :) And the reason I could not find it is because it didn't occur to me that it would be under a *set* module, which the RangeOfRanges parameter of nWayUnion has no such requirement (i.e. any two range can be equal). Ali
Oct 20 2016
parent reply Matthew Gamble <matthew.gamble einstein.yu.edu> writes:
On Thursday, 20 October 2016 at 22:01:01 UTC, Ali Çehreli wrote:
 On 10/20/2016 02:15 PM, Nordlöw wrote:
 On Thursday, 20 October 2016 at 21:14:14 UTC, Nordlöw wrote:
 Given a range of ranges where individual ranges are already
Ahh, my mistake. It's https://dlang.org/phobos/std_algorithm_setops.html#.NWayUnion you're looking for, right?
Thanks! That's exactly what I needed... I consider my "wasted" effort of writing such a range just now, as valuable experience. :) And the reason I could not find it is because it didn't occur to me that it would be under a *set* module, which the RangeOfRanges parameter of nWayUnion has no such requirement (i.e. any two range can be equal). Ali
I've been struggling with a similar issue trying to use NWayUnion and merge. It seems to me that the drawback with NWayUnion is that it requires the elements of the ranges to be assignable or swappable, in addition to the fact that it doesn't give a formal union (i.e. there should be no repetition of elements). The drawback of merge is that it doesn't work on a RoR at all, so the number of ranges to be passed must be know at compile time. I've rewritten both of these functions so that they can work on a RoR that is not assignable or swappable. Of course my nWayMerge could be synonymous with nWayUnion by just sending it to uniq(), but I though the solution below might be more efficient. I guess I'm wondering if there was an easier or better way to do this. I pasted the code below in case it would be valuable for others. Please let me know if you have any suggestions. And if I did something terribly silly please understand, I'm a professional scientist, but not a computer scientist (I'm a molecular biologist). P.S. Ali, I a big fan of your book on D; it was the first book I read on D and gave me a great start. :) Thanks, Matt module nWayMergeAlt; import std.algorithm; import std.range; auto nWayMergeAlt(R)(R[] rs...) if (isForwardRange!R) { return NwayMergeAlt!R(rs); } struct NwayMergeAlt(R) if (isForwardRange!R) { this(R[] rs) { _source = rs; _minPosResult = _source.minPos!("a.front() < b.front()")(); } bool empty() property const { return _source.length == 0; } auto front() property const { return _minPosResult.front().front(); } void popFront() property { _minPosResult.front().popFront(); if (_minPosResult.front().empty()) _source = _source.remove!(SwapStrategy.unstable)(_source.length - _minPosResult.length); if (!empty) _minPosResult = _source.minPos!("a.front() < b.front()")(); } private: R[] _source; R[] _minPosResult; } unittest { import std.stdio; auto a = iota(0,20,2); auto b = iota(1,20,2); auto c = iota(0,20); assert(equal(nWayMergeAlt(a,b), c)); assert(equal(nWayMergeAlt([a,b]), c)); auto d = [1,2,3,4]; auto e = [3,4,5,6]; auto f = [1,2,3,3,4,4,5,6]; assert(equal(nWayMergeAlt(d,e),f)); } auto nWayUnionAlt(R)(R[] rs...) if (isForwardRange!R) { return NwayUnionAlt!R(rs); } struct NwayUnionAlt(R) if (isForwardRange!R) { this(R[] rs) { _source = rs; _minPosResult = _source.minPos!("a.front() < b.front()")(); _currVal = _minPosResult.front().front(); } bool empty() property const { return _source.length == 0; } auto front() property const { return _currVal; } void popFront() property { while(!empty && _currVal == _minPosResult.front().front()) { _minPosResult.front().popFront(); if (_minPosResult.front().empty()) //_source = _minPosResult.remove!(SwapStrategy.unstable)(_source.length - _minPosResult.length); _source = _source.remove!(SwapStrategy.unstable)(_source.length - _minPosResult.length); if (!empty) _minPosResult = _source.minPos!("a.front() < b.front()")(); } if (!empty) _currVal = _minPosResult.front().front(); } private: R[] _source; R[] _minPosResult; typeof(_source.front().front()) _currVal; } unittest { import std.stdio; auto a = iota(0,20,2); auto b = iota(1,20,2); auto c = iota(0,20); //equal((nWayUnion(a,b)),c);//error assert(equal(nWayUnionAlt(a,b), c)); assert(equal(nWayUnionAlt([a,b]), c)); auto d = iota(0,20); auto e = iota(5,25); auto f = iota(0,25); assert(equal(nWayUnionAlt(d,e),f)); }
Dec 31 2016
parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 12/31/2016 02:28 PM, Matthew Gamble wrote:

 Please let me know if you have any suggestions.
I've seen this just now. Random and trivial observations: - Assigning to _minPosResult could be in a separate function like prepareMinPosResult() called from multiple places - There could be a unittest for an empty array (and an empty range element) - It's personal taste and not obvious from its documentation but minPos() and most (all?) other Phobos algorithms can take proper lambdas as well: _source.minPos!((a, b) => a.front() < b.front())()
 P.S. Ali, I a big fan of your book on D; it was the first book I read on
 D and gave me a great start. :)
Very happy to hear that! :) Ali
Jan 05