I wrote:
> Re: efficiency: My experience is that one can have TeX do quite
> extensive processing without slowing things down much *provided one does
> it in the mouth*. (I don't understand quite why that would be, but did
> some timing to confirm it in particular cases for fontinst v1.913.) A
> set of workable semantics for a fully expandable
> \DictionaryGet{<key>}{<dictionary>}{<default>}
> command would be:
>
> 1. \DictionaryGet{#1}{\ToDictionary{#2}{#3}}{#4}
> fully expands to the full expansion of #3 if the full
> expansion of #1 is equal to the full expansion of #2,
> and to the full expansion of #4 otherwise; probably
> equivalent to
> \str_if_eq:xxTF{#1}{#2}{#3}{#4}
> (or would that be \str_if_eq:nnTF?).
>
> 2. \DictionaryGet{#1}{\ToDictionary{#2}{#3}#4}{#5}
> is after full expansion equivalent to
> \DictionaryGet{#1}{\ToDictionary{#2}{#3}}{
> \DictionaryGet{#1}{#4}{#5}
> }
>
> 3. \DictionaryGet{#1}{}{#2}
> is after full expansion equivalent to #2.
>
> The trickiest thing to do in TeX3 is the test for key equality, and I
> believe there has been discussions about newer engines having primitives
> that simplify this. (Not having to go via
> \expandafter\string\csname<key-name>\endcsname to sanitize key names is
> a good first step, although not essential.)
Following up on that: As a proof of concept, I implemented (for
TeX3/LaTeX2e) such a \DictGet command last night; see attached files
(<6K with source documentation and tests). Complexity is linear in the
size of dictionary values, but worst-case quadratic in the average size
of a key.
10000 look-ups (9988 of which won't find anything) in a dictionary of
12 elements took 12.114s on a fairly old (500MHz) iBook. Seems
acceptable to me.
Lars Hellström
% \begin{macro}{\str@if@eq}
% This macro has the syntax
% \begin{quote}
% |\str@if@eq|\marg{str1}\marg{str2}\marg{then}\marg{else}
% \end{quote}
% It expands to \meta{then} if \meta{str1} and \meta{str2} are
% equal, and to \meta{else} otherwise. The first two arguments
% should consist entirely of tokens of categories 11~(letter),
% 12~(other), |&|, |^|, |_|, |$| (possibly |#|), but not
% 1~(beginning of group), 2~(end of group), or 13~(active).
% Category 10~(space) tokens are ignored.
% \begin{macrocode}
%<*pkg>
\def\str@if@eq#1#2{%
\str@if@eq@ #1\relax\str@if@eq@ #2\relax\str@if@eq@
}
\def\str@if@eq@#1#2\str@if@eq@#3#4\str@if@eq@{%
\if #1#3%
\expandafter\@firstoftwo
\else
\expandafter\@secondoftwo
\fi{%
\ifx #1\relax
\expandafter\@secondoftwo
\else
\expandafter\@firstoftwo
\fi{%
\str@if@eq@#2\str@if@eq@#4\str@if@eq@
}\@firstoftwo
}\@secondoftwo
}
% \end{macrocode}
% \end{macro}
%
% \begin{macro}{\q@dict@end}
% \begin{macro}{\gobble@dict}
% A quark (though less dangerous than the \LaTeX3 ones) to
% delimit dictionaries, and a macro that gobbles everything up to
% and including that quark.
% \begin{macrocode}
\def\q@dict@end{\string\q@dict@end}
\long\def\gobble@dict#1\q@dict@end{}
% \end{macrocode}
% \end{macro}
%
% \begin{macro}{\DictEntry}
% The |\DictEntry| command is used to construct dictionary entries.
% It has the syntax
% \begin{quote}
% |\DictEntry|\marg{key}\marg{value}
% \end{quote}
% Code processing dictionaries will test tokens for being
% |\DictEntry|, so its definition has no relevance for such
% processing beyond serving as a ``unique'' identifier. However,
% the definition should be such that it survives full expansion, as
% dictionaries will often occur in moving contexts. Therefore it is
% made unexpandable.
% \begin{macrocode}
\chardef\DictEntry=`/
% \end{macrocode}
% In $\varepsilon$-\TeX, it would be more practical to make
% |\DictEntry| a |\protected| macro.
% \end{macro}
%
% \begin{macro}{\DictGet}
% This command has the syntax
% \begin{quote}
% |\DictGet|\marg{key}\marg{dictionary}\marg{default}
% \end{quote}
% It expands to \meta{default} if there is no \meta{key} entry in
% the \meta{dictionary}, but to the value of that \meta{key} entry
% otherwise.
%
% \begin{macrocode}
\long\def\DictGet#1#2{%
\expandafter\expandafter\expandafter\dict@get@entry
\expandafter\expandafter\expandafter{\expandafter\string
\csname#1\endcsname}#2\q@dict@end\@firstofone
}
% \end{macrocode}
% \end{macro}
%
% \begin{macro}{\dict@get@entry}
% This is the main iterate of |\DictGet|. It should occur either as
% \begin{quote}
% |\dict@get@entry|\marg{key1}^^A
% |\DictEntry|\marg{key2}\marg{value}\dots
% \end{quote}
% or as
% \begin{quote}
% |\dict@get@entry|\marg{key1}|\q@dict@end|
% \end{quote}
% In the second case, there are no more entries in the dictionary
% and it should expand to nothing. In the first case, it should
% prepare for a test of whether \meta{key1} and \meta{key2} are
% equal. It must however also be prepared to handle the error
% situation that neither case is at hand.
% \begin{macrocode}
\long\def\dict@get@entry#1#2{%
\ifx \DictEntry#2%
\expandafter\dict@get@entry@
\else
\dict@verify@end#2\@empty\q@dict@end
\expandafter\@gobble
\fi{#1}%
}
\long\def\dict@verify@end#1#2\q@dict@end{%
\ifx \q@dict@end#1\else
\PackageError{dict}{Malformed dictionary}{Ignoring entries}%
\csname fi\endcsname
\expandafter\gobble@dict
\fi
}
% \end{macrocode}
% \end{macro}
%
%
% \begin{macro}{\dict@get@entry@}
% This macro performs the second step of looking at a dictionary
% entry: santizing the entry key. It occurs in the context
% \begin{quote}
% |\dict@get@entry@|\marg{key1}\marg{key2}\marg{value}\dots
% \end{quote}
% where \meta{key1} already is sanitized but \meta{key2} may need
% processing.
%
% After having sanitized \meta{key2}, the above will have expanded to
% \begin{quote}
% |\str@if@eq|\marg{key2-sanitized}\marg{key1}\\
% |{|\meta{value}\meta{gobble-code}|}|\\
% |{\dict@get@entry{|\meta{key1}|}}|
% \end{quote}
% which either continues with the next entry (when not equal) or
% expands to \meta{value} followed by code to gobble the rest of
% the |\DictGet|.
% \begin{macrocode}
\long\def\dict@get@entry@#1#2#3{%
\expandafter\expandafter\expandafter\str@if@eq
\expandafter\expandafter\expandafter{%
\expandafter\string \csname#2\endcsname}{#1}
{#3\expandafter\@gobbletwo\gobble@dict}%
{\dict@get@entry{#1}}%
}
% \end{macrocode}
% \end{macro}
%
% \begin{macrocode}
%</pkg>
% \end{macrocode}
%
% \begin{macrocode}
%<*test>
Expect `bar': \DictGet{foo}{}{bar}
Expect `bar': \DictGet{foo}{\DictEntry{bar}{baz}}{bar}
Expect `baz': \DictGet{foo}{\DictEntry{foo}{baz}}{bar}
Expect `bar': \DictGet{fo}{\DictEntry{foo}{baz}}{bar}
Expect `bar': \DictGet{foo}{\DictEntry{fo}{baz}}{bar}
Expect `baz1':
\DictGet{foo}{\DictEntry{foo}{baz1}\DictEntry{fo}{baz2}}{bar}
Expect `baz2':
\DictGet{foo}{\DictEntry{fo}{baz1}\DictEntry{foo}{baz2}}{bar}
Expect `baz1':
\DictGet{foo}{\DictEntry{foo}{baz1}\DictEntry{foo}{baz2}}{bar}
Expect `foo':
\DictGet{}{\DictEntry{foo}{baz}\DictEntry{}{foo}}{bar}
Expect `bar':
\DictGet{}{\DictEntry{foo}{baz}\DictEntry{foo}{}}{bar}
\message{Expect error...}
\nonstopmode
Expect `bar': \DictGet{foo}{{fo}{baz}}{bar}
\errorstopmode
\message{After expected error.}
\protected@write{16}{}{Expect `\string\DictEntry\space{foo}{bar}':
\DictEntry{foo}{bar}}
Expect something: \DictEntry{foo}{bar}
%</test>
% \end{macrocode}
%
\endinput
|