\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#351: Add Striding Support to lsearch}
\date{July 09, 2009}
\author{Peter da Silva, Donal K. Fellows, Harald Oehlmann, Andreas Leitgeb}
\urlstyle{sf}
\setlength{\parskip}{1ex}
\setlength{\parindent}{0pt}
\def\tipversion$#1${\texttt{\$#1\$}}
\def\tiplangle#1{\ensuremath{<}}
\def\tiprangle#1{\ensuremath{>}}
\def\tipbar#1{\ensuremath{|}}
\def\tipmail#1#2{\(\langle\){\small\expandafter\url{#1@#2}}\(\rangle\)}
\ifx\pdfoutput\undefined
\newcommand{\tipimage}[2]{\typeout{Make sure you download #1.eps}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.eps}}{\includegraphics[width=0.8\textwidth]{#1.eps}}}
\newcommand{\tipxref}[1]{}
\newcommand{\tipxrefend}{}
\else
\newcommand{\tipimage}[2]{\typeout{Make sure you create #1.pdf}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.pdf}}{\includegraphics[width=0.8\textwidth]{#1.pdf}}}
\pdfcatalog{/PageMode /UseOutlines}
\newcommand{\tipxref}[1]{\pdfannotlink attr {/C [0.5 0.5 1.0] /Border [0 0 1]} goto name {#1}}
\newcommand{\tipxrefend}{\pdfendlink}
\fi
\newenvironment{tipabstract}{\begin{abstract}}{\end{abstract}}
\begin{document}\maketitle
\begin{center}\begin{tabularx}{\linewidth}{|r@{: }X|}\hline
\textbf{TIP \#351}&\textbf{Add Striding Support to lsearch}\\\hline
Author&

Peter da Silva \tipmail{peter}{taronga.com}
\par
Donal K. Fellows \tipmail{donal.k.fellows}{manchester.ac.uk}
\par
Harald Oehlmann \tipmail{harald.oehlmann}{elmicron.de}
\par
Andreas Leitgeb \tipmail{avl}{logic.at}
\\
Created&Thursday, \(\text{9}^{\text{th}}\) July 2009\\
Type&Project\\
Tcl Version&\(8.7\)\\
State&Draft\\
Vote&Pending\\
Version&\tipversion$Revision: 1.19 $\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP allows the searching of lists that are grouped into collections of several elements.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

When operating on strided lists (for example key-value lists) it's normal to convert them between lists and arrays and back again. If it was possible to efficiently perform a strided search of the list it would be possible to (for example) search just the keys and ignore the values. Indeed, Tcl has a long tradition of working with lists which are structured into groups through \textbf{foreach} and \textbf{array get}, and this is strengthened further with dictionaries \cite{tip111} and striding sorts \cite{tip326}. However, there is currently no facility for searching such lists; this TIP proposes fixing this.

\section{Proposed Change}

We propose adding a \textbf{-stride} option to \textbf{lsearch}, by exact analogy with the option added to \textbf{lsort} in \cite{tip326}, whose semantics it should closely match.

If \textbf{-stride} is supplied, the list will be treated as consisting of groups of grpSize elements. The search will be operated within this group as it is a first level of nested lists (see \textit{Conceptual Backround} below).

The first element of \textbf{-index} is used to seach for an item of the group.

The option \textbf{-start} always points to the beginning of the group, even if a position within the group is given.

Returned indices are the first element of the striding group(s) that is/are being indicated.

The list length must be a multiple of \textbf{grpSize}, which in turn must be at least 2.

\section{Conceptual Backround}

\subsection{Striding equivalent to first level of nested lists}

The striding within the list is seen as the first level of list nesting. E.g.

\textbf{Nested list}:
\begingroup\small\begin{verbatim}
set deep {{1 a A} {2 b B} {3 c C}}
\end{verbatim}
\endgroup

\textbf{Flat strided list}: 
\begingroup\small\begin{verbatim}
set flat {1 a A 2 b B 3 c C}
\end{verbatim}
\endgroup

Functions should operate the same way on both representation, with the only difference, that \textbf{-stride 3} must be specified in the second case.

Unfortunately, the current implementation of \textbf{lsort} is not doing this. It interpretes \textbf{-index ""} as \textbf{-index 0}:
\begingroup\small\begin{verbatim}
% lsort -stride 2 {A 1 A 2 A 0}
A 1 A 2 A 0
% lsort -stride 2 -index "" {B 2 B 1 A 3}
A 3 B 2 B 1
\end{verbatim}
\endgroup

\subsection{Numeric position indices}

Numerical positional indices (-start parameter, return value) follow the flattened list and not the grouped list. This is different to the nested list view.

Furthermore, if option \textbf{-subindices} is given and a non-empty argument for \textbf{-index}, then the group-start and index-into-group are added up. This gives compatibility with lindex, as in the no-stride case.

\section{Examples}

In these examples, the variable \textit{kvlist} holds the key-value list:
\begingroup\small\begin{verbatim}
set kvlist {K1 V1 K2 V1 K1 K1}
\end{verbatim}
\endgroup

Example 1: find keys even if they exist multiple times:
\begingroup\small\begin{verbatim}
% lsearch -all -stride 2 -index 0 -exact $kvlist K1
0 4
\end{verbatim}
\endgroup

Example 2: find existance of a value:
\begingroup\small\begin{verbatim}
% lsearch -all -stride 2 -index 1 -exact $kvlist V1
0 2
\end{verbatim}
\endgroup

Remark that the indexes of the first group elements are returned. The real values are at ``result+index'' eq \textbf{1 3}.

Example 3: extract a sub-kv-list starting from key K2:
\begingroup\small\begin{verbatim}
% lrange $kvlist [lsearch -stride 2 -index 0 -exact $kvlist K2] end
K2 V1 K1 K1
\end{verbatim}
\endgroup

Example 4: find a group within a list:
\begingroup\small\begin{verbatim}
% lsearch -stride 2 -exact $kvlist {K2 V1}
2
\end{verbatim}
\endgroup

Example 5: find in combined strided and nested list
\begingroup\small\begin{verbatim}
% lsearch -stride 2 -index {1 1} -exact\
        {K0 {V0.0 V0.1} K1 {V1.0 V1.1}}\
        V1.1
2
\end{verbatim}
\endgroup

Example 6: subindices with strided list:
\begingroup\small\begin{verbatim}
% lsearch -stride 2 -index {1 1} -subindices {1 {a A} 2 {b B}} B
3 1   (that is: 2 for the group-start plus 1 for the intra-group
       index, and separately 1 for the further nested index.
% lindex {1 {a A} 2 {b B}} 3 1
B
\end{verbatim}
\endgroup

to be consisten with:
\begingroup\small\begin{verbatim}
% lsearch -index {1 1} -subindices {{1 {a A}} {2 {b B}}} B
1 1 1
% lindex {{1 {a A}} {2 {b B}}} 1 1 1
B
\end{verbatim}
\endgroup

\section{Copyright}

This document has been placed in the public domain.

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\begin{thebibliography}{TIP \#2}
\addcontentsline{toc}{section}{References}
\bibitem[TIP \#111]{tip111}
Donal K. Fellows,
David S. Cargo,
\emph{Dictionary Values and Manipulators},
on-line at \url{http://purl.org/tcl/tip/111.html}
\bibitem[TIP \#326]{tip326}
Kieran Elby,
\emph{Add -stride Option to lsort},
on-line at \url{http://purl.org/tcl/tip/326.html}
\end{thebibliography}
\end{document}
