Re: [boost] Possible class submission: Sparse Array

From: Spencer Collyer (spencer_at_[hidden])
Date: 2006-04-27 11:07:26

On Thu, 27 Apr 2006 08:21:29 +0100, Spencer Collyer wrote:
> On Wed, 26 Apr 2006 22:02:17 +0200, Pavel Vozenilek wrote:
> > The storage can get better:
> > 
> > - double-array structure provides O(1) retrieving time,
> > requires more-less O(N) space where N = number
> > of nonzero elements (with /no/ overhead due to pointers),
> >  deletion and insertions are bounded.
> > 
> > It is described in IEEE Transaction of SW Engineering,
> > vol 15, No9, Sep 1989 by Jun-Ichi Aoe.
> > An implementation seems to exist on
> > http://linux.thai.net/~thep/datrie/datrie.html
>
> I'll need to look closer at the double-array structure. Do you think it
> would be a good idea to develop a Boost implementation of it to submit
> with my sparse_array class, as another storage policy? I could try and
> do that if you think it would be a good idea. Mind you, it looks (at a
> first quick glance) like it could be a useful class on its own, so
> maybe a separate submission would be appropriate?

Pavel,

Now I've had a bit of time to look at the article on double-array you
mentioned, I think my comment above about it being useful on its own
could prove to be correct.

However, developing such a class is more than I want to take on at the
moment, especially to make it flexible enough to be able to handle keys
that are not strings (the example implementation looks to be string
based, whereas I would hope any Boost-ified implementation would be able
to handle more generalised keys, possibly using a policy to decompose the
keys into values for the trie nodes).

Spencer

-- 
<<< Eagles may soar, but weasels don't get sucked into jet engines >>>
4:01pm up 40 days 3:34, 23 users, load average: 0.04, 0.10, 0.17
Registered Linux User #232457 | LFS ID 11703