Sparse array - table with variable length records preserving field/element types

[Mollymews]

a conversation about sparse arrays here

led to the topic about the inefficiencies of using strings to store variable length records in the form

list table =
[
   "a|b|c",
   "d|e",
   "f|g|h|i",
   "y|z"
]

which prompted me to have a play.  A example of a general purpose 2-dimensional sparse array as a table with variable length records that preserve list element types

i think is ok, but if it breaks I will fix it if you let me know

fix:  ACTION_FIND. Was finding last occurrence of pattern, not the first

/*
   example of
     general purpose sparse array table with helper functions
     in row column format where a row (sublist) can have any number of elements (columns)
   
   row indexing is 0-based same as list 
   for negative indexing use: rowcount-1, rowcount-2,rowcount-3, etc
   
   usage examples in touch_start below
   
   fix: ACTION_FIND. Was finding last occurence of pattern, not the first
   
   placed in public domain
*/
 
integer ACTION_APPEND  = 0;   // table += [some,data]
integer ACTION_INSERT  = 1;   // llListInsertList
integer ACTION_REPLACE = 2;   // llListReplaceList
integer ACTION_DELETE  = 3;   // llDeleteSubList
integer ACTION_FIND    = 4;   // llListFindList 

list table;               // data table
list rows;                // pointers to 1st element of each row
integer currentrow = -1;  // updated on action. is -1 when table is empty
integer rowcount;         // = length of list rows
integer tablecount;       // = length of list table. - 

list fetch(integer row)   // llList2List
{   // fetch/get a list of elements (columns) in row
    if ((row > -1) & (row < rowcount))
    {
        integer e = tablecount - 1;
        if (row < rowcount - 1)
            e = llList2Integer(rows, row + 1) - 1;
        return llList2List(table, llList2Integer(rows, row), e);
    }
    else
       return [];  // return empty when row is out of bounds. bounds in [0 .. rowcount-1]       
}

integer action(integer act, integer row, list data)
{   // default to -1 fail / not found. OnSuccess return currentrow
    integer result = -1;   
    if (act == ACTION_APPEND)
    {   
        if (data) 
        {    
            rows += [tablecount];
            table += data;
            tablecount = llGetListLength(table);                 
            result = currentrow = ++rowcount;               
        }
    }
    else if ((row > -1) & (row < rowcount))  // row in bounds else fail
    {
        integer r = llList2Integer(rows, row);
        integer e = tablecount - 1;
   
        if (act == ACTION_DELETE)
        {              
            if (row < rowcount - 1)
                e = llList2Integer(rows, row + 1) - 1;
            else
                --currentrow;
            table = llDeleteSubList(table, r, e);
            rows = llDeleteSubList(rows, row, row);
            --rowcount;
            e = -(e - r + 1);
            result = currentrow;           
        }
        else if (data)  // fails when data is empty list
        {           
            if (act == ACTION_INSERT)
            {                
                table = llListInsertList(table, data, r);
                rows = llListInsertList(rows, [r], row++);
                ++rowcount;
                e = llGetListLength(data);
                result = currentrow;               
            }
            else if (act == ACTION_REPLACE)
            {
                if (row < rowcount - 1) 
                    e = llList2Integer(rows, ++row) - 1;   
                table = llListReplaceList(table, data, r, e);  
                e = llGetListLength(data) - 1 - (e - r);
                result = currentrow;
            } 
            else if (act == ACTION_FIND)
            { 
                if (row)  // can be memory expensive, but it does enable findNext 
                    e = llListFindList(llDeleteSubList(table, 0, r - 1), data);   
                else  // row = 0. search entire table
                    e = llListFindList(table, data); 
                if (~e) // not found when e = -1
                {   // get row number, disallow when found data pattern crosses row boundary
                    e += r;
                    integer continue = TRUE;
                    for (r = row; (r < rowcount) & continue; ++r)
                    {
                        integer ee = tablecount - 1;
                        if (r < rowcount - 1)
                            ee = llList2Integer(rows, r + 1);
                        if ((e >= llList2Integer(rows, r)) & (e < ee)) 
                        {   // note fetch is called. This could be calculated 
                            result = llListFindList(fetch(r), data); 
                            if (~result)
                            {   // found wholely in row
                                result = currentrow = r;
                                continue = FALSE;
                            }
                        }
                    }
                }
            }
        }     
            
        if (act != ACTION_FIND)
        {   // update rows pointers and tablecount
            for (r = row; r < rowcount; ++r)
                rows = llListReplaceList(rows, [llList2Integer(rows, r) + e], r, r); 
            tablecount = llGetListLength(table);
        }   
    }
    // return currentrow after action
    // return -1 when row out of bounds or not found
    return result;  
}


emptyTable()
{   // empty table and reset supportives
    table = [];
    rows = [];
    currentrow = -1;  
    rowcount = 0;
    tablecount = 0;    
}

default
{
    touch_start(integer num_detected)
    {
        llOwnerSay("BEGIN");
        
        emptyTable();
        
        // fill with some data. Data can be any type. 
        // little strings used to easier see what is happening
        action(ACTION_APPEND, 0, ["aa", "ab", "ac"]);
        action(ACTION_APPEND, 0, ["ba", "bb"]);
        action(ACTION_APPEND, 0, ["ca"]);
        action(ACTION_APPEND, 0, ["da", "db"]);
        action(ACTION_APPEND, 0, ["ea", "eb", "ec"]);
        action(ACTION_APPEND, 0, ["fa", "fb"]);       
       
       llOwnerSay("append: [" + llDumpList2String(table, ",") + "]");
       llOwnerSay("rows: [" + llDumpList2String(rows, " ") + "]");          
      
       action(ACTION_DELETE, 1, []); 
       llOwnerSay("delete row 1: [" + llDumpList2String(table, ",") + "]");
       llOwnerSay("rows: [" + llDumpList2String(rows, " ") + "]");          

       action(ACTION_INSERT, 3, ["ma", "mb", "mc"]);
       llOwnerSay("insert new row 3: [" + llDumpList2String(table, ",") + "]");
       llOwnerSay("rows: [" + llDumpList2String(rows, " ") + "]");          
       
       action(ACTION_REPLACE, 0, ["ya", "yb"]);
       action(ACTION_REPLACE, rowcount - 1, ["xa"]);
       llOwnerSay("replace row 0 and last row: [" + llDumpList2String(table, ",") + "]");
       llOwnerSay("rows: [" + llDumpList2String(rows, " ") + "]");          
       
       list elements = fetch(3);
       llOwnerSay("fetch elements in row 3: [" + llDumpList2String(elements, ",") + "]");
       
       // the pattern to find, can be any number of elements 
       integer i = action(ACTION_FIND, 0, ["db"]);   
       llOwnerSay("find row for [db] in entire table. Row = " + (string)i);
       
       i = action(ACTION_FIND, 4, ["da", "db"]); 
       llOwnerSay("find row for [da,db] from row 4. Row = Not Found = " + (string)i);
       
       i = action(ACTION_FIND, 0, ["db","ma"]); 
       llOwnerSay("find cross boundary fail for [da,ma]. Row = Not Found = " + (string)i);     
       llOwnerSay("END");
   }
}

 

Edited October 27, 2021 by Mollymews

[Profaitchikenz Haiku]

Very comprehensive. I have a simpler method since it was developed for a very specific pair off application

 

// A method of implementing sparse arrays using a list

// NOTE, this relies on the fact that any list entry can have the type determined
// by llGetListEntryType() to actually make use of the dtata in the records

// method 1, simple structure 
// advantages:
// easy to amend since each record counter is relative not absolute
// drawbacks:
// must be traversed from start to finish
// hard when doing a listFindList to determine the actual record start

list sparse = [
				integer numFields	// count of how many fields in this record
				,// data,... (any number of entries
				,integer numFields // entries in next record
				, ...
				];
				
// from the start of the list, to access data record n, 
//       get the number of fields in the current record. 
//       If the current record is not the desired one, 
//           add the number of fields to the current positon and repeat
// to delete an entry, 
//      delete the sublist starting at the record count consisting
//      of that number of fields in the sub-list.
// to change the length of an entry, 
//      delete the record and put in a new one of
//      the required number of fields with the apprpriate count

// method 2, using a -ve counter for the fields
// advantages:
// can be traversed forwards and backwards
// ( in the middle of a record, decrement the list index until a -ve integer is 
//   found to locate the precise star pf the record)
// start of record can be determined from a listFindList position by 
//    moving backwards until a -ve integer is found
// disadvantages:
// -ve integers cannot be a part of the record
// some extra processing at each step through the data from record to record

list cleverSparse = [
						-VE integer // number of fields
						,// data,... (any number of entries
						,-VE integer numFields // next record
						,...
						];
						
// Access, amendments, deletions are as the simple method vith the extra step of 
// negating the number of fields entry

 

Edited October 27, 2021 by Profaitchikenz Haiku