I don't want to change the
topic, but I find it surprising that there is no tree and/or graph
i dont want to get too far off topic either but sorteddictionary<t> is
a rb tree.
On 7/27/07, Sébastien Lorion <[EMAIL PROTECTED]> wrote:
> I will answer you and Stoyan in one go ...
>
> My goal is to have a general purpose base implementation. First concern is
> usability and correctness/completeness of object model in the long term. I
> can always change the concrete implementation later on.
> I am trying to abstract away and put in common
> as much as possible about what you can do with a tree, e.g.
> traversals. I see this implementation as a base for specialized trees,
> like binary,
> ternary, RB tree, heaps, treaps, tries, etc. I don't want to change the
> topic, but I find it surprising that there is no tree and/or graph
> abstractions at all in the .NET framework.
>
> Here is the skeleton of my current model (sorry if formatting gets wrong).
>
> public interface IReadOnlyTree
> : IEnumerable
> {
> ITreeNode Root { get;}
> CacheOption CountCacheOption { get;} // can be NoCache,
> DiscardAfterChange, UpdateAfterChange
>
> bool Contains(ITreeNode node);
> int CalculateCount();
> }
>
> public interface ITree
> : IReadOnlyTree
> {
> new ITreeNode Root { get;set;}
> new CacheOption CountCacheOption { get;set;}
>
> void AddFirst(ITreeNode child, ITreeNode parent);
> void AddLast(ITreeNode child, ITreeNode parent);
>
> void InsertBefore(ITreeNode newChild, ITreeNode refChild);
> void InsertAfter(ITreeNode newChild, ITreeNode refChild);
>
> void Remove(ITreeNode node);
> void RemoveAllChildNodes(ITreeNode parent);
>
> void ReplaceNode(ITreeNode newNode, ITreeNode oldNode);
> void SwapNodes(ITreeNode nodeA, ITreeNode nodeB);
> }
>
> public interface ITreeNode
> : IEnumerable
> {
> object Value { get;set;}
> ITreeNode Parent { get;}
> bool HasChildNodes { get;}
> int Count { get;}
>
> ITreeNode this[int index] { get;}
> int IndexOf(ITreeNode node);
> }
>
> There is also a Algorithms static class (thinking about decomposing it to
> not get a monster class like in PowerCollections).
> Also have various traversal enumerators like Pre/In/PostOrderEnumerator,
> BreadthFirstEnumerator, etc.
>
> In the case where the nodes store their children locally, the TreeNode class
> offers internal methods that the Tree class uses to do its operations.
>
> In the case where the relationships are stored centrally, the nodes are much
> more lightweight in term of code as most operations gets delegated to the
> tree and there is no need to have internal methods.
>
> In the tree-as-a-node approach you describe,
> I am curious about where exactly you store the relationships between the
> nodes.
> I get the general idea and it is something I have explored, but
> I would like to have more details on your implementation.
>
> Sébastien
>
> On 7/26/07, Barry Kelly <[EMAIL PROTECTED]> wrote:
> >
> > Sébastien Lorion <[EMAIL PROTECTED]> wrote:
> >
> > > Considering that operations on the tree are centralized in the Tree
> > class,
> >
> > By making this assertion, IMO you've pre-selected a particular notion of
> > interacting with a tree.
> >
> > Usually, when I work with a tree, my node *is* my tree (i.e. it's the
> > root of the tree). What's more, I often don't store parent pointers and
> > instead rely on e.g. visiting algorithms to store the parent stack
> > during a recursive traversal, if such parents are required for certain
> > operations. And taking a leaf (ahem) from the pages of functional
> > programming, when parent pointers are eliminated, subtrees may be shared
> > between multiple trees, since my nodes are often read-only after
> > construction (and thus aliasing issues aren't important).
> >
> > There's more down this branch too: persistent datastructures often rely
> > on the logarithmic performance of operations on trees to permit keeping
> > e.g. undo-state around quite cheap.
> >
> > Can you say more about your particular tree?
> >
> > -- Barry
> >
> > --
> > http://barrkel.blogspot.com/
> >
> > ===================================
> > This list is hosted by DevelopMentor(r) http://www.develop.com
> >
> > View archives and manage your subscription(s) at
> > http://discuss.develop.com
> >
>
>
>
> --
> Sébastien
> www.sebastienlorion.com
>
--
Studying for the Turing test
===================================
This list is hosted by DevelopMentor® http://www.develop.com
View archives and manage your subscription(s) at http://discuss.develop.com
