Do positions change when inserting/deleting rows

From: <[email protected]> - 4 Nov 1998

 > Consider the following inventory application. [...] What should this
 > reference be? An index, the shelf 'key', a reference to a row?
 >
 > A similar application is the the DisCat example. There the directory
 > that the file was in was stored as a c4_IntProp, an index to a row in
 > the c4_View. I would rather store an actual 'pointer' to the row of
 > the c4_View. Is this possible?
 >
 > If the removal of a shelf is possible, then I assume an index would
 > not be valid. Certainly not to that shelf, and probably not to any
 > box that references a higher index'd shelf. I can obviously program
 > around this.  If the key is used, then only the boxes that reference
 > the non existant key are invalid. But I have the expense of searching
 > for the shelf based on the key. If I could reference the actual row
 > of data that represents the shelf, then I no longer need the search,   > [...] how I can maintain a reference to an individual row in a table.

You raise an important issue.

Metakit has no notion of keys at this stage (it probably will, one day). There are two ways to gain access to a row: by indexing (instant), and by searching for it.

If the order of rows is not important to you, or if you intend to sort anyway, then you may want to consider using positions. They are simplest, and have no time/space overhead. There is one issue to solve: inserting or removing rows may affect positions stored as integers elsewhere. This is very easy to solve, assuming you know exactly where the index values are stored.

The obvious way is to go through them and adjust values:

         for each row:
                 if index >= insertion/deleteion point:
                         adjust index + or - the number of rows

That seems inefficient, but it usually is surprisingly fast, because Metakit stores data column-wise: all indexes are accessed very efficiently inside the loop, without even loading any other data.

I can't stress this enough: Metakit can scan at an extremely high rate.

There is a nice trick, if the order of rows is not important:

         - when adding a new row, add it at the end of the view
         - when deleting a row, do this instead:
                 - replace the row with the last one in the view
                 - delete the last row
                 - adjust the index value of that, now relocated, row

It works quite well, I do it all the time. That last step is easily done with a call to c4_View::Find and a replace. No loops, unless the position could be present more than once.

The other way to do things, the classical one, is to issue unique ID numbers (keep the last one issued somewhere, or scan for the highest used when opening the file again, perhaps). Then search for it. Again, don't assume this is slow until you have tried it - scanning through a single property in thousands of rows works quite well (c4_View::Find). If that is a concern to you, and you need just about instant access, or you are working with tens/hundreds of thousands of rows, then do this:

         - Keep the rows sorted by ID.  This is easy: append at end
           (since new IDs are increasing), and delete as needed.  Never
           insert rows.
         - Make the ID the 1-st property of the view (you can
           restructure to achieve this).
         - Use c4_View::Search to located rows by ID.  It uses binary
           search, and should be virtually instant in any realistic use.

-- JC