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 2017