% \iffalse meta-comment % %% File: l3intarray.dtx Copyright (C) 2017-2018 The LaTeX3 Project % % It may be distributed and/or modified under the conditions of the % LaTeX Project Public License (LPPL), either version 1.3c of this % license or (at your option) any later version. The latest version % of this license is in the file % % https://www.latex-project.org/lppl.txt % % This file is part of the "l3kernel bundle" (The Work in LPPL) % and all files in that bundle must be distributed together. % % ----------------------------------------------------------------------- % % The development version of the bundle can be found at % % https://github.com/latex3/latex3 % % for those people who are interested. % %<*driver> \documentclass[full,kernel]{l3doc} \begin{document} \DocInput{\jobname.dtx} \end{document} % % \fi % % % \title{^^A % The \textsf{l3intarray} package: fast global integer arrays^^A % } % % \author{^^A % The \LaTeX3 Project\thanks % {^^A % E-mail: % \href{mailto:latex-team@latex-project.org} % {latex-team@latex-project.org}^^A % }^^A % } % % \date{Released 2018-04-30} % % \maketitle % % \begin{documentation} % % \section{\pkg{l3intarray} documentation} % % For applications requiring heavy use of integers, this module provides % arrays which can be accessed in constant time (contrast \pkg{l3seq}, % where access time is linear). These arrays have several important % features % \begin{itemize} % \item The size of the array is fixed and must be given at % point of initialisation % \item The absolute value of each entry has maximum $2^{30}-1$ % (\emph{i.e.}~one power lower than the usual \cs{c_max_int} % ceiling of $2^{31}-1$) % \end{itemize} % The use of \texttt{intarray} data is therefore recommended for cases where % the need for fast access is of paramount importance. % % \begin{function}[added = 2018-03-29]{\intarray_new:Nn} % \begin{syntax} % \cs{intarray_new:Nn} \meta{intarray~var} \Arg{size} % \end{syntax} % Evaluates the integer expression \meta{size} and allocates an % \meta{integer array variable} with that number of (zero) entries. % \end{function} % % \begin{function}[EXP, added = 2018-03-29]{\intarray_count:N} % \begin{syntax} % \cs{intarray_count:N} \meta{intarray~var} % \end{syntax} % Expands to the number of entries in the \meta{integer array variable}. % Contrarily to \cs{seq_count:N} this is performed in constant time. % \end{function} % % \begin{function}[added = 2018-03-29]{\intarray_gset:Nnn} % \begin{syntax} % \cs{intarray_gset:Nnn} \meta{intarray~var} \Arg{position} \Arg{value} % \end{syntax} % Stores the result of evaluating the integer expression \meta{value} % into the \meta{integer array variable} at the (integer expression) % \meta{position}. If the \meta{position} is not between $1$ and the % \cs{intarray_count:N}, or the \meta{value}'s absolute value is % bigger than $2^{30}-1$, an error occurs. Assignments are always % global. % \end{function} % % \begin{function}[EXP, added = 2018-03-29]{\intarray_item:Nn} % \begin{syntax} % \cs{intarray_item:Nn} \meta{intarray~var} \Arg{position} % \end{syntax} % Expands to the integer entry stored at the (integer expression) % \meta{position} in the \meta{integer array variable}. If the % \meta{position} is not between $1$ and the \cs{intarray_count:N}, an % error occurs. % \end{function} % % \subsection{Implementation notes} % % It is a wrapper around the \tn{fontdimen} primitive, used to store % arrays of integers (with a restricted range: absolute value at most % $2^{30}-1$). In contrast to \pkg{l3seq} sequences the access to % individual entries is done in constant time rather than linear time, % but only integers can be stored. More precisely, the primitive % \tn{fontdimen} stores dimensions but the \pkg{l3intarray} package % transparently converts these from/to integers. Assignments are always % global. % % While \LuaTeX{}'s memory is extensible, other engines can % \enquote{only} deal with a bit less than $4\times 10^6$ entries in all % \tn{fontdimen} arrays combined (with default \TeX{}Live settings). % % \end{documentation} % % \begin{implementation} % % \section{\pkg{l3intarray} implementation} % % \begin{macrocode} %<*initex|package> % \end{macrocode} % % \begin{macrocode} %<@@=intarray> % \end{macrocode} % % \subsection{Allocating arrays} % % \begin{variable}{\c_@@_sp_dim} % Used to convert integers to dimensions fast. % \begin{macrocode} \dim_const:Nn \c_@@_sp_dim { 1 sp } % \end{macrocode} % \end{variable} % % \begin{variable}{\g_@@_font_int} % Used to assign one font per array. % \begin{macrocode} \int_new:N \g_@@_font_int % \end{macrocode} % \end{variable} % % \begin{macro}{\intarray_new:Nn} % Declare |#1| to be a font (arbitrarily |cmr10| at a never-used % size). Store the array's size as the \tn{hyphenchar} of that font % and make sure enough \tn{fontdimen} are allocated, by setting the % last one. Then clear any \tn{fontdimen} that |cmr10| starts with. % It seems \LuaTeX{}'s |cmr10| has an extra \tn{fontdimen} parameter % number $8$ compared to other engines (for a math font we would % replace $8$ by $22$ or some such). % Every \texttt{intarray} must be global; it's enough to run this % check in \cs{intarray_new:Nn}. % \begin{macrocode} \__kernel_patch:nnNNpn { \__kernel_chk_var_scope:NN g #1 } { } \cs_new_protected:Npn \intarray_new:Nn #1#2 { \__kernel_chk_if_free_cs:N #1 \int_gincr:N \g_@@_font_int \tex_global:D \tex_font:D #1 = cmr10~at~ \g_@@_font_int \c_@@_sp_dim \scan_stop: \tex_hyphenchar:D #1 = \int_eval:n {#2} \scan_stop: \int_compare:nNnT { \tex_hyphenchar:D #1 } > 0 { \tex_fontdimen:D \tex_hyphenchar:D #1 #1 = \c_zero_dim } \int_step_inline:nn { 8 } { \tex_fontdimen:D ##1 #1 = \c_zero_dim } } % \end{macrocode} % \end{macro} % % \begin{macro}[EXP]{\intarray_count:N} % Size of an array. % \begin{macrocode} \cs_new:Npn \intarray_count:N #1 { \tex_the:D \tex_hyphenchar:D #1 } % \end{macrocode} % \end{macro} % % \subsection{Array items} % % \begin{macro}[EXP]{\@@_bounds:NNnTF, \@@_bounds_error:NNn} % The functions \cs{intarray_gset:Nnn} and \cs{intarray_item:Nn} share % bounds checking. The |T| branch is used if |#3| is within bounds of % the array |#2|. % \begin{macrocode} \cs_new:Npn \@@_bounds:NNnTF #1#2#3#4#5 { \if_int_compare:w 1 > #3 \exp_stop_f: \@@_bounds_error:NNn #1 #2 {#3} #5 \else: \if_int_compare:w #3 > \intarray_count:N #2 \exp_stop_f: \@@_bounds_error:NNn #1 #2 {#3} #5 \else: #4 \fi: \fi: } \cs_new:Npn \@@_bounds_error:NNn #1#2#3 { #1 { kernel } { out-of-bounds } { \token_to_str:N #2 } {#3} { \intarray_count:N #2 } } % \end{macrocode} % \end{macro} % % \begin{macro}{\intarray_gset:Nnn, \__kernel_intarray_gset:Nnn} % \begin{macro}{\@@_gset:Nnn, \@@_gset_overflow:Nnn} % Set the appropriate \tn{fontdimen}. The % \cs{__kernel_intarray_gset:Nnn} function does not use % \cs{int_eval:n}, namely its arguments must be suitable for % \cs{int_value:w}. The user version checks the position and value % are within bounds. % \begin{macrocode} \cs_new_protected:Npn \__kernel_intarray_gset:Nnn #1#2#3 { \tex_fontdimen:D #2 #1 #3 \c_@@_sp_dim } \cs_new_protected:Npn \intarray_gset:Nnn #1#2#3 { \exp_after:wN \@@_gset:Nww \exp_after:wN #1 \int_value:w \int_eval:n {#2} \exp_after:wN ; \int_value:w \int_eval:n {#3} ; } \cs_new_protected:Npn \@@_gset:Nww #1#2 ; #3 ; { \@@_bounds:NNnTF \__kernel_msg_error:nnxxx #1 {#2} { \if_int_compare:w \int_abs:n {#3} > \c_max_dim \exp_after:wN \@@_gset_overflow:NNnn \fi: \__kernel_intarray_gset:Nnn #1 {#2} {#3} } { } } \cs_new_protected:Npn \@@_gset_overflow:NNnn #1#2#3#4 { \__kernel_msg_error:nnxxxx { kernel } { overflow } { \token_to_str:N #2 } {#3} {#4} { \int_value:w \int_compare:nNnT {#4} < 0 { - } \c_max_dim } \__kernel_intarray_gset:Nnn #2 {#3} { \int_value:w \int_compare:nNnT {#4} < 0 { - } \c_max_dim } } % \end{macrocode} % \end{macro} % \end{macro} % % \begin{macro}[EXP]{\intarray_item:Nn, \__kernel_intarray_item:Nn} % \begin{macro}{\@@_item:Nn} % Get the appropriate \tn{fontdimen} and perform bound checks. The % \cs{__kernel_intarray_item:Nn} function omits bound checks and omits % \cs{int_eval:n}, namely its argument must be a \TeX{} integer % suitable for \cs{int_value:w}. % \begin{macrocode} \cs_new:Npn \__kernel_intarray_item:Nn #1#2 { \int_value:w \tex_fontdimen:D #2 #1 } \cs_new:Npn \intarray_item:Nn #1#2 { \exp_after:wN \@@_item:Nw \exp_after:wN #1 \int_value:w \int_eval:n {#2} ; } \cs_new:Npn \@@_item:Nw #1#2 ; { \@@_bounds:NNnTF \__kernel_msg_expandable_error:nnfff #1 {#2} { \__kernel_intarray_item:Nn #1 {#2} } { 0 } } % \end{macrocode} % \end{macro} % \end{macro} % % \begin{macrocode} % % \end{macrocode} % % \end{implementation} % % \PrintIndex