On Sunday, 2 November 2014 at 20:19:12 UTC, bearophile wrote:
> Xinok:
>
>> My concern is that SortedRange only accepts a range which is random-access and limits its functionality to those primitives. Concatenation is not required for random-access ranges, so should we expect SortedRange to overload this operator?
>
> I understand, that's why I am asking this here...
> I think the desire to keep a sorted range around and grow it keeping its invariant is a common enough need for my code. Currently I keep an array then I use assumeSorted + upperBound, but this is not safe nor nice.
> Perhaps sorted ranges should become more transparent in Phobos.
>
> There are other invariants beside sortness that can be useful to carry around, like set-ness (every item is unique inside this collection) and few more.
>
> Bye,
> bearophile

I take back my original argument. As of 2.066, the requirements for SortedRange have been relaxed so it now accepts input ranges. The documentation needs to be updated to reflect this change.

Still, I'm not comfortable to adding concatenation to SortedRange. I would prefer named functions which append / prepend elements with the guarantee that it preserves the invariant.

In general, I don't feel that SortedRange is an ideal solution anyways. Wrapping ranges in a struct adds too much overhead and we can't extend the functionality of it. Would it be possible to replace SortedRange with a @sorted attribute or something?

On Sunday, 2 November 2014 at 21:35:00 UTC, Xinok wrote:
> Sorry, you're right, it's not an "upper bound". I read that definition a few times over and still got it wrong. O_o

It is always easier to look for the examples :-).

> In terms of what to call it, perhaps what you're looking for is "upper set"?
>
> https://en.wikipedia.org/wiki/Upper_set

Hm… I think an "upper set" requires that element is present it in the set. I assume you want to be able to do something like:

a.lowerBounded(2).upperBounded(10) and then get "for all x in a where 2 <= x <= 10".

On Sunday, 2 November 2014 at 22:14:33 UTC, Xinok wrote:
> In general, I don't feel that SortedRange is an ideal solution anyways. Wrapping ranges in a struct adds too much overhead and we can't extend the functionality of it. Would it be possible to replace SortedRange with a @sorted attribute or something?

You might be interested in the this proposal:

http://forum.dlang.org/thread/tpctqjlvnrrasiktehaq@forum.dlang.org

I think it is doable… ;)

On Sunday, 2 November 2014 at 15:13:37 UTC, bearophile wrote:
> SortedRange!(Foo[], q{ a.x < b.x }) data;
> data ~= Foo(5);
> immutable n = data.upperBound(Foo(2)).length;

Have anybody implemented SortedRange? I can't find any refs.

On Sunday, 2 November 2014 at 15:13:37 UTC, bearophile wrote:
> I have often arrays that are sorted, and sometimes I'd like to append items to them. So I'd like to write something like:
>
>
> SortedRange!(Foo[], q{ a.x < b.x }) data;
> data ~= Foo(5);
> immutable n = data.upperBound(Foo(2)).length;
>
>
> This means having an array of Foos as sorted range, and appending an item to it keeping the sorting invariant (so in non-release mode the append verifies the array is empty or the last two items satisfy the sorting invariant), and this allows me to call functions like upperBound any time I want on 'data' without using any unsafe and unclean assumeSorted.
>
> Is this possible and a good idea to do?
>
> Bye,
> bearophile

To make it compatible with std.container, you should call it Sorted(T, pred) and make it a accept any std.container, whose opSlice returns a RandomAccesRange. A Sorted(Array!U, pred) wouldn't itself be a RandomAcessRange but a container and it's opSlice should return a SortedRange.

The algorithms that work on arrays and currently return a SortedRange could retur n a Sorted!(U[], pred) instead.