tcl lsearch on list of list

Question

There is a list of list in Tcl.

set somelist {{aaa 1} {bbb 2} {ccc 1}}

How to search the list's element which first item is "bbb"?

I tried this way but it doesn't work.

lsearch $somelist "{bbb *}"

Thanks.

Solution 1

Use -index, it's designed for exactly this case. As ramanman points out, when you have a list, use list procedures. Have you thought about what happens if you have multiple matches?

In your case, I would just do this:

% lsearch -index 0 -all -inline $somelist bbb
{bbb 2}
% lsearch -index 0 -all $somelist "bbb"
1
% lsearch -index 0 -all $somelist "ccc"
2

You use -index of 0 to specify that you are interested in the first index of the outer list. -all returns all results. And you can use -inline if you just want the value of list element that matches, omit it if you just want the index of the matching element.

Solution 2

If you're searching through the first sublist of each list member, the -index option is for you:

set pos [lsearch -index 0 -exact $somelist "bbb"]

The -index 0 option tells the lsearch comparison engine to take the first element of each item (i.e., very much like lindex $item 0) before doing any other comparison operations (-exact comparison in my example). You can even supply a list of indices to drill down into a specific sub-sub-list, etc.

(NB: What lsearch does not do is perform a recursive search through all sublists of a list. The issue is that there's formally no way to know when you've got to the leaves.)

---

EDIT:
If you have an old version of Tcl, you might not have the -index option. In that case, you use manual iteration:

proc findElement {lst idx value} {
    set i 0
    foreach sublist $lst {
        if {[string equal [lindex $sublist $idx] $value]} {
            return $i
        }
        incr i
    }
    return -1
}
set pos [findElement $somelist 0 "bbb"]

(I dislike using glob matching for this sort of thing. It also doesn't work nearly so well when you're looking for an element that isn't the first or the last in a list.)

Solution 3

In Tcl 8.5, but not in Tcl 8.4:

set somelist {{aaa 1} {bbb 2} {ccc 1}}
lsearch -index 0 $somelist bbb; # Returns either the index if found, or -1 if not

The -index flags specifies which index of the sub-list to search: 0 searches for aaa, bbb, ... While 1 searches for 1, 2, 1...

In Tcl 8.4, use the keylget command from the Tclx package:

package require Tclx

set somelist {{aaa 1} {bbb 2} {ccc 1}}
set searchTerm "bbb"
if {[keylget somelist $searchTerm myvar]} {
    puts "Found instance of $searchTerm, value is: $myvar"
}

The keylget command in this syntax returns 1 if found, 0 if not. The value next to bbb (2) is then placed in the variable myvar. Note that there should be no dollar sign ($) in front of somelist in the keylget command.

Update

In fact, the -index flag allows searching for arbitrary depth as illustrated by this code:

package require Tcl 8.5 

# For each sub-list:
# - index 0 = the user's name
# - index 1 = a list of {home value}
# - index 2 = a list of {id value}
# - index 3 = a list of {shell value}
set users {
    {john {home /users/john} {id 501} {shell bash}}
    {alex {home /users/alex} {id 502} {shell csh}}
    {neil {home /users/neil} {id 503} {shell zsh}}
}   

# Search for user name == neil
set term neil
puts "Search for name=$term returns: [lsearch -index 0 $users $term]"; # 2

# Search for user with id = 502. That means we first looks at index
# 2 for {id value}, then index 1 for the value
set term 502
puts "Search for id=$term returns: [lsearch -index {2 1} $users $term]"; # 1

# Search for shell == sh (should return -1, not found)
set term sh
puts "Search for shell=$term returns: [lsearch -index {3 1} $users $term]"; # -1

Solution 4

Use the "-index" option of [lsearch].

Solution 5

If you want to search it the way you are trying to, you can use the glob option:

lsearch -glob $somelist "{bbb *}"

If you those really are lists of lists, and you are looking for matching the first sublist with a first element of bbb you could also do:

foreach sublist $somelist {   
  foreach {name value} $sublist {
    if {[string eq $name "bbb"]} {
      #do interesting stuff here
    }
  }
}

The details of that would of course depend on the details of your list of lists (if you actually have only two elements of your nested list, or if it could be more deeply nested.

View more solutions

Comments

[Kannan Thangadurai]

The problem with doing it the way you mention is that you say you have a list of lists. Using lsearch is a good way to search lists. But, then using a string match on the nested lists brings up a variety of edge cases. In general, if you know it is a list, use list operations on it. Doing a wildcard or glob match is a string operation. You can get away with it if your inputs are well defined, but it will come back to bite you in the general case. If you know a list element is a list, treat it as a list and not a string.

[MKo]

Can you bring an example what "-index" option does?

[MKo]

The -glob option is default for lsearch. And the problem was in double quotes. lsearch $somelist {bbb *} works.

[Donal Fellows]

Always put braces around your if conditions; enables compilation and is (in general) safer too.

[Hai Vu]

Note that the -index option is introduced in version 8.5, thus not available in version 8.4, which is what we have at work.

[Donal Fellows]

@Hai: Added how to handle it. (It's not very elegant, which is why -index was added after all.)