TIP 127: Add an -index Option to [lsearch]

Login
Author:         Michael Schlenker <[email protected]>
State:          Final
Type:           Project
Vote:           Done
Created:        26-Feb-2003
Post-History:   
Tcl-Version:    8.5
Tcl-Ticket:     693836

Abstract

Matching the lsort functionality a -index option should be added to the lsearch command to make searching lists in list easier. The lsort -index and the lsearch -index options should accept list style indices like lindex and lset do. This TIP proposes such added options.

Specification

Under this proposal the syntax of the lsearch is to be modified to accept two extra options.

The -index option:

The lsort -index option would get enhanced with multiple index support.

    lsearch ?-index index? 

The -index option should work similar to the -index option in the lsort command.

If this option is specified, each of the elements of list must itself be a proper Tcl sublist. Instead of searching based on whole sublists, lsearch will extract the index'th element from each sublist and search based on the given element. The keyword end is allowed for the index to search on the last sublist element, and end-index searches on a sublist element offset from the end. For example,

    lsearch -integer -index 1 {{First 24} {Second 18} {Third 30}} 18

returns 1, and

    lsearch -index end-1 {{a 1 e i} {b 2 3 f g} {c 4 5 6 d h}} d

returns 2.

The index given to lsearch -index and lsort -index may be either a single scalar index as in the current lsort implementation or the argument to -index may be a list of scalar indices (similar, but not exactly like the lset/lindex multiple indices). The -index option causes lsearch and lsort to extract the item for searching or sorting comparision from the list element by using in effect lindex $element $index.

For example:

    set record {
        {
          {James Dean} {Musician} {some other data}
        }
        {
          {Elvis Presley} {Musician} {some more data}
        }
     }

   lsearch -index {0 0} $record "Elvis"

returns 1.

   lsort -dictionary -decreasing -index {0 1} $record

returns {{{Elvis Presley} {Musician} {some more data}} {{James Dean} {Musician} {some other data}}}.

Note: The following example is invalid, -index only takes a list as argument, unlike lset and lindex, that take either a list or multiple arguments, that get concatenated by the command.

 lsearch -index 1 1 $record Presley

The -subindices option:

The -subindices option should be added only to the lsearch command as a convenience shortcut. It is only a valid option if the -index option is also used.

If -subindices is given, lsearch should return a list of indices that can be used directly by lindex or lset to manipulate the element used for searching, instead of the top level element of the list.

If -subindices and -inline are specified at the same time, the command returns the value instead of the index.

example:

 lsearch -subindices -index {0 0} $record Elvis

returns {1 0 0}.

If no -all option is specified, this is the same as doing:

 concat [lsearch -index {0 0} $record Elvis] [list 0 0]

Rationale

Lists containing one or more level of sublists are a common technique to simulated complex data structures like matrices or records, or for results from database queries. The lsort command was enhanced with the -index option for this case, to handle sorting on sublist keys.

The lsearch command does not have this functionality yet, one has to use foreach and lindex to loop over the list one by one.

Multiple indices for the -index option to both lsearch and lsort should be added, to make the option more similar to lset and lindex style indices.

The -subindices option is a convenience option to make constructs like this example work well:

 foreach item [lsearch -all -subindices -index {0 0} $record bla] {
         lset record $item bar
 }

Without the subindices option it could be written as:

 foreach item [lsearch -all -index $idx $record bla] {
         lset record [concat $idx $item] bar
 }

Reference Implementation

A reference implementation exists, see the files attached to the Tcl Patch 693836 on SourceForge. http://sf.net/tracker/?func=detail&atid=310894&aid=693836&group\_id=10894

The reference implementation isn't honouring the -inline option if given in conjuction with -subindices, at the moment.

Copyright

This document has been placed in the public domain.