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

On Sunday, 2 November 2014 at 15:13:37 UTC, bearophile wrote:
> 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.

Shouldn't sorted range maintain the invariant automatically in order to remain typesafe?

Ola Fosheim Grøstad:

> Shouldn't sorted range maintain the invariant automatically in order to remain typesafe?

Yes, of course.

Bye,
bearophile

On Sunday, 2 November 2014 at 16:59:30 UTC, bearophile wrote:
> Ola Fosheim Grøstad:
>
>> Shouldn't sorted range maintain the invariant automatically in order to remain typesafe?
>
> Yes, of course.

If SortedRange is fixed, please also switch the names of upperBound and lowerBound… They are currently wrong. An upperBound on something should return the values lower than it and a lowerBound should return values larger…

(C++ got it right).

On Sunday, 2 November 2014 at 17:21:04 UTC, Ola Fosheim Grøstad wrote:
> On Sunday, 2 November 2014 at 16:59:30 UTC, bearophile wrote:
>> Ola Fosheim Grøstad:
>>
>>> Shouldn't sorted range maintain the invariant automatically in order to remain typesafe?
>>
>> Yes, of course.
>
> If SortedRange is fixed, please also switch the names of upperBound and lowerBound… They are currently wrong. An upperBound on something should return the values lower than it and a lowerBound should return values larger…
>
> (C++ got it right).

D got it right. C++ returns an iterator which can be a bit confusing. D returns a slice so it's meaning is much clearer.

https://en.wikipedia.org/wiki/Upper_and_lower_bounds

http://www.cplusplus.com/reference/algorithm/upper_bound/

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

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?

On Sunday, 2 November 2014 at 19:54:38 UTC, Xinok wrote:
> D got it right. C++ returns an iterator which can be a bit confusing. D returns a slice so it's meaning is much clearer.
>

No, according to docs D has defined the lower bound to be the negation of the lower bound…

> https://en.wikipedia.org/wiki/Upper_and_lower_bounds

Quoting your link:
«5 is lower bound for the set { 5, 10, 34, 13934 }»

Hence if you lowerBound(4) the sequence

[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

it should return

[ 4, 5, 6, 7, 8, 9 ]

not

[ 0, 1, 2, 3 ]

http://dlang.org/phobos/std_range.html#.SortedRange.lowerBound

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

And while you're at it, consider fixing the name to be accurate. Call it:

lowerBoundedBy(value)

or something similar.

A lower bound is a single element, not a set.

On Sunday, 2 November 2014 at 20:06:51 UTC, Ola Fosheim Grøstad wrote:
> On Sunday, 2 November 2014 at 19:54:38 UTC, Xinok wrote:
>> D got it right. C++ returns an iterator which can be a bit confusing. D returns a slice so it's meaning is much clearer.
>>
>
> No, according to docs D has defined the lower bound to be the negation of the lower bound…
>

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

In terms of what to call it, perhaps what you're looking for is "upper set"?

https://en.wikipedia.org/wiki/Upper_set