% \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> \documentclass[full]{l3doc} \usepackage{amsmath} \begin{document} \DocInput{\jobname.dtx} \end{document} % % \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: % % \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} % % \end{macrocode} % % \end{implementation} % % \PrintIndex