Re: Sorted ranges in combined sorted order?

[Matthew Gamble via Digitalmars-d-learn]

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));
}