Difference between revisions of "Talk:Array"
Asha Vultee (talk | contribs) |
|||
(5 intermediate revisions by 2 users not shown) | |||
Line 496: | Line 496: | ||
:That is going to be a very slow implementation. You would be better off using [[llListFindList]]. -- [[User:Strife Onizuka|Strife Onizuka]] 13:55, 12 November 2007 (PST) | :That is going to be a very slow implementation. You would be better off using [[llListFindList]]. -- [[User:Strife Onizuka|Strife Onizuka]] 13:55, 12 November 2007 (PST) | ||
::[[llListFindList]] may provide a faster method to locate a given value within a list, however implementing an associative array using llListFindList would yield a crippled associative array. From the docs: "Returns an integer that is the index of the first instance of test in src." Thus, for a given array [ k1 => v1, k2 => v2, k3 => v3 ] you would not be able to have more than one vx with the same value, or a vx with the same value as a kx. You couldn't use this simple data set [ 3 => 1, 2 => 1, 1 => 1 ] without adding special cases or a more complex storage structure, which may cancel any benefit gained by using llListFindList. --[[User:Asha Vultee|Asha Vultee]] 10:59, 19 November 2007 (PST) | ::[[llListFindList]] may provide a faster method to locate a given value within a list, however implementing an associative array using llListFindList would yield a crippled associative array. From the docs: "Returns an integer that is the index of the first instance of test in src." Thus, for a given array [ k1 => v1, k2 => v2, k3 => v3 ] you would not be able to have more than one vx with the same value, or a vx with the same value as a kx. You couldn't use this simple data set [ 3 => 1, 2 => 1, 1 => 1 ] without adding special cases or a more complex storage structure, which may cancel any benefit gained by using llListFindList. --[[User:Asha Vultee|Asha Vultee]] 10:59, 19 November 2007 (PST) | ||
:::You use a buffer and trim the found entries off the buffer as you parse it. Take a look at [[Library_Combined_Library#Replace|str_replace]] for an example of this sort of logic in action. I was working on an ESL version for the Combined Library but it turned out to be very annoying having to deal with strides; ended up having writing specialized versions for stride and non-stride situations; that doesn't even touch on typed-associative arrays. As it stands, you are looking at O^2 for runtime in all situations, if you use llListFindList, in a worst case scenario it is between 2*O and 4*O. -- [[User:Strife Onizuka|Strife Onizuka]] 13:45, 19 November 2007 (PST) | |||
== Life would be grand with real arrays == | |||
I know it doesn't sound like LSL will ever be capable of working with real arrays, and yes it would mean a major rewrite of LSL (so?), and the valiant efforts to implement ''something'' (above) shows the basic displeasure with lists that wears down our will to go on .... But go on we must, and if arrays and writing-to-notecards was ever implemented, it would surely mark the Second Coming and (Eternal) Life of Our Savior (aptly enough commemorated this day in Christendom). So we must humble ourselves to the sad reality that LSL will stay a Pinocchio language, always yearning, but never achieving true language-hood, and that we cannot wait for such a thing as arrays (writing-to-notecards?, true O-O capabilities?...nope), not in this Second Life, surely not in Real Life, and definitely not in Life Eternal, where the Divine Programmer has everything fully coded, in perfect O-O code, with infinite RAM, infinite storage, and infinite parallel processing. All that is left to us toiling LSL'ers is to wax poetic here, and struggle with the eternal bondage of pushing LSL to its frail limits. I love SL, I'm here for the long haul, and I will understand if this comment is considered too demoralizing to merit a continued existence herein. Amen. --[[User:Jeri Zuma|Jeri Zuma]] 15:43, 23 March 2008 (PDT) , Easter Sunday, 2008. |
Latest revision as of 15:43, 23 March 2008
Here is an elementary implementation of an associative array using the list datatype as a primitive storage mechanism.
//////////////////////////////////////////////////////////////////////////////////////////// // Asha's Associative Array // // ______Release 0.1______ // Basic functionality. // Copy this code to your script // and use the av_* functions to access // // TO SAVE DATA: // av_store_assoc( [ key, value ] ); // // TO REPLACE DATA: (currently, this is a synonum for av_store_assoc) // av_replace_assoc( [ key, value ] ); // // TO REMOVE DATA: // av_remove_assoc( [ key, UNUSED ] ); // // TO RETRIEVE DATA: // av_assoc_get_by_key( [ key, UNUSED ] ); // av_assoc_get_by_val( [ UNUSED, val ] ); // // CAUTION: av_assoc_get_by_val() may return a list of more than 2 elements, where the list is // defined as [ key1, val1, key2, val2 ... keyn, valn ] // // TO WHACK THE LIST: // av_reset_assoc( string reserved ); // // CAUTION: in order to maintain API compatability with future releases, use // av_* functions instead of calling any LSL list functions or operators directly. //////////////////////////////////////////////////////////////////////////////////////////// // START COPYING HERE list av_assoc_list_storage; integer av_assoc_list_width = 3; integer av_index_offset = 0; integer av_assoc_key_offset = 1; integer av_assoc_val_offset = 2; integer av_assoc_list_id = 0; av_reset_assoc( string rsvd ) { av_assoc_list_storage = []; } av_store_assoc( list nvpair ) { integer i; integer j; integer matched; float _currkey_float; float _currval_float; integer _currkey_integer; integer _currval_integer; string _currkey_string; string _currval_string; key _currkey_key; key _currval_key; vector _currkey_vector; vector _currval_vector; rotation _currkey_rotation; rotation _currval_rotation; integer key_type; integer inkey_type; inkey_type = llGetListEntryType( nvpair, 0 ); matched = 0; j = llGetListLength( av_assoc_list_storage ); if ( 0 == j ) { av_assoc_list_storage += (av_assoc_list_id++); av_assoc_list_storage += nvpair; return; } for ( i = 0; i < j; i+= av_assoc_list_width ) { key_type = llGetListEntryType( av_assoc_list_storage, i+av_assoc_key_offset ); if ( key_type == inkey_type ) { if ( key_type == TYPE_INTEGER ) { _currkey_integer = llList2Integer( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_integer = llList2Integer( nvpair, 0 ); if ( _currkey_integer == _currval_integer ) { matched = 1; } } else if ( key_type == TYPE_STRING ) { _currkey_string = llList2String( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_string = llList2String( nvpair, 0 ); if ( _currkey_string == _currval_string ) { matched = 1; } } else if ( key_type == TYPE_VECTOR ) { _currkey_vector = llList2Vector( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_vector = llList2Vector( nvpair, 0 ); if ( _currkey_vector == _currval_vector ) { matched = 1; } } else if ( key_type == TYPE_ROTATION ) { _currkey_rotation = llList2Rot( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_rotation = llList2Rot( nvpair, 0 ); if ( _currkey_rotation == _currval_rotation ) { matched = 1; } } else if ( key_type == TYPE_FLOAT ) { _currkey_float = llList2Float( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_float = llList2Float( nvpair, 0 ); if ( _currkey_rotation == _currval_rotation ) { matched = 1; } } else if ( key_type == TYPE_KEY ) { _currkey_key = llList2Key( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_key = llList2Key( nvpair, 0 ); if ( _currkey_key == _currval_key ) { matched = 1; } } if ( matched ) { av_assoc_list_storage = llListReplaceList( av_assoc_list_storage, nvpair, i+1, i+2 ); return; } } } av_assoc_list_storage += (av_assoc_list_id++); av_assoc_list_storage = av_assoc_list_storage + nvpair; } av_replace_assoc( list nvpair ) { av_store_assoc( nvpair ); } av_remove_assoc( list nvpair ) { integer i; integer j; integer matched; float _currkey_float; float _currval_float; integer _currkey_integer; integer _currval_integer; string _currkey_string; string _currval_string; key _currkey_key; key _currval_key; vector _currkey_vector; vector _currval_vector; rotation _currkey_rotation; rotation _currval_rotation; integer key_type; integer inkey_type; inkey_type = llGetListEntryType( nvpair, 0 ); matched = 0; j = llGetListLength( av_assoc_list_storage ); if ( 0 == j ) { return; } for ( i = 0; i < j; i+= av_assoc_list_width ) { key_type = llGetListEntryType( av_assoc_list_storage, i+av_assoc_key_offset ); if ( key_type == inkey_type ) { if ( key_type == TYPE_INTEGER ) { _currkey_integer = llList2Integer( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_integer = llList2Integer( nvpair, 0 ); if ( _currkey_integer == _currval_integer ) { matched = 1; } } else if ( key_type == TYPE_STRING ) { _currkey_string = llList2String( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_string = llList2String( nvpair, 0 ); if ( _currkey_string == _currval_string ) { matched = 1; } } else if ( key_type == TYPE_VECTOR ) { _currkey_vector = llList2Vector( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_vector = llList2Vector( nvpair, 0 ); if ( _currkey_vector == _currval_vector ) { matched = 1; } } else if ( key_type == TYPE_ROTATION ) { _currkey_rotation = llList2Rot( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_rotation = llList2Rot( nvpair, 0 ); if ( _currkey_rotation == _currval_rotation ) { matched = 1; } } else if ( key_type == TYPE_FLOAT ) { _currkey_float = llList2Float( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_float = llList2Float( nvpair, 0 ); if ( _currkey_rotation == _currval_rotation ) { matched = 1; } } else if ( key_type == TYPE_KEY ) { _currkey_key = llList2Key( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_key = llList2Key( nvpair, 0 ); if ( _currkey_key == _currval_key ) { matched = 1; } } if ( matched ) { av_assoc_list_storage = llDeleteSubList( av_assoc_list_storage, i, i+2 ); return; } } } } list av_assoc_get_by_key( list nvpair ) { integer i; integer j; integer matched; float _currkey_float; float _currval_float; integer _currkey_integer; integer _currval_integer; string _currkey_string; string _currval_string; key _currkey_key; key _currval_key; vector _currkey_vector; vector _currval_vector; rotation _currkey_rotation; rotation _currval_rotation; integer key_type; integer inkey_type; inkey_type = llGetListEntryType( nvpair, 0 ); matched = 0; j = llGetListLength( av_assoc_list_storage ); if ( 0 == j ) { return( [] ); } for ( i = 0; i < j; i+= av_assoc_list_width ) { key_type = llGetListEntryType( av_assoc_list_storage, i+av_assoc_key_offset ); if ( key_type == inkey_type ) { if ( key_type == TYPE_INTEGER ) { _currkey_integer = llList2Integer( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_integer = llList2Integer( nvpair, 0 ); if ( _currkey_integer == _currval_integer ) { matched = 1; } } else if ( key_type == TYPE_STRING ) { _currkey_string = llList2String( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_string = llList2String( nvpair, 0 ); if ( _currkey_string == _currval_string ) { matched = 1; } } else if ( key_type == TYPE_VECTOR ) { _currkey_vector = llList2Vector( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_vector = llList2Vector( nvpair, 0 ); if ( _currkey_vector == _currval_vector ) { matched = 1; } } else if ( key_type == TYPE_ROTATION ) { _currkey_rotation = llList2Rot( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_rotation = llList2Rot( nvpair, 0 ); if ( _currkey_rotation == _currval_rotation ) { matched = 1; } } else if ( key_type == TYPE_FLOAT ) { _currkey_float = llList2Float( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_float = llList2Float( nvpair, 0 ); if ( _currkey_rotation == _currval_rotation ) { matched = 1; } } else if ( key_type == TYPE_KEY ) { _currkey_key = llList2Key( av_assoc_list_storage, i+av_assoc_key_offset ); _currval_key = llList2Key( nvpair, 0 ); if ( _currkey_key == _currval_key ) { matched = 1; } } if ( matched ) { list l = llList2List( av_assoc_list_storage, i+1, i+2 ); return( l ); } } } return( [] ); } list av_assoc_get_by_val( list nvpair ) { integer i; integer j; integer matched; list ret; float _currkey_float; float _currval_float; integer _currkey_integer; integer _currval_integer; string _currkey_string; string _currval_string; key _currkey_key; key _currval_key; vector _currkey_vector; vector _currval_vector; rotation _currkey_rotation; rotation _currval_rotation; integer key_type; integer inkey_type; inkey_type = llGetListEntryType( nvpair, 1 ); matched = 0; j = llGetListLength( av_assoc_list_storage ); if ( 0 == j ) { return( [] ); } for ( i = 0; i < j; i+= av_assoc_list_width ) { key_type = llGetListEntryType( av_assoc_list_storage, i+av_assoc_val_offset ); if ( key_type == inkey_type ) { if ( key_type == TYPE_INTEGER ) { _currkey_integer = llList2Integer( av_assoc_list_storage, i+av_assoc_val_offset ); _currval_integer = llList2Integer( nvpair, 1 ); if ( _currkey_integer == _currval_integer ) { matched = 1; } } else if ( key_type == TYPE_STRING ) { _currkey_string = llList2String( av_assoc_list_storage, i+av_assoc_val_offset ); _currval_string = llList2String( nvpair, 1 ); if ( _currkey_string == _currval_string ) { matched = 1; } } else if ( key_type == TYPE_VECTOR ) { _currkey_vector = llList2Vector( av_assoc_list_storage, i+av_assoc_val_offset ); _currval_vector = llList2Vector( nvpair, 1 ); if ( _currkey_vector == _currval_vector ) { matched = 1; } } else if ( key_type == TYPE_ROTATION ) { _currkey_rotation = llList2Rot( av_assoc_list_storage, i+av_assoc_val_offset ); _currval_rotation = llList2Rot( nvpair, 1 ); if ( _currkey_rotation == _currval_rotation ) { matched = 1; } } else if ( key_type == TYPE_FLOAT ) { _currkey_float = llList2Float( av_assoc_list_storage, i+av_assoc_val_offset ); _currval_float = llList2Float( nvpair, 1 ); if ( _currkey_rotation == _currval_rotation ) { matched = 1; } } else if ( key_type == TYPE_KEY ) { _currkey_key = llList2Key( av_assoc_list_storage, i+av_assoc_val_offset ); _currval_key = llList2Key( nvpair, 1 ); if ( _currkey_key == _currval_key ) { matched = 1; } } if ( matched ) { ret += llList2List( av_assoc_list_storage, i+1, i+2 ); } } } return( ret ); } // STOP COPYING HERE //////////////////////////////////////////////////////////////////////////////////////////// default { state_entry() { llOwnerSay( "Asha's Associative Array Test Ready" ); } touch_start(integer total_number) { list l = [ 123, "Hello" ]; list m = [ 456, "Wassup" ]; list n = [ 789, "Yadda Yadda" ]; list o = [ 790, "Yadda Yadda" ]; list p = [ 791, "yadda YADDA" ]; av_store_assoc( l ); av_store_assoc( m ); av_store_assoc( l ); av_remove_assoc( l ); l = av_assoc_get_by_key( m ); llOwnerSay( llList2CSV( l ) ); av_store_assoc( n ); av_store_assoc( o ); av_store_assoc( p ); llOwnerSay( llList2CSV( av_assoc_get_by_val( [ "", "Yadda Yadda" ] ) ) ); } }
--Asha Vultee 12:11, 12 November 2007 (PST)
- That is going to be a very slow implementation. You would be better off using llListFindList. -- Strife Onizuka 13:55, 12 November 2007 (PST)
- llListFindList may provide a faster method to locate a given value within a list, however implementing an associative array using llListFindList would yield a crippled associative array. From the docs: "Returns an integer that is the index of the first instance of test in src." Thus, for a given array [ k1 => v1, k2 => v2, k3 => v3 ] you would not be able to have more than one vx with the same value, or a vx with the same value as a kx. You couldn't use this simple data set [ 3 => 1, 2 => 1, 1 => 1 ] without adding special cases or a more complex storage structure, which may cancel any benefit gained by using llListFindList. --Asha Vultee 10:59, 19 November 2007 (PST)
- You use a buffer and trim the found entries off the buffer as you parse it. Take a look at str_replace for an example of this sort of logic in action. I was working on an ESL version for the Combined Library but it turned out to be very annoying having to deal with strides; ended up having writing specialized versions for stride and non-stride situations; that doesn't even touch on typed-associative arrays. As it stands, you are looking at O^2 for runtime in all situations, if you use llListFindList, in a worst case scenario it is between 2*O and 4*O. -- Strife Onizuka 13:45, 19 November 2007 (PST)
- llListFindList may provide a faster method to locate a given value within a list, however implementing an associative array using llListFindList would yield a crippled associative array. From the docs: "Returns an integer that is the index of the first instance of test in src." Thus, for a given array [ k1 => v1, k2 => v2, k3 => v3 ] you would not be able to have more than one vx with the same value, or a vx with the same value as a kx. You couldn't use this simple data set [ 3 => 1, 2 => 1, 1 => 1 ] without adding special cases or a more complex storage structure, which may cancel any benefit gained by using llListFindList. --Asha Vultee 10:59, 19 November 2007 (PST)
Life would be grand with real arrays
I know it doesn't sound like LSL will ever be capable of working with real arrays, and yes it would mean a major rewrite of LSL (so?), and the valiant efforts to implement something (above) shows the basic displeasure with lists that wears down our will to go on .... But go on we must, and if arrays and writing-to-notecards was ever implemented, it would surely mark the Second Coming and (Eternal) Life of Our Savior (aptly enough commemorated this day in Christendom). So we must humble ourselves to the sad reality that LSL will stay a Pinocchio language, always yearning, but never achieving true language-hood, and that we cannot wait for such a thing as arrays (writing-to-notecards?, true O-O capabilities?...nope), not in this Second Life, surely not in Real Life, and definitely not in Life Eternal, where the Divine Programmer has everything fully coded, in perfect O-O code, with infinite RAM, infinite storage, and infinite parallel processing. All that is left to us toiling LSL'ers is to wax poetic here, and struggle with the eternal bondage of pushing LSL to its frail limits. I love SL, I'm here for the long haul, and I will understand if this comment is considered too demoralizing to merit a continued existence herein. Amen. --Jeri Zuma 15:43, 23 March 2008 (PDT) , Easter Sunday, 2008.