TIP #351: Add Striding Support to lsearch

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

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

[Index] [History] [HTML Format] [Source Format] [LaTeX Format] [Text Format] [XML Format] [*roff Format (experimental)] [RTF Format (experimental)]