TIP #351 Version 1.8: 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. 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

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.

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\
        {K0 {V0.0 V0.1} K1 {V1.0 V1.1}}\
        V1.1
2

Copyright

This document has been placed in the public domain.

This is not necessarily the current version of this TIP.