queue.tex (3638B)
1 \newcount\@qn 2 \newcount\@qt 3 \newcount\qnum 4 \newdimen\qdim 5 \newskip\qskip 6 \newmuskip\qmu 7 \newbox\qbox 8 \newtoks\qtoks 9 \newif\if@qapp 10 \newif\if@qpeek 11 12 \protected\def\newqueue#1{\newbox#1\gsetbox#1=\hbox{\penalty0}} 13 \protected\def\gnewqueue{\@galloctrue \newqueue} 14 \let\freequeue=\freebox 15 16 \def\@qexec{% 17 \gsetbox\@qn=\hbox{\unhbox\@qn \global\@qt=\lastpenalty \unpenalty}% 18 \gsetbox\@qn=\hbox{% 19 \if@qapp \unhbox\@qn \fi 20 \@qop 21 \unhbox\@qn % no op iff @qapp is true 22 \penalty\@qt 23 }% 24 } 25 \def\@qmodify#1{\def\@qop{#1}\afterassignment\@qexec\@qn=} 26 \def\@qcs{q:\the\@qn:\the\@qt} 27 28 \def\@qwnum {\@qmodify{\penalty\qnum}} 29 \def\@qwdim {\@qmodify{\kern\qdim}} 30 \def\@qwskip{\@qmodify{\hskip\qskip}} 31 \def\@qwmu {\@qmodify{\hskip\mutoglue\qmu}} 32 \def\@qwbox {\@qmodify{\box\qbox}} 33 \def\@qwtoks{\@qmodify{\xcsdef\@qcs{\the\qtoks}\gincr\@qt}} 34 \def\@qwtok {\@qmodify{\gcslet\@qcs\qtok\gincr\@qt}} 35 36 \protected\def\prenum {\@qappfalse \@qwnum} 37 \protected\def\predim {\@qappfalse \@qwdim} 38 \protected\def\preskip{\@qappfalse \@qwskip} 39 \protected\def\premu {\@qappfalse \@qwmu} 40 \protected\def\prebox {\@qappfalse \@qwbox} 41 % TODO: Implement prepending of tok and toks, which have their own stacking 42 % mechanism using \@qt. My current idea for how to implement this is to track 43 % two integers, \@qh (head) and \@qt (tail), for the allocation of unique 44 % control sequences for tok and toks. Prepending would decrement \@qh, 45 % appending would increment \@qt, and popping would decrement \@qt. This 46 % naive implementation would have \@qh never increase, which would potentially 47 % allocate an essentially unbounded number of control sequences in TeX's hash 48 % table. To get around this, we could "compact the queue" whenever 49 % (\@qh - \@qt) >= \@qt >= -threshold, where threshold is some arbitrary value 50 % like 100 to avoid the overhead of compaction. By "compact the queue", we mean 51 % shift all the entries over so that \@qt becomes 0 and \@qh becomes 52 % \@qh - \@qt. With this compaction scheme, appends and prepends remain 53 % constant time operations, whereas popping becomes amortized constant 54 % (assuming that compaction happens only after pops). 55 56 \protected\def\pushnum {\@qapptrue \@qwnum} 57 \protected\def\pushdim {\@qapptrue \@qwdim} 58 \protected\def\pushskip{\@qapptrue \@qwskip} 59 \protected\def\pushmu {\@qapptrue \@qwmu} 60 \protected\def\pushbox {\@qapptrue \@qwbox} 61 \protected\def\pushtoks{\@qapptrue \@qwtoks} 62 \protected\def\pushtok {\@qapptrue \@qwtok} 63 64 \def\@qrnum {\@qmodify{\global\qnum\lastpenalty \if@qpeek\else\unpenalty\fi}} 65 \def\@qrdim {\@qmodify{\global\qdim\lastkern \if@qpeek\else\unkern\fi}} 66 \def\@qrskip{\@qmodify{\global\qskip\lastskip \if@qpeek\else\unskip\fi}} 67 \def\@qrmu {\@qmodify{\global\qmu\gluetomu\lastskip \if@qpeek\else\unskip\fi}} 68 \def\@qrbox {\@qmodify{\gsetbox\qbox\lastbox \if@qpeek\copy\qbox\fi}} 69 \def\@qrtoks{\@qmodify{{\if@qpeek\else\global\fi\decr\@qt \gletcs\qtok\@qcs \global\qtoks\ea{\qtok}}}} 70 \def\@qrtok {\@qmodify{{\if@qpeek\else\global\fi\decr\@qt \gletcs\qtok\@qcs}}} 71 72 \protected\def\popnum {\@qpeekfalse \@qrnum} 73 \protected\def\popdim {\@qpeekfalse \@qrdim} 74 \protected\def\popskip{\@qpeekfalse \@qrskip} 75 \protected\def\popmu {\@qpeekfalse \@qrmu} 76 \protected\def\popbox {\@qpeekfalse \@qrbox} 77 \protected\def\poptoks{\@qpeekfalse \@qrtoks} 78 \protected\def\poptok {\@qpeekfalse \@qrtok} 79 80 \protected\def\peeknum {\@qpeektrue \@qrnum} 81 \protected\def\peekdim {\@qpeektrue \@qrdim} 82 \protected\def\peekskip{\@qpeektrue \@qrskip} 83 \protected\def\peekmu {\@qpeektrue \@qrmu} 84 \protected\def\peekbox {\@qpeektrue \@qrbox} 85 \protected\def\peektoks{\@qpeektrue \@qrtoks} 86 \protected\def\peektok {\@qpeektrue \@qrtok} 87 88 \endinput