[Adobe-source-devel] Depth Tracking In Forest -

[Sean P. <sp...@ad...>]

[Caution - Non Adobe Employees On To List]

I'm in the middle of revamping adobe::forest<> (if you don't know  
what forest is, you can probably stop reading now).

One thing I'm considering is pulling depth() out of the fullorder  
cursor/iterator (still can't quite settle on the name...). It would  
be replaced with an adapter which would add the depth() tracking back  
in. The pros for this are that it would simplify and reduce the cost  
of the forest iterators - the biggest con is that tracking depth  
during insert or erase would be considerably more complicated - but I  
don't know of any use cases where this is currently done and before  
it could only be done locally to the insert or erase because the  
depth of iterators was invalided by these operations.

Does anyone have an objection to moving depth() to an adaptor?

As an FYI - the revamped forest<> work includes:

* fixed a bug in erase() of a single node where the returned iterator  
was incorrect if you erase() from a leading edge (did not effect  
erase range or destruction as these always erase from trailing edge).
* cleaned up the size invalidation code during splicing - size is now  
preserved in many more cases.
* added a splice range which takes a count to avoid invalidating size  
when the size of the spliced range is known.
* added a reverse() member function which reverses a range of  
children. (This was what started this work... I'm adding Right To  
Left support in Eve but it turns out I probably won't use this to  
implement it).
* added an insert() member function which takes a sub-forest denoted  
as a range of children and inserts them (keeping the sub-forest  
structure). May rename this to be insert_subforest before release.
* added a proper copy-ctor and assignment (don't know how I missed  
these before!).
* fullorder and childiterator support a new function adobe::set_next 
(), which can be used to implement node based algorithms (like  
reverse) - this may be changed to adobe::unsafe::set_next() before  
release. The definition of unsafe being an operation which  
temporarily violates invariants and must be used as part of a  
sequence of operations to restore the invariants.
* added a root() member function for use with set_next() - may change  
to a stand alone unsafe::root() function before release. This returns  
an iterator which cannot be dereferenced, like end(), and ++root()  
always yields begin().

_lots_ of code cleanup. The resulting file is smaller then when I  
started.

Sean