TIP #351: Add Striding Support to lsearch
_____________________________________________________________________________
TIP:	351
Title:	Add Striding Support to lsearch
Version:	$Revision: 1.19 $
Authors:	Peter da Silva <peter@taronga.com>
	Donal K. Fellows <donal.k.fellows@manchester.ac.uk>
	Harald Oehlmann <harald.oehlmann@elmicron.de>
	Andreas Leitgeb <avl@logic.at>
State:	Draft
Type:	Project
Tcl-Version:	8.7
Vote:	Pending
Created:	Thu Jul 09 00:00:00 UTC 2009
Abstract
This TIP allows the searching of lists that are grouped into collections of several elements.
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 foreach and array get, and this is strengthened further with dictionaries [111] and striding sorts [326]. However, there is currently no facility for searching such lists; this TIP proposes fixing this.
Proposed Change
We propose adding a -stride option to lsearch, by exact analogy with the option added to lsort in [326], whose semantics it should closely match.
If -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 Conceptual Backround below).
The first element of -index is used to seach for an item of the group.
The option -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 grpSize, which in turn must be at least 2.
Conceptual Backround
Striding equivalent to first level of nested lists
The striding within the list is seen as the first level of list nesting. E.g.
Nested list:
set deep 1 a A 2 b B 3 c C
Flat strided list: 
set flat 1 a A 2 b B 3 c C
Functions should operate the same way on both representation, with the only difference, that -stride 3 must be specified in the second case.
Unfortunately, the current implementation of lsort is not doing this. It interpretes -index "" as -index 0:
% 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
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 -subindices is given and a non-empty argument for -index, then the group-start and index-into-group are added up. This gives compatibility with lindex, as in the no-stride case.
Examples
In these examples, the variable kvlist holds the key-value list:
set kvlist K1 V1 K2 V1 K1 K1
Example 1: find keys even if they exist multiple times:
% lsearch -all -stride 2 -index 0 -exact $kvlist K1
0 4
Example 2: find existance of a value:
% lsearch -all -stride 2 -index 1 -exact $kvlist V1
0 2
Remark that the indexes of the first group elements are returned. The real values are at "result+index" eq 1 3.
Example 3: extract a sub-kv-list starting from key K2:
% lrange $kvlist [lsearch -stride 2 -index 0 -exact $kvlist K2] end
K2 V1 K1 K1
Example 4: find a group within a list:
% lsearch -stride 2 -exact $kvlist K2 V1
2
Example 5: find in combined strided and nested list
% lsearch -stride 2 -index 1 1 -exact\par        K0 V0.0 V0.1 K1 V1.0 V1.1\par        V1.1
2
Example 6: subindices with strided list:
% 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
to be consisten with:
% 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
Copyright
This document has been placed in the public domain.
_____________________________________________________________________________
Colophon
TIP AutoGenerator - written by Donal K. Fellows