TIP: | 351 |

Title: | Add Striding Support to lsearch |

Version: | $Revision: 1.19 $ |

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> Andreas Leitgeb <avl at logic dot at> |

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

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

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.

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

This document has been placed in the public domain.

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