Author: Peter da Silva <peter@taronga.com>
Author: Donal K. Fellows <donal.k.fellows@manchester.ac.uk>
Author: Harald Oehlmann <harald.oehlmann@elmicron.de>
Author: Andreas Leitgeb <avl@logic.at>
State: Final
Type: Project
Vote: Done
Created: 09-Jul-2009
Post-History:
Tcl-Version: 8.7
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 if 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. If -stride is given and not 1, -index defaults to 0.
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 1. A -stride of 1 is the default and indicates no grouping.
With -inline, the return value is a strided list if length grpSize (or multiple of, with -all).
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
For symmetry this TIP proposes the same behaviour for lsearch.
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 in combined strided and nested list
% lsearch -stride 2 -index {1 1} -exact\
{K0 {V0.0 V0.1} K1 {V1.0 V1.1}}\
V1.1
2
Example 5: 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
Implementation
Is available in tip-351 branch.
Copyright
This document has been placed in the public domain.