You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Currently Indexes acts like a lookup table between absolute positions and IDs. However, this makes modification to the tree as discussed in #13 expensive since the entire Indexes struct would have to be updated, or remade from scratch. Instead each Links could store the length of the token and functions could iteratively search the tree to find the token at that position.
Advantages
Links stores one usize for len instead of two for Span
Searching for an index goes from O(log_2 n) to O(log_a n) where a is the average number of child nodes per parent. This could be an advantage or disadvantage depending on the language's grammar.
I may be missing something obvious, but as far as I can tell all of the current API could be implemented this way. I'll prototype it later tonight and see how it goes 🤷♂️
The text was updated successfully, but these errors were encountered:
Currently
Indexes
acts like a lookup table between absolute positions and IDs. However, this makes modification to the tree as discussed in #13 expensive since the entireIndexes
struct would have to be updated, or remade from scratch. Instead eachLinks
could store the length of the token and functions could iteratively search the tree to find the token at that position.Advantages
Links
stores one usize forlen
instead of two forSpan
I may be missing something obvious, but as far as I can tell all of the current API could be implemented this way. I'll prototype it later tonight and see how it goes 🤷♂️
The text was updated successfully, but these errors were encountered: