%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PACKAGE: sets %%
%% FILE: sets.sty %%
%% %%
%% AUTHOR: Jochen Wertenauer %%
%% VERSION: 1.2 %%
%% DATE: 2009-03-01 %%
%% %%
%% 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 ------------------------------------------------------------
\let \sets@xpa \expandafter
\def \sets@xxpa{\sets@xpa\sets@xpa\sets@xpa}
\def \sets@empty{\empty}
%% Appends #1 to the definition of macro #2.
\def \sets@append #1\to#2{\sets@xpa \def \sets@xpa #2\sets@xpa{#2#1}}
%% Removes the first character of the content of #2 and stores the result in
%% #1. Note that \sets@xpa\sets@xpa\sets@xpa cannot be replaced by \sets@xxpa here!
\def \sets@gobblefirst #1#2{%
\sets@xxpa \def \sets@xpa\sets@xpa\sets@xpa #1\sets@xpa\sets@xpa\sets@xpa {\sets@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\sets@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{\sets@xpa\sets@erasetobrace\meaning \sets@CSti}%
\def \sets@CStii{#2}%
\edef\sets@ctempii{\sets@xpa\sets@erasetobrace\meaning \sets@CStii}%
\sets@lessfalse\sets@greaterfalse
\sets@xxpa\sets@compI \sets@xpa\sets@ctempi\sets@xpa|\sets@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}%
\sets@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\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{\sets@xpa\sets@listset #1|\empty\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
}
%-----------------------------------------------------------------------------
%% 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}%
\sets@xpa\lookup \sets@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{\sets@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
\sets@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
\sets@xpa\sets@append\sets@xpa{\sets@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{}%
\sets@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{}%
\sets@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