summaryrefslogtreecommitdiff
path: root/graphics/metapost
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2023-05-12 03:02:23 +0000
committerNorbert Preining <norbert@preining.info>2023-05-12 03:02:23 +0000
commit23711a0fa219bf3164abd4aa2e25cb4db9757d7d (patch)
tree2ff6367ebc2164bcd857ce389e6221f2bf6f64a6 /graphics/metapost
parent9e4111819083b4794937d896ecb306c32daa1c2e (diff)
CTAN sync 202305120302
Diffstat (limited to 'graphics/metapost')
-rw-r--r--graphics/metapost/contrib/macros/huffman/LICENSE11
-rw-r--r--graphics/metapost/contrib/macros/huffman/README.md58
-rw-r--r--graphics/metapost/contrib/macros/huffman/doc/ctan.bib25
-rw-r--r--graphics/metapost/contrib/macros/huffman/doc/fond.pdfbin0 -> 1309 bytes
-rw-r--r--graphics/metapost/contrib/macros/huffman/doc/huffman-doc-en.pdfbin0 -> 123346 bytes
-rw-r--r--graphics/metapost/contrib/macros/huffman/doc/huffman-doc-en.tex480
-rw-r--r--graphics/metapost/contrib/macros/huffman/doc/huffman-preamble.tex174
-rw-r--r--graphics/metapost/contrib/macros/huffman/metapost/huffman.mp278
8 files changed, 1026 insertions, 0 deletions
diff --git a/graphics/metapost/contrib/macros/huffman/LICENSE b/graphics/metapost/contrib/macros/huffman/LICENSE
new file mode 100644
index 0000000000..130ede1e51
--- /dev/null
+++ b/graphics/metapost/contrib/macros/huffman/LICENSE
@@ -0,0 +1,11 @@
+
+This work may be distributed and/or modified under the
+conditions of the LaTeX Project Public License, either version 1.3c
+of this license or (at your option) any later version.
+The latest version of this license is in
+ http://www.latex-project.org/lppl.txt
+and version 1.3c or later is part of all distributions of LaTeX
+version 2005/12/01 or later.
+
+This work has the LPPL maintenance status “maintained”.
+
diff --git a/graphics/metapost/contrib/macros/huffman/README.md b/graphics/metapost/contrib/macros/huffman/README.md
new file mode 100644
index 0000000000..886ad58c6c
--- /dev/null
+++ b/graphics/metapost/contrib/macros/huffman/README.md
@@ -0,0 +1,58 @@
+# huffman
+
+This METAPOST package allows to draw binary Huffman trees from two
+arrays : a string one, and a value one. It is based on METAOBJ package which
+provides many tools to build trees in general.
+
+_This package is in beta version, do not hesitate to report bugs, as well as
+requests for improvement_.
+
+## Github
+
+To allow for easier feedback and bug reporting, this repository has a mirror
+repository on github:
+[https://github.com/chupinmaxime/huffman](https://github.com/chupinmaxime/huffman)
+
+## Installation
+
+huffman is on the [ctan](ctan.org) and can be installed via the package manager of your
+distribution [https://www.ctan.org/pkg/mpchess](https://www.ctan.org/pkg/huffman).
+
+### With TeX live under Linux or MacOS
+
+To install huffman with TeX live, you will have to create the directory texmf
+directory in your home.
+```bash
+user $> mkdir ~/texmf
+```
+
+Then, you will have to place the .mp files in the
+`~/texmf/tex/metapost/huffman/`.
+
+Once this is done, huffman will be loaded with the classic
+```metapost
+input huffman
+```
+
+### With MikTEX and Windows
+
+These two systems are unknown to the author of MPchess, so we refer to their
+documentation to add local packages:
+[http://docs.miktex.org/manual/localadditions.html](http://docs.miktex.org/manual/localadditions.html)
+
+## Dependencies
+
+huffman depends on the packages METAPOST: `metaobj` and, if MPchess is not
+used with LuaLaTeX and luamplib, `latexmp`.
+
+## Documentation
+
+* [English documentation](doc/huffman-doc-en.pdf)
+
+## Contact
+
+Maxime Chupin, `notezik(at)gmail.com`
+
+## Licenses
+
+This projet is under LATEX Project Public License 1.3c. \ No newline at end of file
diff --git a/graphics/metapost/contrib/macros/huffman/doc/ctan.bib b/graphics/metapost/contrib/macros/huffman/doc/ctan.bib
new file mode 100644
index 0000000000..3ff880adba
--- /dev/null
+++ b/graphics/metapost/contrib/macros/huffman/doc/ctan.bib
@@ -0,0 +1,25 @@
+
+@manual{ctan-metapost,
+ title = {The \texttt{metapost} package},
+ subtitle = {A development of Metafont for creating graphics},
+ author = {{The MetaPost Team} and John Hobby},
+ date = {2021-08-26},
+ license = {lgpl},
+ url = {https://ctan.org/pkg/metapost},
+ annotation = {MetaPost uses a language based on that of
+ to produce precise
+ technical illustrations. Its output is scalable PostScript or
+ SVG, rather than the bitmaps Metafont creates.},
+}
+
+
+@manual{ctan-metaobj,
+ title = {The \texttt{metaobj} package},
+ subtitle = {MetaPost package providing high-level objects},
+ author = {Denis B. Roegel},
+ date = {2016-06-24},
+ version = {0.93},
+ license = {lppl},
+ mirror = {https://mirror.ctan.org/graphics/metapost/contrib/macros/metaobj},
+ url = {https://ctan.org/pkg/metaobj},
+} \ No newline at end of file
diff --git a/graphics/metapost/contrib/macros/huffman/doc/fond.pdf b/graphics/metapost/contrib/macros/huffman/doc/fond.pdf
new file mode 100644
index 0000000000..22218152cc
--- /dev/null
+++ b/graphics/metapost/contrib/macros/huffman/doc/fond.pdf
Binary files differ
diff --git a/graphics/metapost/contrib/macros/huffman/doc/huffman-doc-en.pdf b/graphics/metapost/contrib/macros/huffman/doc/huffman-doc-en.pdf
new file mode 100644
index 0000000000..283ba984fc
--- /dev/null
+++ b/graphics/metapost/contrib/macros/huffman/doc/huffman-doc-en.pdf
Binary files differ
diff --git a/graphics/metapost/contrib/macros/huffman/doc/huffman-doc-en.tex b/graphics/metapost/contrib/macros/huffman/doc/huffman-doc-en.tex
new file mode 100644
index 0000000000..b6d1a42cb3
--- /dev/null
+++ b/graphics/metapost/contrib/macros/huffman/doc/huffman-doc-en.tex
@@ -0,0 +1,480 @@
+
+% LTeX: language=en
+
+% huffman : draw binary huffman trees with MetaPost/MetaObj
+%
+% Originally written by Maxime Chupin <notezik@gmail.com>,
+% 2023.
+%
+% Distributed under the terms of the GNU free documentation licence:
+% http://www.gnu.org/licenses/fdl.html
+% without any invariant section or cover text.
+
+\documentclass[english]{ltxdoc}
+
+\input{huffman-preamble}
+
+\usepackage[english]{babel}
+
+\makeindex[title=Command Index, columns=2]
+
+
+
+%\lstset{moredelim=*[s][\color{red}\rmfamily\itshape]{<}{>}}
+%\lstset{moredelim=*[s][\color{blue}\rmfamily\itshape]{<<}{>>}}
+
+\begin{document}
+
+\title{{Huffman} : drawing binary Huffman trees with \hologo{METAPOST} and \MO/}
+\author{Maxime Chupin, \url{notezik@gmail.com}}
+\date{\today}
+
+%% === Page de garde ===================================================
+\thispagestyle{empty}
+\begin{tikzpicture}[remember picture, overlay]
+ \node[below right, shift={(-4pt,4pt)}] at (current page.north west) {%
+ \includegraphics{fond.pdf}%
+ };
+\end{tikzpicture}%
+
+\noindent
+{\Huge \texttt{huffman}}\par\bigskip
+\noindent
+{\Large drawing binary Huffman trees \\[0.2cm]with \hologo{METAPOST} and \MO/}\\[1cm]
+\parbox{0.6\textwidth}{
+ \begin{mplibcode}
+ input huffman
+
+ string charList[];
+numeric frequency[];
+show_bits:=false;
+beginfig(1);
+charList[4]:="a"; frequency[4]:=4;
+charList[5]:="b"; frequency[5]:=5;
+charList[3]:="c"; frequency[3]:=6;
+charList[1]:="d"; frequency[1]:=7;
+charList[2]:="e"; frequency[2]:=10;
+charList[6]:="f"; frequency[6]:=10;
+charList[7]:="g"; frequency[7]:=18;
+charList[8]:="h"; frequency[8]:=40;
+newBinHuffman.myHuff(8)(charList,frequency) "treemode(T)", "vbsep(0.3cm)";
+myHuff.c=origin;
+drawObj(myHuff);
+endfig;
+ \end{mplibcode}
+}\hfill
+\parbox{0.5\textwidth}{\Large\raggedleft
+ \textbf{Contributor}\\
+ Maxime \textsc{Chupin}\\
+ \url{notezik@gmail.com}
+}
+\vfill
+\begin{center}
+ Version 0.1, 2023, May, 10th \\
+ \url{https://plmlab.math.cnrs.fr/mchupin/huffman}
+\end{center}
+%% == Page de garde ====================================================
+\newpage
+
+%\maketitle
+
+\begin{abstract}
+ This \hologo{METAPOST} package allows to draw binary Huffman trees from two
+ arrays : an arraw of strings, and an array of weights (\lstinline+numeric+).
+ It is based on the \MO/ package which
+ provides many tools to build trees in general.
+\end{abstract}
+
+
+\begin{center}
+ \url{https://plmlab.math.cnrs.fr/mchupin/huffman}
+ \url{https://github.com/chupinmaxime/huffman}
+\end{center}
+
+\tableofcontents
+
+\bigskip
+
+\begin{tcolorbox}[ arc=0pt,outer arc=0pt,
+ colback=darkred!3,
+ colframe=darkred,
+ breakable,
+ boxsep=0pt,left=5pt,right=5pt,top=5pt,bottom=5pt, bottomtitle =
+ 3pt, toptitle=3pt,
+ boxrule=0pt,bottomrule=0.5pt,toprule=0.5pt, toprule at break =
+ 0pt, bottomrule at break = 0pt,]
+ \itshape
+ This package is in beta version---do not hesitate to report bugs, as well as requests for improvement.
+\end{tcolorbox}
+
+\section{Installation}
+
+\huffman is on \ctan{} and can also be installed via the package manager of your
+distribution.
+
+\begin{center}
+ \url{https://www.ctan.org/pkg/huffman}
+\end{center}
+
+
+\subsection{With \TeX live under Linux or macOS}
+
+To install \huffman with \TeX Live, you will have to create the directory
+\lstinline+texmf+ in your \lstinline+home+.
+
+\begin{commandshell}
+mkdir ~/texmf
+\end{commandshell}
+
+Then, you will have to place the \lstinline+huffman.mp+ file in
+\begin{center}
+ \lstinline+~/texmf/metapost/huffman/+
+\end{center}
+
+
+Once this is done, \huffman will be loaded with the classic \MP{}
+input code
+\begin{mpcode}
+input huffman
+\end{mpcode}
+
+\subsection{With Mik\TeX{} and Windows}
+
+These two systems are unknown to the author of \huffman, so we
+refer you to the Mik\TeX documentation concerning the addition of local packages:
+\begin{center}
+ \url{http://docs.miktex.org/manual/localadditions.html}
+\end{center}
+
+
+
+\subsection{Dependencies}
+
+
+\huffman depends, of course on \MP~\cite{ctan-metapost}, as well as the packages
+\package{metaobj}~\cite{ctan-metaobj} and---if \huffman is not used with
+\hologo{LuaLaTeX} and the \package{luamplib} package---the \package{latexmp}
+package.
+
+\section{Main Command}
+
+The package \huffman provides one principal command (which is a \MO/ like
+constructor):
+
+\commande|newBinHuffman.«name»(«sizeofarrays»)(«symbarray»,«valuearray»)|\smallskip\index{newBinHuffman@\lstinline+newBinHuffman+}
+
+
+\begin{description}
+ \item[\meta{name}:] is the name of the object;
+ \item[\meta{sizeofarrays}:] is the size (integer) of the arrays;
+ \item[\meta{symbarray}:] is the array of \lstinline+string+ containing the
+ symbols;
+ \item[\meta{valuearray}:] is the array of \lstinline+numeric+ containing the
+ weights associated to the symbols.
+\end{description}
+
+The data arrays should begin at index 1.
+
+\begin{ExempleMP}
+input huffman
+
+beginfig(0);
+string charList[];
+numeric frequency[];
+charList[1]:="a"; frequency[1]:=0.04;
+charList[2]:="b"; frequency[2]:=0.05;
+charList[3]:="c"; frequency[3]:=0.06;
+charList[4]:="d"; frequency[4]:=0.07;
+charList[5]:="e"; frequency[5]:=0.1;
+charList[6]:="f"; frequency[6]:=0.1;
+charList[7]:="g"; frequency[7]:=0.18;
+charList[8]:="h"; frequency[8]:=0.4;
+
+newBinHuffman.myHuff(8)(charList,frequency);
+myHuff.c=origin;
+drawObj(myHuff);
+endfig;
+\end{ExempleMP}
+
+Note that the symbols are composed in mathematical \TeX{} mode.
+\section{Package Options}
+
+You can modify the size of the internal nodes of the tree with the following
+command:
+
+\commande|set_node_size(«dim»)|\smallskip\index{set_node_size@\lstinline+set_node_size+}
+\begin{description}
+ \item[\meta{dim}:] is the diameter with unit of the circle (default: 13pt).
+\end{description}
+
+You can change the color for the symbol boxes with the following command:
+
+\commande|set_leaf_color(«color»)|\smallskip\index{set_leaf_color@\lstinline+set_leaf_color+}
+\begin{description}
+ \item[\meta{color}:] is a \hologo{METAPOST} \lstinline+color+.
+\end{description}
+
+You can hide the bit values printed on the edges of the tree with the following
+boolean
+(\lstinline+true+ by default):
+
+\commande|show_bits|\smallskip\index{show_bits@\lstinline+show_bits+}
+
+Similarly, you can set the following boolean to \lstinline+false+ to hide the
+node values:
+
+\commande|show_node_values|\smallskip\index{show_node_values@\lstinline+show_node_values+}
+
+Finally, you can set the following boolean to \lstinline+false+ to hide the
+leaf values:
+
+\commande|show_leaf_values|\smallskip\index{show_leaf_values@\lstinline+show_leaf_values+}
+
+Here an example combining all these commands and variables.
+
+\begin{ExempleMP}
+input huffman
+
+beginfig(0);
+string charList[];
+numeric frequency[];
+charList[1]:="s_1"; frequency[1]:=2;
+charList[2]:="s_2"; frequency[2]:=4;
+charList[3]:="s_3"; frequency[3]:=2;
+charList[4]:="s_4"; frequency[4]:=12;
+charList[5]:="s_5"; frequency[5]:=8;
+
+set_leaf_color(0.2[white,green]);
+set_node_size(8pt);
+show_bits:=false;
+show_node_values:=false;
+show_leaf_values:=false;
+newBinHuffman.myHuff(5)(charList,frequency);
+myHuff.c=origin;
+drawObj(myHuff);
+endfig;
+\end{ExempleMP}
+
+
+
+\section{\MO/ Tree Options}
+
+Because the Huffman tree is built using the \MO/ tree constructor, the \MO/ tree
+options are available. All of them are not well suited for this application
+mostly because the Huffman tree is built using elementary trees. The
+options we give to the Huffman constructor are passed to all the subtrees.
+
+We give in table~\ref{tab:options} the \MO/ options for the trees that could be
+used for the Huffman constructor.
+
+\begin{table}[ht]
+\centering\small
+\begin{tabular}{HHHp{5.5cm}}
+ \toprule
+ Option & Type & Default & Description \\
+ \midrule
+ treemode & string & "D" & direction in which the tree develops; there are
+ four different possible values: \lstinline+"D"+ (default),
+ \lstinline+"U"+, \lstinline+"L"+ and \lstinline+"R"+\\
+ treeflip & boolean & false & if true, reverses the order of the subtrees\\
+ treenodehsize & numeric & -1pt & if non-negative, all the nodes are assumed to
+ have this width\\
+ treenodevsize & numeric & -1pt & if non-negative, all the nodes are assumed to
+ have this height\\
+ dx & numeric & 0 & horizontal clearance around the tree\\
+ dy & numeric & 0 & vertical clearance around the tree\\
+ hsep & numeric & 1cm & for a horizontal tree, this is the separation be-
+ tween the root and the subtrees\\
+ vsep & numeric & 1cm & for a vertical tree, this is the separation be-
+ tween the root and the subtrees\\
+ hbsep & numeric & 1cm &for a vertical tree, this is the horizontal separation between subtrees;
+ the subtrees are actually put in a \lstinline+HBox+ and the value of this
+ option is passed to the \lstinline+HBox+ constructor\\
+ vbsep & numeric & 1cm & for an horizontal tree, this is the vertical separation between subtrees;
+ the subtrees are actually put in a \lstinline+HBox+ and the value of this
+ option is passed to the \lstinline+HBox+ constructor\\
+ edge & string & "ncline" & name of a connection command (se \MO/
+ documentation)
+ \\
+ Dalign & string & "top" & vertical alignment of subtrees for trees that go
+ down (the root on the top); the other possible
+ values are \lstinline+"center"+ and \lstinline+"bot"+\\
+ \bottomrule
+\end{tabular}
+\caption{Table of \MO/ tree options.}\label{tab:options}
+\end{table}
+
+Here is an example using some of these options.
+
+\begin{ExempleMP}
+input huffman
+
+beginfig(0);
+string charList[];
+numeric frequency[];
+charList[1]:="s_1"; frequency[1]:=2;
+charList[2]:="s_2"; frequency[2]:=4;
+charList[3]:="s_3"; frequency[3]:=2;
+charList[4]:="s_4"; frequency[4]:=12;
+charList[5]:="s_5"; frequency[5]:=8;
+
+newBinHuffman.myHuff(5)(charList,frequency)
+"treemode(R)","treeflip(true)","hsep(1.5cm)", "edge(nccurve)" , "angleA(0)", "angleB(0)";
+myHuff.c=origin;
+drawObj(myHuff);
+endfig;
+\end{ExempleMP}
+
+\section{Access to Nodes and Leaves}
+
+To access the nodes and the leaves, you can use the \lstinline+treeroot+ command
+from \MO/, see the documentation for details.
+
+\commande|ntreepos(Obj(«name»))(«int»,«int»,etc.)|\smallskip\index{ntreepos@\lstinline+ntreepos+}
+
+The sequence of \meta{int} gives the choice of branch where the children are
+numbered from 1 to $n$.
+
+The following example shows a use of this mecanism.
+\begin{ExempleMP}
+input huffman;
+beginfig(0);
+string charList[];
+numeric frequency[];
+charList[1]:="s_1"; frequency[1]:=2;
+charList[2]:="s_2"; frequency[2]:=4;
+charList[3]:="s_3"; frequency[3]:=2;
+charList[4]:="s_4"; frequency[4]:=12;
+charList[5]:="s_5"; frequency[5]:=8;
+
+newBinHuffman.myHuff(5)(charList,frequency);
+myHuff.c=origin;
+ncarcbox(ntreepos(Obj(myHuff))(2,1,2))(ntreepos(Obj(myHuff))(2,2))
+"linestyle(dashed evenly)", "nodesepA(5mm)", "nodesepB(5mm)" ;
+drawObj(myHuff);
+endfig;
+\end{ExempleMP}
+
+Of course, this can only be used in two steps, first build the tree, then
+annotate it.
+
+You can also access the leaves and the nodes using names. During the
+construction of the tree, names are given to leaves and nodes. Because you may
+want to build several Huffman trees, the trees are numbered. You can get the
+current tree number with the following command:
+
+\commande|get_huffmanTreeNbr()|\smallskip\index{get_huffmanTreeNbr@\lstinline+get_huffmanTreeNbr+}
+
+The leaves are numbered during the construction, and the corresponding \MO/
+object is named as follows:
+
+\commande|leaf«leaf number»_«tree number»|\smallskip
+
+The nodes are numbered during the construction, and the corresponding \MO/
+object is named as follows:
+
+\commande|node«node number»_«tree number»|\smallskip
+
+Thanks to \MO/ you can annotate the tree using all the tools \MO/ provides.
+
+\begin{ExempleMP}
+input huffman;
+beginfig(0);
+string charList[];
+numeric frequency[];
+charList[1]:="s_1"; frequency[1]:=2;
+charList[2]:="s_2"; frequency[2]:=4;
+charList[3]:="s_3"; frequency[3]:=2;
+charList[4]:="s_4"; frequency[4]:=12;
+charList[5]:="s_5"; frequency[5]:=8;
+
+newBinHuffman.myHuff(5)(charList,frequency);
+myHuff.c=origin;
+ncarcbox(node2_1)(leaf4_1)
+"linestyle(dashed evenly)", "nodesepA(5mm)", "nodesepB(5mm)" ;
+drawObj(myHuff);
+endfig;
+\end{ExempleMP}
+
+
+
+
+
+
+
+
+\section{Constructors}
+
+The Huffman algorithm uses only three constructors that you can redefine to adapt
+the tree to your needs. Here are the three constructors (roughly commented in
+French) defined in this package. We will not discuss the code here but
+you are free to redefine and adapt it.
+
+\begin{mpcode}[title={Leaf Code}]
+% style d’une feuille caractère et proba
+vardef newHuffmanLeaf@#(expr ch)(expr v) text options=
+ % @# est l’identifiant de la feuille
+ % c est le caractère considéré (ou la chaine)
+ % v est la proba ou l’entier associé
+ save _text_v,
+ _text_token,_height_v,_height_token,_height_max,_width_token,_width_v;
+ picture _text_v,_text_token;
+ % on calcule le height max des deux écritures pour faire deux boites de même
+ % hauteur
+ _text_v := textext(v);
+ _text_token := textext("$"&ch&"$");
+ _height_v := abs((ulcorner _text_v) - (llcorner _text_v));
+ _width_v := abs(urcorner _text_v - ulcorner _text_v);
+ _height_token := abs(ulcorner _text_token - llcorner _text_token);
+ _width_token := abs(urcorner _text_token - ulcorner _text_token);
+ _height_max := max(_height_token,_height_v);
+ % on fabrique deux boîtes vides aux bonne dimensions
+ % et on ajoute un label au centre de celles-ci
+ if(show_leaf_values):
+ newEmptyBox.scantokens(str @# & "ch1")(_width_token+4,2_height_max)
+ "framed(true)","fillcolor(_huffmanLeaf)", "filled(true)", options;
+ ObjLabel.Obj(scantokens(str @# & "ch1"))(textext("$" & ch & "$"));
+ newEmptyBox.scantokens(str @# & "ch2")(_width_v+4,2_height_max)
+ "framed(true)", options;
+ ObjLabel.Obj(scantokens(str @# & "ch2"))(textext(v));
+ % on fixe relativement les coordonnées des deux boites pour qu’elles se % touchent
+ scantokens(str @# & "ch1").e=scantokens(str @# & "ch2").w;
+ % on fabrique un container qui les regroupes et qui sera la feuille
+ newContainer.@#(scantokens(str @# & "ch1"),scantokens(str @# & "ch2"));
+ else:
+ % si seulement le symbole
+ newBox.@#(textext("$" & ch & "$"))
+ "framed(true)","fillcolor(_huffmanLeaf)", "filled(true)", options;
+ fi
+enddef;
+\end{mpcode}
+
+
+\begin{mpcode}[title={Node Code}]
+% style d’un nœud interne (non feuille) de l’arbre
+vardef newHuffmanNode@#(expr v) text options=
+ newCircle.@#("") "circmargin(_node_size)",options;
+ if(show_node_values):
+ ObjLabel.Obj(scantokens(str @#))(textext(v));
+ fi
+enddef;
+\end{mpcode}
+
+\begin{mpcode}[title={Tree Code}]
+% style de l’arbre binaire de Huffman
+vardef newHuffmanBinTree@#(suffix theroot)(text subtrees) text options=
+ % un simple arbre
+ newTree.@#(theroot)(subtrees) "Dalign(top)" , "hbsep(0.3cm)",options;
+ if(show_bits):
+ % et on met 0 et 1 sur ses deux connections
+ ObjLabel.Obj(@#)(btex 0 etex)
+ "labpathid(1)", "laberase(true)", "labcolor(_huffmanBit)";
+ ObjLabel.Obj(@#)(btex 1 etex)
+ "labpathid(2)", "laberase(true)", "labcolor(_huffmanBit)";
+ fi
+enddef;
+\end{mpcode}
+
+\printbibliography
+\printindex
+\end{document}
diff --git a/graphics/metapost/contrib/macros/huffman/doc/huffman-preamble.tex b/graphics/metapost/contrib/macros/huffman/doc/huffman-preamble.tex
new file mode 100644
index 0000000000..d264ecb462
--- /dev/null
+++ b/graphics/metapost/contrib/macros/huffman/doc/huffman-preamble.tex
@@ -0,0 +1,174 @@
+\usepackage{tcolorbox}
+\tcbuselibrary{listings,breakable}
+%\tcbuselibrary{documentation}
+\usepackage{enumitem}
+\usepackage[tikz]{bclogo}
+\usepackage{mflogo}
+\usepackage{hologo}
+\usepackage{luamplib}
+\mplibtextextlabel{enable}
+\usepackage{biblatex}
+\addbibresource{ctan.bib}
+\usepackage{wrapfig}
+\usepackage{accsupp}
+\usepackage{siunitx}
+\usepackage{imakeidx}
+%\usepackage{csquotes}
+\usepackage{fancyvrb,xparse,xargs}
+\usepackage[sfdefault]{FiraSans}
+\usepackage[mathrm=sym]{firamath-otf}
+\setmonofont{Fira Mono}
+%\setmonofont{FiraCode-Regular.ttf}[BoldFont= FiraCode-Bold.ttf,ItalicFont= FiraCode-RegularItalic.otf,BoldItalicFont= FiraCode-BoldItalic.otf,Ligatures={NoCommon, NoDiscretionary, NoHistoric, NoRequired, NoContextual}]
+
+\usepackage{xspace}
+\usepackage{animate}
+\newcommand{\ctan}{\textsc{ctan}}
+\NewDocumentCommand{\package}{ m }{%
+ \href{https://ctan.org/pkg/#1}{#1}\xspace
+}
+
+\definecolor{darkred}{rgb}{0.6,0.1,0.1}
+\definecolor{vert}{rgb}{0.1,0.4,0.1}
+\definecolor{bleu}{rgb}{0.2,0.2,0.6}
+\definecolor{orange}{rgb}{0.6,0.4,0.}
+\colorlet{code}{blue!80!black}
+
+\usepackage[colorlinks=true,urlcolor=orange,linkcolor=orange,menucolor=black,citecolor=orange]{hyperref}
+
+\newcommand \file {\nolinkurl}
+\renewcommand \cmd {\texttt}
+\renewcommand \code [1] {\texorpdfstring {\texttt{\color{code}#1}} {#1}}
+\renewcommand*\cs [1] {\code{\textbackslash #1}}
+
+
+
+\newcommand*\commande{\par\bigskip\noindent\hspace{-30pt}%
+ \SaveVerb[aftersave={%
+ \UseVerb{Vitem}%
+ }%
+ ]{Vitem}%
+ }
+ \newcommand\vitem[1][]{\SaveVerb[%
+ aftersave={\item[\textnormal{\UseVerb[#1]{vsave}}]}]{vsave}}
+\newcommand*\textme[1]{\textcolor{black}{\rmfamily\textit{#1}}}
+%\renewcommand*\meta[1]{% % meta
+% \textme{\ensuremath{\langle}#1\ensuremath{\rangle}}}
+\newcommand*\optstar{% % optional star
+ \meta{\ensuremath{*}}\xspace}
+\DefineShortVerb{\|}
+\newcommand\R{\mathbf{R}}
+\setlength{\fboxsep}{2pt}
+\fvset{%
+ codes={\catcode`\«\active \catcode`\×\active },
+ defineactive={\makefancyog\makefancytimes},
+ formatcom=\color{darkred},
+ frame=single
+}
+% rendre «...» équivalent à \meta{...}
+{\catcode`\«\active
+ \newcommandx\makefancyog[0][addprefix=\global]{%
+ \def«##1»{\meta{##1}}}}
+% rendre × équivalent à \optstar
+{\catcode`\×\active
+ \newcommandx\makefancytimes[0][addprefix=\global]{%
+ \def×{\optstar{}}}}
+
+
+\newcommand\huffman{\texttt{huffman}\xspace}
+
+\def\MO/{{\fontspec{fetamont}META\-OBJ}}
+
+%\addbibresource{biblio.bib}
+
+
+\lstset{
+ numberstyle=\footnotesize\color{vert},
+ keywordstyle=\ttfamily\bfseries\color{bleu},
+ basicstyle=\ttfamily,
+ commentstyle=\itshape\color{vert},
+ stringstyle=\ttfamily\color{orange},
+ showstringspaces=false,
+ language=MetaPost,
+ breaklines=true,
+ breakindent=30pt,
+ defaultdialect=MetaPost,
+ classoffset=1,% frame=tb
+ morekeywords={init_backboard,set_backboard_width,set_backboard_size,set_color_theme,get_backboard_width,get_backboard_size,set_backboard_width,get_square_dim,set_white_color,set_black_color,set_coords_inside,set_coords_outside,set_coords_font,set_coords,
+ set_no_coords,set_white_view,set_black_view,
+ set_white_player,set_black_player,set_pieces_theme,set_players_side,init_chessboard,set_empty_chessboard,add_white_pieces,add_black_pieces,clear_areas,clear_files,clear_ranks,clear_squares,build_chessboard_from_fen,build_chessboards_from_pgn,clear_chessboard,
+ color_square,draw_arrows,draw_circles,draw_comment,draw_crosses,get_halfmove_number,get_totalmove_number,
+ reset_mpchess,set_black_to_move,set_last_move_color,set_comment_color,set_white_to_move,set_whos_to_move,show_last_move,unset_whos_to_move,set_arrow_width,clip_chessboard,build_chessboard_from_fen_file,build_chessboard_from_pgn_file,draw_black_main_lines,draw_black_main_lines_step,draw_white_main_lines,draw_white_main_lines_step,set_main_lines_color,set_possible_moves_color,show_possible_moves,show_possible_moves_step,newEllipse,drawObj,newBox,newPolygon,newCircle,newTree,ObjLabel,newEmptyBox,scantokens,newContainer,newBinHuffman,newHuffmanLeaf,newHuffmanNode,newHuffman,ncarcbox,ntreepos,set_node_size,set_leaf_color,show_bits,show_node_values,show_leaf_values,newHuffmanBinTree,get_huffmanTreeNbr},
+ keywordstyle=\color{darkred},
+ classoffset=2,% frame=tb
+ morekeywords={backboard,chessboard,chessboard_step},
+ keywordstyle=\color{vert},
+ classoffset=0,% frame=tb
+ morekeywords={draw},
+ keywordstyle=\color{bleu}
+}
+
+
+\extractcolorspecs{darkred!3}\modelcmd\colorcmd
+\makeatletter
+\tcbset{%
+ listing metapost/.code={%
+ \def\tcbuselistingtext@input{\begin{mplibcode} verbatimtex \leavevmode etex;
+ background:=(\colorcmd); input \jobname.listing; \end{mplibcode}}%
+ }
+}
+\makeatother
+\newtcblisting[auto counter,]{ExempleMP}[1][]{%
+ arc=0pt,outer arc=0pt,
+ colback=darkred!3,
+ colframe=darkred,
+ breakable,fontupper=\small,
+ boxsep=0pt,left=5pt,right=5pt,top=5pt,bottom=5pt, bottomtitle =
+ 3pt, toptitle=3pt,
+ boxrule=0pt,bottomrule=0.5pt,toprule=0.5pt, toprule at break =
+ 0pt, bottomrule at break = 0pt,
+ %listing side text,
+ listing metapost,
+ title=Exemple~\thetcbcounter,
+ listing options={breaklines},#1
+}
+
+\newtcblisting{commandshell}{colback=black,colupper=white,colframe=black,
+ arc=0pt,
+ listing only,boxsep=0pt,listing
+ options={style=tcblatex,language=sh},
+ every listing line={\BeginAccSupp{ActualText={}}\textcolor{red}{\small\ttfamily\bfseries user \$> }}\EndAccSupp{}}
+
+
+ \newtcblisting{mpcode}[1][]{
+ arc=0pt,outer arc=0pt,
+ colback=darkred!3,
+ colframe=darkred,
+ breakable,
+ boxsep=0pt,left=5pt,right=5pt,top=5pt,bottom=5pt, bottomtitle =
+ 3pt, toptitle=3pt,
+ boxrule=0pt,bottomrule=0.5pt,toprule=0.5pt, toprule at break =
+ 0pt, bottomrule at break = 0pt,
+ listing only,boxsep=0pt,listing
+ options={breaklines},#1
+}
+
+\newtcblisting{latexcode}{
+ arc=0pt,outer arc=0pt,
+ colback=darkred!3,
+ colframe=darkred,
+ breakable,
+ boxsep=0pt,left=5pt,right=5pt,top=5pt,bottom=5pt, bottomtitle =
+ 3pt, toptitle=3pt,
+ boxrule=0pt,bottomrule=0.5pt,toprule=0.5pt, toprule at break =
+ 0pt, bottomrule at break = 0pt,
+ listing only,boxsep=0pt,listing
+ options={breaklines,language={[LaTeX]TeX}}
+}
+
+
+\newcommand\pdf{\textsc{pdf}}
+
+\usepackage{array,booktabs}
+\usepackage{collcell}
+
+\newcolumntype{H}{>{\collectcell\lstinline}l<{\endcollectcell}} \ No newline at end of file
diff --git a/graphics/metapost/contrib/macros/huffman/metapost/huffman.mp b/graphics/metapost/contrib/macros/huffman/metapost/huffman.mp
new file mode 100644
index 0000000000..92b3020fb4
--- /dev/null
+++ b/graphics/metapost/contrib/macros/huffman/metapost/huffman.mp
@@ -0,0 +1,278 @@
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% huffman.mp %%
+%% draw huffman trees with metapost %%
+%% notezik@gmail.com %%
+%% Version 0.1 (may 2023) %%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%
+% This work may be distributed and/or modified under the conditions of
+% the LaTeX Project Public License, either version 1.3c of this license
+% or (at your option) any later version. The latest version of this
+% license is in http://www.latex-project.org/lppl.txt
+%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+input metaobj;
+if not known mplib: input latexmp fi;
+input format; % pour avoir la fonction roundd(x,d)
+
+show_empty_boxes:=true;
+
+% variable globale pour numéroter les instances des arbres
+% pour pouvoir appeler plusieurs fois le Huffman
+_huffmanTreeNbr:=0;
+
+def get_huffmanTreeNbr=
+ _huffmanTreeNbr
+enddef;
+
+% taille des nœuds
+_node_size:=13pt;
+def set_node_size(expr c)=
+ _node_size:=c;
+enddef;
+
+% les couleurs
+color _huffmanLeaf,_huffmanBit;
+_huffmanLeaf:=(0.95,0.6,0.6);
+_huffmanBit:=(0.7,0.1,0.1);
+
+def set_leaf_color(expr c)=
+ _huffmanLeaf:=c;
+enddef;
+
+def set_bit_color(expr c)=
+ _huffmanBit:=c;
+enddef;
+
+boolean show_bits;
+show_bits:=true;
+
+boolean show_node_values;
+show_node_values:=true;
+
+boolean show_leaf_values;
+show_leaf_values:=true;
+
+% style d’une feuille caractère et proba
+vardef newHuffmanLeaf@#(expr ch)(expr v) text options=
+ % @# est l’identifiant de la feuille
+ % c est le caractère considéré (ou la chaine)
+ % v est la proba ou l’entier associé
+ picture _text_v,_text_token;
+ % on calcule le height max des deux écritures pour faire deux boites de même
+ % hauteur
+ _text_v := textext(v);
+ _text_token := textext("$"&ch&"$");
+ _height_v := abs((ulcorner _text_v) - (llcorner _text_v));
+ _width_v := abs(urcorner _text_v - ulcorner _text_v);
+ _height_token := abs(ulcorner _text_token - llcorner _text_token);
+ _width_token := abs(urcorner _text_token - ulcorner _text_token);
+ _height_max := max(_height_token,_height_v);
+ % on fabrique deux boîtes vides aux bonne dimensions
+ % et on ajoute un label au centre de celles-ci
+ if(show_leaf_values):
+ newEmptyBox.scantokens(str @# & "ch1")(_width_token+4,2_height_max)
+ "framed(true)","fillcolor(_huffmanLeaf)", "filled(true)", options;
+ ObjLabel.Obj(scantokens(str @# & "ch1"))(textext("$" & ch & "$"));
+ newEmptyBox.scantokens(str @# & "ch2")(_width_v+4,2_height_max)
+ "framed(true)", options;
+ ObjLabel.Obj(scantokens(str @# & "ch2"))(textext(v));
+ % on fixe relativement les coordonnées des deux boites pour qu’elles se % touchent
+ scantokens(str @# & "ch1").e=scantokens(str @# & "ch2").w;
+ % on fabrique un container qui les regroupes et qui sera la feuille
+ newContainer.@#(scantokens(str @# & "ch1"),scantokens(str @# & "ch2"));
+ else:
+ newBox.@#(textext("$" & ch & "$"))
+ "framed(true)","fillcolor(_huffmanLeaf)", "filled(true)", options;
+ fi
+enddef;
+
+% style de l’arbre binaire de Huffman
+vardef newHuffmanBinTree@#(suffix theroot)(text subtrees) text options=
+ % un simple arbre
+ newTree.@#(theroot)(subtrees) "Dalign(top)" , "hbsep(0.3cm)",options;
+ if(show_bits):
+ % et on met 0 et 1 sur ses deux connections
+ ObjLabel.Obj(@#)(btex 0 etex)
+ "labpathid(1)", "laberase(true)", "labcolor(_huffmanBit)";
+ ObjLabel.Obj(@#)(btex 1 etex)
+ "labpathid(2)", "laberase(true)", "labcolor(_huffmanBit)";
+ fi
+enddef;
+
+% style d’un nœud interne (non feuille) de l’arbre
+vardef newHuffmanNode@#(expr v) text options=
+ newCircle.@#("") "circmargin(_node_size)",options;
+ if(show_node_values):
+ ObjLabel.Obj(scantokens(str @#))(textext(v));
+ fi
+enddef;
+
+
+% fonction de tri à bulle d’un tableau
+vardef _sorttab(expr nbr)(suffix tab,chartab)=
+ string _tempchar;
+ for i:=nbr downto 1:
+ for j:=1 upto i-1:
+ if(tab[j+1]<tab[j]):
+ _temptab:=tab[j+1];
+ tab[j+1]:=tab[j];
+ tab[j]:=_temptab;
+ _tempchar:=chartab[j+1];
+ chartab[j+1]:=chartab[j];
+ chartab[j]:=_tempchar;
+ fi
+ endfor;
+ endfor;
+enddef;
+
+% le constructeur d’un objet Tree du code de Hufmann
+vardef newBinHuffman@#(expr nbr)(suffix ch, fr) text options=
+ % nbr : taille des tableaux
+ % ch : tableau des symboles à coder (string)
+ % fr : tableau des valeurs associées (numeric)
+ _huffmanTreeNbr:=_huffmanTreeNbr+1;
+ save _frtab,_chtab,_nbr;
+ % on copie les tableaux
+ numeric _frtab[];
+ numeric _nbr;
+ _nbr:=nbr;
+ string _chtab[];
+ for i:=1 upto nbr:
+ _frtab[i]:=fr[i];
+ _chtab[i]:=ch[i];
+ endfor;
+ % on va numéroter les nœuds fabriqués
+ _nbrnode:=1;
+ % on numérote les feuilles
+ _nbrleaf:=0;
+ forever:
+ % on sort s’il n’y a plus qu’un seul élément
+ exitif(_nbr=1);
+ % on trie pour avoir les deux plus petits en première et deuxième positions
+ _sorttab(_nbr,_frtab,_chtab);
+ for i:=1 upto nbr-1:
+ % on teste les 4 cas possibles sur les deux premiers éléments
+ % (symbole, symbole), (symbole, sousarbre), (sousarbre, symbole)
+ % et (sousarbre,sousarbre)
+ if(i=1):
+
+ if(substring (0,1) of _chtab[1]<>"T"): %(symbole,*)
+ % on fabrique la feuille
+ _nbrleaf:=_nbrleaf+1;
+ newHuffmanLeaf.scantokens("leaf"&decimal
+ _nbrleaf&"_"&decimal _huffmanTreeNbr)(_chtab[1])(decimal
+ roundd(_frtab[1],2));
+ if(substring (0,1) of _chtab[2]<>"T"): %(symbole, symbole)
+ % on fabrique la feuille
+ _nbrleaf:=_nbrleaf+1;
+ newHuffmanLeaf.scantokens("leaf"&decimal
+ _nbrleaf&"_"&decimal _huffmanTreeNbr)(_chtab[2])(decimal
+ roundd(_frtab[2],2));
+ % on fabrique le nœud qui et l’arbre qui a les deux
+ % feuilles en descendants
+ _tmpsum:=_frtab[1]+_frtab[2];
+ newHuffmanNode.scantokens("node"&decimal
+ _nbrnode&"_"&decimal _huffmanTreeNbr)(decimal
+ roundd(_tmpsum,2));
+ if(_nbr=2): % dernier arbre, on nomme avec @#
+ newHuffmanBinTree@#(scantokens("node"&decimal
+ _nbrnode&"_"&decimal
+ _huffmanTreeNbr))(scantokens("leaf"&decimal(
+ _nbrleaf-1)&"_"&decimal
+ _huffmanTreeNbr),scantokens("leaf"&decimal(
+ _nbrleaf)&"_"&decimal
+ _huffmanTreeNbr)) options;
+ else:
+ newHuffmanBinTree.scantokens("Tree"&decimal
+ _nbrnode&"_"&decimal _huffmanTreeNbr)(scantokens("node"&decimal
+ _nbrnode&"_"&decimal
+ _huffmanTreeNbr))(scantokens("leaf"&decimal(
+ _nbrleaf-1)&"_"&decimal
+ _huffmanTreeNbr),scantokens("leaf"&decimal(
+ _nbrleaf)&"_"&decimal
+ _huffmanTreeNbr)) options;
+ fi
+ else: %(symbole, sousarbre)
+ _tmpsum:=_frtab[1]+_frtab[2];
+ newHuffmanNode.scantokens("node"&decimal
+ _nbrnode&"_"&decimal _huffmanTreeNbr)(decimal
+ roundd(_tmpsum,2));
+ if(_nbr=2): % dernier arbre, on nomme avec @#
+ newHuffmanBinTree@#(scantokens("node"&decimal
+ _nbrnode&"_"&decimal
+ _huffmanTreeNbr))(scantokens("leaf"&decimal(
+ _nbrleaf)&"_"&decimal
+ _huffmanTreeNbr),scantokens(_chtab[2])) options;
+ else:
+ newHuffmanBinTree.scantokens("Tree"&decimal
+ _nbrnode&"_"&decimal
+ _huffmanTreeNbr)(scantokens("node"&decimal
+ _nbrnode&"_"&decimal
+ _huffmanTreeNbr))(scantokens("leaf"&decimal(
+ _nbrleaf)&"_"&decimal
+ _huffmanTreeNbr),scantokens(_chtab[2])) options;
+ fi
+ fi
+ else: %(sousarber,*)
+ if(substring (0,1) of _chtab[2]<>"T"): %(sousarbre,symbole)
+ _nbrleaf:=_nbrleaf+1;
+ newHuffmanLeaf.scantokens("leaf"&decimal(
+ _nbrleaf)&"_"&decimal
+ _huffmanTreeNbr)(_chtab[2])(decimal
+ roundd(_frtab[2],2));
+ _tmpsum:=_frtab[1]+_frtab[2];
+ newHuffmanNode.scantokens("node"&decimal _nbrnode&"_"&decimal _huffmanTreeNbr)(decimal
+ roundd(_tmpsum,2));
+ if(_nbr=2): % dernier arbre, on nomme avec @#
+ newHuffmanBinTree@#(scantokens("node"&decimal
+ _nbrnode&"_"&decimal
+ _huffmanTreeNbr))(scantokens(_chtab[1]),scantokens("leaf"&decimal(
+ _nbrleaf)&"_"&decimal
+ _huffmanTreeNbr)) options;
+ else:
+ newHuffmanBinTree.scantokens("Tree"&decimal
+ _nbrnode&"_"&decimal _huffmanTreeNbr)(scantokens("node"&decimal
+ _nbrnode&"_"&decimal
+ _huffmanTreeNbr))(scantokens(_chtab[1]),scantokens("leaf"&decimal(
+ _nbrleaf)&"_"&decimal
+ _huffmanTreeNbr)) options;
+ fi
+ else: % (sousarbre, sousarbre)
+ _tmpsum:=_frtab[1]+_frtab[2];
+ newHuffmanNode.scantokens("node"&decimal _nbrnode&"_"&decimal _huffmanTreeNbr)(decimal roundd(_tmpsum,2));
+ if(_nbr=2): % dernier arbre, on nomme avec @#
+ newHuffmanBinTree@#(scantokens("node"&decimal
+ _nbrnode&"_"&decimal
+ _huffmanTreeNbr))(scantokens(_chtab[1]),scantokens(_chtab[2]))
+ options;
+ else:
+ newHuffmanBinTree.scantokens("Tree"&decimal
+ _nbrnode&"_"&decimal
+ _huffmanTreeNbr)(scantokens("node"&decimal
+ _nbrnode&"_"&decimal
+ _huffmanTreeNbr))(scantokens(_chtab[1]),scantokens(_chtab[2]))
+ options;
+ fi
+ fi
+ fi
+ % on indique dans la première case le nom de l’arbre créé
+ _chtab[1]:="Tree"&decimal _nbrnode&"_"&decimal _huffmanTreeNbr;
+ % et sa valeur
+ _frtab[1]:=_frtab[1]+_frtab[2];
+ _nbrnode:=_nbrnode+1;
+ else:
+ % on décale toutes les autres cases d’un vers la gauche
+ _chtab[i]:=_chtab[i+1];
+ _frtab[i]:=_frtab[i+1];
+ fi
+ endfor
+ _nbr:=_nbr-1;
+ endfor;
+enddef;
+
+
+
+