• RazvanN (14/14) Nov 11 2016 I am trying to concatenate 2 ranges of the same type (SortedRange
• Vladimir Panteleev (6/12) Nov 11 2016 .array allocates, so it's going to be O(n), but the allocation
• RazvanN (7/20) Nov 11 2016 It does work, the problem is that [1, 2, 3].sort() is of type
• Vladimir Panteleev (19/24) Nov 11 2016 If you absolutely need a `SortedRange(int[], "a < b")` without
• Saurabh Das (8/22) Nov 11 2016 I think chain of 2 sorted ranges will not necessarily be sorted.

RazvanN <razvan.nitu1305 gmail.com> writes:

I am trying to concatenate 2 ranges of the same type (SortedRange 
in my case). I have tried merge, join and chain, but the problem 
is that the result is not an object of the type of the initial 
ranges. For example:

1. If I use chain(r1, r2), the result will be an object of type 
Result which I cannot cast to my specific type (SortedRange).

2. If I use merge(r1, r2), the result will be an object of type 
Merge!(typeof(r1), typeof(r)).

I know that I can use the .array property, but I think that this 
iterates through all of my elements. Using assumeSorted(chain(r1, 
r2).array) will return a SortedRange, but I am not sure what the 
complexity for this operation is.

Is there a way to concatenate 2 ranges (SortedRange in my case) 
in O(1) time?

Vladimir Panteleev <thecybershadow.lists gmail.com> writes:

On Friday, 11 November 2016 at 13:30:17 UTC, RazvanN wrote:
 I know that I can use the .array property, but I think that 
 this iterates through all of my elements. Using 
 assumeSorted(chain(r1, r2).array) will return a SortedRange, 
 but I am not sure what the complexity for this operation is.

.array allocates, so it's going to be O(n), but the allocation 
will probably be more expensive.

 Is there a way to concatenate 2 ranges (SortedRange in my case) 
 in O(1) time?

assumeSorted(chain(a, b)) ?

This works for me:

auto r = assumeSorted(chain([1, 2, 3].sort(), [1, 2, 3].sort()));

RazvanN <razvan.nitu1305 gmail.com> writes:

On Friday, 11 November 2016 at 13:33:20 UTC, Vladimir Panteleev 
wrote:
 On Friday, 11 November 2016 at 13:30:17 UTC, RazvanN wrote:
 I know that I can use the .array property, but I think that 
 this iterates through all of my elements. Using 
 assumeSorted(chain(r1, r2).array) will return a SortedRange, 
 but I am not sure what the complexity for this operation is.

 .array allocates, so it's going to be O(n), but the allocation 
 will probably be more expensive.

 Is there a way to concatenate 2 ranges (SortedRange in my 
 case) in O(1) time?

 assumeSorted(chain(a, b)) ?

 This works for me:

 auto r = assumeSorted(chain([1, 2, 3].sort(), [1, 2, 
 3].sort()));

It does work, the problem is that [1, 2, 3].sort() is of type 
SortedRange(int[], "a < b") while r is of type 
SortedRange(Result, "a < b"). This is a problem if you want to 
return r in a function which has return type SortedRange(int[], 
"a < b").

Vladimir Panteleev <thecybershadow.lists gmail.com> writes:

On Friday, 11 November 2016 at 13:39:32 UTC, RazvanN wrote:
 It does work, the problem is that [1, 2, 3].sort() is of type 
 SortedRange(int[], "a < b") while r is of type 
 SortedRange(Result, "a < b"). This is a problem if you want to 
 return r in a function which has return type SortedRange(int[], 
 "a < b").

If you absolutely need a `SortedRange(int[], "a < b")` without 
substitute, then there's no way except building an array that has 
the numbers sorted, which is always going to be O(n) unless you 
can place the two input arrays adjacent into memory beforehand 
somehow. However, if you just want the pre-chain ranges and 
post-chain ranges be a compatible type, you can use a class 
wrapper, such as RandomAccessFinite - thus, the assumeSorted 
result will be `SortedRange(RandomAccessFinite, "a < b")`. Note, 
though, that even though the algorithmic complexity will be O(1), 
every access to the wrapped range will go through a virtual 
method call, so it will affect performance in practice. There is 
no way around this because the type pulls in the underlying 
range's behavior, and e.g. SortedRange!(int[]) knows that the 
underlying elements are arranged linearly in memory, SortedRange 
of a chain knows that it first has to check which sub-range any 
operation will refer to, and SortedRange of a RandomAccessFinite 
knows that it just has to pass the request to a virtual class 
method which hides the underlying implementation.

Saurabh Das <saurabh.das gmail.com> writes:

On Friday, 11 November 2016 at 13:30:17 UTC, RazvanN wrote:
 I am trying to concatenate 2 ranges of the same type 
 (SortedRange in my case). I have tried merge, join and chain, 
 but the problem is that the result is not an object of the type 
 of the initial ranges. For example:

 1. If I use chain(r1, r2), the result will be an object of type 
 Result which I cannot cast to my specific type (SortedRange).

 2. If I use merge(r1, r2), the result will be an object of type 
 Merge!(typeof(r1), typeof(r)).

 I know that I can use the .array property, but I think that 
 this iterates through all of my elements. Using 
 assumeSorted(chain(r1, r2).array) will return a SortedRange, 
 but I am not sure what the complexity for this operation is.

 Is there a way to concatenate 2 ranges (SortedRange in my case) 
 in O(1) time?

I think chain of 2 sorted ranges will not necessarily be sorted.

For example, chain([1, 2, 10], [4, 5, 11]) -> [1, 2, 10, 4, 5, 
11] which is not sorted.

You will need some kind of a merge to get a sorted range from 2 
already sorted ranges.

Thanks,
SD