diff options
Diffstat (limited to 'Master/texmf-dist/source/latex/l3kernel/l3tree.dtx')
-rw-r--r-- | Master/texmf-dist/source/latex/l3kernel/l3tree.dtx | 595 |
1 files changed, 595 insertions, 0 deletions
diff --git a/Master/texmf-dist/source/latex/l3kernel/l3tree.dtx b/Master/texmf-dist/source/latex/l3kernel/l3tree.dtx new file mode 100644 index 00000000000..27e5b7e5d44 --- /dev/null +++ b/Master/texmf-dist/source/latex/l3kernel/l3tree.dtx @@ -0,0 +1,595 @@ +% \iffalse +% +%% File l3tree.dtx (C) Copyright 2012 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 +%% +%% http://www.latex-project.org/lppl.txt +%% +%% This file is part of the "l3trial bundle" (The Work in LPPL) +%% and all files in that bundle must be distributed together. +%% +%% The released version of this bundle is available from CTAN. +%% +%% ----------------------------------------------------------------------- +%% +%% The development version of the bundle can be found at +%% +%% http://www.latex-project.org/svnroot/experimental/trunk/ +%% +%% for those people who are interested. +%% +%%%%%%%%%%% +%% NOTE: %% +%%%%%%%%%%% +%% +%% Snapshots taken from the repository represent work in progress and may +%% not work or may contain conflicting material! We therefore ask +%% people _not_ to put them into distributions, archives, etc. without +%% prior consultation with the LaTeX Project Team. +%% +%% ----------------------------------------------------------------------- +%% +% +%<*driver|package> +\RequirePackage{expl3} +\GetIdInfo$Id: l3tree.dtx 3177 2012-01-11 02:11:43Z bruno $ + {L3 Experimental tree manipulations} +%</driver|package> +%<*driver> +\documentclass[full]{l3doc} +\usepackage{amsmath} +\begin{document} + \DocInput{\jobname.dtx} +\end{document} +%</driver> +% \fi +% +% \title{^^A +% The \pkg{l3tree} package\\ Trees^^A +% \thanks{This file describes v\ExplFileVersion, +% last revised \ExplFileDate.}^^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 \ExplFileDate} +% +% \maketitle +% +% \begin{documentation} +% +% \section{\pkg{l3tree} documentation} +% +% \LaTeX3 comes with a tree data-type, whose keys are integers. +% ^^A Currently, we only support binary trees, but that will probably +% ^^A be extended as the need arises. +% +% A tree is a box containing +% +% \begin{function}{\tree_new:N, \tree_new:c} +% \begin{syntax} +% \cs{tree_new:N} \meta{tree} +% \end{syntax} +% Creates a new tree, with no node. +% \end{function} +% +% \begin{function}{\tree_put:Nn, \tree_put:cn, \tree_gput:Nn, \tree_gput:cn} +% \begin{syntax} +% \cs{tree_put:Nn} \meta{tree} \Arg{integer expression} +% \end{syntax} +% Evaluates the \meta{integer expression}, and puts the +% \end{function} +% +% \end{documentation} +% +% \begin{implementation} +% +% \section{\pkg{l3tree} implementation} +% +% \begin{macrocode} +%<*initex|package> +% \end{macrocode} +% +% \begin{macrocode} +%<*package> +\ProvidesExplPackage + {\ExplFileName}{\ExplFileDate}{\ExplFileVersion}{\ExplFileDescription} +\package_check_loaded_expl: +%</package> +% \end{macrocode} +% +% \subsection{Variables} +% +% \begin{variable}{\l_tree_index_int} +% +% \begin{macrocode} +\int_new:N \l_tree_index_int +% \end{macrocode} +% \end{variable} +% +% \begin{variable}{\l_tree_item_box} +% +% \begin{macrocode} +\box_new:N \l_tree_item_box +% \end{macrocode} +% \end{variable} +% +% \begin{variable}{\l_tree_left_box,\l_tree_right_box} +% During the splaying step, these two boxes hold the left and right +% children of the node which we splay. +% \begin{macrocode} +\box_new:N \l_tree_left_box +\box_new:N \l_tree_right_box +% \end{macrocode} +% \end{variable} +% +% \begin{variable}{\l_tree_first_box, \l_tree_second_box} +% Temporary variables holding subtrees of the full tree +% in various circumstances. +% \begin{macrocode} +\box_new:N \l_tree_first_box +\box_new:N \l_tree_second_box +% \end{macrocode} +% \end{variable} +% +% \begin{variable}{\l_tree_parent_box, \l_tree_grandpa_box} +% +% \begin{macrocode} +\box_new:N \l_tree_parent_box +\box_new:N \l_tree_grandpa_box +% \end{macrocode} +% \end{variable} +% +% \begin{variable}{\c_one_sp_dim} +% Smallest dimension that \TeX{} recognizes. When implicitly +% converting from integers to dimensions, this is the conversion +% factor. +% \begin{macrocode} +\dim_new:N \c_one_sp_dim +\dim_set:Nn \c_one_sp_dim { 1 sp } +% \end{macrocode} +% \end{variable} +% +% \begin{variable}{\l_tree_parent_dim,\l_tree_grandpa_dim} +% +% \begin{macrocode} +\dim_new:N \l_tree_parent_dim +\dim_new:N \l_tree_grandpa_dim +% \end{macrocode} +% \end{variable} +% +% \begin{variable}{\g_tree_result_seq} +% When extracting keys from a tree, the result is temporarily stored +% globally in \cs{g_tree_result_seq} to exit a group. +% \begin{macrocode} +\seq_new:N \g_tree_result_seq +% \end{macrocode} +% \end{variable} +% +% \begin{variable}{\l_tree_internal_box} +% Scratch box register for temporary use. +% \begin{macrocode} +\box_new:N \l_tree_internal_box +% \end{macrocode} +% \end{variable} +% +% \subsection{Generic helpers} +% +% \begin{macro}{\tree_end:} +% Used to end box assignments started by \cs{tree_edit:Nw}, +% \cs{tree_gedit:Nw}, or \cs{tree_cat:Nw}. +% \begin{macrocode} +\cs_new_eq:NN \tree_end: \c_group_end_token +% \end{macrocode} +% \end{macro} +% +%^^A explain that we need protection against a potential \tn{everyhbox}. +% +% \begin{macro}{\tree_edit:Nw, \tree_gedit:Nw} +% Accessing the contents of a tree requires unpacking its contents, +% to access them using the \tn{lastbox} primitive. We may not do +% that in the current list. Instead, this is done within a box +% assignment to the tree itself: this choice allows us to modify +% (\enquote{edit}) the tree and not only access the nodes. +% This editing should be ended by \cs{tree_end:}. +% \begin{macrocode} +\cs_new_protected:Npn \tree_edit:Nw #1 + { + \tex_afterassignment:D \use_none_delimit_by_q_stop:w + \tex_setbox:D #1 \tex_hbox:D \c_group_begin_token + \q_stop + \tex_everyhbox:D { } + \hbox_unpack_clear:N #1 + } +\cs_new_protected:Npn \tree_gedit:Nw #1 + { + \tex_afterassignment:D \use_none_delimit_by_q_stop:w + \tex_global:D \tex_setbox:D #1 \tex_hbox:D \c_group_begin_token + \q_stop + \tex_everyhbox:D { } + \hbox_unpack_clear:N #1 + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{\tree_cat:Nw} +% Similar to \cs{tree_edit:Nw}, but without altering the tree contents. +% \begin{macrocode} +\cs_new_protected:Npn \tree_cat:Nw #1 + { + \tex_afterassignment:D \use_none_delimit_by_q_stop:w + \tex_setbox:D \l_tree_internal_box \tex_hbox:D \c_group_begin_token + \q_stop + \tex_everyhbox:D { } + \hbox_unpack:N #1 + } +% \end{macrocode} +% \end{macro} +% +% \subsection{Empty trees} +% +% \begin{macro}{\tree_new:N, \tree_new:c} +% \begin{macro}{\tree_clear:N, \tree_clear:c} +% \begin{macro}{\tree_gclear:N, \tree_gclear:c} +% Trees are simply boxes, so we copy the box functions. +% \begin{macrocode} +\cs_new_eq:NN \tree_new:N \box_new:N +\cs_new_eq:NN \tree_new:c \box_new:c +\cs_new_eq:NN \tree_clear:N \box_clear:N +\cs_new_eq:NN \tree_clear:c \box_clear:c +\cs_new_eq:NN \tree_gclear:N \box_gclear:N +\cs_new_eq:NN \tree_gclear:c \box_gclear:c +% \end{macrocode} +% \end{macro} +% \end{macro} +% \end{macro} +% +% \begin{macro}[pTF, EXP]{\tree_if_empty:N} +% Test whether a tree is empty, \emph{i.e.}, contains no node at all. +% \begin{macrocode} +\prg_new_eq_conditional:NNn \tree_if_empty:N + \box_if_empty:N { p , T , F , TF } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[EXP]{\if_tree_empty:N} +% The primitive conditional is used in the code because it expands +% in only one step. +% \begin{macrocode} +\cs_new_eq:NN \if_tree_empty:N \if_box_empty:N +% \end{macrocode} +% \end{macro} +% +% \subsection{Extracting the keys} +% +% \begin{macro}{\seq_set_from_tree:NN, \seq_gset_from_tree:NN} +% \begin{macro}[aux]{\tree_extract_aux:NNN} +% The local and global versions only differ by how the sequence +% is assigned once it has been built in \cs{g_tree_result_seq}. +% We open the tree with \cs{tree_cat:Nw}, then extract the keys +% non-expandably into \tn{dimen} registers (used as integers) +% using \cs{tree_extract_loop:}, and store the values of those +% \tn{dimen} registers expandably as the sequence +% \cs{g_tree_result_seq}. After closing the tree, store the +% result sequence into the user's variable, and clear the +% internal sequence (a small cost operation to avoid memory leaks). +% \begin{macrocode} +\cs_new_protected_nopar:Npn \seq_set_from_tree:NN + { \tree_extract_aux:NNN \seq_set_eq:NN } +\cs_new_protected_nopar:Npn \seq_gset_from_tree:NN + { \tree_extract_aux:NNN \seq_gset_eq:NN } +\cs_new_protected:Npn \tree_extract_aux:NNN #1#2#3 + { + \int_zero:N \l_tree_index_int + \tree_cat:Nw #3 + \tree_extract_loop: + \tl_gset:Nx \g_tree_result_seq + { + \exp_after:wN \tree_extract_loop:w + \int_use:N \l_tree_index_int ; + \prg_break_point:n { } + } + \tree_end: + #1 #2 \g_tree_result_seq + \tl_gclear:N \g_tree_result_seq + } +% \end{macrocode} +% \end{macro} +% \end{macro} +% +% \begin{macro}[aux]{\tree_extract_loop:} +% +% \begin{macrocode} +\cs_new_protected:Npn \tree_extract_loop: + { + \tex_setbox:D \l_tree_first_box \tex_lastbox:D + \if_hbox:N \l_tree_first_box + \hbox_unpack_clear:N \l_tree_first_box + \else: + \if_num:w \tex_ht:D \l_tree_first_box = \c_zero + \exp_after:wN \exp_after:wN \exp_after:wN \use_none:n + \else: + \tex_advance:D \l_tree_index_int \c_one + \tex_dimen:D \l_tree_index_int \tex_ht:D \l_tree_first_box + \fi: + \fi: + \tree_extract_loop: + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[aux, EXP]{\tree_extract_loop:w} +% +% \begin{macrocode} +\cs_new:Npn \tree_extract_loop:w #1 ; + { + \if_num:w #1 = \c_zero + \exp_after:wN \prg_map_break: + \fi: + \exp_not:N \seq_item:n { \int_value:w \tex_dimen:D #1 } + \exp_after:wN \tree_extract_loop:w + \int_use:N \int_eval:w #1 - \c_one ; + } +% \end{macrocode} +% \end{macro} +% +% \subsection{Comparison} +% +% \begin{macro}{\tree_compare:NN} +% +% \begin{macrocode} +\cs_new_protected:Npn \tree_compare:NN #1 #2 + { + \if_num:w \tex_ht:D #1 > \tex_ht:D #2 \exp_stop_f: + \tree_reversed: + \else: + \tree_ordered: + \fi: + } +% \end{macrocode} +% \end{macro} +% +% \subsection{Adding nodes to a tree} +% +% \begin{macro}{\tree_put:Nnn, \tree_gput:Nnn} +% \begin{macro}[aux]{\tree_put_aux:NNnn} +% +% \begin{macrocode} +\cs_new_protected:Npn \tree_put:Nnn + { \tree_put_aux:NNnn \tree_edit:Nw } +\cs_new_protected:Npn \tree_gput:Nnn + { \tree_put_aux:NNnn \tree_gedit:Nw } +\cs_new_protected:Npn \tree_put_aux:NNnn #1#2#3#4 + { + \tex_setbox:D \l_tree_left_box \tex_box:D \c_empty_box + \tex_setbox:D \l_tree_right_box \tex_box:D \c_empty_box + \tex_setbox:D \l_tree_item_box + \tex_vbox:D to \int_eval:w #3 \int_eval_end: \c_one_sp_dim {#4} + \exp_after:wN #1 \exp_after:wN #2 + \if_tree_empty:N #2 + \else: + \tree_put_loop: + \tree_splay_loop: + \fi: + \box_use_clear:N \l_tree_left_box + \box_use_clear:N \l_tree_item_box + \box_use_clear:N \l_tree_right_box + \tree_end: + } +% \end{macrocode} +% \end{macro} +% \end{macro} +% +% \begin{macro}[aux]{\tree_put_loop:} +% +% \begin{macrocode} +\cs_new_protected:Npn \tree_put_loop: + { + \tex_setbox:D \l_tree_first_box \tex_lastbox:D + \tex_setbox:D \l_tree_parent_box + \if_vbox:N \l_tree_first_box + \tex_box:D \l_tree_first_box + \else: + \tex_lastbox:D + \fi: + \tree_compare:NN \l_tree_parent_box \l_tree_item_box + \if_box_empty:N \l_tree_first_box + \exp_after:wN \use_none:n + \else: + \hbox_unpack_clear:N \l_tree_first_box + \fi: + \tree_put_loop: + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{\tree_ordered:, \tree_reversed:} +% +% \begin{macrocode} +\cs_new_protected:Npn \tree_ordered: + { + \box_use_clear:N \l_tree_parent_box + \tex_kern:D \c_one_sp_dim + } +\cs_new_protected:Npn \tree_reversed: + { + \tex_setbox:D \l_tree_second_box \tex_lastbox:D + \box_use_clear:N \l_tree_first_box + \tex_setbox:D \l_tree_first_box \tex_box:D \l_tree_second_box + \box_use_clear:N \l_tree_parent_box + \tex_kern:D - \c_one_sp_dim + } +% \end{macrocode} +% \end{macro} +% +% \subsection{Splaying} +% +% \begin{macro}[int]{\tree_splay_loop:} +% +% \begin{macrocode} +\cs_new_protected:Npn \tree_splay_loop: + { + \l_tree_parent_dim \tex_lastkern:D + \tex_unkern:D + \tex_setbox:D \l_tree_parent_box \tex_lastbox:D + \tex_setbox:D \l_tree_first_box \tex_lastbox:D + \l_tree_grandpa_dim \tex_lastkern:D + \tex_unkern:D + \tex_setbox:D \l_tree_grandpa_box \tex_lastbox:D + \tex_setbox:D \l_tree_second_box \tex_lastbox:D + \cs:w + tree_splay + _\int_value:w \l_tree_parent_dim + _\int_value:w \l_tree_grandpa_dim + : + \cs_end: + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[aux]{\tree_splay_0_0:} +% +% \begin{macrocode} +\cs_new_protected:cpn { tree_splay_0_0: } { } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[aux]{\tree_splay_1_0:} +% +% \begin{macrocode} +\cs_new_protected:cpn { tree_splay_1_0: } + { + \tex_setbox:D \l_tree_left_box \tex_hbox:D + { + \box_use_clear:N \l_tree_first_box + \box_use_clear:N \l_tree_parent_box + \box_use_clear:N \l_tree_left_box + } + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[aux]{\tree_splay_-1_0:} +% +% \begin{macrocode} +\cs_new_protected:cpn { tree_splay_-1_0: } + { + \tex_setbox:D \l_tree_right_box \tex_hbox:D + { + \box_use_clear:N \l_tree_right_box + \box_use_clear:N \l_tree_parent_box + \box_use_clear:N \l_tree_first_box + } + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[aux]{\tree_splay_1_1:} +% +% \begin{macrocode} +\cs_new_protected:cpn { tree_splay_1_1: } + { + \tex_setbox:D \l_tree_left_box \tex_hbox:D + { + \tex_hbox:D + { + \box_use_clear:N \l_tree_second_box + \box_use_clear:N \l_tree_grandpa_box + \box_use_clear:N \l_tree_first_box + } + \box_use_clear:N \l_tree_parent_box + \box_use_clear:N \l_tree_left_box + } + \tree_splay_loop: + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[aux]{\tree_splay_1_-1:} +% +% \begin{macrocode} +\cs_new_protected:cpn { tree_splay_1_-1: } + { + \tex_setbox:D \l_tree_right_box \tex_hbox:D + { + \box_use_clear:N \l_tree_right_box + \box_use_clear:N \l_tree_grandpa_box + \box_use_clear:N \l_tree_second_box + } + \tex_setbox:D \l_tree_left_box \tex_hbox:D + { + \box_use_clear:N \l_tree_first_box + \box_use_clear:N \l_tree_parent_box + \box_use_clear:N \l_tree_left_box + } + \tree_splay_loop: + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[aux]{\tree_splay_-1_1:} +% +% \begin{macrocode} +\cs_new_protected:cpn { tree_splay_-1_1: } + { + \tex_setbox:D \l_tree_right_box \tex_hbox:D + { + \box_use_clear:N \l_tree_right_box + \box_use_clear:N \l_tree_parent_box + \box_use_clear:N \l_tree_first_box + } + \tex_setbox:D \l_tree_left_box \tex_hbox:D + { + \box_use_clear:N \l_tree_second_box + \box_use_clear:N \l_tree_grandpa_box + \box_use_clear:N \l_tree_left_box + } + \tree_splay_loop: + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[aux]{\tree_splay_-1_-1:} +% +% \begin{macrocode} +\cs_new_protected:cpn { tree_splay_-1_-1: } + { + \tex_setbox:D \l_tree_right_box \tex_hbox:D + { + \box_use_clear:N \l_tree_right_box + \box_use_clear:N \l_tree_parent_box + \tex_hbox:D + { + \box_use_clear:N \l_tree_first_box + \box_use_clear:N \l_tree_grandpa_box + \box_use_clear:N \l_tree_second_box + } + } + \tree_splay_loop: + } +% \end{macrocode} +% \end{macro} +% +% \subsection{Sorting} +% +% \begin{macrocode} +% \end{macrocode} +% +% \begin{macrocode} +%</initex|package> +% \end{macrocode} +% +% \end{implementation} +% +% \PrintIndex
\ No newline at end of file |