Boost logo

Boost :

Subject: [boost] Augmented trees
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2012-10-11 10:23:30

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.

It seems to me that an augmented tree lets me do all of those
operations in log(N) time - and no other data structure offers the same performance.

I'm aware of two augmented trees that have been proposed here.
Francisco Jose Tapia has proposed "Countertree", but this only stores
the count of elements not the sum of a property of the elements (i.e.
the widths in my example). Vadim Stadnik has proposed stl_ext_adv,
which is a doubly-augmented B+ tree. Has anyone looked at Vadim's code
since it was proposed last year? I have a couple of concerns about
Vadim's proposal:

1. It uses B+ trees, and in the discussion it was suggested that these
are inferior to red-black trees in some way.

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.

Is there any other work that I've overlooked?

Is there a "friendly" red-black tree implementation somewhere that
could be augmented relatively easily?

Regards, Phil.

Boost list run by bdawes at, gregod at, cpdaniel at, john at