mattunderscorechampion/tree-root

Tree collection and utility library

tree-root's Issues

IMutableNode

Presumable getChildren() returns a mutable collection? Why is removeChild() better than getChildren().remove()?

If its to reduce garbage, it might be better to allow an iterator (IWalker?) to mutate. E.g. remove the current node, alter children, ..

Switch over to Java 8

Java 7 public updates end April 2015 so it needs to move to Java 8.

http://www.oracle.com/technetwork/java/javase/eol-135779.html

'I' interface naming is non-idiomatic

A little bikeshedding...

The naming of interfaces IFoo is not idiomatic for Java. Please change to Foo.

Design Principles

Please document the design principles behind this API.

• Can common implementation operations (such as rebalancing) be implemented efficiently using the API, or is that some other interface?
• Attitude to garbage
• Internal vs external iteration. Proxing all access through INode (no API to walk just over E's). Why not Visitor?
• Relationship to other collection libraries
• Unordered children. What if I know I have a binary tree - its inconvenient to work through a Collection to get to Left and Right.
• Prior art

INode.isLeaf()

Would an isLeaf() convenience method be useful?

Selectors and matchers

Should the selectors and matchers be generic classes or have generic methods? Currently they are generic classes. Can a single selector apply to trees with different element types?

Path copy tree concurrent modification

The concurrent modification of path copy trees results in one modification winning out and the others discarded. This is a result of setting the root node to the new path. Only a single path should be copied at a time.

TreeSelectors may return a copy of the subtree

Supporting the selection of subtrees was always intended however with mutable trees it poses a question. Should modifications to the original tree be propagated to any selected subtrees? Initial implementations involved returning the root node of a subtree as the root. This provides O(1) node to tree conversion and is fine for immutable trees but with mutable trees modifications to the original or the subtree are visible in the other tree. I have decided that the mutations to different trees should not be visible in the other.

This means that several existing implementations are broken and the performance of tree selection may be O(n). It does however make it easier to understand and predict the consequences of modifying trees. It also makes it more in line with the possibility of selecting a subtree with different properties to the source tree.

Binary tree walkers and iterators

It is possible for a binary trees to have a right node but not a left node. The iterators have been implemented to treat the first node returned by the iterator for the children as the left node. I suspect that the a missing left node would need to be handled by having a null as the placeholder for the left node with the walkers and iterators treating it as a left node but not traversing it

ITreeWalker.onEmpty()

Does ITreeWalker.onEmpty() really pull its weight?

I'd have thought that an ITW that did something useful in onEmpty would naturally be stateful and so adding an additional boolean would be trivial.

Would hasMore() be better?

Unable to use provided iterators or walkers to print a Lispy tree

I'd like to be able to create an internal iterator to print a lisp like tree. Something like:

(root (firstChild secondChild))

The problem is that the walkers do not have callbacks for when walking a node's children. Instead it is presented as a stream of nodes.

Sorted trees

There needs to be a way to created sorted trees. These would be related to the balancing trees.

Returning a simple collection from a node creates duplicate methods.

To support sorting algorithms it is necessary to add nodes to specific positions. The initial tree implementation assumed an unordered bag of child nodes.

As support for structural iteration and placement has been added it has undermined the value of returning a collection.

The Node returns a SimpleCollection and says whether or not the Node is a leaf (the collection is empty). The SimpleCollection returns the size and a pair of iterators (one of which was added specifically for structural iteration). The MutableStructuralNode adds methods for adding new nodes in specific places. Methods for accessing and modifying nodes are split and duplicated between the Node and the SimpleCollection.

The SimpleCollection needs to be removed and everything needed placed directly on the node.

See issue #2 for some related problems.

Path copy trees parent references

The parent node and tree reference in the path copy tree node implementation makes it difficult to implement certain operations such as getting a subtree. A more flexible implementation needs to be implemented.

Use of generics

The current API does not support polymorphic access to elements - it expects them all to be an E.

Using generics with containers breaks down a little due to Java's limited type model, but I suspect some methods could be relaxed to take INode<? extends E>, and provide INode<? super E>, supporting operations between trees with related but different types.

Also, it would be nice to be able to create an IWalker that is restricted to visiting nodes of type .

Binary trees

There should be an implementation of binary trees with a left and right node. Will also need a mutable version. Need mentioned by issue #6. Problem with iterators mentioned by issue #7.