Debian Codegraph @

texmf-dist/tex/plain/pdftoolbox/pdfData/ptb-mergesort.tex

raw
1 \input ptb-utils
2
3 \_checkloaded{mergesort}
4
5 \input pdfData/ptb-arrays
6
7 \def\splitmarray#1#2#3{%
8 \edef\_arr_half_len{\the\numexpr\csname marr@#1@len\endcsname / 2}%
9 \_arr_cnt=0 %
10 \createmarray{#2}%
11 \createmarray{#3}%
12 \loop\ifnum\_arr_cnt < \csname marr@#1@len\endcsname %
13 \ifnum\_arr_cnt < \_arr_half_len%
14 \_xp\_xp\_xp\_rappendmarray\_xp\_xp\_xp{\csname marr@#1@idx@\the\_arr_cnt\endcsname}{#2}%
15 \else%
16 \_xp\_xp\_xp\_rappendmarray\_xp\_xp\_xp{\csname marr@#1@idx@\the\_arr_cnt\endcsname}{#3}%
17 \fi%
18 \advance\_arr_cnt by 1 %
19 \repeat%
20 }
21
22
23 \def\findmin#1#2#3{%
24 \let\_regA=\_nul%
25 \let#3=\_nul%
26 \_arr_cnt=0 %
27 \def\_arr_index##1{%
28 \ifx\_regA\_nul%
29 \def\_regA{##1}%
30 \def#3{0}%
31 \else%
32 \_xp#2\_xp{\_regA}{##1}%
33 \unless\ifnum\_return_val=-1 %
34 \def\_regA{##1}%
35 \_xp\def\_xp#3\_xp{\the\_arr_cnt}%
36 \fi%
37 \fi%
38 \advance\_arr_cnt by 1 %
39 }%
40 \csname arr@#1\endcsname%
41 }
42
43 \def\_sortarr#1#2#3{%
44 \findmin{#1}{#3}\_regB%
45 \unless\ifx\_regB\_nul%
46 \removearray{#1}\_regB\_regC%
47 \_xp\_rappendarray\_xp{\_regC}{#2}%
48 \_afterfi{\_sortarr{#1}{#2}{#3}}%
49 \fi%
50 }
51
52 \def\sortarr#1#2#3{%
53 \copyarray{#1}{_orig}%
54 \createarray{#2}%
55 \_sortarr{_orig}{#2}{#3}%
56 }
57
58 \def\merge#1#2#3#4{%
59 \createmarray{#1}%
60 \edef\_min_len{\min{\csname marr@#2@len\endcsname}{\csname marr@#3@len\endcsname}}%
61 \_arr_cnt=0 %
62 \_arr_cntB=0 %
63 \def\_temp{\appendmarray{#1}}
64 %
65 \loop%
66 \let\_tempA=\_nul%
67 \ifnum\_arr_cnt < \csname marr@#2@len\endcsname
68 \ifnum\_arr_cntB < \csname marr@#3@len\endcsname
69 \_xp\let\_xp\_first\csname marr@#2@idx@\the\_arr_cnt\endcsname%
70 \_xp\let\_xp\_second\csname marr@#3@idx@\the\_arr_cntB\endcsname%
71 #4\_first\_second%
72 \ifnum\_return_val=-1 %
73 \_xp\_temp\_xp{\_first}%
74 \advance\_arr_cnt by 1 %
75 \else%
76 \_xp\_temp\_xp{\_second}%
77 \advance\_arr_cntB by 1 %
78 \fi%
79 \let\_tempA=\empty%
80 \fi\fi
81 \ifx\_tempA\empty%
82 \repeat%
83 %
84 \loop%
85 \ifnum\_arr_cnt < \csname marr@#2@len\endcsname %
86 \_xp\let\_xp\_first\csname marr@#2@idx@\the\_arr_cnt\endcsname%
87 \_xp\_temp\_xp{\_first}%
88 \advance\_arr_cnt by 1 %
89 \repeat%
90 \loop%
91 \ifnum\_arr_cntB < \csname marr@#3@len\endcsname %
92 \_xp\let\_xp\_first\csname marr@#3@idx@\the\_arr_cntB\endcsname%
93 \_xp\_temp\_xp{\_first}%
94 \advance\_arr_cntB by 1 %
95 \repeat%
96 }
97
98 \def\_mergesort#1#2{%
99 \ifnum\csname marr@#1@len\endcsname>1 %
100 \_afterfi{%
101 \beginscope%
102 \def\_regA{#1}%
103 \def\_regB{_m1}%
104 \def\_regC{_m2}%
105 \unless\ifx\_regA\_regB%
106 \localizemarray{_m1}%
107 \fi
108 \unless\ifx\_regA\_regC%
109 \localizemarray{_m2}%
110 \fi
111 \copymarray{#1}{_m}%
112 \splitmarray{_m}{_m1}{_m2}%
113 \_mergesort{_m1}{#2}%
114 \_mergesort{_m2}{#2}%
115 \merge{_m}{_m1}{_m2}{#2}%
116 \copymarray{_m}{#1}%
117 \endscope%
118 }%
119 \fi%
120 }
121
122 \def\mergesort#1#2{%
123 \convertarray{#1}{_orig}%
124 \createmarray{_m1}%
125 \createmarray{_m2}%
126 \_mergesort{_orig}{#2}%
127 \convertmarray{_orig}{#1}%
128 }
129
130 \def\_cmp_num#1#2{%
131 \edef\_return_val{\ifnum#1=#2 0\else\ifnum #1<#2 -1\else 1\fi\fi}
132 }
133
134 \def\_cmp_str#1#2{%
135 \edef\_return_val{\pdfstrcmp{#1}{#2}}
136 }
137