commit f1bf6810ddfff1b5aa7b03c8ce85e05ad6e74b59
parent 70cdf3c3b997031c0f9ad15586cc5ede030c0112
Author: robert <robertrussell.72001@gmail.com>
Date: Fri, 14 Jan 2022 11:54:33 -0800
Remove broken prepending operations for tok and toks
Diffstat:
1 file changed, 18 insertions(+), 8 deletions(-)
diff --git a/queue.tex b/queue.tex
@@ -7,10 +7,6 @@
\newbox\qbox
\newtoks\qtoks
-% TODO make expandable with immediateassignment?
-% TODO option to avoid all \deferasn's to improve performance?
-% \def\@pushcount{\penalty\pcount} % \afterassignment this, instead of deferasn
-
\newif\if@qapp \@qappfalse
\newif\if@qpeek \@qpeekfalse
\protected\def\newq#1{\newbox#1\g\setbox#1=\hbox{\penalty0}}
@@ -31,16 +27,30 @@
\protected\def\preskip {\deferasn{\@qq{\hskip\qskip}\g\qskip=}\@qn=}
\protected\def\premuskip{\deferasn{\@qq{\hskip\mutoglue\qmuskip}\g\qmuskip=}\@qn=}
\protected\def\prebox {\deferasn{\@qq{\box\qbox}\g\setbox\qbox=}\@qn=}
-\protected\def\pretoks {\deferasn{\@qq{\xcsdef\@qcs{\the\qtoks}\gincr\@qt}\g\qtoks=}\@qn=}
-\protected\def\pretok {\deferasn{\@qq{\gcslet\@qcs\qtok\gincr\@qt}\glet\qtok=}\@qn=}
+% TODO: Implement prepending of tok and toks, which have their own stacking
+% mechanism using \@qt. My current idea for how to implement this is to track
+% two integers, \@qh (head) and \@qt (tail), for the allocation of unique
+% control sequences for tok and toks. Prepending would decrement \@qh,
+% appending would increment \@qt, and popping would decrement \@qt. This
+% naive implementation would have \@qh never increase, which would potentially
+% allocate an essentially unbounded number of control sequences in TeX's hash
+% table. To get around this, we could "compact the queue" whenever
+% (\@qh - \@qt) >= \@qt >= -threshold, where threshold is some arbitrary value
+% like 100 to avoid the overhead of compaction. By "compact the queue", we mean
+% shift all the entries over so that \@qt becomes 0 and \@qh becomes
+% \@qh - \@qt. With this compaction scheme, appends and prepends remain
+% constant time operations, whereas popping becomes amortized constant
+% (assuming that compaction happens only after pops).
+% \protected\def\pretoks{?}
+% \protected\def\pretok{?}
\protected\def\pushcount {\@qapptrue \precount}
\protected\def\pushdimen {\@qapptrue \predimen}
\protected\def\pushskip {\@qapptrue \preskip}
\protected\def\pushmuskip{\@qapptrue \premuskip}
\protected\def\pushbox {\@qapptrue \prebox}
-\protected\def\pushtoks {\@qapptrue \pretoks}
-\protected\def\pushtok {\@qapptrue \pretok}
+\protected\def\pushtoks {\@qapptrue \deferasn{\@qq{\xcsdef\@qcs{\the\qtoks}\gincr\@qt}\g\qtoks=}\@qn=}
+\protected\def\pushtok {\@qapptrue \deferasn{\@qq{\gcslet\@qcs\qtok\gincr\@qt}\glet\qtok=}\@qn=}
\protected\def\popcount {\@qq{\g\qcount\lastpenalty \if@qpeek\else\unpenalty\fi}\@qn=}
\protected\def\popdimen {\@qq{\g\qdimen\lastkern \if@qpeek\else\unkern\fi}\@qn=}
