I sometimes need to assemble a list of unique values, while preserving
the order of the list. So when creating the list, I append a value to
a list, but only if the value isn't already on the list. In Tcl,
usually I do this with the bb_lappend_uniq procedure below. It uses a
helper Tcl array to maintain the state info of what values are already
on the list - presumably this is faster than calling lsearch every
time.
But does anyone have something to generate the same unique Tcl list,
but implemented in C? Or something else similar?
Reason I care, is I have lots of key/value pairs, and each key is made
up several strings concatenated together. For discussion, we'll
assume each key has the structure "ABCD". And what I need, is a list
of all the unique SUB-keys "AB". Right now, I do that in Tcl. But
that extra pass of grubbing through all my keys is dominating my
execution time - and it's too slow. (There's regexp involved, etc.)
But, I'm generating all those keys and sub-keys myself in my C code,
so rather than tuning my Tcl, the obvious thing to do is to assemble
my unique list of subkeys right there in C, and thus avoid having to
iterate through all my data an extra time in Tcl.
Note I still want to end up with a Tcl list of unique sub-keys, I just
want the implementation done in C. It would be extra nice if I could
pass in a Tcl array or NSV name from Tcl to maintain the state of
what's already on the list, because then I could pre-populate it if I
wanted to, in order to append to an already existing list, etc. But
that's frosting really, it'd be ok if the C code always starts with an
empty list and the state array/nav isn't accessible to anything
outside my C function.
Well, I've probably rambled on too long about something so simple, but
before I start implementing my simple solution (using Tcl_AppendResult
and a TclHashTable to maintain list state, I think), I figured I'd ask
if anyone else has already done it...
And of course, maybe somebody will point out some entirely different
and better way to do this, instead. :)
ad_proc bb_lappend_uniq {{
-key_prefix {}
} list_name item_name luniq_state_arr_name} {
Appends an item to a list <em>only</em> if that item is not already
on the list. In order to avoid doing an lsearch of the whole list
for every single lappend, takes a helper state array which is
<em>must</em> alrady have an array variable defined for each item
already on the list, if the list is not empty.
} {
upvar 1 $list_name L
upvar 1 $item_name item
upvar 1 $luniq_state_arr_name arr
if { [info exists arr("${key_prefix}${item}")] } {
# Do nothing, this left_key is already on the list.
} else {
lappend L $item
set arr("${key_prefix}${item}") 1
}
}
ad_proc bb_luniq {L} {
Returns a list with all duplicates removed, and keeping the
original order.
<p>
Code taken from the
<a href="http://mini.net/tcl/526.html";>Tcl'ers Wiki</a>
} {
set t {}
foreach i $L {if {[lsearch -exact $t $i]==-1} {lappend t $i}}
return $t
}
--
Andrew Piskorski <[EMAIL PROTECTED]>
http://www.piskorski.com
