TIP #351 Version 1.6: Add Striding Support to lsearch

This is not necessarily the current version of this TIP.

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 TIP #111 and striding sorts TIP #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 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). No specified index option or an index option with the empty list is equivalent of an index value of 0.

When lsearch is returning indices, it should return the indices of 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.

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 -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

Alternate propositions

Don't use option -index, but -groupindex as striding group index. In lsort, -index has two meanings: striding group index and nested group index. As a compatibility to lsort, this is specified here the same way. It might be clearer to separate the two functionalities.

Search sublists in list groups: There might be an option -grouplength to search a sublist of the given length within the list group. Nevertheless, this is out of the scope of this TIP

Copyright

This document has been placed in the public domain.

This is not necessarily the current version of this TIP.