Re: [boost] Countertree

Subject: Re: [boost] Countertree
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2012-11-21 18:00:11

Hi Francisco,

First of all I think that your library will be a great addition to Boost.
To make it even better I will suggest to make CounterTree more generic:

1) Expand CounterTree implementation to RangeTree (the name might be
different).
RangeTree is a data structure that supports any operation on its nodes that
is
associative ((a*b)*c = a*(b*c)) and commutative (a*b = b*a). The examples
of such
an operation are: addition, multiplication, gcd, xor, bit count, etc.
RangeTree allows to execute the following operations in logarithmic time:
a) insertion / removal / lookup of the new element by key;
b) operation evaluation on the tree nodes within the given key range.

2) Considering above, expand RangeTree to support any type of operation
argument (I call it property).
E.g. for the CounterTree this is an integer representing number of elements
in a subtree,
for the ColourTree this can be node colour and operation defined as mixing
all the colours in the subtree.

3) Considering 1) and 2), it will be possible to implement CounterTree as
specialization of RangeTree.
Augmented tree, recently requested by Phil Endecott for dynamic text width
querying,
can be implemented as specialization of the RangeTree data structure as
well.

4) Summarizing all of the above the RangeTree declaration will look like:
template <class Key, class Compare, class Property, class Operation, class
Allocator> class RangeTree;
Property RangeTree::query(const Key& left, const Key& right); // basic
query interface

The CounterTree specialization:
template <class Key, class Compare, class Allocator> class CounterTree :
  RangeTree<Key, Compare, int, addition<int>, Allocator>;

And even more, the CounterRangeTree specialization:
template <class Key, class Compare, class Property, class Operation, class
Allocator> class CounterRangeTree :
  RangeTree<Key, Compare, pair<int, Property>, operation< addition<int>,
Operation >, Allocator>;
Property CounterRangeTree::query(int start_index, int end_index); //
counter query interface

Such a design will widely expand application area of the library and will
allow to use it
for the large number of live updating/querying systems.

Regards,
Andrii

_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost