summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/vhistory/sets.sty
blob: b2f3d2b21b1c5f436cf2d8dbb58cd2c02f5c7ccc (plain)
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PACKAGE: sets                                                            %%
%% FILE: sets.sty                                                           %%
%%                                                                          %%
%% AUTHOR: Jochen Wertenauer                                                %%
%% VERSION: 1.3                                                             %%
%%                                                                          %%
%% LICENSE: This program may be distributed and/or modified under the       %%
%% conditions of the LaTeX Project Public License, either version 1.2       %%
%% 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.2 or later is part of all distributions of LaTeX           %%
%% version 1999/12/01 or later.                                             %%
%%                                                                          %%
%% This program consists of the file sets.sty (this file).                  %%
%%                                                                          %%
%%--------------------------------------------------------------------------%%
%% DESCRIPTION (see separate file for more information):                    %%
%%   This package allows basic usage of sets. A set has the structure:      %%
%%                   set    --> {contents}                                  %%
%%                 contents --> element(|element)*                          %%
%%                 contents --> \epsilon                                    %%
%%     A element can consist of strings and command tokens. Command tokens  %%
%%   will not be expanded before you call \listset.  Command tokens with    %%
%%   parameters (in {}) are not allowed, i.e. \textbf{Test} would result in %%
%%   lots of errors. Defining a macro \boldTest                             %%
%%              \newcommand{\boldTest}{\textbf{Test}}                       %%
%%   and using that macro would solve the problem.  Commands like like "A   %%
%%   work fine.  Of course an element cannot contain the character | (but   %%
%%   you can "hide" it in a command like \boldTest, too).                   %%
%%     Other forbidden elemente are the commands \endset and \empty.        %%
%%     In this package a set is normally sorted and contains no duplicates  %%
%%   unless you explicitly want it as it is by using \newsetsimple (but     %%
%%   several operations will return a sorted set without duplicates).       %%
%%     An empty set cannot be destinguished from a set that contains only   %%
%%   the an empty string, i.e. {} is an empty set.                          %%
%%                                                                          %%
%% INTERFACE:                                                               %%
%%   Constructors:                                                          %%
%%     \newset, \newsetsimple                                               %%
%%   Inspectors:                                                            %%
%%     \sizeofset, \listset, \iselementofset                                %%
%%   Modificators:                                                          %%
%%     \deleteduplicates, \sortset                                          %%
%%     \unionsets, \intersectsets, \minussets                               %%
%%   OTHER COMMANDS:                                                        %%
%%     \setseparator                                                        %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{sets}

%% Helper Methods ------------------------------------------------------------

\def \sets@xxpa{\expandafter\expandafter\expandafter}

\def \sets@empty{\empty}

%% Appends #1 to the definition of macro #2.
\def \sets@append #1\to#2{\expandafter \def \expandafter #2\expandafter{#2#1}}

%% Removes the first character of the content of #2 and stores the result in
%% #1. Note that \expandafter\expandafter\expandafter cannot be replaced by \sets@xxpa here!
\def \sets@gobblefirst #1#2{%
  \sets@xxpa \def \expandafter\expandafter\expandafter #1\expandafter\expandafter\expandafter {\expandafter\@gobble #2}}

%% Deletes everthing to the next occurance of > inludung the >.
\def \sets@erasetobrace #1>{}

%% A do-while construct based on the macro of Alois Kabelschacht.
%%
%% Syntax:
%% \loop
%%   ...
%%   \if ...
%% \repeat  
\def \sets@loop #1\repeat{%
  \def \iterate {#1\expandafter \iterate\fi}%
  \iterate \let\iterate\relax}

\long\def \sets@ReturnFi #1\fi{\fi #1}
\long\def \sets@ReturnII #1\fi\fi{\fi\fi #1}
\long\def \sets@ReturnIII #1\fi\fi\fi{\fi\fi\fi #1}

\long\def \sets@ReturnElseIII #1\else#2\fi\fi\fi{\fi\fi\fi #1}

\long\def \sets@Returntrue #1\fi{\fi \iftrue}
\long\def \sets@Returnfalse #1\fi{\fi \iffalse}

\newif \ifsets@less \newif \ifsets@greater

%% Compares to strings. Result will be in \ifgreater and \ifless.
%% #1 and #2 are compared as they are. There will be no expansion.
%% The comparison is based on the position of the symbols in the
%% ASCII table. Therefore the comparison is case sensitive (B<a).
%%
%% The macros are based on a sort algorithm by Klaus Lagally.
\def \sets@compStrings #1#2{%
  \def \sets@CSti{#1}%
  \edef\sets@ctempi{\expandafter\sets@erasetobrace\meaning \sets@CSti}%
  \def \sets@CStii{#2}%
  \edef\sets@ctempii{\expandafter\sets@erasetobrace\meaning \sets@CStii}%
  \sets@lessfalse\sets@greaterfalse
  \sets@xxpa\sets@compI \expandafter\sets@ctempi\expandafter|\expandafter\\\sets@ctempii|\relax
}


%% Recursive string comparison. Called by \sets@compStrings.
%% (1) Because of the position of | in the ASCII table, there must be a
%%     special test to get the right result.
\def \sets@compI #1#2\\#3#4\relax{%
  \ifnum `#1<`#3
    \ifx |#3 \sets@greatertrue \else \sets@lesstrue \fi%(1)
  \else
    \ifnum `#1>`#3
      \ifx |#1 \sets@lesstrue \else \sets@greatertrue \fi%(1)
    \else
      \ifx |#1\else
  	\sets@ReturnIII{\sets@compI#2\\#4\relax}%
      \fi
    \fi
  \fi
}
%-----------------------------------------------------------------------------



%% Create a new set ----------------------------------------------------------

%% Creates a new set. The set will be sorted and will contain no duplicate
%% elements.
%%
%% Example: \newset{\myset}{Alice|Bob|Charly}
\def \newset #1#2{%
  \def #1{#2}%
  \sortset{#1}{#1}%
  \deleteduplicates{#1}{#1}%
}

%% Simple constructor of a set. There is no sorting or duplicate detection
%% done by this macro.
%%
%% Example: \newsetsimple{\myset}{Alice|Bob|Charly}
\def \newsetsimple #1#2{\def #1{#2}}
%-----------------------------------------------------------------------------



%% Size determination --------------------------------------------------------

%% Stores the size of set #1 in the LaTeX counter #2. #2 has to be existing.
\def \sizeofset #1\is#2{%
  \setcounter{#2}{0}%
  \expandafter\sets@sizeofset #1|\endset{#2}%
}

% Helper method for \sizeofset. Recursively calls itself. Implemented straight
% forward.
\def \sets@sizeofset #1|#2\endset#3{%
  \def \sizetemps@t{#1}%
  \ifx \sizetemps@t\empty\relax\else
    \stepcounter{#3}%
    \def \sizetemps@t{#2}%
    \ifx\sizetemps@t\empty\else
      \sets@ReturnII{\sets@sizeofset #2\endset{#3}}%
    \fi
  \fi
}
%-----------------------------------------------------------------------------



%% Printing a set ------------------------------------------------------------

%% The content of this macro will be used to separate the elements of the set.
\def \setseparator{, } 

%% Prints the contents of set #1. Elements will be separated by \setseparator.
%\def \listset #1{\expandafter\sets@listset #1|\empty\endset}
\def \listset #1{\expandafter\sets@listset #1|\endset|}


%% Helper method for \listset.
%\def \sets@listset #1|#2\endset{%
%  #1%
%  \def\temps@t{#2}%
%  \ifx \temps@t\sets@empty{}\else
%    \setseparator
%    \sets@ReturnFi{\sets@listset #2\endset}%
%  \fi
%}

\def \sets@listset #1|#2|{%
  #1%
  \ifx\endset #2%
  \else
    \setseparator\sets@ReturnFi{\sets@listset#2|}%
  \fi
}
%-----------------------------------------------------------------------------



%% Testing for membership ----------------------------------------------------

%% This macro tests, if #1 is included in set #2.  Can be used in constructs
%% like \if \iselementofset{...}{...} ... \else ... \fi.  It has complexity
%% O(1), assuming that the pattern matching is done in O(1), too.
%%
\def \iselementofset #1#2{%
  00\fi
  \begingroup
  \def \lookup ##1|#1|##2\endset{%
    \def \temp{##2}%
    \ifx \temp\empty 
      \endgroup
      \sets@Returnfalse
    \else
      \endgroup
      \sets@Returntrue
    \fi}%
  \expandafter\lookup \expandafter |#2|#1|\endset%
}
%-----------------------------------------------------------------------------



%% Duplicate detection: ------------------------------------------------------

%% This macro finds alle duplicate elements in the SORTED set #1 and removes
%% them. The result set (still sorted) is stored in #2.
\def \deleteduplicates #1#2{\expandafter\sets@duplicates#1|\endset#2}

%% Helper method for \deleteduplicates. Does some preparations and catches the
%% special case of an set with size <= 1. Parameter #3 is the result set.
\def \sets@duplicates #1|#2\endset#3{%
  \def #3{}% Clear #3
  \def \temps@t{#2}%
  \ifx \temps@t\empty% Has the set more than one element?
    \def #3{#1}% Just one element!
  \else% More than one element
    \sets@ReturnFi{\sets@duplicatesI#1|#2\endset#3}%
  \fi
}


%% Called by \sets@duplicates, if the sorted set contains two or more elements. It
%% checks, if two elements, which are directly following each other are equal.
%% If yes, the first one will not be part of the result set, which is stored
%% in #4.
\def \sets@duplicatesI #1|#2|#3\endset#4{%
  \def\temps@ti{#1}%
  \def\temps@tii{#2}%
  \def\temps@tiii{#3}%
  \ifx \temps@tii\empty % Is #2 empty?
    \def #4{#1}% A set with one element has no duplicates
  \else % #2 not empty --> at least two elements (left)
    \ifx \temps@tiii\empty% Is #3 empty?
      % The set contains two elements, so work is nearly done.
      % An additional | was inserted at the beginning. It has to be gobbled
      % away.
      \ifx \temps@ti\temps@tii % #1=#2
	\sets@append{|#1}\to#4%
        \sets@gobblefirst{#4}{#4}%
      \else
 	\sets@append{|#1|#2}\to#4%
        \sets@gobblefirst{#4}{#4}%
      \fi
    \else % #3 not empty --> at least three elements (left)
      \ifx \temps@ti\temps@tii
        \sets@ReturnElseIII{\sets@duplicatesI #2|#3\endset#4}%
      \else
        \sets@append{|#1}\to#4%
        \sets@ReturnIII{\sets@duplicatesI #2|#3\endset#4}%
      \fi
    \fi
  \fi
}
%-----------------------------------------------------------------------------



%% Sorting a set -------------------------------------------------------------
\newcounter{s@tlength} % LaTeX-counter used by \sortset.

%% Takes an unsorted set #1, sorts it and stores the result in #2. If #1 has
%% less than two elements, sorting is unneccessary, otherwise \sets@sortset is
%% called.
%%
%% Syntax \sortset <set> <result set>
\def \sortset #1#2{%
  \sizeofset#1\is{s@tlength}%
  \ifnum 2>\value{s@tlength}\relax
    \let #2 #1%
  \else
    \sets@sortset #1#2%
  \fi
}

%% Called by \sortset. This macro represents the outer loop of the bubblesort
%% algorithm. Bubblesort has O(n^2) and is stable.
%%
\def \sets@sortset #1#2{%
  \let \sorttemps@t #1%
  \sets@loop
    \expandafter\sets@bubblesortRun \sorttemps@t|\endset\sorttemps@t
    \addtocounter{s@tlength}{-1}%
    \ifnum 1<\value{s@tlength}\relax
  \repeat
  \let #2 \sorttemps@t
}

%% Called by \sets@sortset. Does some preparation for \sets@bubblesortRunI and
%% removes the first character of the result. #4 is the result set.
\def \sets@bubblesortRun #1|#2|#3\endset#4{%
  \def\temps@t{}%
  \sets@bubblesortRunI #1|#2|#3\endset\temps@t%
  \sets@gobblefirst{#4}{\temps@t}%
}

%% Called by \sets@bubblesortRun and recursively by itself.
%% This recursive macro represents the inner loop of "normal" bubblesort.
%% #4 is the result set.
\def \sets@bubblesortRunI #1|#2|#3\endset#4{%
  \def\temps@tii{#2}%
  \def\temps@tiii{#3}%
  \ifx \temps@tii\empty 
    \sets@append{|#1}\to#4%
  \else
    \ifx \temps@tiii\empty
      \sets@compStrings{#2}{#1}%
      \ifsets@greater
        \sets@append{|#1|#2}\to#4%
      \else
        \sets@append{|#2|#1}\to#4%
      \fi
    \else
      \sets@compStrings{#2}{#1}%
      \ifsets@greater
	\sets@ReturnElseIII{%
          \sets@append{|#1}\to#4%
          \sets@bubblesortRunI#2|#3\endset#4}%
      \else
        \sets@ReturnIII{%
          \sets@append{|#2}\to#4%
          \sets@bubblesortRunI#1|#3\endset#4}%
      \fi
    \fi
  \fi
}
%-----------------------------------------------------------------------------



%% Set manipulation ----------------------------------------------------------

%% Takes two sets #1 and #2 and performs a union operation. #1 and #2 do not
%% have to be sorted and may contain duplicate elements.
%% The result is stored in #3. It contains the elements of #1 and #2 and is
%% sorted. Duplicates are removed.
\def \unionsets #1#2\to#3{%
  \let\uniont@mpi=#1%
  \let\uniont@mpii=#2%
  \ifx \uniont@mpi\empty
    \let \uniontemps@t=\uniont@mpii
  \else
    \let \uniontemps@t=\uniont@mpi
    \ifx \uniont@mpii\empty \else
      \expandafter\sets@append\expandafter{\expandafter|#2}\to\uniontemps@t
    \fi
  \fi
  \sortset{\uniontemps@t}{\uniontemps@t}%
  \deleteduplicates{\uniontemps@t}{#3}%
}
%-----------------------------------------------------------------------------


%% Takes two sets #1 and #2 and performs an intersect operation. The result is
%% stored in #3. #3 contains only elements that have been in both sets #1 and
%% #2. #1 and #2 don't have to be sorted, but if #1 is sorted, #3 will be
%% sorted, too. If #1 contains duplicates, #3 may also contain duplicates.
\def \intersectsets #1#2\to#3{%
  \def \tempinters@ct{}%
  \expandafter \sets@intersectsets #1|\endset#2\tempinters@ct
  \ifx \tempinters@ct\empty
    \def #3{}%
  \else
    \sets@gobblefirst{#3}{\tempinters@ct}%
  \fi
}

%% #1 and #2 are parts of set #1 of \intersectsets. #3 is #2 of \intersectsets
%% #4 is the result set
\def \sets@intersectsets #1|#2\endset#3#4{%
  \if \iselementofset{#1}{#3}%
    \sets@append{|#1}\to#4%
  \fi
  \def \tempinters@cti{#2}%
  \ifx \tempinters@cti\empty \else
    \sets@ReturnFi{\sets@intersectsets #2\endset#3#4}%
  \fi
}
%-----------------------------------------------------------------------------


%% Takes two sets #1 and #2 and performs a minus operation, i.e. all elements
%% of #1 that are in #2, too, are removed. The result is saved in #3. If #1 is
%% sorted, #3 will be sorted, too.
%%
%% This macro is implemented like \intersectsets. The only difference is, that
%% an element will only be part of #1 if it is NOT in #2. In \intersectsets it
%% will be part if it is in #2.
\def \minussets #1\minus#2\to#3{%
  \def \@tempminus{}%
  \expandafter \sets@minussets #1|\endset#2\@tempminus
  \ifx \@tempminus\empty
    \def #3{}%
  \else
    \sets@gobblefirst{#3}{\@tempminus}%
  \fi
}

%% Syntax like \sets@intersectsets, but of course different semantics.
\def \sets@minussets #1|#2\endset#3#4{%
  \if \iselementofset{#1}{#3}\else
    \sets@append{|#1}\to#4%
  \fi
  \def \temp@minus{#2}%
  \ifx \temp@minus\empty \else
    \sets@ReturnFi{\sets@minussets #2\endset#3#4}%
  \fi
}
%-----------------------------------------------------------------------------

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\endinput