\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#127: Add an -index Option to [lsearch]}
\date{February 26, 2003}
\author{Michael Schlenker}
\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 \#127}&\textbf{Add an -index Option to [lsearch]}\\\hline
Author&

Michael Schlenker \tipmail{schlenk}{uni-oldenburg.de}
\\
Created&Wednesday, \(\text{26}^{\text{th}}\) February 2003\\
Type&Project\\
Tcl Version&\(8.5\)\\
State&Final\\
Vote&Done\\
Version&\tipversion$Revision: 1.13 $\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

Matching the \textit{lsort} functionality a \textit{-index} option should be added to the \textit{lsearch} command to make searching lists in list easier. The \textit{lsort -index} and the \textit{lsearch -index} options should accept list style indices like \textit{lindex} and \textit{lset} do. This TIP proposes such added options.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Specification}

Under this proposal the syntax of the \textit{lsearch} is to be modified to accept two extra options. 

The \textit{-index} option:

The \textit{lsort} -index option would get enhanced with multiple index support.
\begingroup\small\begin{verbatim}
    lsearch ?-index index? 
\end{verbatim}
\endgroup

The \textit{-index} option should work similar to the \textit{-index} option in the \textit{lsort} command.

If this option is specified, each of the elements of list must itself be a proper Tcl sublist. Instead of searching based on whole sublists, \textit{lsearch} will extract the index'th element from each sublist and search based on the given element. The keyword end is allowed for the index to search on the last sublist element, and end-index searches on a sublist element offset from the end. For example,
\begingroup\small\begin{verbatim}
    lsearch -integer -index 1 {{First 24} {Second 18} {Third 30}} 18
\end{verbatim}
\endgroup

returns \textit{1}, and
\begingroup\small\begin{verbatim}
    lsearch -index end-1 {{a 1 e i} {b 2 3 f g} {c 4 5 6 d h}} d
\end{verbatim}
\endgroup

returns \textit{2}.

The index given to \textit{lsearch -index} and \textit{lsort -index} may be either a single scalar index as in the current \textit{lsort} implementation or the argument to \textit{-index} may be a list of scalar indices (similar, but not exactly like the lset/lindex multiple indices). The -index option causes lsearch and lsort to extract the item for searching or sorting comparision from the list element by using in effect \textit{lindex \$element \$index}.

For example:
\begingroup\small\begin{verbatim}
    set record {
        {
          {James Dean} {Musician} {some other data}
        }
        {
          {Elvis Presley} {Musician} {some more data}
        }
     }

   lsearch -index {0 0} $record "Elvis"
\end{verbatim}
\endgroup

returns \textit{1}.
\begingroup\small\begin{verbatim}
   lsort -dictionary -decreasing -index {0 1} $record
\end{verbatim}
\endgroup

returns \textit{\{\{\{Elvis Presley\} \{Musician\} \{some more data\}\} \{\{James Dean\} \{Musician\} \{some other data\}\}\}}.

Note: The following example is invalid, -index only takes a list as argument, unlike lset and lindex, that take either a list or multiple arguments, that get concatenated by the command.
\begingroup\small\begin{verbatim}
 lsearch -index 1 1 $record Presley
\end{verbatim}
\endgroup

The \textit{-subindices} option:

The \textit{-subindices} option should be added only to the \textit{lsearch} command as a convenience shortcut. It is only a valid option if the \textit{-index} option is also used.

If \textit{-subindices} is given, \textit{lsearch} should return a list of indices that can be used directly by \textit{lindex} or \textit{lset} to manipulate the element used for searching, instead of the top level element of the list.

If \textit{-subindices} and \textit{-inline} are specified at the same time, the command returns the value instead of the index.

example:
\begingroup\small\begin{verbatim}
 lsearch -subindices -index {0 0} $record Elvis
\end{verbatim}
\endgroup

returns \textit{\{1 0 0\}}.

If no -all option is specified, this is the same as doing:
\begingroup\small\begin{verbatim}
 concat [lsearch -index {0 0} $record Elvis] [list 0 0]
\end{verbatim}
\endgroup

\section{Rationale}

Lists containing one or more level of sublists are a common technique to simulated complex data structures like matrices or records, or for results from database queries. The \textit{lsort} command was enhanced with the \textit{-index} option for this case, to handle sorting on sublist keys.

The \textit{lsearch} command does not have this functionality yet, one has to use \textit{foreach} and \textit{lindex} to loop over the list one by one.

Multiple indices for the \textit{-index} option to both \textit{lsearch} and \textit{lsort} should be added, to make the option more similar to \textit{lset} and \textit{lindex} style indices.

The \textit{-subindices} option is a convenience option to make constructs like this example work well:
\begingroup\small\begin{verbatim}
 foreach item [lsearch -all -subindices -index {0 0} $record bla] {
         lset record $item bar
 }
\end{verbatim}
\endgroup

Without the subindices option it could be written as:
\begingroup\small\begin{verbatim}
 foreach item [lsearch -all -index $idx $record bla] {
         lset record [concat $idx $item] bar
 }
\end{verbatim}
\endgroup

\section{Reference Implementation}

A reference implementation exists, see the files attached to the Tcl Patch 693836 on SourceForge. \url{http://sf.net/tracker/?func=detail&atid=310894&aid=693836&group_id=10894}

The reference implementation isn't honouring the -inline option if given in conjuction with -subindices, at the moment.

\section{Copyright}

This document has been placed in the public domain.

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\end{document}
