On the subject of an XML parser

[tsbockman]

On Monday, 12 September 2022 at 09:29:11 UTC, Ali Çehreli wrote:
> On 8/24/22 08:16, Ali Çehreli wrote:
>   https://code.dlang.org/packages/alid
>
> > (Aside: It actually makes a RandomAccessRange because it
> supports
> > opIndex as well but it does not honor O(1): It will grab 'n'
> elements if
> > you say myRange[n] and if those elements are not in the cache
> yet.)
>
> I realized that it is still O(1) because the seemingly 
> unnecessarily grabbed elements would still count as "amortized" 
> because they are readily available at O(1) for consumption of 
> both this range and all its .save'd ranges.

I believe it's actually **O(log(n))** amortized because 
`CircularBlocks.addExistingBlock_` will reallocate `blocks` and 
move the contents over to the new address, an **O(n)** operation, 
for every **O(log(n))** accesses to `ElementCache`.

(This extra **O(log(n))** factor is typical for 
[Appender](https://dlang.org/phobos/std_array.html#Appender)-like 
systems.)