See Roodi report at http://getcaliper.com/caliper/tool?tool=roodi&repo=git://github.com/evolve75/RubyTree.git
Fix bug #28613 which was affecting the `leftChild=’ and `rightChild=’ methods for binary trees.
This is a bugfix release.
Resolve the tree.rb file conflict with the netaddr gem
tree.each_leaf do |tree_leaf|
tree_leaf_parent = tree_leaf.parent
tree_leaf.remove_from_parent!
puts tree_leaf_parent.is_leaf?
endwill return false, while technically tree_leaf_parent becomes leaf itself when tree_leaf is removed.
The problem here is that the code above is trying to concurrently modify the collection over which the each_leaf
iterator is looping, which has unpredicable results. As an example, try this with an array:
a = Array(1..5)
a.each do |e|
a.delete(e)
end
aThe result is surprising, as not all elements are being deleted. A good explanation is available in this thread on Ruby-Talk @ Google.
The correct way to handle the original need is:
leafs = @root.each_leaf
parents = leafs.collect {|leaf| leaf.parent }
leafs.each {|leaf| leaf.remove_from_parent!}
parents.each {|parent| assert(parent.is_leaf?) if not parent.has_children?}Basically, the parent removal is done in a separate block, and then the check for the parents becoming leafs is done.
The current behavior is correct, and has been left as is.Left the code as-is, since we need some way to un-ambiguously find the root, regardless of the node given.
This release contains the following features and fixes:
- Ability to merge in another tree at a chosen node
- Support for the Comparable mixin module
- Ability to export the tree to a hash, and create a new tree from another existing hash
- Fix (partial) for preventing cyclic graphs in the tree
- Refactored
eachmethod to prevent stack errors while navigating deep trees - Check to ensure that the added node’s name is unique to the destination tree
- Fix for the issue where tree traversal would fail if the binary-tree’s left child was nil
- Fixed the return type for the iterator methods (each, postordered_each, breadth_each, etc.). They now return an Enumerator if no block is provided, or else return the receiver node itself, if a block was provided. This is consistent with how Ruby’s standard collections work
- Structural changes in the code to refactor out the non-core functions into modules
- Massive documentation updates
- Addition of the examples directory (only a bare-bones placeholder for now, with the basic example code)
- Ability to run the examples from the Rakefile
- Various bundler and travis-ci related changes
- [X] each
- [X] postordered_each
- [X] Handling of CamelCase methods
- [X] Convertion to and from JSON
- [X] The merge feature
- [X] The metrics measurements
Implement an `inordered_each` method for the BinaryTree
Rename the COPYING.rdoc file to LICENSING.rdoc
Fix the inconsistency of returning root as its first sibling, and returning a nil instead. Ditto for last sibling.
fix the inconsistency of returning nil for the root, and an empty array for nodes which have no siblings.
Pull the hash converter code from Mark Thomas (Issue #13).
This is primarily a modernization of the library, with removal of deprecated methods, the much-hated dependency on
structured_warnings, and cleanup of other cruft.
In addition, the CI pipeline has been moved from https://travis.ci to Github Actions.
- [X] Merge the modernization PR from @jmortlock (multiple changes).
- [X] Update the documentation to reflect the modernization changes.
Issue #5.
This is a subtle problem to resolve. The specific case of a node being added to itself is trivial to resolve, and the fix has been put in for 0.8.3.
However, the general problem is that in the current code, a node
can be added as a child to any portion of the tree down the
hierarchy (e.g., as a grandchild), which will need a more thorough
detection code in the TreeNode#add method, if it is to be done at
runtime.
The issue is really to prevent the tree becoming a graph. Note that the issue is with duplicate nodes, not duplicated content.
A few options exist:
- Perform a runtime check in the
TreeNode#addmethod. This will cause a performance hit as the tree becomes larger. - Allow the additions to go through, but create a new
validatemethod that checks for such cycles. - Create separate configuration object which can be attached to the root of the tree, which allows per-tree configuration of the behavior - this does allow for the user to take control, but also introduces complications during tree mergers and spitting subtrees.
- Create a registry (to be maintained at the root?) of all nodes, and use this for validating the node additions (and preventing duplicates). This needs to be a hash (to allow O(1) access), and will sacrifice memory. There might be a need to restructure the internals to make better use of memory.
The semantic of length is probably unclear. Should return the node_depth instead (or remove the method)
The current equivalence of length to size should also be removed.