summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/source/latex/l3kernel/l3tree.dtx
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/source/latex/l3kernel/l3tree.dtx')
-rw-r--r--Master/texmf-dist/source/latex/l3kernel/l3tree.dtx595
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