inplace_merge, nWayUnion

bearophile bearophileHUGS at lycos.com
Tue Aug 31 03:10:33 PDT 2010


Andrei:

Sorry for my late answer, yesterday I was very busy.


>What I was saying is that in a past bug report you complained that find() is too hard to understand.<

An in a later post I have explained what in my opinion it can be done to improve the situation (this is not a fully good answer, but it gives a good idea of what I was thinking):
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=113555


>That was because find() supported things like heterogeneous ranges and finding more things than one in a single-pass manner.<

The main problem of find() is in what it returns, not in what it takes as arguments.


>Making nWayUnion accept heterogeneous ranges would no doubt increase its implementation complexity - probably worth it given the increased leverage.<

My idea probably will make it more complex internally. But it's library code, so what's more important is how complex its usage is, not its internal complexity.

I have had to use nWayUnion three times so far, and in two times I was in need to perform a 2-way or 3-way merge of lazy iterables, and I have had troubles in using nWayUnion, so much that I have written my own merge. So I think currently nWayUnion is not so useful because it is too much limited.


>All I'm saying is, please remember that solutions that are at the same time simpler and more general are in short supply.<

"simpler" means many different things. Your library code may be simple to use and to understand and yet be complex internally. The point of a library of algorithms is to make user code shorter and clean and efficient. I agree that designing a good library is a job of balancing some opposed needs, but this is not my fault, it's the nature of the game :-)


If you don't want to modify nWayUnion(), there is another solution, to not modify nWayUnion and to create an adaptor:

nWayUnion(Sequence(r1, r2, r3))

Sequence() takes as arguments one or more iterables, it's like a Tuple and it supports random access with [], but its template constraint assures that all the given iterables yield the same type:

Sequence(iota(10), [20, 30])  this is OK.

Sequence(iota(10), [20.5, 30.5])  this is not OK.

So:
Sequence(r1, r2, r3)[0].front() returns what r1.front() returns.


I don't know if this is a good idea. I prefer the simpler syntax nWayUnion(r1, r2, ...)

Bye,
bearophile


More information about the Digitalmars-d mailing list