% \iffalse meta-comment % %% File: l3intarray.dtx % % Copyright (C) 2017-2020 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 2020-06-18} % % \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, \intarray_new:cn} % \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. % The variable name should start with |\g_| because assignments are % always global. % \end{function} % % \begin{function}[EXP, added = 2018-03-29]{\intarray_count:N, \intarray_count:c} % \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, \intarray_gset:cnn} % \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}[added = 2018-05-04] % {\intarray_const_from_clist:Nn, \intarray_const_from_clist:cn} % \begin{syntax} % \cs{intarray_const_from_clist:Nn} \meta{intarray~var} \meta{intexpr clist} % \end{syntax} % Creates a new constant \meta{integer array variable} or raises an % error if the name is already taken. The \meta{integer array % variable} is set (globally) to contain as its items the results of % evaluating each \meta{integer expression} in the \meta{comma list}. % \end{function} % % \begin{function}[added = 2018-05-04]{\intarray_gzero:N, \intarray_gzero:c} % \begin{syntax} % \cs{intarray_gzero:N} \meta{intarray~var} % \end{syntax} % Sets all entries of the \meta{integer array variable} to zero. % Assignments are always global. % \end{function} % % \begin{function}[EXP, added = 2018-03-29]{\intarray_item:Nn, \intarray_item:cn} % \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} % % \begin{function}[EXP, added = 2018-05-05] % {\intarray_rand_item:N, \intarray_rand_item:c} % \begin{syntax} % \cs{intarray_rand_item:N} \meta{intarray~var} % \end{syntax} % Selects a pseudo-random item of the \meta{integer array}. If the % \meta{integer array} is empty, produce an error. % \end{function} % % \begin{function}[added = 2018-05-04] % {\intarray_show:N, \intarray_show:c, \intarray_log:N, \intarray_log:c} % \begin{syntax} % \cs{intarray_show:N} \meta{intarray~var} % \cs{intarray_log:N} \meta{intarray~var} % \end{syntax} % Displays the items in the \meta{integer array variable} in the % terminal or writes them in the log file. % \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{macro}{\@@_entry:w, \@@_count:w} % We use these primitives quite a lot in this module. % \begin{macrocode} \cs_new_eq:NN \@@_entry:w \tex_fontdimen:D \cs_new_eq:NN \@@_count:w \tex_hyphenchar:D % \end{macrocode} % \end{macro} % % \begin{variable}{\l_@@_loop_int} % A loop index. % \begin{macrocode} \int_new:N \l_@@_loop_int % \end{macrocode} % \end{variable} % % \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{macrocode} \__kernel_msg_new:nnn { kernel } { negative-array-size } { Size~of~array~may~not~be~negative:~#1 } % \end{macrocode} % % \begin{macro}{\intarray_new:Nn, \intarray_new:cn} % \begin{macro}{\@@_new:N} % 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} \cs_new_protected:Npn \@@_new:N #1 { \__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: \int_step_inline:nn { 8 } { \__kernel_intarray_gset:Nnn #1 {##1} \c_zero_int } } \cs_new_protected:Npn \intarray_new:Nn #1#2 { \@@_new:N #1 \@@_count:w #1 = \int_eval:n {#2} \scan_stop: \int_compare:nNnT { \intarray_count:N #1 } < 0 { \__kernel_msg_error:nnx { kernel } { negative-array-size } { \intarray_count:N #1 } } \int_compare:nNnT { \intarray_count:N #1 } > 0 { \__kernel_intarray_gset:Nnn #1 { \intarray_count:N #1 } { 0 } } } \cs_generate_variant:Nn \intarray_new:Nn { c } % \end{macrocode} % \end{macro} % \end{macro} % % \begin{macro}[EXP]{\intarray_count:N, \intarray_count:c} % Size of an array. % \begin{macrocode} \cs_new:Npn \intarray_count:N #1 { \int_value:w \@@_count:w #1 } \cs_generate_variant:Nn \intarray_count:N { c } % \end{macrocode} % \end{macro} % % \subsection{Array items} % % \begin{macro}[EXP]{\@@_signed_max_dim:n} % Used when an item to be stored is larger than \cs{c_max_dim} in % absolute value; it is replaced by $\pm\cs{c_max_dim}$. % \begin{macrocode} \cs_new:Npn \@@_signed_max_dim:n #1 { \int_value:w \int_compare:nNnT {#1} < 0 { - } \c_max_dim } % \end{macrocode} % \end{macro} % % \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, \intarray_gset:cnn, \__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 { \@@_entry:w #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_generate_variant:Nn \intarray_gset:Nnn { c } \cs_new_protected:Npn \@@_gset:Nww #1#2 ; #3 ; { \@@_bounds:NNnTF \__kernel_msg_error:nnxxx #1 {#2} { \@@_gset_overflow_test:nw {#3} \__kernel_intarray_gset:Nnn #1 {#2} {#3} } { } } \cs_if_exist:NTF \tex_ifabsnum:D { \cs_new_protected:Npn \@@_gset_overflow_test:nw #1 { \tex_ifabsnum:D #1 > \c_max_dim \exp_after:wN \@@_gset_overflow:NNnn \fi: } } { \cs_new_protected:Npn \@@_gset_overflow_test:nw #1 { \if_int_compare:w \int_abs:n {#1} > \c_max_dim \exp_after:wN \@@_gset_overflow:NNnn \fi: } } \cs_new_protected:Npn \@@_gset_overflow:NNnn #1#2#3#4 { \__kernel_msg_error:nnxxxx { kernel } { overflow } { \token_to_str:N #2 } {#3} {#4} { \@@_signed_max_dim:n {#4} } #1 #2 {#3} { \@@_signed_max_dim:n {#4} } } % \end{macrocode} % \end{macro} % \end{macro} % % \begin{macro}{\intarray_gzero:N, \intarray_gzero:c} % Set the appropriate \tn{fontdimen} to zero. No bound checking % needed. The \cs{prg_replicate:nn} possibly uses quite a lot of % memory, but this is somewhat comparable to the size of the array, % and it is much faster than an \cs{int_step_inline:nn} loop. % \begin{macrocode} \cs_new_protected:Npn \intarray_gzero:N #1 { \int_zero:N \l_@@_loop_int \prg_replicate:nn { \intarray_count:N #1 } { \int_incr:N \l_@@_loop_int \@@_entry:w \l_@@_loop_int #1 \c_zero_dim } } \cs_generate_variant:Nn \intarray_gzero:N { c } % \end{macrocode} % \end{macro} % % \begin{macro}[EXP]{\intarray_item:Nn, \intarray_item:cn, \__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 \@@_entry:w #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_generate_variant:Nn \intarray_item:Nn { c } \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{macro}{\intarray_rand_item:N, \intarray_rand_item:c} % Importantly, \cs{intarray_item:Nn} only evaluates its argument once. % \begin{macrocode} \cs_new:Npn \intarray_rand_item:N #1 { \intarray_item:Nn #1 { \int_rand:n { \intarray_count:N #1 } } } \cs_generate_variant:Nn \intarray_rand_item:N { c } % \end{macrocode} % \end{macro} % % \subsection{Working with contents of integer arrays} % % \begin{macro}{\intarray_const_from_clist:Nn, \intarray_const_from_clist:cn} % \begin{macro}{\@@_const_from_clist:nN} % Similar to \cs{intarray_new:Nn} (which we don't use because when % debugging is enabled that function checks the variable name starts % with |g_|). We make use of the fact that \TeX{} allows allocation % of successive \tn{fontdimen} as long as no other font has been % declared: no need to count the comma list items first. We need the % code in \cs{intarray_gset:Nnn} that checks the item value is not too % big, namely \cs{@@_gset_overflow_test:nw}, but not the code that % checks bounds. At the end, set the size of the intarray. % \begin{macrocode} \cs_new_protected:Npn \intarray_const_from_clist:Nn #1#2 { \@@_new:N #1 \int_zero:N \l_@@_loop_int \clist_map_inline:nn {#2} { \exp_args:Nf \@@_const_from_clist:nN { \int_eval:n {##1} } #1 } \@@_count:w #1 \l_@@_loop_int } \cs_generate_variant:Nn \intarray_const_from_clist:Nn { c } \cs_new_protected:Npn \@@_const_from_clist:nN #1#2 { \int_incr:N \l_@@_loop_int \@@_gset_overflow_test:nw {#1} \__kernel_intarray_gset:Nnn #2 \l_@@_loop_int {#1} } % \end{macrocode} % \end{macro} % \end{macro} % % \begin{macro}[rEXP]{\intarray_to_clist:N, \intarray_to_clist:c} % \begin{macro}[rEXP]{\@@_to_clist:Nn, \@@_to_clist:w} % Loop through the array, putting a comma before each item. Remove % the leading comma with |f|-expansion. We also use the auxiliary in % \cs{intarray_show:N} with argument comma, space. % \begin{macrocode} \cs_new:Npn \intarray_to_clist:N #1 { \@@_to_clist:Nn #1 { , } } \cs_generate_variant:Nn \intarray_to_clist:N { c } \cs_new:Npn \@@_to_clist:Nn #1#2 { \int_compare:nNnF { \intarray_count:N #1 } = \c_zero_int { \exp_last_unbraced:Nf \use_none:n { \@@_to_clist:w 1 ; #1 {#2} \prg_break_point: } } } \cs_new:Npn \@@_to_clist:w #1 ; #2#3 { \if_int_compare:w #1 > \@@_count:w #2 \prg_break:n \fi: #3 \__kernel_intarray_item:Nn #2 {#1} \exp_after:wN \@@_to_clist:w \int_value:w \int_eval:w #1 + \c_one_int ; #2 {#3} } % \end{macrocode} % \end{macro} % \end{macro} % % \begin{macro}{\intarray_show:N, \intarray_show:c, \intarray_log:N, \intarray_log:c} % Convert the list to a comma list (with spaces after each comma) % \begin{macrocode} \cs_new_protected:Npn \intarray_show:N { \@@_show:NN \msg_show:nnxxxx } \cs_generate_variant:Nn \intarray_show:N { c } \cs_new_protected:Npn \intarray_log:N { \@@_show:NN \msg_log:nnxxxx } \cs_generate_variant:Nn \intarray_log:N { c } \cs_new_protected:Npn \@@_show:NN #1#2 { \__kernel_chk_defined:NT #2 { #1 { LaTeX/kernel } { show-intarray } { \token_to_str:N #2 } { \intarray_count:N #2 } { >~ \@@_to_clist:Nn #2 { , ~ } } { } } } % \end{macrocode} % \end{macro} % % \subsection{Random arrays} % % \begin{macro}{\intarray_gset_rand:Nn, \intarray_gset_rand:cn} % \begin{macro}{\intarray_gset_rand:Nnn, \intarray_gset_rand:cnn} % \begin{macro} % { % \@@_gset_rand:Nnn, % \@@_gset_rand:Nff, % \@@_gset_rand_auxi:Nnnn, % \@@_gset_rand_auxii:Nnnn, % \@@_gset_rand_auxiii:Nnnn, % \@@_gset_all_same:Nn, % } % We only perform the bounds checks once. This is done by two % \cs{@@_gset_overflow_test:nw}, with an appropriate empty argument to % avoid a spurious \enquote{at position \texttt{\#1}} part in the % error message. Then calculate the number of choices: this is at % most $(2^{30}-1)-(-(2^{30}-1))+1=2^{31}-1$, which just barely does % not overflow. For small ranges use \cs{__kernel_randint:n} (making % sure to subtract~$1$ \emph{before} adding the random number to the % \meta{min}, to avoid overflow when \meta{min} or \meta{max} are % $\pm\cs{c_max_int}$), otherwise \cs{__kernel_randint:nn}. Finally, % if there are no random numbers do not define any of the auxiliaries. % \begin{macrocode} \cs_new_protected:Npn \intarray_gset_rand:Nn #1 { \intarray_gset_rand:Nnn #1 { 1 } } \cs_generate_variant:Nn \intarray_gset_rand:Nn { c } \sys_if_rand_exist:TF { \cs_new_protected:Npn \intarray_gset_rand:Nnn #1#2#3 { \@@_gset_rand:Nff #1 { \int_eval:n {#2} } { \int_eval:n {#3} } } \cs_new_protected:Npn \@@_gset_rand:Nnn #1#2#3 { \int_compare:nNnTF {#2} > {#3} { \__kernel_msg_expandable_error:nnnn { kernel } { randint-backward-range } {#2} {#3} \@@_gset_rand:Nnn #1 {#3} {#2} } { \@@_gset_overflow_test:nw {#2} \@@_gset_rand_auxi:Nnnn #1 { } {#2} {#3} } } \cs_generate_variant:Nn \@@_gset_rand:Nnn { Nff } \cs_new_protected:Npn \@@_gset_rand_auxi:Nnnn #1#2#3#4 { \@@_gset_overflow_test:nw {#4} \@@_gset_rand_auxii:Nnnn #1 { } {#4} {#3} } \cs_new_protected:Npn \@@_gset_rand_auxii:Nnnn #1#2#3#4 { \exp_args:NNf \@@_gset_rand_auxiii:Nnnn #1 { \int_eval:n { #3 - #4 + 1 } } {#4} {#3} } \cs_new_protected:Npn \@@_gset_rand_auxiii:Nnnn #1#2#3#4 { \exp_args:NNf \@@_gset_all_same:Nn #1 { \int_compare:nNnTF {#2} > \c__kernel_randint_max_int { \exp_stop_f: \int_eval:n { \__kernel_randint:nn {#3} {#4} } } { \exp_stop_f: \int_eval:n { \__kernel_randint:n {#2} - 1 + #3 } } } } \cs_new_protected:Npn \@@_gset_all_same:Nn #1#2 { \int_zero:N \l_@@_loop_int \prg_replicate:nn { \intarray_count:N #1 } { \int_incr:N \l_@@_loop_int \__kernel_intarray_gset:Nnn #1 \l_@@_loop_int {#2} } } } { \cs_new_protected:Npn \intarray_gset_rand:Nnn #1#2#3 { \__kernel_msg_error:nnn { kernel } { fp-no-random } { \intarray_gset_rand:Nnn #1 {#2} {#3} } } } \cs_generate_variant:Nn \intarray_gset_rand:Nnn { c } % \end{macrocode} % \end{macro} % \end{macro} % \end{macro} % % \begin{macrocode} % % \end{macrocode} % % \end{implementation} % % \PrintIndex