Re: Merging one Array with Another
On Monday, 11 May 2015 at 07:12:05 UTC, Per Nordlöw wrote: I guess we should support bi-directional access through back() and popBack() aswell right? Does this mean that we need to statically check whether the SortedRanges support Bidirectional access or not? Or is a SortedRange by convention always random-access?
Re: Merging one Array with Another
On Monday, 11 May 2015 at 07:05:30 UTC, Per Nordlöw wrote: So I implemented a first working version of merge() by reusing roundRobin(). Working version at: https://github.com/nordlow/justd/blob/master/range_ex.d#L599 Destroy! I guess we should support bi-directional access through back() and popBack() aswell right?
Re: Merging one Array with Another
On Thursday, 7 May 2015 at 21:53:24 UTC, Per Nordlöw wrote: Thanks. These are good ideas in general. I'm curious to why something like merge isn't already in Phobos. The most similar existing range in Phobos is probably So I implemented a first working version of merge() by reusing roundRobin(). Working version at: https://github.com/nordlow/justd/blob/master/range_ex.d#L599 Destroy!
Re: Merging one Array with Another
On Monday, 11 May 2015 at 07:12:05 UTC, Per Nordlöw wrote: I guess we should support bi-directional access through back() and popBack() aswell right? I believe I have BidirectionalRange support aswell now at https://github.com/nordlow/justd/blob/master/range_ex.d#L597
Re: Merging one Array with Another
On Thursday, 7 May 2015 at 21:53:24 UTC, Per Nordlöw wrote: On Thursday, 7 May 2015 at 13:38:23 UTC, Andrea Fontana wrote: Because it is a more generic operation and you can work on a lazy range. Anyway, to sort and to do uniq it isn't the fastest way. Or maybe I just didn't understand what you really need. :) Thanks. These are good ideas in general. I'm curious to why something like merge isn't already in Phobos. The most similar existing range in Phobos is probably http://dlang.org/phobos/std_range.html#roundRobin I believe MergeRange will be bi-directional right? Further, I believe minElement and maxElement at https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L215 should have a CT-specialization in the case when input is a SortedRange. In that case minElement should return front and maxElement should return back, right? Name could be misleading. This is a sortedrange: [4,3,2,1,0]. In your case minElement is 4, maxElement is 0 :) On ranges with more complex elements sort order can be even less obvious. I think first and back it's ok!
Re: Merging one Array with Another
On Friday, 8 May 2015 at 08:27:19 UTC, Andrea Fontana wrote: Name could be misleading. This is a sortedrange: [4,3,2,1,0]. In your case minElement is 4, maxElement is 0 :) On ranges with more complex elements sort order can be even less obvious. I think first and back it's ok! Ok. I guess you mean front and back right?
Re: Merging one Array with Another
On Friday, 8 May 2015 at 09:23:42 UTC, Per Nordlöw wrote: On Friday, 8 May 2015 at 08:27:19 UTC, Andrea Fontana wrote: Name could be misleading. This is a sortedrange: [4,3,2,1,0]. In your case minElement is 4, maxElement is 0 :) On ranges with more complex elements sort order can be even less obvious. I think first and back it's ok! Ok. I guess you mean front and back right? ahah :) You're right!
Re: Merging one Array with Another
On Thursday, 7 May 2015 at 09:21:58 UTC, Per Nordlöw wrote: I was only interested in removing equal consequtive elements within the same range. I looked at UniqResult. What we need is to fix the typesystem with perhaps some traits the figure out which ranges (multi-layered meta-ranges) posses the sorted property or not.
Re: Merging one Array with Another
On Wednesday, 6 May 2015 at 16:05:15 UTC, Andrea Fontana wrote: Maybe a way like this could be useful: http://dpaste.dzfl.pl/7b4b37b490a7 If r is a SortedRange this is very unneccesary wasteful because of the use AA. In that case you, instead, only want to remove equal consequtive elements without the need for any AA. I'm guessing there's already an algorithm for this somewhere in Phobos. Ideas anyone?
Re: Merging one Array with Another
On Thursday, 7 May 2015 at 06:53:39 UTC, Per Nordlöw wrote: On Wednesday, 6 May 2015 at 16:05:15 UTC, Andrea Fontana wrote: Maybe a way like this could be useful: http://dpaste.dzfl.pl/7b4b37b490a7 If r is a SortedRange this is very unneccesary wasteful because of the use AA. In that case you, instead, only want to remove equal consequtive elements without the need for any AA. I'm guessing there's already an algorithm for this somewhere in Phobos. Ideas anyone? It's not that difficult to implement. You just need to implement a merge() range that returns the min of all ranges' front(). Then you can define distinct() for SortedRange as: merge(sortedrange1, sortedrange2, sortedrange3).uniq Andrea
Re: Merging one Array with Another
On Thursday, 7 May 2015 at 08:03:41 UTC, Andrea Fontana wrote: It's not that difficult to implement. You just need to implement a merge() range that returns the min of all ranges' front(). Then you can define distinct() for SortedRange as: merge(sortedrange1, sortedrange2, sortedrange3).uniq Andrea Why do you need variadics here? Why the need for sortedrange1, sortedrange2 and sortedrange3? I was only interested in removing equal consequtive elements within the same range.
Re: Merging one Array with Another
On Thursday, 7 May 2015 at 13:38:23 UTC, Andrea Fontana wrote: Because it is a more generic operation and you can work on a lazy range. Anyway, to sort and to do uniq it isn't the fastest way. Or maybe I just didn't understand what you really need. :) Thanks. These are good ideas in general. I'm curious to why something like merge isn't already in Phobos. The most similar existing range in Phobos is probably http://dlang.org/phobos/std_range.html#roundRobin I believe MergeRange will be bi-directional right? Further, I believe minElement and maxElement at https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L215 should have a CT-specialization in the case when input is a SortedRange. In that case minElement should return front and maxElement should return back, right?
Re: Merging one Array with Another
On Thursday, 7 May 2015 at 09:21:58 UTC, Per Nordlöw wrote: On Thursday, 7 May 2015 at 08:03:41 UTC, Andrea Fontana wrote: It's not that difficult to implement. You just need to implement a merge() range that returns the min of all ranges' front(). Then you can define distinct() for SortedRange as: merge(sortedrange1, sortedrange2, sortedrange3).uniq Andrea Why do you need variadics here? Why the need for sortedrange1, sortedrange2 and sortedrange3? I was only interested in removing equal consequtive elements within the same range. Because it is a more generic operation and you can work on a lazy range. Anyway, to sort and to do uniq it isn't the fastest way. Or maybe I just didn't understand what you really need. :)
Re: Merging one Array with Another
On Friday, 1 May 2015 at 19:08:51 UTC, Per Nordlöw wrote: What's the fastest Phobos-way of doing either x ~= y; // append x = x.uniq; // remove duplicates or x = (x ~ y).uniq; // append and remove duplicates in one go provided that T[] x, y; ? Maybe a way like this could be useful: http://dpaste.dzfl.pl/7b4b37b490a7
Re: Merging one Array with Another
On Saturday, 2 May 2015 at 04:08:04 UTC, Ali Çehreli wrote: Interesting idea. I have defined a simple algorithm below to see how it could work (my skipped() function instead of uniq()). That's a bit above my current D experience to decide. What about just tweaking uniq() for now to propagate SortedRange and leave the rest for later? Or will this break existing uses of uniq?
Re: Merging one Array with Another
On 05/03/2015 07:56 AM, Per =?UTF-8?B?Tm9yZGzDtnci?= per.nord...@gmail.com wrote: On Saturday, 2 May 2015 at 04:08:04 UTC, Ali Çehreli wrote: Interesting idea. I have defined a simple algorithm below to see how it could work (my skipped() function instead of uniq()). That's a bit above my current D experience to decide. What about just tweaking uniq() for now to propagate SortedRange and leave the rest for later? The implementation seems trivial to me. If others don't object, I suggest you open an enhancement request. Or will this break existing uses of uniq? Other than the fact that uniq may return SortedRange, I don't see any issue. If an existing piece of code was explicitly checking whether a certain range object was UniqResult, no code should be affected. Another possibility is to return UniqResult in both cases but expose the special SortedRange member functions on it if the input were SortedRange. (Again, trivial.) Ali
Re: Merging one Array with Another
On Friday, 1 May 2015 at 19:30:08 UTC, Ilya Yaroshenko wrote: Both variants are wrong because uniq needs sorted ranges. Probably you need something like that: x = x.chain(y).sort.uniq.array; Interesting. Is x = x.chain(y).sort faster than x ~= y; x.sort; ? If so why?
Re: Merging one Array with Another
On Saturday, 2 May 2015 at 10:18:07 UTC, Per Nordlöw wrote: On Friday, 1 May 2015 at 19:30:08 UTC, Ilya Yaroshenko wrote: Both variants are wrong because uniq needs sorted ranges. Probably you need something like that: x = x.chain(y).sort.uniq.array; Interesting. Is x = x.chain(y).sort faster than x ~= y; x.sort; ? If so why? Probably the latter is slower than the former, at the very least because the latter requires memory allocation whereas the former does not.
Re: Merging one Array with Another
On Saturday, 2 May 2015 at 11:16:30 UTC, Meta wrote: Probably the latter is slower than the former, at the very least because the latter requires memory allocation whereas the former does not. Ahh!, auto x = [11, 3, 2, 4, 5, 1]; auto y = [0, 3, 10, 2, 4, 5, 1]; auto z = x.chain(y).sort; // sort them in place assert(x == [0, 1, 1, 2, 2, 3]); assert(y == [3, 4, 4, 5, 5, 10, 11]); is very cool, provided that y is allowed to mutate. Now I understand why chain is useful. A reallocation will however be needed in the final assignment though. But no temporary!
Re: Merging one Array with Another
On Friday, 1 May 2015 at 22:47:17 UTC, Ali Çehreli wrote: It is about the uniqueness of consecutive elements. It says unique consecutive elements. Ali Ah. Then I guess that if input is SortedRange then SortedRange should be returned. Thanks.
Re: Merging one Array with Another
On 05/01/2015 06:39 PM, Per =?UTF-8?B?Tm9yZGzDtnci?=
per.nord...@gmail.com wrote: On Friday, 1 May 2015 at 22:47:17 UTC,
Ali Çehreli wrote:
It is about the uniqueness of consecutive elements. It says unique
consecutive elements.
Ali
Ah.
Then I guess that if input is SortedRange then SortedRange should be
returned.
Interesting idea. I have defined a simple algorithm below to see how it
could work (my skipped() function instead of uniq()).
import std.stdio;
import std.range;
import std.algorithm;
import std.exception;
struct Skipper(R)
{
R range;
this(R range)
{
enforce(range.length % 2 == 0,
This example requires even number of elements);
this.range = range;
}
@property bool empty() { return range.empty; }
@property auto front() { return range.front; }
void popFront()
{
range.popFront();
range.popFront();
}
}
auto skipped(R)(R range)
{
import std.traits;
static if (isInstanceOf!(SortedRange, R)) {
// Nice! Let's add an .assumeSorted at the end
return Skipper!R(range).assumeSorted;
} else {
return Skipper!R(range);
}
}
void use(R)(R range)
{
pragma(msg, R);
writeln(range);
writeln();
}
void main()
{
auto a = [ 1, 2, 3, 4, 5, 6 ];
use(a.skipped);
use(a.assumeSorted.skipped);
}
Prints at compile time:
Skipper!(int[])
SortedRange!(Skipper!(SortedRange!(int[], a b)), a b)
Prints at run time:
[1, 3, 5]
[1, 3, 5]
One issue is that many standard algorithms could benefit from this as
well. Should it be only for SortedRange? What about user defined
types... What if I wanted MyCoolRange to be appended automatically as
.myCoolRange. Could there we standard mechanism to support any range type?
Maybe the answer is a helper mixin that defines a template
specialization for SortedRange!(R2, Func) instead of my 'static if'
solution. (I was too impatient to get that syntax right. :) )
Ali
Re: Merging one Array with Another
fix: completeSort(x.assumeSorted, y); x = x.chain(y).uniq.array; or (was fixed) y = y.sort().uniq.array; completeSort(x.assumeSorted, y); x ~= y;
Re: Merging one Array with Another
On Friday, 1 May 2015 at 19:30:08 UTC, Ilya Yaroshenko wrote: Probably you need something like that: x = x.chain(y).sort.uniq.array; You're right: import std.stdio, std.algorithm, std.range; auto x = [11, 3, 2, 4, 5, 1]; auto y = [0, 3, 10, 2, 4, 5, 1]; writeln(x.chain(y).uniq); writeln(x.chain(y).sort.uniq); outputs [11, 3, 2, 4, 5, 1, 0, 3, 10, 2, 4, 5, 1] [0, 1, 2, 3, 4, 5, 10, 11] so why doesn't http://dlang.org/phobos/std_algorithm_iteration.html#.uniq say anything about need for sortness!? I expected D to be strict here and SortedRange as input to uniq.
Re: Merging one Array with Another
On 05/01/2015 03:41 PM, Per =?UTF-8?B?Tm9yZGzDtnci?= per.nord...@gmail.com wrote: so why doesn't http://dlang.org/phobos/std_algorithm_iteration.html#.uniq say anything about need for sortness!? It is about the uniqueness of consecutive elements. It says unique consecutive elements. Ali
Re: Merging one Array with Another
fix: completeSort(x.assumeSorted, y); x = x.chain(y).uniq.array; or completeSort(x.assumeSorted, y.uniq.array); x ~= y; On Friday, 1 May 2015 at 19:34:20 UTC, Ilya Yaroshenko wrote: If x is already sorted x = x.completeSort(y).uniq.array; On Friday, 1 May 2015 at 19:30:08 UTC, Ilya Yaroshenko wrote: Both variants are wrong because uniq needs sorted ranges. Probably you need something like that: x = x.chain(y).sort.uniq.array; On Friday, 1 May 2015 at 19:08:51 UTC, Per Nordlöw wrote: What's the fastest Phobos-way of doing either x ~= y; // append x = x.uniq; // remove duplicates or x = (x ~ y).uniq; // append and remove duplicates in one go provided that T[] x, y; ?
Re: Merging one Array with Another
Both variants are wrong because uniq needs sorted ranges. Probably you need something like that: x = x.chain(y).sort.uniq.array; On Friday, 1 May 2015 at 19:08:51 UTC, Per Nordlöw wrote: What's the fastest Phobos-way of doing either x ~= y; // append x = x.uniq; // remove duplicates or x = (x ~ y).uniq; // append and remove duplicates in one go provided that T[] x, y; ?
Re: Merging one Array with Another
If x is already sorted x = x.completeSort(y).uniq.array; On Friday, 1 May 2015 at 19:30:08 UTC, Ilya Yaroshenko wrote: Both variants are wrong because uniq needs sorted ranges. Probably you need something like that: x = x.chain(y).sort.uniq.array; On Friday, 1 May 2015 at 19:08:51 UTC, Per Nordlöw wrote: What's the fastest Phobos-way of doing either x ~= y; // append x = x.uniq; // remove duplicates or x = (x ~ y).uniq; // append and remove duplicates in one go provided that T[] x, y; ?
Merging one Array with Another
What's the fastest Phobos-way of doing either x ~= y; // append x = x.uniq; // remove duplicates or x = (x ~ y).uniq; // append and remove duplicates in one go provided that T[] x, y; ?
