summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgfplots/liststructure/pgfplotsarray.code.tex
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgfplots/liststructure/pgfplotsarray.code.tex')
-rw-r--r--Master/texmf-dist/tex/generic/pgfplots/liststructure/pgfplotsarray.code.tex63
1 files changed, 63 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/generic/pgfplots/liststructure/pgfplotsarray.code.tex b/Master/texmf-dist/tex/generic/pgfplots/liststructure/pgfplotsarray.code.tex
index 55a91874293..df9a26d6839 100644
--- a/Master/texmf-dist/tex/generic/pgfplots/liststructure/pgfplotsarray.code.tex
+++ b/Master/texmf-dist/tex/generic/pgfplots/liststructure/pgfplotsarray.code.tex
@@ -17,6 +17,7 @@
% \pgfplotsarraycheckempty
% \pgfplotsarrayforeach
% \pgfplotsarraysort
+% \pgfplotsarraybinarysearch
%
% and a subset also for global arrays:
% \pgfplotsarraynewemptyglobal
@@ -668,3 +669,65 @@
\pgfplotsarrayinsertionsort@@next
}%
+% applies a binary seach for value '#2' on array '#1', starting with
+% index '#3' (inclusive) and ending in index '#4' (exclusive).
+%
+% Returns: \pgfplotsretval, the index of the search key, if it is
+% contained in the array; otherwise, (-(insertion point) - 1). The
+% insertion point is defined as the point at which the key would be
+% inserted into the array: the index of the first element greater than
+% the key, or a.length if all elements in the array are less than the
+% specified key. Note that this guarantees that the return value will
+% be >= 0 if and only if the key is found.
+%
+\def\pgfplotsarraybinarysearch#1#2#3#4{%
+ \begingroup
+ \edef\targetvalue{#2}%
+ \pgfkeysgetvalue{/pgfplots/iflessthan/.@cmd}\pgfplotsarray@iflt
+ \let\mid=\c@pgf@counta
+ \let\left=\c@pgf@countb
+ \let\right=\c@pgf@countc
+ \left=#3\relax
+ \right=#4\relax
+ \advance\right by-1 % make it inclusive
+ \let\pgfplotsretval\pgfutil@empty
+ %
+ \pgfutil@loop
+ \ifnum\left>\right
+ \pgfplots@loop@CONTINUEfalse
+ \else
+ \pgfplots@loop@CONTINUEtrue
+ \fi
+ \ifpgfplots@loop@CONTINUE
+ \mid=\right
+ \advance\mid by -\left
+ \divide\mid by2 %
+ \advance\mid by\left
+ %
+ \pgfplotsarrayselect\mid\of#1\to\midvalue
+ \pgfplotsarray@iflt{\targetvalue}{\midvalue}{%
+ \right=\mid
+ \advance\right by-1 %
+ }{%
+ \pgfplotsarray@iflt{\midvalue}{\targetvalue}{%
+ \left=\mid
+ \advance\left by1 %
+ }{%
+ % found it! abort loop!
+ \left=\right
+ \advance\left by1 %
+ \edef\pgfplotsretval{\the\mid}%
+ }%
+ \pgfeov%
+ }%
+ \pgfeov%
+ \pgfutil@repeat
+ %
+ \ifx\pgfplotsretval\pgfutil@empty
+ \advance\left by1 %
+ \left=-\left
+ \edef\pgfplotsretval{\the\left}%
+ \fi
+ \pgfmath@smuggleone\pgfplotsretval
+ \endgroup
+}%