TIP: 351 Title: Add Striding Support to lsearch Version: $Revision: 1.19 $ Author: Peter da Silva Author: Donal K. Fellows Author: Harald Oehlmann Author: Andreas Leitgeb State: Draft Type: Project Vote: Pending Created: 09-Jul-2009 Post-History: Tcl-Version: 8.7 ~ 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 [111] and striding sorts [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 [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.