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 2020
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 2020
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 2020
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 2020