\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#326: Add -stride Option to lsort}
\date{September 01, 2008}
\author{Kieran Elby}
\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 \#326}&\textbf{Add -stride Option to lsort}\\\hline
Author&

Kieran Elby \tipmail{kieran}{dunelm.org.uk}
\\
Created&Monday, \(\text{1}^{\text{st}}\) September 2008\\
Type&Project\\
Tcl Version&\(8.6\)\\
State&Final\\
Vote&Done\\
Version&\tipversion$Revision: 1.5 $\\
Keywords&Tcl, lsort, sorting\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP adds a new option, \textbf{-stride}, to \textbf{lsort} to request that a list be treated as consisting of repeated groups of elements (as opposed to sublists), and that the the groups be sorted according to a chosen element within each group.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

Flat name-value pair lists are common in Tcl --- consider the output of \textbf{array get} and \textbf{dict create} or the input to \textbf{foreach}.

It is surprising then that there is no command to directly sort such a list by either the name or the value elements, while preserving the name-value mapping.

Doing so currently requires turning a name-value pair list into a list of sublists, using the \textbf{lsort} \textit{-index} option to sort them, then flattening the list again, which is rather fiddly and inefficient.

While sorting name-value pair lists is no doubt the most common use case, lists containing groups of more than two elements are also reasonably common, and so providing support for groups of any size seems useful and no harder to implement.

The option format follows the Feature Request here: \url{https://sourceforge.net/support/tracker.php?aid=747083}

\section{Proposed Change}

A new option, \textbf{-stride}, taking one parameter, \textit{grpSize} will be added to the \textbf{lsort} command.

If \textbf{-stride} is supplied, the list will be treated as consisting of groups of \textit{grpSize} elements, and the groups will be sorted by either their first element or, if the \textbf{-index} option is used, by the element within each group given by the first index passed to \textbf{-index} (which is then ignored by \textbf{-index}).

Elements always remain in the same position within their group.

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

\section{Examples}
\begingroup\small\begin{verbatim}
 lsort -stride 2 {carrot 10 apple 50 banana 25}
\end{verbatim}
\endgroup

returns ``apple 50 banana 25 carrot 10''
\begingroup\small\begin{verbatim}
 lsort -stride 2 -index 1 -integer {carrot 10 apple 50 banana 25}
\end{verbatim}
\endgroup

returns ``carrot 10 banana 25 apple 50''
\begingroup\small\begin{verbatim}
 lsort -stride 3 -index {0 1} {{Bob Smith} 25 Audi {Jane Doe} 40 Ford}
\end{verbatim}
\endgroup

returns ``\{Jane Doe\} 40 Ford \{Bob Smith\} 25 Audi'' (since Smith, which is at index 1 of element 0 of the first group comes after Doe, which is at the same position in the next group of 3.)

\section{Reference Implementation}

Available online at \url{https://sourceforge.net/support/tracker.php?aid=2082681}

\section{Compatibility}

Since this is a new and unambiguous option, and since the distinction between the options and the list to sort is clear, no compatibility problems are expected.

\section{Limitations}

Only one element in each group can be used for comparison; it's not possible to compare groups element-by-element.

\section{Further Thoughts}

There may be some merit in adding a similar option to \textbf{lsearch}.

The name-value pair case is common enough that an argument could be made for adding \textbf{-pairname} and \textbf{-pairvalue} options as synonyms for \textbf{-stride 2 -index 0} and \textbf{-stride 2 -index 1} respectively.

\section{Copyright}

This document has been placed in the public domain.

\section{Colophon}

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