On the subject of an XML parser

[tsbockman]

On Monday, 3 October 2022 at 17:10:29 UTC, Ali Çehreli wrote:
> Yes but blocks_ does not carry elements but blocks to place 
> elements on.

I meant "elements" in the general sense of "items in an array". 
The blocks are stored in an array, and hence are "elements".

> Here, we have O(M); if M (number of blocks) is small compared 
> to N (number of live elements as in a sliding window), then we 
> have just a few blocks to shuffle with 
> std.algorithm.bringToFront.)
>
> addExistingBlock_() is called only when existing blocks are all 
> in use.
>
> The typical use case is a sliding window of cached elements. 
> Empty blocks at the frot are moved to the end and they get 
> reused for new elements later.

I don't think this changes the big O run time analysis. It sounds 
like, at least in the worst case, **M** is proportional to **N**, 
meaning that for big O purposes **M** is **N**.

Regardless, it would still be **O(1)** amortized time like you 
said before. To change that **M** would have to be greater than 
**N**, which never happens.