2.2 Windows, internal vertices, and left children
For a position \(i\) in \(w\), its window is the interval \([i,\; i + \operatorname {win}_i(w))\), the in-order range of the subtree rooted at the \(\mathrm{Node}\) for position \(i\) in \(M(w)\).
\(\operatorname {win}_i(w)\) is defined by fuel-based recursion that descends \(M(w)\) via \(\texttt{mm\_ pos}\): at the root position one returns \(|w| - i\); otherwise one recurses into the left or right subtree according to whether \(i\) lies before or after the root.
Position \(i\) is internal in \(w\) iff \(i {\lt} |w|\) and \(\operatorname {win}_i(w) {\gt} 1\). Equivalently, the \(\mathrm{Node}\) for position \(i\) in \(M(w)\) has at least one non-\(\mathrm{Leaf}\) child.
\(\operatorname {hlc}_i(w)\) is true iff in \(M(w)\) the \(\mathrm{Node}\) at position \(i\) has a non-\(\mathrm{Leaf}\) left subtree. This is Stanley’s \(\operatorname {hlc}\) predicate from p. 57 (it distinguishes the cd-letters c and d; see Chapter 3).
\(\texttt{internal\_ vertices}(w)\) is the strictly increasing sequence of positions \(i\) for which \(\operatorname {int}_i(w)\) holds.