diff options
Diffstat (limited to 'Master/texmf-dist')
-rw-r--r-- | Master/texmf-dist/doc/metapost/huffman/LICENSE | 11 | ||||
-rw-r--r-- | Master/texmf-dist/doc/metapost/huffman/README.md | 58 | ||||
-rw-r--r-- | Master/texmf-dist/doc/metapost/huffman/ctan.bib | 25 | ||||
-rw-r--r-- | Master/texmf-dist/doc/metapost/huffman/fond.pdf | bin | 0 -> 1309 bytes | |||
-rw-r--r-- | Master/texmf-dist/doc/metapost/huffman/huffman-doc-en.pdf | bin | 0 -> 123346 bytes | |||
-rw-r--r-- | Master/texmf-dist/doc/metapost/huffman/huffman-doc-en.tex | 480 | ||||
-rw-r--r-- | Master/texmf-dist/doc/metapost/huffman/huffman-preamble.tex | 174 | ||||
-rw-r--r-- | Master/texmf-dist/metapost/huffman/huffman.mp | 278 |
8 files changed, 1026 insertions, 0 deletions
diff --git a/Master/texmf-dist/doc/metapost/huffman/LICENSE b/Master/texmf-dist/doc/metapost/huffman/LICENSE new file mode 100644 index 00000000000..130ede1e510 --- /dev/null +++ b/Master/texmf-dist/doc/metapost/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/Master/texmf-dist/doc/metapost/huffman/README.md b/Master/texmf-dist/doc/metapost/huffman/README.md new file mode 100644 index 00000000000..886ad58c6c9 --- /dev/null +++ b/Master/texmf-dist/doc/metapost/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/Master/texmf-dist/doc/metapost/huffman/ctan.bib b/Master/texmf-dist/doc/metapost/huffman/ctan.bib new file mode 100644 index 00000000000..3ff880adba5 --- /dev/null +++ b/Master/texmf-dist/doc/metapost/huffman/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/Master/texmf-dist/doc/metapost/huffman/fond.pdf b/Master/texmf-dist/doc/metapost/huffman/fond.pdf Binary files differnew file mode 100644 index 00000000000..22218152ccb --- /dev/null +++ b/Master/texmf-dist/doc/metapost/huffman/fond.pdf diff --git a/Master/texmf-dist/doc/metapost/huffman/huffman-doc-en.pdf b/Master/texmf-dist/doc/metapost/huffman/huffman-doc-en.pdf Binary files differnew file mode 100644 index 00000000000..283ba984fc1 --- /dev/null +++ b/Master/texmf-dist/doc/metapost/huffman/huffman-doc-en.pdf diff --git a/Master/texmf-dist/doc/metapost/huffman/huffman-doc-en.tex b/Master/texmf-dist/doc/metapost/huffman/huffman-doc-en.tex new file mode 100644 index 00000000000..b6d1a42cb33 --- /dev/null +++ b/Master/texmf-dist/doc/metapost/huffman/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/Master/texmf-dist/doc/metapost/huffman/huffman-preamble.tex b/Master/texmf-dist/doc/metapost/huffman/huffman-preamble.tex new file mode 100644 index 00000000000..d264ecb4627 --- /dev/null +++ b/Master/texmf-dist/doc/metapost/huffman/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/Master/texmf-dist/metapost/huffman/huffman.mp b/Master/texmf-dist/metapost/huffman/huffman.mp new file mode 100644 index 00000000000..92b3020fb44 --- /dev/null +++ b/Master/texmf-dist/metapost/huffman/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; + + + + |