On Fri, Oct 12, 2012 at 1:23 AM, Phil Endecott < spam_from_boost_dev@chezphil.org> 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