www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - More flexible sorted ranges?

reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Nov 02 2014
next sibling parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
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?
Nov 02 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Ola Fosheim Grøstad:


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


Yes, of course.

Bye,
bearophile
Nov 02 2014
parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
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).
Nov 02 2014
parent reply "Xinok" <xinok live.com> writes:
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/
Nov 02 2014
parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
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 ]
Nov 02 2014
next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
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.
Nov 02 2014
prev sibling parent reply "Xinok" <xinok live.com> writes:
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
Nov 02 2014
parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
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".
Nov 02 2014
prev sibling next sibling parent reply "Xinok" <xinok live.com> writes:
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?
Nov 02 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Nov 02 2014
parent reply "Xinok" <xinok live.com> writes:
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?
Nov 02 2014
parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
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… ;)
Nov 02 2014
prev sibling next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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.
Dec 03 2014
prev sibling parent "Tobias Pankrath" <tobias pankrath.net> writes:
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.
Dec 04 2014