bytestring-trie
bytestring-trie copied to clipboard
Asymptotic complexity of functions deleting values
When using the internal functions arc
, arc_
, arcNN
, or prepend
to rebuild the spine after deleting values, under certain circumstances we can end up chaining those together and thus encounter an asymptotic slowdown similar to #25 (albeit greatly reduced in scope and severity). However, unlike #25, the bug here is not intrinsic to the data structure. We should be able to adjust those functions to behave more like a zipper, and only do the bytestring concatenation once an arc is "complete" (akin to the use of RevLazyByteString
in the priority-queue functions).