From: Marcin Kalicinski (kalita_at_[hidden])
Date: 2006-05-22 17:52:18
> Personally I think it would be a good idea to let each node carry parent
> and/or root information. That way you could store tree-wide information
> separator, locale, source) in the root.
> Only downside I can think of is O(N) swap instead of O(1).
You mean O(N) if node carried root+parent, and O(1) if parent only, or am I
missing something? I think it should only carry parent. Otherwise almost all
mutating operations would invoke additional hierarchy walking, and caused
updating of the root pointer everywhere. Root could be obtained from parents
in O(log n), I think this is cheap enough.
Anyway, I plan to get rid of separator overloads in favor of paths. I.e. if
one wants a different separator, please use a path object.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk