[Israel.pm] tie

[Shlomi Fish]

On Tuesday 15 June 2004 17:17, Shlomo Yona wrote:
> Hello,
>
> I have a list of lists (LoL), which is a list of binary
> vectors.
>
> .1.
>
> I'd like to have this list of vectos tied to a file.
> That's easy:
>
> 	tie @list_of_vectors, 'Tie::File', $vectors_list_filename;
>
> BUT -- the vectors themselves must now be represented as
> strings... and I cannot look up in them, I cannot do
> operations on them unless I split the "line" before usage
> and then join the "vector" back to a "line" after doing my
> stuff.
>
> I wonder if there's a way to allow a LoL to be tied nicely
> to a file, so that the usage is just like using a LoL but in
> fact the data is tied to a file, rather than being all in
> memory.
>
> .2.
>
> To make things more complicated: What if I wanted to have
> the vectors be sparse-vectors, but still keep the simple LoL
> usage instead of all the extra hassle which is now required
> to handle the tied list and the sparse vector.....?
>

Well, since a sparse vector is actually a set of items, I can think of the 
following representation:

One works against a file-based hash implementation (i.e: DB_File, GDBM_File, 
Berkeley DB, etc.) where the following keys apply:

"superlist-next-id" : the next ID (see below) assigned to each bit vector.
"superlist-length" : the length of the list of bit vectors.
"superlist-id-$index" : the ID of the bit vector in place No. $index.
"sparse-vec-$id-$bit" : exists if Bit #$bit is set for the bit vector with the 
ID $id.

I used on level of indirection here so that some operation on the array (like 
swapping two elements) can be performed with more efficiency. To set a bit:

$my_db_file{"sparse-vec-".$my_db_file{"superlist-id-$index"}."-$bit"} = 1;

To unset:

delete($my_db_file{"sparse-vec-".$my_db_file{"superlist-id-$index"}."-$bit"});

To check for the setting of a bit, check for the existence of the appropriate 
bit.

To delete a bit-vector you need to iterate over all the keys in the hash and 
delete sparse-vec-$id-.* (or keep them there if you don't mind the extra 
space taken - you can do the cleaning up periodically).

To add an (empty) bit vector to somewhere, just get an ID for it using the one 
in superlist-next-id (just increment it afterwards), and then put this ID in 
the appropriate superlist-id-$index.

Note that all this will work against a binary file. If you want to use a text 
file, then you'll need to implement something like Tie::File only that 
returns another tied element representing a bit vector instead of the text of 
the line. You can do it by either extending Tie::File somehow, or writing a 
wrapper class that uses it.

Regards,

	Shlomi Fish

>
>
> Are there ready made solutions for this? How?

-- 

---------------------------------------------------------------------
Shlomi Fish      shlomif at iglu.org.il
Homepage:        http://shlomif.il.eu.org/

Quidquid latine dictum sit, altum viditur.
        [Whatever is said in Latin sounds profound.]