Requirements for Slicing Ranges

[Richard (Rikki) Andrew Cattermole]

On 02/09/2024 4:35 PM, Jonathan M Davis wrote:
> On Sunday, September 1, 2024 9:31:23 PM MDT Richard (Rikki) Andrew Cattermole
> via Digitalmars-d wrote:
>> On 02/09/2024 2:47 PM, Jonathan M Davis wrote:
>>> Can anyone see something that I'm missing here?
>>
>> Indexing and range intervals are indeed distinct things.
>>
>> An interval does not have to evaluate to a specific bit of data, but an
>> index does.
>>
>> They can also use non-integral keys.
>>
>> Typically both ``size_t`` and ``ptrdiff_t`` will have defined
>> sequentiality, but they may not in the case of a map. Whereby an index
>> works but not an interval.
>>
>> So the question is, how many assumptions surrounding sequentiality is
>> being made, along with the key type?
> 
> The range API uses size_t for indices, and it is required that the indices
> be sequential. range[3] gives you the 4th element and range[3 .. 9] gives
> you a 6 element range starting at the 4th element.
> 
> Containers may do other things with keys (particularly containers like hash
> tables and sorted maps), but the range API treats indices the same way that
> arrays do. Doing anything else would complicate things considerably, and if
> anything, the range API is arguably already too complex.
> 
> In essence, the range API provides an abstraction based on arrays, with
> random-access ranges providing the full capabilities of a dynamic array /
> slice aside from the capabilities related to increasing their size or doing
> any kind allocations. Each lower category of range then loses capabilities
> as it moves further away from being an array, with basic input ranges just
> providing a way to iterate through the elements once and nothing else. Or,
> if you want to view the situation in reverse, we start with a basic input
> range being only able to iterate through a sequential list of elements once,
> and each category of range builds up towards the capabilities of an array.
> 
> As such, the situation with keys is simple in that there are no keys in the
> general sense. We're just dealing with indices, and an index needs to mean
> the same thing that it would with an array. It's simply a question of where
> in the hierarchy we put each capability.
> 
> Indexing requires random-access ranges. Slicing at present does not, but as
> far as I can tell, from a technical persective, with regards to a sequential
> data structure such as a range, it is not possible to implement indexing
> without also being able to implement slicing, and I don't see how it would
> be possible to implement slicing but not be possible to implement indexing.
> 
> Non-sequential data structures really don't have anything to do with ranges
> aside from cases where such a data structure provides a sequential view into
> its data via a range.
> 
> - Jonathan M Davis

Your question appears to be answered :)