From 4239ff3d14b29560c7813a5856524b7226d60c32 Mon Sep 17 00:00:00 2001 From: Karl Berry Date: Thu, 2 Jul 2020 21:47:41 +0000 Subject: bubblesort (2jul20) git-svn-id: svn://tug.org/texlive/trunk@55733 c570f23f-e606-0410-a88d-b1316a301751 --- .../source/latex/bubblesort/bubblesort.dtx | 448 +++++++++++++++++++++ .../source/latex/bubblesort/bubblesort.ins | 39 ++ 2 files changed, 487 insertions(+) create mode 100644 Master/texmf-dist/source/latex/bubblesort/bubblesort.dtx create mode 100644 Master/texmf-dist/source/latex/bubblesort/bubblesort.ins (limited to 'Master/texmf-dist/source/latex') diff --git a/Master/texmf-dist/source/latex/bubblesort/bubblesort.dtx b/Master/texmf-dist/source/latex/bubblesort/bubblesort.dtx new file mode 100644 index 00000000000..a96fe27fb6d --- /dev/null +++ b/Master/texmf-dist/source/latex/bubblesort/bubblesort.dtx @@ -0,0 +1,448 @@ +% \iffalse meta-comment +% +% Copyright (C) 2019 by Laurence R Taylor +% ----------------------------------- +% +% This file 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. +% +% \fi +% +% \iffalse +% +%<*driver> +\documentclass{ltxdoc} +\usepackage{bubblesort} +\usepackage{graphicx} +\usepackage{hyperref} +\hypersetup{ + colorlinks=true, + linkcolor=blue, + filecolor=magenta, + urlcolor=cyan, +} +\DisableCrossrefs +\CodelineNumbered +\RecordChanges +\begin{document} +\DocInput{bubblesort.dtx} +\end{document} +% +% \fi +% +% \CheckSum{293} +% +% \CharacterTable +% {Upper-case \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z +% Lower-case \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z +% Digits \0\1\2\3\4\5\6\7\8\9 +% Exclamation \! Double quote \" Hash (number) \# +% Dollar \$ Percent \% Ampersand \& +% Acute accent \' Left paren \( Right paren \) +% Asterisk \* Plus \+ Comma \, +% Minus \- Point \. Solidus \/ +% Colon \: Semicolon \; Less than \< +% Equals \= Greater than \> Question mark \? +% Commercial at \@ Left bracket \[ Backslash \\ +% Right bracket \] Circumflex \^ Underscore \_ +% Grave accent \` Left brace \{ Vertical bar \| +% Right brace \} Tilde \~} +% +% +% \hfuzz=200pt +% \changes{v1.0}{?2019?/?07?/?17?}{Initial version} +% \title{bubblesort} +% \author{Laurence R Taylor} +% \date{2020/06/24} +% \maketitle +% \begin{abstract} +% This package is a \LaTeX\ port of the sorting function \href{https://en.wikipedia.org/wiki/Bubble_sort}{bubble sort}. +% Bubble sort is usually coded using arrays but it can be done without them and +% since \LaTeX\ does not support arrays natively, bubble sort seemed like a good routine to port. +% It's lack of speed is not really a problem with the data sizes likely to be encountered in most \LaTeX\ applications. +% +% The objects to be sorted are either a stack or a list. +% A \emph{stack} is a sequence of legal \TeX\ code items enclosed in brace pairs, \vskip0pt% +% \begin{center}|{|\emph{item 1}|}{|\emph{item 2}|}|\dots|{|\emph{item n}|}|\end{center} +% while a \emph{list} is a macro which expands to a stack. Fragile commands in an \emph{item} may not work as expected. +% To sort the items one needs a notion of when one \emph{item} is ``less than'' another. +% +% The macro |\bubblesort| does the bubble sort. It takes three arguments: |\bubblesort[#1]{#2}{#3}|. +% The optional argument is a comparator macro telling when one item is smaller than another. +% If empty it assumes the stack is a stack of integers or real numbers +% and sorts it using the usual $<$. Argument |#2| is the stack or list to be sorted and +% argument |#3| a macro which will contain the sorted list in increasing order. +% +% The only dependency is |etoolbox.sty|. +% \end{abstract} +% \section{Introduction} +% \makeatletter +% \newcounter{LineAA} +% \def\Label#1{\hypertarget{@bubblesort@ref#1}\relax\setcounter{LineAA}{\value{CodelineNo}}\stepcounter{LineAA} +% {\immediate\write\@auxout{\string\gdef\string\@bubblesort@ref#1{\number\value{LineAA}}}}} +% \def\codeRef#1{\ifcsdef{@bubblesort@ref#1}{\hyperlink{@bubblesort@ref#1}{\csname @bubblesort@ref#1\endcsname}}{\textbf{??}}} +% \def\LabelLine#1{\Label{#1}\nointerlineskip\begin{macrocode}} +% \newbox\ff\setbox\ff=\hbox{\scalebox{0.75}{\hbox{\Large\tt doublebubblesort}}} +% \newbox\fff\setbox\fff=\hbox{\scalebox{0.75}{\hbox{\Large\tt doublebubblesortB}}} +% \newbox\mm\setbox\mm=\hbox{\rotatebox{114}{\vrule depth0.8pt height 0pt width 9pt}} +% \makeatother +% \newbox\ff\setbox\ff=\hbox{\scalebox{0.75}{\hbox{\Large\tt doublebubblesort}}} +% \newbox\fff\setbox\fff=\hbox{\scalebox{0.75}{\hbox{\Large\tt doublebubblesortB}}} +% \newbox\mm\setbox\mm=\hbox{\rotatebox{114}{\vrule depth0.8pt height 0pt width 9pt}} +% There are two macros provided which implement the standard bubble sort algorithms +% on stacks or lists. See section \ref{SandL} for a discussion of stacks or lists. +% \subsection{\texorpdfstring{\copy\mm\tt bubblesort}{bubblesort}} +% |\bubblesort[#1]{#2}{#3}|: Argument |#2| is the stack or list to be sorted. Argument |#3| contains the sorted list +% after evaluation. Argument |#2| can be the same as argument |#3|. Argument |#3| can also be blank in which +% case the output string is inserted into the input stream. +% Optional argument |#1| is a comparator macro. +% \subsubsection{Comparator macros} +% A comparator macro can have any legal \TeX\ name. It must have two arguments. +% When in use the comparator macro is evaluated on consecutive pairs of elements in the stack. +% If argument |#2| is ``smaller'' than argument |#1| the macro sets |\bubblesortflag| to |1| and sets it +% to |-1| otherwise. +% Two examples are supplied: |\realSort| on line \codeRef{realSort}\ of the code below and +% |\alphSort| on line \codeRef{alphSort}. +% +% \subsection{\texorpdfstring{\copy\mm\tt doublebubblesort}{bubblesort}}|\doublebubblesort[#1]{#2}{#3}{#4}{#5}|: +% +% The macro |\doublebubblesort| sorts two stack/lists. Arguments |#1|, |#2| and |#3| are identical to the corresponding +% arguments for |\bubblesort|. Argument |#4| is another stack or list of the same length or longer than stack/list |#2|. +% When expanded |\doublebubblesort| sorts |#2| just the same as |\bubblesort| would. However, every move made on +% stack |#2| is also done on stack |#4|. Argument |#5| is the name for the output of the result of this ``sort'' on |#4|. +% As usual |#5| can be blank or |#4| and |#5| can be the same macro. |#3| and |#5| can also be the same macro, in +% which case it contains the result of the sort on argument |#4|, \emph{except} if both |#3| and |#5| are blank, |#3| +% is put into the input stream followed by |#5|. +% +% An example to keep in mind is the following. One way to mimic a hash in \LaTeX\ is to have a list of keys and a second +% list of values with the value associated to a key being determined by position in the values list. If the key list is sorted it +% will be necessary to do the same interchanges on the values list to maintain the correspondence. +% See subsection \ref{permute} for another example using |\doublebubblsort|. +% \section{Stacks and lists}\label{SandL} +% The lists here closely resemble Knuth's lists in the +% \href{http://www.ctex.org/documents/shredder/src/texbook.pdf}{\TeX book}, page 378, Appendix D, +% except they lack Knuth's initial |\\| prepended to each item. As discussed by Knuth, the |\\| can be used to process +% each item in the list. +% Sort algorithms require knowledge of pairs of items from the list +% so macros which only know about one item are not needed. +% +% +% Other implementations of lists use a reserved character as a separator. +% Separators like commas or semicolons or whatever have the drawback that then the separator can not be used in the item text +% without additional coding. +% +% \TeX's brace-pair mechanism is quite robust. It handles nested brace pairs just fine. One word of \textcolor{red}{warning}: +% an empty brace pair |{}| is used as an end of list indicator. They are added to the stack/list arguments +% when needed and are not present at the end of lists produced by macros in this package so they rarely trouble the user. +% It does mean that +% \textcolor{red}{there can be no empty (or even |{white space}|) brace pairs in the input list.} +% Given how \TeX\ discards white space, |{white space}| is probably not what is wanted anyway. Using |{{white space}}| will probably +% yield results closer to what was intended and this works. +% \section{Examples} +% Here are a few examples if things that can be done with sorts. +% \subsection{\texorpdfstring{\copy\mm\tt refs}{refs}} +% Given a stack of references defined from |\label| such as |{ref 1}{ref 2}|\dots|{ref n}| which expand to integers or real numbers +% try to define +% \begin{center} +% \color{red}|\def\refs#1{\bubblesort[\refSort]{#1}{\answers}}|\hskip1in\null \\where |\refSort#1#2{\realSort{\ref{#1}}{\ref{#2}}}|. \color{black} +% \end{center} +% The above does not work because |\ref| is protected and does not expand to just the number. +% Instead, the package |refcount.sty| supplies |\getrefnumber| which is expandable and does what is needed. +% Add |\usepackage{refcount}| to the preamble and define +% \begin{verbatim} +% \def\refSort#1#2{% +% \edef\aa{\getrefnumber{#1} pt}\edef\bb{\getrefnumber{#2} pt}% +% \ifdimless{\bb}{\aa}{\bubblesortflag=1}{\bubblesortflag=-1}% +% } +% \end{verbatim} +% Then|\def\refs#1{\bubblesort[\refSort]{#1}{\ans}}| sorts the numbers in increasing order and puts the answer in |\ans|. +% +% \subsection{Use {\texorpdfstring{\copy\mm\tt refs}{refs}}\ twice} +% Since |\bubblesort| is a stable sorting algorithm, it can be usefully used more than once on the same data. +% Suppose |\refSort| is defined as above and there is a list |\def\LL{{ref 1}{ref 2}|\dots|{ref n}}|. +% Then |\bubblesort[\refSort]{\LL}{\LL}| sorts the numbers in increasing order. +% +% But some of them may be from definitions, others from theorems, or lemmas, etc. +% Suppose |\refName#1| is a macro such that |\refName{ref k}| returns |Definition|, |Theorem|, |Lemma|, etc.. +% Then +% \begin{center} +% |\bubblesort[\refSort]{\LL}{\LL} \bubblesort[\alphSort]{\LL}{\LL}| +% \end{center} +% \noindent returns +% |\def\LL{{ref k_1}{ref k_2}|\dots|{ref k_n}}| +% where the first set of references are |Definition|'s, the second set of references are |Lemma|'s and +% the third set of references are |Theorem|'s. +% The set of numbers for the |Definition|'s are increasing, +% the set of numbers for the |Lemma|'s are increasing and +% the set of numbers for the |Theorem|'s are increasing. +% With more complicated coding, the names can be added and the lists compactified to get something line +% |Theorems 1-3 and 5, Lemma 9 and Definitions 6, 8 and 12|. +% +% \subsection{\texorpdfstring{\copy\mm\tt permute}{permute}}\label{permute} +% Use |\doublebubblesort| to apply a permutation to a stack/list. +% A \emph{permutation} is an ordered stack/list of symbols which also has a natural order. +% Popular symbol sets are positive integers and lowercase letters. The comparator macro needs +% to sort a list of symbols with no repetitions back to its natural order. +% A permutation $\pi$ can be given by listing the values of $\pi$ when applied to the symbols +% in their natural order. For example $\pi$|={{5}{1}{2}{3}{4}}| means $\pi$|(1)=5|, $\pi$|(2)=1|, $\pi$|(3)=2|, $\pi$|(4)=3|, $\pi$|(5)=4|. +% +% At the end of line 2 of the displayed code below, |\ott| contains the symbols in their natural order +% so |\permute| does not need to be told the symbols in advance. +% At the end of line 3, |\ott| contains the inverse to the original permutation. +% At the end of line 4, |#4| contains the permuted version of |#3|. +% +% \null\hskip0.13\textwidth \vbox{\begin{verbatim} +% \newcommand{\permute}[4][\realSort]{% +% \bubblesort[#1]{#2}{\ott}% +% \doublebubblesort[#1]{#2}{\ott}{\ott}{\ott}% +% \doublebubblesort[#1]{\ott}{\ott}{#3}{#4}% +% } +% \end{verbatim}} +% If |\def\LL{{${a_1}$}{${a_2}$}{${a_3}$}{${a_4}$}{${a_5}$}}| then\\ +% |\permute{{5}{1}{2}{3}{4}}{\LL}{}| yields +% +% {${\tt a}_5$}\, {${\tt a}_1$}\, {${\tt a}_2$}\, {${\tt a}_3$}\, {${\tt a}_4$}\ , which is +% {${\tt a}_{\pi(1)}$}\, {${\tt a}_{\pi(2)}$}\, {${\tt a}_{\pi(3)}$}\, {${\tt a}_{\pi(4)}$}\, {${\tt a}_{\pi(5)}$}\ as desired. +% \bigskip +% +% |\permute| can also be used to multiply permutations: +% \begin{itemize} +% \item |\permute{\pi_1}{\pi_2}{\ans}| yields |\pi_2|$\circ$|\pi_1| +% \item |\permute{\pi_2}{\pi_1}{\ans}| yields |\pi_1|$\circ$|\pi_2|. +% \end{itemize} +% +% \section{Implementation}\label{implementation} +% Line numbers refer to the line numbers printed next to the code beginning with |\NeedsTeXFormat| \hyperlink{NeedsTeXFormat}{here}. +% There are only four public macros, |\bubblesort| on line \codeRef{bubblesort} +% and |\doublebubblesort| on line \codeRef{doublebubblesort} and comparator macros |\realSort| on line \codeRef{realSort}\ and +% |\alphSort| on line \codeRef{alphSort}. +% Private macros begin with |\@bubblesort@| to minimize the chance of name conflicts with other packages. +% This makes reading the code somewhat tedious so +% in the descriptions of the code below, the initial |\@bubblesort@| will be replaced by |*|. +% +% \subsection{\texorpdfstring{\copy\mm\tt bubblesort}{bubblesort}} +% |\bubblesort[#1]{#2}{#3}|: +% The implementation of |\bubblesort| begins by defining an empty |*rightList| and putting the stack/list to be sorted, |#2|, into |*workingList|. +% Note |#2| is now safe - unless |#2| equals |#3|, |#2| will never change. +% Then |\bubblesort| removes the leftmost item in |*workingList| +% and saves it in |*testItem|. Then it moves on to |\@bubblesort@S| which does the recursion. +% +% First, |\bubblesort@S| (line \codeRef{bubblesortS}) sets an |etoolbox| boolean, |did a flip|, to false and sets |*leftList| to empty. +% Then the macro removes the leftmost element in |*workingList| and saves it in |*nextItem|. +% Then it enters the |while| loop (line \codeRef{while}). +% The exit condition is that |*nextItem| is empty. +% Then the comparator macro is evaluated on the ordered pair $\bigl($|*testItem| , |*nextItem|$\bigr)$. +% The smaller of the pair is append to |*leftList| on the right and the larger is set to |*testItem|. +% The loop continues until |*workingList| is empty. At this point |*testItem| contains the largest element in the +% original |*workingList| and it is added to |*rightList| at the left end. +% Hence |*leftList| followed by |*rightList| is the original list. +% Next |*leftList| is put into |*workingList| and then the leftmost element is removed and put into |*testItem|. +% Finally the |while| loop is reentered. +% +% After $k$ iterations of the |while| loop, |*rightList| has $k$ elements which are the $k$ largest elements in the original list in increasing order. +% When the boolean |did a flip| is false, |*leftList| is also ordered so |*leftList| followed by |*rightList| is the original list sorted +% and the |while| loop exits. +% The sorted list and macro |#3| from |\bubblesort| are passed on to |\@bubblesort@output| which outputs the list as requested +% and |\bubblesort| is finished. +% +% \noindent\textbf{Remark:} The reader who has worked through the discussion above will have noticed that this implementation of bubble sort +% uses about four times the storage as the |C| version which sorts the array in place. +% Stacks used in \LaTeX, are probably small enough that this is not a problem. +% +% Sorting a thousand item list of integers in reverse order (which is the worse case scenario) took less than sixty-five seconds running +% |TexShop| |4.44| on a Mac 2013 Powerbook using timing code from +% \href{https://tex.stackexchange.com/questions/456316/what-is-the-latex-equivalent-of-context-testfeatureonce-to-benchmark-performanc/456322#456322}{tex.stackexchange}. It put no strain on \TeX's memory allocations. +% +% \bigskip +% \subsection{\texorpdfstring{\copy\mm\tt doublebubblesort}{doublebubblesort}} +% |\doublebubblesort[#1]{#2}{#3}{#4}{#5}|: +% The |\doublebubblesort| (line \codeRef{doublebubblesort}), |\@doublebubblesort@S| (line \codeRef{doublebubblesortS}), +% macros work much like |\bubblesort|, |\@bubblesort@S|. +% The code in the |double|'d version contains the identical code from |\bubblesort|, |\@bubblesort@S| except that |A| is added +% to the end of each of the internal macros. There is also a parallel copy of macros with |B| added and everything done with the +% |A| variables is mimicked with the |B| variables. +% +% \bigskip +% \subsection{The remaining macros} +% The macro |\@bubblesort@output#1#2| (line \codeRef{output}) is just to shorten the code +% since there are three places a stack or a list is output (lines \codeRef{outputA}, \codeRef{outputB} and \codeRef{outputC}). +% +% The macro |\@bubblesort@EoS| is the End-of-Stack indicator. +% +% The remaining macros do the removing items from a list and inserting items at either end of a list. +% The shift macro is \\ +% \null\hskip1in|\@bubblesort@shift#1#2\@bubblesort@EoS#3#4| (line \codeRef{shiftM})\\ +% which is used as \\|\expandafter\@bubblesort@shift{stack/list}\@bubblesort@EoS{\itemA}{\itemB}| which +% puts the leftmost item in the stack/list into |\itemA| and the rest of the stack/list into |\itemB|. +% +% The macros |\@bubblesort@rightappendItem| (line \codeRef{rAi}) \\and +% |\@bubblesort@lefttappendItem| (line \codeRef{lAi}) are identical to Knuth's +% |\rightappenditem| and |\leftappenditem| except that there are no prepended |\\|'s. +% +% \StopEventually{} +% \color{white} +% \setcounter{CodelineNo}{15} +% \begin{macro}{blank}\color{black}\textbf{Start of code:} +% \hypertarget{NeedsTeXFormat}{} +% The rest of the file from the end of this paragraph onward is a copy of the file +% generated by \TeX ing the |bubblesort.ins| file except that the standard set of comments +% at the start of an |ins| generated file are omitted. And of course the line numbers on the left here are +% not present in the |\bubblesort.sty| file. +% The comments portion takes 15 lines. +% Most editors show line numbers and allow line number navigation so it has been arranged that +% the line numbers in the typeset |bubblesort.dtx| file below match the line numbers +% in the |ins|-generated |bubblesort.sty| file. +% \begin{macrocode} +\NeedsTeXFormat{LaTeX2e}[2005/12/01] +\ProvidesPackage{bubblesort} + [2020/07/01 v1.0 implements a bubble sort] + +\RequirePackage{etoolbox} + +\makeatletter + +\newcount\bubblesortflag +\newbool{did a flip} +\def\@bubblesort@EoS{}% End-of-Stack indicator + +% \end{macrocode} \LabelLine{realSort} +\def\realSort#1#2{% +\ifdimless{#2 pt}{#1 pt}{\bubblesortflag=1}{\bubblesortflag=-1}} +% \end{macrocode} \LabelLine{alphSort} +\def\alphSort#1#2{\ifnumequal{\pdfstrcmp{#1}{#2}}{1}% +{\bubblesortflag=1}{\bubblesortflag=-1}} +% \end{macrocode} \LabelLine{bubblesort} +\newcommand{\bubblesort}[3][\realSort]{% +%% #1 comparator macro, #2 input stack/list, #3 answer list: #2=#3 OK +\def\@bubblesort@rightList{}% +\expandafter\@bubblesort@shiftOne#2{}{}{}\@bubblesort@EoS{% +\@bubblesort@testItem}{\@bubblesort@workingList}% +\expandafter\@bubblesort@S{#3}{#1}% +} +% \end{macrocode} \LabelLine{bubblesortS} +\def\@bubblesort@S#1#2{% #1 is name for answer --- #2 is comparator macro +\boolfalse{did a flip}\def\@bubblesort@leftList{}% +\expandafter\@bubblesort@shiftOne\@bubblesort@workingList{}{}\@bubblesort@EoS{% +\@bubblesort@nextItem}{\@bubblesort@workingList}% +% \end{macrocode} \Label{while}\nointerlineskip\begin{macrocode} +\whileboolexpr{not test{\ifdefvoid{\@bubblesort@nextItem}}}{% +#2{\@bubblesort@testItem}{\@bubblesort@nextItem}\relax% +\ifnumequal{\bubblesortflag}{1}{% flip +\booltrue{did a flip}% +\expandafter\@bubblesort@rightappendItem\expandafter{\@bubblesort@nextItem}% +\to\@bubblesort@leftList% +}{% +\expandafter\@bubblesort@rightappendItem\expandafter{\@bubblesort@testItem}% +\to\@bubblesort@leftList% +\expandafter\def\expandafter\@bubblesort@testItem\expandafter{\@bubblesort@nextItem}% +}% +\expandafter\@bubblesort@shiftOne\@bubblesort@workingList\@bubblesort@EoS{% +\@bubblesort@nextItem}{\@bubblesort@workingList}% +}% +\expandafter\leftappendItem\expandafter{\@bubblesort@testItem}\to\@bubblesort@rightList% +\ifbool{did a flip}{% +\expandafter\def\expandafter\@bubblesort@workingList\expandafter% +{\@bubblesort@leftList{}{}{}}% +\expandafter\@bubblesort@shiftOne\@bubblesort@workingList\@bubblesort@EoS{% +\@bubblesort@testItem}{\@bubblesort@workingList}% +\def\@bubblesort@leftList{}% +\@bubblesort@S{#1}{#2}}% +% \end{macrocode} \Label{outputA}\nointerlineskip\begin{macrocode} +{\@bubblesort@output{#1}{\@bubblesort@leftList\@bubblesort@rightList}% +}} +% \end{macrocode} \Label{output}\nointerlineskip\begin{macrocode} +\def\@bubblesort@output#1#2{% #1 name of output list or empty --- #2 sorted stack +\ifstrempty{#1}% +{#2}{\expandafter\edef\expandafter#1\expandafter{#2}}% +} +% \end{macrocode} \Label{doublebubblesort}\nointerlineskip\begin{macrocode} +\newcommand{\doublebubblesort}[5][\realSort]{% +%% #1 comparator macro +%% #2 input stack/list --- #3 output for #2 stack/list; #2=#3 OK +%% #4 second stack/list --- #5 answer list for #4; #4=#5 OK +\def\@bubblesort@rightListA{}\def\@bubblesort@rightListB{}% +\expandafter\@bubblesort@shiftOne#2{}{}{}\@bubblesort@EoS{% +\@bubblesort@testItemA}{\@bubblesort@workingListA}% +\expandafter\@bubblesort@shiftOne#4{}{}{}\@bubblesort@EoS{% +\@bubblesort@testItemB}{\@bubblesort@workingListB}% +\expandafter\@doublebubblesort@S{#3}{#5}{#1}% +} +% \end{macrocode} \Label{doublebubblesortS}\nointerlineskip\begin{macrocode} +\def\@doublebubblesort@S#1#2#3{% +%% #1 output for sorted stack/list --- #2 output for ``sorted'' stack/list +%% #3 comparator macro +\boolfalse{did a flip}\def\@bubblesort@leftListA{}\def\@bubblesort@leftListB{}% +\expandafter\@bubblesort@shiftOne\@bubblesort@workingListA{}{}% +\@bubblesort@EoS{\@bubblesort@nextItemA}{\@bubblesort@workingListA}% +\expandafter\@bubblesort@shiftOne\@bubblesort@workingListB{}{}% +\@bubblesort@EoS{\@bubblesort@nextItemB}{\@bubblesort@workingListB}% +\whileboolexpr{not test{\ifdefvoid{\@bubblesort@nextItemA}}}{% +#3{\@bubblesort@testItemA}{\@bubblesort@nextItemA}\relax% +\ifnumequal{\bubblesortflag}{1}{% flip +\booltrue{did a flip}% +\expandafter\@bubblesort@rightappendItem\expandafter{% +\@bubblesort@nextItemA}\to\@bubblesort@leftListA% +\expandafter\@bubblesort@rightappendItem\expandafter{% +\@bubblesort@nextItemB}\to\@bubblesort@leftListB% +}{% +\expandafter\@bubblesort@rightappendItem\expandafter{% +\@bubblesort@testItemA}\to\@bubblesort@leftListA% +\expandafter\@bubblesort@rightappendItem\expandafter{% +\@bubblesort@testItemB}\to\@bubblesort@leftListB% +\expandafter\def\expandafter\@bubblesort@testItemA\expandafter{% +\@bubblesort@nextItemA}% +\expandafter\def\expandafter\@bubblesort@testItemB\expandafter{% +\@bubblesort@nextItemB}% +}% +\expandafter\@bubblesort@shiftOne\@bubblesort@workingListA\@bubblesort@EoS{% +\@bubblesort@nextItemA}{\@bubblesort@workingListA}% +\expandafter\@bubblesort@shiftOne\@bubblesort@workingListB\@bubblesort@EoS{% +\@bubblesort@nextItemB}{\@bubblesort@workingListB}% +}% +\expandafter\leftappendItem\expandafter{\@bubblesort@testItemA}\to% +\@bubblesort@rightListA% +\expandafter\leftappendItem\expandafter{\@bubblesort@testItemB}\to% +\@bubblesort@rightListB% +\ifbool{did a flip}{% +\expandafter\def\expandafter\@bubblesort@workingListA\expandafter{% +\@bubblesort@leftListA{}{}{}}% +\expandafter\def\expandafter\@bubblesort@workingListB\expandafter{% +\@bubblesort@leftListB{}{}{}}% +\expandafter\@bubblesort@shiftOne\@bubblesort@workingListA\@bubblesort@EoS{% +\@bubblesort@testItemA}{\@bubblesort@workingListA}% +\expandafter\@bubblesort@shiftOne\@bubblesort@workingListB\@bubblesort@EoS{% +\@bubblesort@testItemB}{\@bubblesort@workingListB}% +\def\@bubblesort@leftListA{}% +\def\@bubblesort@leftListB{}% +\expandafter\@doublebubblesort@S{#1}{#2}{#3}}% +% \end{macrocode} \Label{outputB}\nointerlineskip\begin{macrocode} +{\@bubblesort@output{#1}{\@bubblesort@leftListA\@bubblesort@rightListA}% +% \end{macrocode} \Label{outputC}\nointerlineskip\begin{macrocode} +\@bubblesort@output{#2}{\@bubblesort@leftListB\@bubblesort@rightListB}}% +} + +% \end{macrocode} \Label{shiftM}\nointerlineskip\begin{macrocode} +\def\@bubblesort@shiftOne#1#2\@bubblesort@EoS#3#4{% +\expandafter\gdef\expandafter#3\expandafter{#1}% +\expandafter\gdef\expandafter#4\expandafter{#2}% +} + +\newtoks\ta\newtoks\tb +% \end{macrocode} \Label{rAi}\nointerlineskip\begin{macrocode} +\long\def\@bubblesort@rightappendItem#1\to#2{\ta={{#1}}\tb=\expandafter{#2}% +\edef#2{\the\tb\the\ta}} +% \end{macrocode} \Label{lAi}\nointerlineskip\begin{macrocode} +\long\def\leftappendItem#1\to#2{\ta={{#1}}\tb=\expandafter{#2}% +\edef#2{\the\ta\the\tb}} +\makeatother +\endinput +% \end{macrocode} +% \end{macro} +% \Finale diff --git a/Master/texmf-dist/source/latex/bubblesort/bubblesort.ins b/Master/texmf-dist/source/latex/bubblesort/bubblesort.ins new file mode 100644 index 00000000000..6f3f61ef1be --- /dev/null +++ b/Master/texmf-dist/source/latex/bubblesort/bubblesort.ins @@ -0,0 +1,39 @@ +%% http://texdoc.net/texmf-dist/doc/latex/dtxtut/dtxtut.pdf +%% Copyright (C) 2019 by Laurence R Taylor +%% +%% This file 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. +%% +\input docstrip.tex +\keepsilent +\usedir{} +\preamble +This is a generated file. Copyright (C) 2020 by Laurence R Taylor +This file 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. +\endpreamble +\askforoverwritefalse +\generate{\file{bubblesort.sty}{\from{bubblesort.dtx}{package}}} +\Msg{*********************************************************} +\Msg{*} +\Msg{* To finish the installation you have to move the} +\Msg{* following file into a directory searched by TeX:} +\Msg{*} +\Msg{* \space\space bubblesort.sty} +\Msg{*} +\Msg{* To produce the documentation run the file bubblesort.dtx} \Msg{* through LaTeX.} +\Msg{*} +\Msg{*********************************************************} +\endbatchfile \ No newline at end of file -- cgit v1.2.3