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
