diff options
author | Karl Berry <karl@freefriends.org> | 2006-01-13 00:11:01 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2006-01-13 00:11:01 +0000 |
commit | fc416931f4cc4fc8797c441d7a68b37ad37a153f (patch) | |
tree | da09bc45be9b51de63af2eaca2ba701b8a4d0f27 /Master/texmf-dist/tex/latex/vhistory/sets.sty | |
parent | 93f92b29a63483ccdfcc4cf32be7bd57b3cd2a55 (diff) |
vhistory
git-svn-id: svn://tug.org/texlive/trunk@1440 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/tex/latex/vhistory/sets.sty')
-rw-r--r-- | Master/texmf-dist/tex/latex/vhistory/sets.sty | 426 |
1 files changed, 426 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/latex/vhistory/sets.sty b/Master/texmf-dist/tex/latex/vhistory/sets.sty new file mode 100644 index 00000000000..2a16a869cbc --- /dev/null +++ b/Master/texmf-dist/tex/latex/vhistory/sets.sty @@ -0,0 +1,426 @@ +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% PACKAGE: sets %% +%% FILE: sets.sty %% +%% %% +%% AUTHOR: Jochen Wertenauer %% +%% VERSION: 1.0 %% +%% DATE: 2005-02-17 %% +%% %% +%% 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). %% +%% Another forbidden element is the command \endset. %% +%% 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 ------------------------------------------------------------ + +\let \xpa \expandafter +\def \xxpa{\xpa\xpa\xpa} + +%% Appends #1 to the definition of macro #2. +\def \sets@append #1\to#2{\xpa \def \xpa #2\xpa{#2#1}} + +%% Removes the first character of the content of #2 and stores the result in +%% #1. Note that \xpa\xpa\xpa cannot be replaced by \xxpa here! +\def \sets@gobblefirst #1#2{% + \xxpa \def \xpa\xpa\xpa #1\xpa\xpa\xpa {\xpa\@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\xpa \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{\xpa\sets@erasetobrace\meaning \sets@CSti}% + \def \sets@CStii{#2}% + \edef\sets@ctempii{\xpa\sets@erasetobrace\meaning \sets@CStii}% + \sets@lessfalse\sets@greaterfalse + \xxpa\sets@compI \xpa\sets@ctempi\xpa|\xpa\\\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}% + \xpa\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\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{\xpa\sets@listset #1|\endset} + +%% Helper method for \listset. +\def \sets@listset #1|#2\endset{% + \def \temps@t{#2}% + #1% + \ifx\temps@t\empty{}\else + \setseparator + \sets@ReturnFi{\sets@listset #2\endset}% + \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}% + \xpa\lookup \xpa |#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{\xpa\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 + \xpa\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 + \xpa\sets@append\xpa{\xpa|#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{}% + \xpa \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{}% + \xpa \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 |