www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - What's the deal with SortedRange

reply Steven Schveighoffer <schveiguy gmail.com> writes:
This type has some annoying characteristics. Are these intentional? Are 
they up for debate?

1. elem in sortedRange => bool, not typeof(elem)*. Why?
2. No access to input range, except via "release" which is a completely 
ineffective mechanism to "ensure sortedness". Ways to circumvent:
    a. r.save.release
    b. r[0] = r[$-1];
    c. r.sort!("a > b") (yes, this works).
    d. just modify the original input data.

I find the "is this element in here, and if so, give me a reference" 
mechanism you HAVE TO USE super super-annoying.

i.e. instead of if(auto ptr = elem in sortedRange) { /* use ptr */ }
you have to do:

auto eqr = sortedRange.equalRange(elem);
if(!eqr.empty) { /* use eqr.front */ }

Can we fix the API? I'd like to see `elem in r` become a pointer (if 
possible). I'd also like to see a non-destructive way to get the input 
as the "protections" against breaking sorting are so lacking that you 
might as well make the type easier to use. Like maybe alias this the 
input, and get rid of the release thing.

-Steve
Apr 19
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 4/19/20 3:54 PM, Steven Schveighoffer wrote:

 i.e. instead of if(auto ptr = elem in sortedRange) { /* use ptr */ }
 you have to do:
 
 auto eqr = sortedRange.equalRange(elem);
 if(!eqr.empty) { /* use eqr.front */ }
Another bug I just found. The above doesn't even work for my case. https://issues.dlang.org/show_bug.cgi?id=20751 -Steve
Apr 19
parent reply 9il <ilyayaroshenko gmail.com> writes:
On Sunday, 19 April 2020 at 21:06:41 UTC, Steven Schveighoffer 
wrote:
 On 4/19/20 3:54 PM, Steven Schveighoffer wrote:

 i.e. instead of if(auto ptr = elem in sortedRange) { /* use 
 ptr */ }
 you have to do:
 
 auto eqr = sortedRange.equalRange(elem);
 if(!eqr.empty) { /* use eqr.front */ }
Another bug I just found. The above doesn't even work for my case. https://issues.dlang.org/show_bug.cgi?id=20751 -Steve
The following API is used for Mir [1] - transitionIndex - assumeSortedEqualIndex - assumeSortedContains The sorted range type looks to me like overengineering. Mir's Series [2] allows getting pointers, but it is a sorted dictionary composed of two arrays (keys and values). The "in" operator is always system because it can return null pointer. The safe alternative is `tryGet`. [1] http://mir-algorithm.libmir.org/mir_ndslice_sorting.html [2] http://mir-algorithm.libmir.org/mir_series.html
Apr 19
parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 4/19/20 10:33 PM, 9il wrote:
 On Sunday, 19 April 2020 at 21:06:41 UTC, Steven Schveighoffer wrote:
 On 4/19/20 3:54 PM, Steven Schveighoffer wrote:

 i.e. instead of if(auto ptr = elem in sortedRange) { /* use ptr */ }
 you have to do:

 auto eqr = sortedRange.equalRange(elem);
 if(!eqr.empty) { /* use eqr.front */ }
Another bug I just found. The above doesn't even work for my case. https://issues.dlang.org/show_bug.cgi?id=20751
The following API is used for Mir [1]  - transitionIndex  - assumeSortedEqualIndex  - assumeSortedContains The sorted range type looks to me like overengineering.
The nice thing is that the assumption that the data is sorted can be part of the type. So for instance, you can require a sorted range as a function parameter. I don't think the idea of having a specific type for sorted data is overengineering, but the limitations are annoying and not fit for purpose anyway.
 Mir's Series [2] allows getting pointers,  but it is a sorted dictionary 
 composed of two arrays (keys and values). The "in" operator is always 
  system because it can return null pointer. The safe alternative is 
 `tryGet`.
safe code can return null pointers. -Steve
Apr 20