## digitalmars.D.learn - Concatenate 2 ranges

• 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?
```
Nov 11 2016
```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()));
```
Nov 11 2016
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").
```
Nov 11 2016
```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),
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.
```
Nov 11 2016
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