operator grapheme tree

jaynuine commented

2026-08-07 07:18:17 +00:00

Owner

store operator graphemes in a diff tree, where only differing string subsections are stored, with root to leaf verticality encoding left to right order, and horizontality mapping to a greater than relation between strings (bucket comparison)

so to traverse the tree test for issubstr{operator, token} to descend, and since all strings of a layer are comparable by >, subsequent tests should be optimised by only considering strings still in range after each comparison (chaudfroid)

a
b
- a
- d
- k
- v
m
w
x

token := "bd"

we need not test for unnecessary possibilities ; beginning at the root layer, the character b is between a and x, so we pick a value near the middle of our interval (just pick one of the middle two on even lengths) and the result of comparing the current character (b) to the chosen middle (let's say m) will inform us of which slice of the layer may hold an exact match ;
since b < m, we will be interested in the left half ; so we redefine our search bracket to this interval, and repeat until a match is found, or none is ; assuming the former, we may plunge one level deeper, and continue matching from there, offsetting the token of course by the length of the previously matched segment

store operator graphemes in a diff tree, where only differing string subsections are stored, with root to leaf verticality encoding left to right order, and horizontality mapping to a greater than relation between strings (bucket comparison) so to traverse the tree test for issubstr{operator, token} to descend, and since all strings of a layer are comparable by `>`, subsequent tests should be optimised by only considering strings still in range after each comparison (chaudfroid) - a - b - a - d - k - v - m - w - x token := "bd" we need not test for unnecessary possibilities ; beginning at the root layer, the character `b` is between `a` and `x`, so we pick a value near the middle of our interval (just pick one of the middle two on even lengths) and the result of comparing the current character (`b`) to the chosen middle (let's say `m`) will inform us of which slice of the layer may hold an exact match ; since `b < m`, we will be interested in the left half ; so we redefine our search bracket to this interval, and repeat until a match is found, or none is ; assuming the former, we may plunge one level deeper, and continue matching from there, offsetting the token of course by the length of the previously matched segment

jaynuine added this to the todo project

2026-08-07 07:18:17 +00:00

jaynuine commented

2026-08-07 07:21:03 +00:00

Author

Owner

this may be overkill for the few operators we have
> < >> << |
and i guess $ could be implemented as one since this would allow precedence ?

this may be overkill for the few operators we have `>` `<` `>>` `<<` `|` and i guess `$` could be implemented as one since this would allow precedence ?

jaynuine commented

2026-08-07 10:10:31 +00:00

Author

Owner

yea this is overkill let's just implement this naively

jaynuine added the

area

parsing

label

2026-08-14 05:45:37 +00:00

Rows
Columns

operator grapheme tree #4