I meant a general tree or graph abstraction. There are several tree-like
structures, but each has its own public interface (e.g. Xml classes,
ASP.NET/Winforms/WPF/etc. control hierarchies, tree view, etc.).
Btw, there is another (and quite different) generic RB tree implementation
in .NET, in System.Data (RBTree<K>, internal).
Sébastien
On 7/27/07, Greg Young <[EMAIL PROTECTED]> wrote:
>
> 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(r) http://www.develop.com
>
> View archives and manage your subscription(s) at
> http://discuss.develop.com
>
--
Sébastien
www.sebastienlorion.com
