This is not necessarily the current version of this TIP.This is not necessarily the current version of this TIP.
| TIP: | 351 |
| Title: | Add Striding Support to lsearch |
| Version: | $Revision: 1.5 $ |
| Authors: |
Peter da Silva <peter at taronga dot com> Donal K. Fellows <donal dot k dot fellows at manchester dot ac dot uk> Harald Oehlmann <harald dot oehlmann at elmicron dot de> |
| State: | Draft |
| Type: | Project |
| Tcl-Version: | 8.7 |
| Vote: | Pending |
| Created: | Thursday, 09 July 2009 |
This TIP allows the searching of lists that are grouped into collections of several elements.
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 TIP #111 and striding sorts TIP #326. However, there is currently no facility for searching such lists; this TIP proposes fixing this.
We propose adding a -stride option to lsearch, by exact analogy with the option added to lsort in TIP #326, whose semantics it should closely match.
If -stride is supplied, the list will be treated as consisting of groups of grpSize elements, and the groups will be searched for either the first element or, if the -index option is used, by the element within each group given by the first index passed to -index (which is then ignored by -index).
When lsearch is returning indices, it should return the indices of the first element of the striding group(s) that is/are being indicated.
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 -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 -exact $kvlist K2] end K2 V1 K1 K1
This document has been placed in the public domain.
This is not necessarily the current version of this TIP.