Re: [boost] [serialization] request: low-level info about orderofserialization

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2004-09-08 01:22:31

Hi Robert,

Robert Ramey ha escrito:

> >I'm slowly designing the addition of serialization support to
> >Boost.MultiIndex, and come up with a need that, AFAIK, the
> >current serialization library does not cover:
>
> >The serialization of a multi_index_container should ensure that
> >the order in which elements appear is preserved for all indices
> >of the container.
>
> Appear?

Ummm, I guess I'm not explaining myself, let me try with an example:
consider a multi_index_container like this:

typedef multi_index_container<
  int,
  indexed_by<
    sequenced<>,
    sequenced<>
  >
> bilist;

Then, when serializing such a bilist, the order maintained by indices #0 and
#1 must be recorded separately. Roughly speaking, this involves:

1. serializing the elements in the order induced by index #0.
2. traversing index #1 and serializing a record of rearrangements with respect
to index #0.

Step 2 can be accomplished in a simple manner by serializing pointers to
the (previously serialized) elements, but in the order induced by index #1. As
Boost.Serialization keeps track of previously stored objects, this will work
OK. To further exemplify this, consider a particular bilist like this:

index #0: [begin(),end) = 1 4 3 5 2 6
index #1: [begin(),end) = 1 3 5 6 2 4

then all the info we need to reconstruct the container can be saved as:

1 4 3 5 2 6
&1 &3 &5 &6 &2 &4

where & means we save a pointer to a previously serialized element.
I hope everything's clear up to this point.
But now, we can do better: it is not necessary to save that much info
for reconstructing index #1, as we really only need the "difference"
with respect to the order induced by index #0. In fact, index #1 has
the same order as index #0 except that elements 4 and 2 are
relocated. So we can instead save this info (sort of):

1 4 3 5 2 6
&2 &4

and at reconstruction time we can simply relocate those elements in
index #1 whose position differ from that in index #0.
Generally speaking, the best algorithm for computing such a
rearrangement between index #1 and index #0 involves calculating
what's called a "longest increasing subsequence"; check for
instance http://tinyurl.com/6ouog for details. And now we get to the
core of my request: this algorithm needs to know the order in
which the base elements were serialized in step 1, in the manner
I propose in my previous post: given an object, return an ordinal
corresponding to the position that object was serialized in the
archive.

I'm not saying this request is worth honoring, but at least I want
to make sure you know exactly why I need it. Of course, I can
record that information myself, but it feels like duplicate work as
your lib most likely already has it.

If I haven't made myself clear please do ask.

Best,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

>
>
> >This implies serializing the elements and then
> >recording the appropriate rearrangements in each index. I'm
> >writing the code for serializing these rearrangements in
> >an efficient manner as some sort of "diff" sequences, using
> >an algorithm called "longest increasing subsequence" (LIS).
>
> >The algorithm would greatly benefit for some low-level API
> >by the serialization lib that, given an object reference, would
> >return the order in which that object was serialized. I guess this
> >information is already available internally, as the lib must keep
> >track of previously saved objects.
>
> >If this requirement is deemed too exotic to provide to the
> >general user, well, I can write something myself without aid from
> >the lib, but I thought I should ask at least :)
>
> It seems too exotic to me.
>
> The focus of the serialization library is to re-create exactly that which
> was there before.  So far, that has already been possible with the API
> provided.  Some containers (e.g. slist) required a little bit of special
> handling to preserve sequence but this did not require any change in the
> basic API. All of this special handling is part of the implementation of the
> container in question.
>
> I'm really not sure what your doing, so without knowing more its hard for me
> to comment.
>
> Robert Ramey
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost