string lexical comparison question

I'm writing a nifty little color chooser script. I started out with a nice strided list:

list colors = [
    "amber", <255,191,0>,
    "amethyst", <153,102,204>,
    "asparagus", <123,160,91>,
   ...
];

I built the list sorted in alphabetical order. It's fairly long, so for efficiency, I decided to write a binary search algorithm to look up colors in it:

integer STRIDE = 2;

integer binarySearch(list l, string targ, integer left, integer right)
{
    integer mid;
    integer lf = left;   // not sure if LSL allows modifying arguments, so we'll copy it
    integer rt = right; // ditto
    string myVal;

    while (lf <= rt)
    {
        mid = ((rt-lf) / 2) + lf;
        
        mid -= (mid % STRIDE);  // stay on first element of a 'row' in the strided list
        
        myVal = llList2String(l, mid);
        
        if (myVal == targ)
        {
            return mid;
        }
        
        if (myVal < targ)
        {
            rt = mid - STRIDE;
        }
        else
        {
            lf = mid + STRIDE;
        }
    }
    return -1;
}

All was going well until I got to the line: "if (myVal < targ)", when the LSL compiler complained "ERROR : Type Mismatch". Both myVal and targ are declared as string, so I figure it must be complaining about "<" not accepting string arguments.

I verified that (myVal == targ) works as expected, and (myVal != targ) works as well, but inequality operators appear to not be supported. Looking around the LSL wiki, I don't see any way to pull characters out of a string (certainly myVal doesn't work), so it doesn't look as if I can even do a for() loop to compare the strings -- i.e., write my own strcmp().

I thought about putting my target into a list and using llListFindList(), but I don't know how efficient it is (since it doesn't assume the list is sorted, I figure it has to do a linear search), and it isn't really set up to handle strided lists, either.

Am I doomed to do inefficient linear searches of my lists?

Salvador

http://secondlife.com/badgeo/wakka.php?wakka=llGetSubString with start and end parameter equal.

No idea if with all the extra work it'd actually turn out faster -- someone posted a while ago LSL is executed at 'one function call per simulation frame' speed, which would suggest the higher level functions you can use to reduce overall number of them, the more mileage you'll get out of it o.O;

If choosing a color using a list is all you need...

/54/c4/112507/1.html

See my post there.

*hugs*
Sheila!

I just ran into this myself I'm amazed that SL doesn't actually have string comparison!

Still, as of the current LSL version, you can use

integer Search(list data, integer stride, string value)
{
     return llListFindList( llList2ListStrided(data, 0, -1, stride) , [value]);
}

llListFindList is probably linear search since it doesn't require that its argument be sorted, but given the memory restrictions of LSL it's quite likely you simply cannot have enough strings to make linear search significantly worse than binary anyway

No need to stride the list on a linear search, just do something like:

integer pos = llListFindList( colors, [ searchCol ] );
if ( pos == -1 )
{
    llOwnerSay( searchCol + " color not found" );
}
else
{
    color = llList2Vector( colors, pos + 1 ) / 255.0;
}