Talk:ParseString2List

From Second Life Wiki
Revision as of 18:56, 1 May 2010 by Strife Onizuka (talk | contribs) (→‎How it works: new section)
Jump to navigation Jump to search

Hi Strife,

you did a really good job with this contribution. I just added a description of this script to 'LSL Script Library' section in Category 'LSL Library', but stumbled over this entry's name.

Why didn't you just name it 'ParseString2List' according to the standard naming conventions for functions?

Greetz --Huney Jewell 04:02, 18 September 2007 (PDT)

Not really sure, was pretty tired by the time I made that contribution. The function naming standard is a bit informal. Seemed like a good idea at the time... which was after having spent many hours on a jet. I wrote it and posted it while I should have been packing for my trip last week, thanks for putting it in the library. -- Strife Onizuka 21:22, 18 September 2007 (PDT)

Strife, maybe you misunderstood. What I'd like to say, is just concerning the name of this entry (not it's function): 'Parse String To List' instead of 'ParseString2List' as usual for LSL Functions.

Greetz --Huney Jewell 01:39, 19 September 2007 (PDT)

Ah. In that Light it seems like a good idea to sync them. I'll move the pages. -- Strife Onizuka 11:04, 19 September 2007 (PDT)

Optimized

I wrote an optimized version for kicks, it should work but I haven't tested it yet. -- Strife Onizuka

Tested and posting on main page. -- Strife Onizuka 16:29, 19 September 2007 (PDT)

How it works

Here is a break down of how this function works (the source is highly optimized and obscures the methods used)

Steps
  1. Set the initial value of index to the first character in the string.
  2. Generate a list that contains the first occurrence of each separator and spacer (along with a pointer back to the spacer/separator).
  3. Sort the list by first occurrence.
  4. Pop the first item off the list. If the occurrence is before index goto Step 7
  5. Add the preceding non-spacer/separator text to the output list. If it is a spacer, add the spacer to the output list too.
  6. Advance the index pointer to the first character after the spacer/separator.
  7. Find the next occurrence of the spacer/separator and if it exists push it onto the far end of the list.
  8. Goto step 3 if spacer/separator occurrence list is not empty.
  9. Return the output list with the addition of any remaining text
Optimizations
  • Instead of using a strided list containing the spacer/separator and an integer we use just a single integer. The low bits are the index of the spacer/separator, the high bits are the occurrence position. This has the added benefit that it solves the problem of ensuring the proper behavior when collisions happen. The low bits restore the original order when collisions occur.
  • While it would be easy to add a special loop for the purpose of checking the following entries in the list to see if their occurrence indexes are now invalid (due to being less than index) it would require more code. The runtime speed gained needs to be balanced against the size requirements of the code.

-- Strife (talk|contribs) 01:56, 2 May 2010 (UTC)