# TIP 351: Add Striding Support to lsearch
	Author:         Peter da Silva <peter@taronga.com>
	Author:         Donal K. Fellows <donal.k.fellows@manchester.ac.uk>
	Author:         Harald Oehlmann <harald.oehlmann@elmicron.de>
	Author:         Andreas Leitgeb <avl@logic.at>
	State:          Final 
	Type:           Project
	Vote:           Done
	Created:        09-Jul-2009
	Post-History:   
	Tcl-Version:    8.7
	Tcl-Branch:     tip-351
-----

# 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]](111.md) and striding sorts [[326]](326.md). 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]](326.md), 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 if 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. If **-stride** is given and not 1, **-index** defaults to 0.

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 1. A **-stride** of 1 is the default and indicates no grouping.

With **-inline**, the return value is a strided list if length **grpSize** (or multiple of, with **-all**).

# 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

For symmetry this TIP proposes the same behaviour for lsearch.

## 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 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 5: 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

# Implementation

Is available in tip-351 branch.

# Copyright

This document has been placed in the public domain.

