Re: [boost] Re: Boost library inclusion: generic tree containers?

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2005-02-24 08:30:36

Thorsten Ottosen ha escrito:

> "Justin Gottschlich" <jgottschlich_at_[hidden]> wrote in message
> news:cvjt7a$cn2$1_at_sea.gmane.org...
> |> | "Thorsten Ottosen" <nesotto_at_[hidden]> wrote in message
> | >
>
> | At this point, I'm ready to step back and say, "ok, so ... let's figure out
> | what we need to build." As I was discussing with Richard, I think we have
> | two primary trees to develop:
> |
> |    1) trees as containers
> |    2) trees as algorithms
> |
> | I think we need to figure out a design that is inherently inclusive to both
> | groups (so everyone is happy). That being said, what do you think the best
> | format to do that is?
>
> |
> | What do you think? And boy is this fun. =)
>
> I'm not sure I like the expression "trees as algorithms". I would like to see
> different types of iterators which can then be used to implement algorithms.
>
> So I only see trees as containers.
>

I agree with Thorste here. Thinking about the relation between a tree
structure and its various iterators, maybe we can adopt a similar conceptual
approach as Boost.MultiIndex: a tree container is the underyling data structure,
on top of which several "indices" are provided with different iteration policies:

typedef tree<element> tree_t;
tree_t tr;

tree_t::iterator<inorder>::type it1=tr.get<inorder>().begin; // inorder iteration
tree_t::iterator<preorder>::type it2=tr.get<preorder>().begin; // preorder
iteration

// convertibility between different types of iterators
it2=tr.project<preorder>(it1);

Apart from classical iteration schemes, the structure could provide
a general-purpose interface from which to derive user-defined
iterators: here we'd have "cursors" allowing for arbitrary movement
across the structure.

Maybe this makes little sense, but I felt like bringing it forward :)

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo