Sorted ranges in combined sorted order?
Matthew Gamble via Digitalmars-d-learn
digitalmars-d-learn at puremagic.com
Sat Dec 31 14:28:03 PST 2016
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));
}
More information about the Digitalmars-d-learn
mailing list