Re: [boost] Augmented trees

Subject: Re: [boost] Augmented trees
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2012-10-12 04:37:21

On Fri, Oct 12, 2012 at 1:23 AM, Phil Endecott <
spam_from_boost_dev_at_[hidden]> wrote:

> Dear Experts,
>
> I find myself in need of an augmented tree.  My problem is something like
> [but not exactly] this:
>
> - Say I have a line of text, i.e. a sequence of characters, in a
> variable-width font; each character stores its width in pixels.
>
> - I need to efficiently insert and remove characters.
>
> - I need to efficiently find the range of characters that spans a given
> range of pixels.
>
>
Thank you for the interest in augmented data structures!
Because of the last requirement it seems to me that you do not have to sum
up width values. The problem requires a type that represents an interval or
a range or a one-dimensional extension rectangle. There is an example in
documentation to the stl_ext_adv library that shows how to count
intersections of one interval with a sequence of intervals in logarithmic
time. This example looks more relevant to the described problem.

> 2. In order to get the property to be accumulated (i.e. the widths in my
> case) it requires that arithmetic can be done on the stored type itself;
> this is fine for e.g. a sequence of ints, but if the stored type is a
> struct it is necessary to add various "unnatural" operator overloads.  I
> think I would prefer it to have some sort of user-supplied accessor to get
> the property to be accumulated.
>
>
If my first guess was incorrect and you really need to sum the width values
and would like to avoid complications of operator overloading then you can
create for this algorithm an additional container, such as sequence or
multiset, which supports fast accumulate() algorithm for type <int> that
represents the width parameter only. This approach requires mapping and
synchronization of processing between original data container(s) and the
new additional container.

Hope that my comments are helpful,
Regards,
Vadim Stadnik