"Jason Hise" <chaos@ezequal.com> wrote in message news:421BF5C5.2050507@ezequal.com...
Justin Gottschlich wrote:
I haven't looked at the code, so please correct me if I am off base. But isn't having iterators which behave like stl iterators the only way to make the tree work with generic algorithms? I think that your multi-purpose iterator could be very convenient for the code that is hardwired to use trees, but I think that it would also be nice if the other iterators were provided, so that you could for_each over a single level in the tree, or over the whole tree, etc...
Hi Jason - You're right on target. With my current base tree iterator, I only supply increment and decrement over a single level and in order to get access to depths within deeper levels of the tree, I'd have to use the iterator to step "in()" / "begin()" - thus standard algorithms would only work for a single level based on the single-level iteration functionality of the current iterator (but, keep reading). You could still use for_each for the tree that way, but only a single level would be covered. So, if you had a tree/iterator with 10 direct children, each of which had 10 direct children, if you did this (which would be perfectly legal with my current implementation): ///////////////////////////////////////////////////////////////////////////// void outputBranch(int i) { std::cout << i << std::endl; } ///////////////////////////////////////////////////////////////////////////// int main() { core::tree<int> t; for (int i = 0; i < 10; ++i) { core::tree<int>::iterator iter = t.push_back(i); for (int j = 0; j < 10; ++j) iter.push_back(j); } std::for_each(t.begin(), t.end(), outputBranch); } it would simply output all the elements of the first level - not the entire tree. In order to iterate over the whole tree (your second point), I would simply have to create an additional iterator which iterated recursively through the tree using ++ and it would require a minor change to the above code: ///////////////////////////////////////////////////////////////////////////// int main() { core::tree<int> t; for (int i = 0; i < 10; ++i) { core::tree<int>::iterator iter = t.push_back(i); for (int j = 0; j < 10; ++j) iter.push_back(j); } core::tree<int>::recursive_depth_iterator riter = t.begin(); std::for_each(riter, t.end(), outputBranch); } I don't currently have a recursive_depth_iterator, because in the past I haven't really needed it. But as you pointed out, it'd really do a lot of good having a full tree iterator for standard algorithm usage. The point I was really trying to make in the previous post (which I can see I did a rather poor job of) is that based on the way I designed the tree and its iterator, any type of iterator can be constructed from the current implementation without changing the design of the tree or its iterator - thus, allowing full standard algorithm usage. Since the one basic iterator performs fully as a tree and an iterator, any kind of iterator can be constructed just from that one iterator (because the iterator has the ability to step into itself or out of itself, just like the tree can). My initial driving idea behind the tree was to create a framework generic enough that any kind of tree could be constructed from its base functionality (rather than trying to guess at every kind of tree people would need). Thus, any programmer using the tree could create an iterator for the tree to perform any kind of iteration they like (level iteration, tree-depth iteration, backwards tree-breadth iteration) and have standard algorithms work on that iterator exactly as they had coded. Thus, I wouldn't have to "pre-determine" all possible types of iterations (nor tree types) the end coder needs. Some basic types of tree iteration clearly need to be available that I currently don't have. After the great points made today, I most certainly will add them. =) Thanks for the discussion and point for clarification Jason, Justin