在 LaTeX 中写排序宏命令对 TOKEN 排序

pop-sci
, ,

不管你信不信， LaTeX 的宏系统是可以用来排序的。这一篇博文会讲述如何在 LaTeX 里面来进行对 token 的排序。

简介

起因是想在一个论文中对交叉引用的某个东西排序。然后就通过搜索引擎找到了这个在 Stack Exchange 上的 回答。最后根据这个回答改了我宏包中的一些代码，使得交叉引用某个东西的时候，会根据序号进行排序。

知识点

这个回答中对于排序的设计完全是基于 LaTeX/TeX 宏系统的。但是我目前对于这个宏系统的了解也不多。尽管如此，我还是会尽量解释清楚的。

最重要的是类似递归的思想，毕竟是宏系统，通过类似递归的思想，让待排序的 Token 在展开的时候在不同的“队列”中“移动”，然后反复比较一遍遍挑出最小的（或者最大的，这个看根据比较函数确定）。

原理分析

首先先贴一下回答中作者贴上去的部分代码（排序的核心部分）。如果实在看不懂的话，先看我的总结部分的内容，然后再看我的分析，可能就清除一下了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
% #1 - comparator
% #2 - token list to sort
\newcommand\sort[2]{%
    \ifstrempty{#2}
    {}% else
    {%
        \sort@begin#1{}#2\sort@s\sort@begin
    }%
}

% helpers
\def\sort@s{\sort@s}
\def\ifsort@s#1{%
    \ifx\sort@s#1%
        \expandafter\@firstoftwo
    \else
        \expandafter\@secondoftwo
    \fi
}

% #1 - comparator
% #2 - tokens processed so far
% #3 - smallest token so far
% #4 - rest of the list
\def\sort@begin#1#2#3#4\sort@begin{%
    \ifsort@s{#4}
    {%
        \sortend{#3}%
        \sort#1{#2}%
    }% else
    {%
        \sort@go#1{#2}{#3}#4\sort@go
    }%
}

% #1 - comparator
% #2 - tokens processed so far
% #3 - smallest token so far
% #4 - token under consideration
% #5 - rest of the list
\def\sort@go#1#2#3#4#5\sort@go{%
        #1{#3}{#4}{\sort@output#1{#2}{#5}}%
}

% #1 - comparator
% #2 - tokens processed so far
% #3 - rest of the list
% #4 - smaller of the two tokens
% #5 - larger of the two tokens
\def\sort@output#1#2#3#4#5{%
    \ifsort@s{#3}
    {%
        \sortoutput{#4}%
        \sort#1{#2{#5}}%
    }% else
    {%
        \sort@begin#1{#2{#5}}{#4}#3\sort@begin
    }%
}

\def\sort@numcmp#1#2#3{%
    \ifnumcomp{#1}<{#2}
    {#3{#1}{#2}}% else
    {#3{#2}{#1}}%
}
...

\newcommand*\sortoutput[1]{#1, }
\newcommand*\sortend[1]{#1.}

入口 \sort

首先是入口函数 \sort，入口函数接收两个参数： 一个是“比较”的宏命令，另一个是待排序的 token “们”。然后输入的参数被传送到了另一个 宏命令 \sort@begin 中。

要说明的是 \sort@begin 接收 “5” 个 token 作为输入分别是输入参数 #1，空的 token {}，输入参数 #2，自定义的“终止” token \sort@s，与 \sort@begin 宏命令自己。

Token \sort@begin

\sort@begin 宏命令只做了两件事情，判断了一下第四个输入的参数是不是 \sort@s，宏命令 \ifsort@s 就是用来判断的。

如果第四个参数是 \sort@s 的时候，就意味着排序已经执行完了，会执行 \sortend 与 \sort 来“收尾”。但是实际上来说 再次展开 \sort 是开启了对没有排序的内容进行处理，但是你懂的。而\sortend 是一个自定义的宏命令，只是用来处理排序的结果的，直接写成 #3 也是可以的。

如果第四个参数不是 \sort@s 的话，则是会去展开 \sort@go 宏命令。

Token \sort@go

这个 Token 是实际负责作比较的， \sort@go Token一共接收三个，不，准确是六个输入的的 token。第一个输入的 Token是负责比较的。第二个 Token 是可以理解为一种列表，是所有处理过的要排序 Token。

负责比较的 Token 定义应该是类似 \sort@numcmp 定义的。这个 Token 要负责解决真正的比较过程（比较 #3 与 #4 这两个输入） ，然后处理 #3、#4 与 {\sort@output#1{#2}{#5}} 这三个 Token 之间的关系：是展开 \sort@output#1{#2}{#5{#3}{#4} 还是展开 \sort@output#1{#2}{#5}{#4}{#3}。

Token \sort@output

这个 Token 是负责输出的，因为 LaTeX 本身是一种宏系统，排版用的，所以这个代码就是为了解决输出内容排版的，所以就是为了输出。

输出的条件是 #3 是否是 Token \sort@s，如果是的话，那就意味着一次扫描已经完成了，从所有要排序的 Token 中 找出最小的（或者是最大的，这个比较由 #1 执行），然后继续在已经处理过的 Token 中找出下一个最小的。

如果不是 Token \sort@s，那就继续比较后面的没有比较的 Token。

总结

如果你看完了分析，尤其是 Token \sort@output 的，你是不是觉得有一种似曾相识的感觉？？对！这个算法就是利用 LaTeX 宏系统整出来的选择排序。 从 \sort@begin 到 \sort@output的反复的过程是在所有待排序的 Token 中找出来最小的一个，然后输出。剩下的 Token 就继续传递给 \sort 从头再来一遍排序。

Reference

[1] programming - How to sort an alphanumeric list - TeX - LaTeX Stack Exchange. Stackexchange. Retrieved July 30, 2020 from https://tex.stackexchange.com/questions/6988/how-to-sort-an-alphanumeric-list/7095#7095

我最后在论文中使用的代码

下面是我在论文中最终使用的代码。和原始的代码相比，除了 Token 的名字不同还没注释外，我这个代码还有一个特别之处，我的待排序的 token 是用逗号分割的 label，然后比较的结果是按照 label 对应的计数器的值排序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
\RequirePackage{etoolbox}

\def\data@sort#1#2{%
    \data@IfEmpty{#2}\relax\else%
        \data@sort@begin#1{}#2,\data@sort@s\data@sort@begin%
    \fi%
}

\def\data@sort@s{\data@sort@s}
\def\data@ifsort@s#1{\ifx\data@sort@s#1}
\def\data@show#1#2{\data@IfEmpty{#1}\ref{#2}\else\ref{#2},~\fi}

\def\data@sort@begin#1#2#3,#4\data@sort@begin{%
    \data@ifsort@s{#4}%
        \data@show{#2}{#3}%
        \data@sort#1{#2}%
    \else\data@sort@go#1{#2}{#3}#4\data@sort@go%
    \fi%
}

\def\data@sort@go#1#2#3#4,#5\data@sort@go{%
    #1{#3}{#4}{\data@sort@end#1{#2}{#5}}%
}

\def\data@sort@end#1#2#3#4#5{%
    \data@IfEmpty{#2}%
        \data@sort@begin#1{#5}{#4},#3\data@sort@begin%
    \else%
        \data@sort@begin#1{#2,#5}{#4},#3\data@sort@begin%
    \fi%
}

\def\data@num@inner#1#2#3{\ifx#1\relax 0\else\expandafter#2#1\fi}
\def\data@num#1{\expandafter\data@num@inner\csname r@#1\endcsname\@firstoffive{#1}}

\def\data@sort@numlt#1#2#3{%
    \ifnum\data@num{#1}<\data@num{#2}%
        #3{#1}{#2}%
    \else%
        #3{#2}{#1}%
    \fi%
}

\newcommand{\idata}[1]{%
    \data@begin\data@sort\data@sort@numlt{#1}\data@end%
}