%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % This is a helper package with an elementary double-ended-queue % (deque) datastructure, % featuring O(1) index access and O(N) creation, deletion, copy. % % The following macros are supplied: % % \pgfplotsdequenewempty % \pgfplotsdequecopy % \pgfplotsdequepushback % \pgfplotsdequepopfront % \pgfplotsdequecheckempty % \pgfplotsdequeforeach % % Copyright 2007/2008 by Christian Feuersänger. % % This program is free software: you can redistribute it and/or modify % it under the terms of the GNU General Public License as published by % the Free Software Foundation, either version 3 of the License, or % (at your option) any later version. % % This program is distributed in the hope that it will be useful, % but WITHOUT ANY WARRANTY; without even the implied warranty of % MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the % GNU General Public License for more details. % % You should have received a copy of the GNU General Public License % along with this program. If not, see . % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % IMPLEMENTATION NOTES: % I allocate an array which provides storage capacity and two pointers % (indices) into that array. % % The deque is stored as % - an array: \csname pgfpldq@\endcsname % - the pointers: % \csname pgfpldq@@beg\endcsname % \csname pgfpldq@@end\endcsname (one after the end) % % ATTENTION: may NOT be a control sequence! % this is in contrast to my other container structures. % Allocates a new, empty deque #1. % % #1 the name of a deque (NO control sequence!) % #2 is an integer denoting the maximum capacity. For now, this % capacity is fixed afterwards and denotes the maximum number of % entries. \def\pgfplotsdequenewempty#1{% \pgfutil@ifnextchar\capacity{% \pgfplotsdequenewempty@{#1}% }{% \pgfplots@error{Expected \string\capacity\{the capacity\} after \string\pgfplotsdequenewempty...}% \pgfplotsdequenewempty@{#1}\capacity{100}% }% }% \def\pgfplotsdequenewempty@#1\capacity#2{% \pgfplotsarrayresize{pgfpldq@#1}{#2}% \pgfutil@namedef{pgfpldq@#1@beg}{0}% \pgfutil@namedef{pgfpldq@#1@end}{0}% }% \def\pgfplotsdequecopy#1\to#2{% \pgfutil@namelet{pgfpldq@#1@beg}{pgfpldq@#2@beg}% \pgfutil@namelet{pgfpldq@#1@end}{pgfpldq@#2@end}% \pgfplotsarraycopy{pgfpldq@#1}\to{pgfpldq@#2}% }% \def\pgfplotsdequepushback#1\to#2{% \pgfplotsarrayset{\csname pgfpldq@#2@end\endcsname}\of{pgfpldq@#2}\to{#1}% \c@pgfplotsarray@tmp=\csname pgfpldq@#2@end\endcsname \advance\c@pgfplotsarray@tmp by1 \ifnum\c@pgfplotsarray@tmp=\pgfplotsarraysizeof{pgfpldq@#2} \c@pgfplotsarray@tmp=0 \fi \expandafter\edef\csname pgfpldq@#2@end\endcsname{\the\c@pgfplotsarray@tmp}% \pgfplotsdequeifempty{#2}{\pgfplots@error{Error: \string\pgfplotsdeque\space capacity has been reached - it was too small. Sorry, I didn't write auto-enlargement...}}{}% }% \def\pgfplotsdequepopfront#1\to#2{% \pgfplotsarrayselect{\csname pgfpldq@#1@beg\endcsname}\of{pgfpldq@#1}\to{#2}% \c@pgfplotsarray@tmp=\csname pgfpldq@#1@beg\endcsname \advance\c@pgfplotsarray@tmp by1 \ifnum\c@pgfplotsarray@tmp=\pgfplotsarraysizeof{pgfpldq@#1} \c@pgfplotsarray@tmp=0 \fi \expandafter\edef\csname pgfpldq@#1@beg\endcsname{\the\c@pgfplotsarray@tmp}% }% % invokes #2 if deque '#1' is empty and '#3' if it is not empty. \def\pgfplotsdequeifempty#1#2#3{% \ifnum\csname pgfpldq@#1@beg\endcsname=\csname pgfpldq@#1@end\endcsname\relax #2% \else #3% \fi }% \long\def\pgfplotsdequeforeach#1\as#2#3{% \c@pgfplotsarray@tmp=\csname pgfpldq@#1@beg\endcsname \long\def\pgfplotsdequeforeach@next{\pgfplotsdequeforeach@iter{#1}{#2}{#3}}% \pgfplotsdequeforeach@next }% \long\def\pgfplotsdequeforeach@iter#1#2#3{% \ifnum\c@pgfplotsarray@tmp=\csname pgfpldq@#1@end\endcsname \def\pgfplotsdequeforeach@next{}% \else \pgfplotsarrayselect\c@pgfplotsarray@tmp\of pgfpldq@#1\to#2% \edef\pgfplotsdequeforeach@{\the\c@pgfplotsarray@tmp}% #3\relax \c@pgfplotsarray@tmp=\pgfplotsdequeforeach@ \advance\c@pgfplotsarray@tmp by1 \ifnum\c@pgfplotsarray@tmp=\pgfplotsarraysizeof{pgfpldq@#1} \c@pgfplotsarray@tmp=0 \fi \fi \pgfplotsdequeforeach@next }%