evolve75 / rubytree Goto Github PK

If a TreeNode n with parent p within a tree t1 is added as a child of p' within another tree t2, then n remains a child of p within t1 but inconsistently reports its parent to be p' (by calling TreeNode#parent).

I suggest to change behavior in one of the following two ways:
Change possibility 1: Adding n to p' gets a 'move' semantics, i.e. n is removed from p by adding n to p'.
Change possibility 2: Duplicate n, then add the copy to p' and leave t1 untouched.

Example:
t1 = Tree::TreeNode.new('1')
t1 << Tree::TreeNode.new('2') << Tree::TreeNode.new('4')
t1 << Tree::TreeNode.new('3') << Tree::TreeNode.new('5')
t['3'] << Tree::TreeNode.new('6')

t2 = t1.dup

t2['3'] << t1['2']['4']

t1['2']['4'].parent.name # => '3' !

It would be nice to have a TreeNode instance method find(name) that returns (if present) the TreeNode with the given (unique) name within the same tree as the receiver TreeNode.
Example:
t = Tree::TreeNode.new('1')
t << Tree::TreeNode.new('2') << Tree::TreeNode.new('4')
t << Tree::TreeNode.new('3') << Tree::TreeNode.new('5')
t['3'] << Tree::TreeNode.new('6')

t['2']['4'].find('3') # should return the TreeNode a.k.a. t['3']

When you create nodes with specifying an integer as the name of the node, finding a node like so @tree[node_name] results in the node at the index, not the node named as the integer. The test below fails:

   @root = Tree::TreeNode.new("ROOT", "Root Node")

      @child1 = Tree::TreeNode.new("Child1", "Child Node 1")
      @child2 = Tree::TreeNode.new("Child2", "Child Node 2")
      @child3 = Tree::TreeNode.new("Child3", "Child Node 3")
      @child4 = Tree::TreeNode.new("Child4", "Grand Child 1")
      @child5 = Tree::TreeNode.new("Child5", "Child Node 4")

      @n_root = Tree::TreeNode.new(0, "Root Node")

      @n_child1 = Tree::TreeNode.new(1, "Child Node 1")
      @n_child2 = Tree::TreeNode.new(2, "Child Node 2")
      @n_child3 = Tree::TreeNode.new(3, "Child Node 3")
      @n_child4 = Tree::TreeNode.new(4, "Grand Child 1")
      @n_child5 = Tree::TreeNode.new(5, "Child Node 4")


      @root << @child1
      @root << @child2
      @root << @child3 << @child4

      @n_root << @n_child1
      @n_root << @n_child2
      @n_root << @n_child3 << @n_child4

      assert_equal(@root['Child1'].name,'Child1') #passes
     assert_equal(@n_root[1].name,1) #fails

Perhaps integers should be explicitly disallowed as node names?

structured_warnings overrides warn -and that should scare you. This has caused several problems for us across a couple of codebases that have a dependency on RubyTree. Here's the latest issue: no such dynamic variable: disabled_warnings.

Stacktrace:

/web/releases/working/ROOT/WEB-INF/gems/gems/structured_warnings-0.2.0/lib/structured_warnings/dynamic.rb:26:in `here!'
org/jruby/RubyProc.java:271:in `call'
org/jruby/RubyHash.java:703:in `default'
org/jruby/RubyHash.java:1087:in `[]'
/web/releases/working/ROOT/WEB-INF/gems/gems/structured_warnings-0.2.0/lib/structured_warnings/dynamic.rb:55:in `[]'
/web/releases/working/ROOT/WEB-INF/gems/gems/structured_warnings-0.2.0/lib/structured_warnings.rb:38:in `disabled_warnings'
/web/releases/working/ROOT/WEB-INF/gems/gems/structured_warnings-0.2.0/lib/structured_warnings/warning.rb:54:in `active?'
/web/releases/working/ROOT/WEB-INF/gems/gems/structured_warnings-0.2.0/lib/structured_warnings/kernel.rb:61:in `warn'
/web/releases/working/ROOT/WEB-INF/gems/gems/active_utils-2.2.3/lib/active_utils/common/utils.rb:16:in `deprecated'
/web/releases/working/ROOT/WEB-INF/gems/gems/activemerchant-1.42.9/lib/active_merchant/billing/gateways/paypal/paypal_common_api.rb:125:in `credit'

ActiveMerchant is trying to call Kernel#warn but structured_warnings steps in and causes an otherwise non existent problem.

Hi,

I've been using the library a bit more and have come across a new bottleneck. A significant amount of time is being spent in error checking / assertions. While this is very useful during development, once the app has been verified as "correct" it would be great if it was possible to turn these off.

A few examples (these are the most expensive that I've come across):

https://github.com/evolve75/RubyTree/blob/master/lib/tree.rb#L215
https://github.com/evolve75/RubyTree/blob/master/lib/tree.rb#L219-L220
https://github.com/evolve75/RubyTree/blob/master/lib/tree.rb#L369

The problem is: I'm not quite sure how to solve it. The naïve solution is for me to fork the project and simply delete these lines, but maintaining a fork is lame and it might be an issue that others face. Deleting the lines in your repo would be unacceptable because they are very handy during dev.

Ideally, we could opt out of these checks. Sort of like this:

StandardWarning.disable do
  node = Tree::TreeNode.new 1234
end

But with an addition: if the warnings are disabled, the checks shouldn't happen at all -- instead of having the checks occur and not raising. Do you know what I mean or do I need to clarify?

The print_tree method fails (as does the Tree::TreeNode#each method) if the left_child of a Tree::BinaryTreeNode is nil.

tree1 = Tree::TreeNode.new("tree 1")
tree2 = Tree::TreeNode.new("tree 2")

# NoMethodError: undefined method `replace_with'
tree1.replace_with(tree2)

Also, replace! doesn't exist. Both methods are in the docs. http://rubytree.anupamsg.me/rdoc/Tree/TreeNode.html#replace_with-instance_method

Hi all,

I need postordered_each in my work, and could not found it in the gem version of RubyTree. Is it outdated? Thanks!

Tree::TreeNode#[] has an optional second parameter that can be provided to indicate that the "name" of a node is an integer. However, when a node is initialised with an integer as a name, a warning is raised in all cases.

Ideally, I'd like for no warnings to be printed to stdout when my program is running, but right now there isn't a parameter for Tree::TreeNode#initialize to indicate that an integer name is intentional and that I don't need to be warned.

Is there interest in providing such an option?

The default is for print_tree to send output to stdout, I would like the option to send it somewhere else by passing in and IO object to it.

Currently, I'm using this workaround, but I don't really like capturing all of stdout (even if temporarily):

def fetch_tree_text(tree)
  begin
    old_stdout = $stdout
    $stdout = StringIO.new
    tree.print_tree
    $stdout.string
  ensure
    $stdout = old_stdout
  end
end

I would much rather do something like this:

def fetch_tree_text(tree)
  string_io = StringIO.new
  tree.print_tree(io: string_io)
  string_io.string
end

Or maybe even better, have a method that does the same thing, but returns a string, instead sending to an IO.

I would like to be able to control the order in which child nodes get visited when I traverse them with each. I might be able to accomplish that if there was a sort_children! method, maybe like this. Assuming my content is an object that responds to a method "order" then:

subtree.sort_children! { |a, b| a.content.order <=> b.content.order }

would have the effect of reordering the leaves of that subtree so that subsequent iterations with each would encounter the leaves in said order.

Not sure I am making myself totally clear. Do you follow?

If TreeNode#postordered_each or TreeNode#breadth_each are called without a block to get the enumerators, these enumerators incorrectly enumerate in the same order as TreeNode#preordered_each. If called instead with blocks they enumerate correctly.
Example:
t = Tree::TreeNode.new('1')
t << Tree::TreeNode.new('2') << Tree::TreeNode.new('4')
t << Tree::TreeNode.new('3') << Tree::TreeNode.new('5')
t['3'] << Tree::TreeNode.new('6')
a = []
t.postordered_each {|n| a << n.name}
a # => ["4", "2", "5", "6", "3", "1"](correct postorder)
t.postordered_each.collect {|n| n.name} # => ["1", "2", "4", "3", "5", "6"](that's preorder instead of
postorder)

Pull request #9 changed the behavior of node name uniqueness, and this went out in release 0.9.3.

In the discussion on that pull request (#9 (comment)), it was pointed out "there is existing code which is using duplicate node names already, and this fix will break that code", which is true and broke my code which was using version 0.8.3.

From what I can tell, the reasoning behind the fix was twofold:

• The documentation states that the name must be unique within the entire tree
• The name is used implicitly as an "id" across the whole tree

I propose that a tree that looks like this should be perfectly valid:

* root
|---+ one
|    +---> deep
+---+ two
    +---> deep

The fact that there are two nodes with the name "deep" in this tree is irrelevant. They are not the same node, they just happen to have the same name.

Conceptually, when you retrieve nodes out of the tree, you do it like so:

root["one"]["deep"]
root["two"]["deep"]

If we expected all node names to be unique and used as a key within the entire tree, then we would expect this to work:

root["deep"]

But it doesn't, and it shouldn't.

It's worth noting that a node's name is used as an implicit id in two ways:

• As the key in @children_hash, which implies that the name is unique only among its siblings
• As the comparator in #<=>, which would then sort all the nodes in the tree by their name alone, which seems wrong

Rather than fundamentally changing the behavior of the tree to match the documentation, I think the following changes should be made:

• Fix the documentation such that node names must be unique among their siblings, not among the entire tree
• Change Tree::TreeNode#<=> so that the comparison is not based only on the node's name, but on a combination of the node's parent (or parentage array, if you prefer) and the node's name

Thoughts?

I'm using RubyTree for very large trees (file system trees), and I have subclassed the node to represent my file system nodes (and it's working beautifully!). As I recurse through the tree and call my class's methods, my console/log is spammed with tons and tons of this:

The camelCased methods are deprecated. Please use preexisting_fingerprint_timestamp instead of preexisting_fingerprint_timestamp (DeprecatedMethodWarning)

I noticed the warning has been removed in the latest code... any chance you could release a new version of the gem?

Running this test with RSpec:

require "rspec"
require "tree"

describe 'tree' do
  it 'does something' do
    tree = Tree::TreeNode.new("")
    expect(tree).to eq(Object.new)
    end
end

Turtles all the way down when the expectation fails:

➜  treetest  rspec treetest_spec.rb
/Users/jon/.rvm/gems/ruby-2.2.2@treetest/gems/rspec-expectations-3.2.1/lib/rspec/matchers/built_in/eq.rb:35: warning: Comparable#== will no more rescue exceptions of #<=> in the next release.
/Users/jon/.rvm/gems/ruby-2.2.2@treetest/gems/rspec-expectations-3.2.1/lib/rspec/matchers/built_in/eq.rb:35: warning: Return nil in #<=> if the comparison is inappropriate or avoid such comparison.
F

Failures:

  1) tree does something
     Failure/Error: expect(tree).to eq(Object.new)
     SystemStackError:
       stack level too deep
     # /Users/jon/.rvm/gems/ruby-2.2.2@treetest/gems/rubytree-0.9.6/lib/tree.rb:643:in `each'
     ...recurses into oblivion...
     # /Users/jon/.rvm/gems/ruby-2.2.2@treetest/gems/rubytree-0.9.6/lib/tree.rb:643:in `each'
     # ./treetest_spec.rb:7:in `block (2 levels) in <top (required)>'

It behaves normally when the test passes. Interestingly, fails normally when compared to a fixnum. For example, using eq(1) results in a normal test fail.

version info:

ruby 2.2.2p95 (2015-04-13 revision 50295) [x86_64-darwin14]

*** LOCAL GEMS ***

bigdecimal (1.2.6)
bundler-unload (1.0.2)
diff-lcs (1.2.5)
executable-hooks (1.3.2)
gem-wrappers (1.2.7)
io-console (0.4.3)
json (1.8.1)
minitest (5.4.3)
power_assert (0.2.2)
psych (2.0.8)
rake (10.4.2)
rdoc (4.2.0)
rspec (3.2.0)
rspec-core (3.2.3)
rspec-expectations (3.2.1)
rspec-mocks (3.2.1)
rspec-support (3.2.2)
rubygems-bundler (1.4.4)
rubytree (0.9.6)
rvm (1.11.3.9)
structured_warnings (0.2.0)
test-unit (3.0.8)

I have created a tree as by the example in the README:

require 'tree'
require 'JSON'
root_node = Tree::TreeNode.new("ROOT", "Root Content")
root_node << Tree::TreeNode.new("CHILD1", "Child1 Content") << Tree::TreeNode.new("GRANDCHILD1", "GrandChild1 Content")
root_node << Tree::TreeNode.new("CHILD2", "Child2 Content")

I then create a JSON string from this tree:

j = root_node.to_json
=> {"name":"ROOT","json_class":"Tree::TreeNode","content":"Root Content","children":[{"name":"CHILD1","json_class":"Tree::TreeNode","content":"Child1 Content","children":[{"name":"GRANDCHILD1","json_class":"Tree::TreeNode","content":"GrandChild1 Content"}]},{"name":"CHILD2","json_class":"Tree::TreeNode","content":"Child2 Content"}]}

Then I want to create a new tree from the generated JSON:

other_node = Tree::TreeNode.json_create(j)

However, this results in an exception:

NoMethodError: undefined method `name' for "children":String
from /Users/ariejan/.rvm/gems/ruby-1.8.7-p249/gems/rubytree-0.7.0/lib/tree.rb:242:in `add'
from /Users/ariejan/.rvm/gems/ruby-1.8.7-p249/gems/rubytree-0.7.0/lib/tree.rb:219:in `<<'
from /Users/ariejan/.rvm/gems/ruby-1.8.7-p249/gems/rubytree-0.7.0/lib/tree.rb:756:in `json_create'
from /Users/ariejan/.rvm/gems/ruby-1.8.7-p249/gems/rubytree-0.7.0/lib/tree.rb:755:in `each'
from /Users/ariejan/.rvm/gems/ruby-1.8.7-p249/gems/rubytree-0.7.0/lib/tree.rb:755:in `json_create'

I get this warning on ruby 3.0.* :

Warning:[rake --tasks] D:/program/dvlt/ruby/Ruby30-x64/lib/ruby/gems/3.0.0/gems/rubytree-1.0.0/lib/tree/utils/camel_case_method_handler.rb:61:in protected': warning: calling protected without arguments inside a method may not have the intended effect (StructuredWarnings::BuiltInWarning)

Perhaps it would be possible to suppress the whole CamelCaseMethodHandler module? It is only needed to allow deprecated methods names.

Or simply replace 'protected' with 'protected :to_snake_case' ?

Cheers

Just try this code by mistake:

node = Tree::TreeNode.new("Root")
node << node

And it throw following exception:

SystemStackError: stack level too deep
    from /Users/leo.liang/.rvm/gems/ruby-1.9.3-p125@des_scorecard/gems/rubytree-0.8.2/lib/tree.rb:508

As it try to output node in irb.

It maybe better to check the input data and prevent user to change node if they add children node that may cause loop.

Small issue. I try to use this method print_tree in my project, however, it just give me:

__path_name__/autoload.rb:28:in `<top (required)>': undefined method `print_tree' for #<Tree::TreeNode:0x007fedd91e8268> (NoMethodError)
Did you mean?  printTree

(Although I solved it just by changing to printTree method, however, the README should be updated OR according to the Ruby style guide it should be named as print_tree)

Hi thanks for the gem
I found I needed a way to find a node in a tree that has auto generated node names
So I added this recursive search method in the tree.rb file

# Recursive search for a node by name returns the node if found or nil if not.
#
#@return Tree::TreeNode | nil
def find_node(f_name)
  node=nil
  if name ==f_name
      return self
  else
      children { |child| 
          node=child.find_node(f_name)
          if node!=nil
             break
          end
          }
        return node
    end
end

Just thought I'd pass it on
Cheers
zkt

As requested per #70 kindly asking for a rubygems version 1.0.1 to publish fix for protected syntax warning.

Title says it all, JSON.parse is returning the default hash instead of tree

json file

{
  "name": "ROOT",
  "content": null,
  "json_class": "Tree::TreeNode",
  "children": [
    {
      "name": "NON-ROOT",
      "content": null,
      "json_class": "Tree::TreeNode",
      "children": [
        {
          "name": "NON-ROOT-2",
          "content": null,
          "json_class": "Tree::TreeNode"
        }
      ]
    }
  ]
}

r = JSON.parse(File.read('config/routes.json'))

=> {"name"=>"ROOT", "content"=>nil, "json_class"=>"Tree::TreeNode", "children"=>[{"name"=>"NON-ROOT", "content"=>nil, "json_class"=>"Tree::TreeNode", "children"=>[{"name"=>"NON-ROOT-2", "content"=>nil, "json_class"=>"Tree::TreeNode"}]}]}

r.class

=> Hash

rubytree version 0.9.7
JSON version 1.8.3
on JRUBY 9.0.5.0

..and it's my fault. Refer to b3b8863

require 'rubytree'
n1 = Tree::TreeNode.new 'n1'
n2 = Tree::TreeNode.new 'n2'
n3 = Tree::TreeNode.new 'n3'
n4 = Tree::TreeNode.new 'n4'
n1 << n2
n2 << n3
n3.node_depth # => 2
n4 << n1
n3.node_depth # => 2

The second time #node_depth is called on n3, it should return 3, not 2. The caching is problematic because it is only cleared when the direct parent node is changed, but is not cleared when nodes further up the tree are changed.

I suppose the best course of action for now is:

1. Revert that commit
2. Add a unit test so this regression doesn't happen again
3. (maybe) try to think of a better way to retain this optimisation

My sincere apologies for introducing this bug into your library!

Hi,

first of all thanks a lot for all the developers and maintainers of this gem.

I have a quick question regarding the license of this gem. In this repository you link to the bsd-2-clause. On Ruby Gems it states BSD-3-Clause-Clear.

I am not an license expert so please excuse a poentially stupid question: What is the correct license of the rubytree gem? And can you confirm that this is compatible with OpenProject that uses GPLv3?

Best regards and thanks a lot in advance
Niels

Since the name of each node is unique, I am wondering if there can be a way to access a node by its name, without traversing the whole tree. This probably only makes sense at the root node.

The method #<=> does not behave in the way the doc says.

The doc of #<=> says

Comparison is based on the natural ordering of the node name objects.

Returns: (Integer) — +1 if this node is a ‘successor’, 0 if equal and -1 if this node is a ‘predecessor’. Returns ‘nil’ if the other object is not a ‘Tree::TreeNode’.

So, actually, the descriptions contradict.

In the current version (2.0.0 and HEAD(60629c1)), #<=> behaves in the former way, that is, the comparison is based on #name and is valid only for the descendants of Tree::TreeNode.

Personally, I think the latter should be the way.
I have forked the repository to implement it (see below).

Here is the justification for the latter policy, that i, judging on the basis of "successor" or "predecessor".

1. Arguably, the comparison based on #name is not intuitive, when there are definitive "successor-predecessor" or parent-child (and sibling) relationships between elements in TreeNode. Personally, when I first used this library, I didn't imagine that would be the case (and scratched my head, not understanding how it worked)... According to the doc, the meaning of #name is no more than the ID, and the fact that it is the key parameter for Comparable is mentioned only in the above-mentioned sentence in the method #<=>, which is a bit obscured and surprising...
2. Currently, nodes that have different roots are comparable, which is in my opinion neither intuitive nor useful (in most cases).
3. Comparison based on #name can be very easily implemented with users anyway, such as, sort{|a, b| a.name <=> b.name}.
4. How to define "successor-predecessor" is not definitive in the sense not everyone agrees completely. I can think of a few candidates as listed below.
   1. Perhaps (though arguable), the most convincing comparison with the spaceship operator <=> (and hence < and >) would be to follow the order of #each. If an instance A appears before instance B in #each, A < B or (A <=> B) == -1 holds. If their root nodes are different, it returns nil, because it does not make sense to compare them.
   2. An alternative is to follow the order of breadth-first search; that is, If an instance A appears before instance B in #breadth_each, then A < B or (A <=> B) == -1 holds.
   3. Another possibility is similar but more restrictive, and returns nil if they are not in the direct ancestor-descendant line or direct siblings, that is, uncle-nephew relationships or cousin relationships would return nil.
   4. Last and most strict criterion is similar to the previous one but returns nil if they are siblings, namely only ancestor-descendant relationships are allowed.

I am well aware this would be in practice a backward-incompatible change in the specifications, although it does follow the current doc (at least in the second part), and that is the only cons I can think of.

I have forked the repository from the current head (60629c1 on 24 Jun) and implemented the above-mentioned four algorithms plus the current <=> one in the new method #cmp. The method #cmp takes an optional parameter :policy for which one of :each (Default) (above-mentioned case 1), :breadth_each (case 2), :direct_or_sibling (case 3), :direct_only (case 4), and :name (emulation of the current <=>) is accepted. See def test_cmp in /test/test_tree.rb for demonstrations.

I note that methods < and > in the forked repo are unaffected and behave in the same way as the current <=> because #<=> is not modified.

My fork is https://github.com/masasakano/RubyTreeCmpOperator and the current head is 1f6127a. All tests (I added over 100 assertions for the new method) have passed.

A final note is, if you stick to the current "name"-based comparison, I think it is conceptually better to replace return nil in def <=>(other) with return super (which should in practice always return nil, that is, there would be no change in behaviour).

Thank you,
Masa

Cycle detection should be fairly easy to add using Ruby's built-in TSort module. It will reduce performance unless done carefully, but I managed to monkey patch a version of RubyTree that works with polytrees and errors out if you try to add a node that would create a cycle (vanilla RubyTree produces an infinite loop).

I have to detect cycles as a business requirement of my code, since I'm building a tree representation of untrusted data that SHOULD NOT have cycles, but may anyway (and if a cycle is detected, we need to go yell at someone, basically).

Any method that enumerates, iterates, or otherwise traverses the tree needs to implement cycle detection, or you will potentially get an infinite loop or (in the case of recursion) an infinite recursion and stack overflow.

At first I started by including TSort mixin into the TreeNode class, then I implemented the required tsort methods as follows:

def tsort_each_node(&block)
  self.each(&block)
end

def tsort_each_child(node, &block)
  node.children(&block)
end

Then I augmented the add method as follows, right before returning child:

# ... all the stuff before the last line of the method
#CYCLE DETECTION - raises TSort::Cyclic if this caused a cycle
  begin
    root.tsort()
  rescue TSort::Cyclic => exce
    self.remove!(child)
    raise exce
  end

Funnily enough, this doesn't work, because somewhere in this method before the return call, to_s() is getting implicitly invoked (perhaps that's a bug in and of itself, since it causes unnecessary string building when we aren't even asking about a string representation of the node). to_s() in turn asks for the size(), which can get stuck in an infinite loop on a cycle. So can the root accessor. That one is particularly sneaky (IMO).

Perhaps to avoid the performance hit this could only be enabled upon user request, but I don't really have time to develop the feature and test it fully, especially not with the full robustness expected (where if cycle detection is disabled, there is no added overhead, but if it's enabled, every possible functionality that could cause cycles to be found will throw an exception).

Anyway, just wanted to point out that it should at least be uncomplicated from an algorithmic perspective to add cycle detection when we have a reasonably efficient cycle detection algorithm built into Ruby. It's very easy to integrate it into RubyTree, at least for detecting cycles on add().

Whenever I try to print one of my trees, I get an undefined NoMethodError:

NoMethodError: undefined methodprint_tree' for #Tree::TreeNode:0x9a23588`

Any idea what could be going on?

Warning class could not be used in 2.4 ruby, cause ruby has The same class
More info in schmidt/structured_warnings#7
Please remove structured_warnings dependency

I would like to be able to control the order in which child nodes get visited when I traverse them with each. I might be able to accomplish that if there was a sort_children! method, maybe like this. Assuming my content is an object that responds to a method "order" then:

subtree.sort_children! { |a, b| a.content.order <=> b.content.order }

would have the effect of reordering the leaves of that subtree so that subsequent iterations with each would encounter the leaves in said order.

Not sure I am making myself totally clear. Do you follow?

Sorry I'm new to github so i don't know much about it. Here's an example to illustrate this bug

irb(main):001:0> require 'tree'
=> true
irb(main):002:0> trunk = Tree::TreeNode.new("trunk")
=> Node Name: trunk Content:  Parent: <None> Children: 0 Total Nodes: 1
irb(main):003:0> trunk << Tree::TreeNode.new("branch")
=> Node Name: branch Content:  Parent: trunk Children: 0 Total Nodes: 1
irb(main):004:0> trunk["branch"] << Tree::TreeNode.new("twig")
NoMethodError: undefined method `<<' for nil:NilClass
        from (irb):4
        from C:/Ruby193/bin/irb:12:in `<main>'
irb(main):005:0> trunk << Tree::TreeNode.new("BRANCH")
=> Node Name: BRANCH Content:  Parent: trunk Children: 0 Total Nodes: 1
irb(main):006:0> trunk["BRANCH"] << Tree::TreeNode.new("TWIG")
=> Node Name: TWIG Content:  Parent: BRANCH Children: 0 Total Nodes: 1
irb(main):007:0>

Hi All,

During my work I needed to retrieve the path for some nodes so i've implemented the following code:

class Tree::TreeNode
  def path_as_string(separator)
    get_path_array().reverse.join(separator)
  end

  def path_as_array()
    get_path_array().reverse
  end

  def get_path_array(current_array_path = [])
    path_array = current_array_path + [name]
    if !parent
      return path_array
    else
      path_array=parent.get_path_array(path_array)
      return path_array
    end
  end
end

I though it may be useful for someone else to have something similar.
Thanks

I understand that TreeNode#each walks the whole subtree starting at itself.

I would have thought that TreeNode#find would search similarly as it also comes from Enumerable, but I must be misunderstanding. Can you explain?

Please remove strict dependency on JSON gem in gemspec, as JSON v.2 is out:

s.add_runtime_dependency 'json'                , '~> 1.8'

running the example via ruby examples/example_basic.rb gives

examples/example_basic.rb:30:in <main>': undefined methodprint_tree' for #Tree::TreeNode:0xb8008a6c (NoMethodError)

After upgrading my project to Ruby 2.7, the following warning is being emitted:

/home/chris/.rbenv/versions/2.7.1/lib/ruby/gems/2.7.0/gems/rubytree-1.0.0/lib/tree/utils/camel_case_method_handler.rb:61:in `protected': calling protected without arguments inside a method may not have the intended effect (StructuredWarnings::BuiltInWarning)

Does this gem support graph data structures as well

The inclusion of structured_warnings breaks Logger#warn.

Seems sortof like bad form to include a library that monkey patches the standard library.

RubyTree uses recursion for methods such as each and detached_subtree_copy. This is ok for smaller well-balanced trees, but fails for unbalanced trees when Fiber or Threads are involved.

Constructing and Walking a Linear Tree

See the following example method to construct a linear tree:

#!/usr/bin/ruby
require "tree"

def run_test(depth=100)
    tree = Tree::TreeNode.new("/")
    current = tree
    depth.times do |i|
        new_node = Tree::TreeNode.new("#{i}")
        current << new_node
        current = new_node
    end
    tree.each{|n| nil}
end

This runs fine when executed in the main thread...

puts "Run test in the main thread"
run_test()

...but fails when a Fiber or Thread is involved:

puts "Run test in a fiber"
begin
    Fiber.new do
        run_test()
    end.resume
rescue SystemStackError
    puts "Fiber died."
end

puts "Run test in a thread"
begin
    Thread.abort_on_exception = true
    Thread.new do
        run_test(600) # 600 is not chosen arbitrary: this is the first number where it fails here.
    end
    sleep(3)
rescue SystemStackError
    puts "Thread died."
end

Note that the recursion depth between Fiber and Thread differs.

Demo Output

The example script above produces the following output with my machine:

% ./example.rb
Run test in the main thread
Run test in a fiber
Fiber died.
Run test in a thread
Thread died.

Possible Solution

This should be resolvable by replacing the recursion in each, detached_subtree_copy and elsewhere with the respective iterative representation. each could possibly be fixed like this:

module Tree
    class TreeNode
        def each(&blk)
            expand_nodes = [self]
            while expand_nodes != []
                current = expand_nodes.shift
                yield current
                expand_nodes = current.children.concat(expand_nodes)
            end
        end
    end

Not sure this is a feature request or simply a question. It seems to me that the 'content' slot is very often going to contain an aggregate of some kind, a Hash or a Struct or something like that. Does it make sense to build that in? So instead of having to initialize my own aggregate object, one is assigned there by default -- or maybe there's some better solution.

I realize the philosophy might be that everyone has a separate need so why make an assumption. Just put in a 'content' attribute and let everyone use it as they like. Just checking whether I am missing a trick!

We get this error

Buildr aborted!
TypeError : Tree is not a module
rvm/gems/ruby-2.1.2/gems/rubytree-0.9.4/lib/tree/version.rb:38:in <top (required)>' rvm/rubies/ruby-2.1.2/lib/ruby/site_ruby/2.1.0/rubygems/custom_require.rb:36:inrequire'
rvm/rubies/ruby-2.1.2/lib/ruby/site_ruby/2.1.0/rubygems/custom_require.rb:36:in require' rvm/gems/ruby-2.1.2/gems/rubytree-0.9.4/lib/tree/tree_deps.rb:43:in<top (required)>'
rvm/rubies/ruby-2.1.2/lib/ruby/site_ruby/2.1.0/rubygems/custom_require.rb:36:in `require'

Documentation says this about node name: "Expected to be unique within the tree". But what could happend when names are not unique? In many cases you really don't need to care about it, you don't need a unique id.
I'd like you make a comment about it in documentation.

Thank you for your project! And congraturatons! You got rubytree is the facto ruby standart for a very very important data structure.

Hi, I'm a newbie as a ruby programmer, so please forgive me if I'm wrong.
I have experienced some problems with TreeNode#to_s, when the TreeNode content is not a String.

An example:

    Tree::TreeNode.new "hello",{}

gives this output:

    TypeError: can't convert Hash into String
from /usr/local/lib/ruby/gems/1.9.1/gems/rubytree-0.8.1/lib/tree.rb:187:in `+'
from /usr/local/lib/ruby/gems/1.9.1/gems/rubytree-0.8.1/lib/tree.rb:187:in `to_s'
from /usr/local/bin/irb:12:in `<main>'

I solved this problem changing the old TreeNode#to_s method to this:

   def to_s
      "Node Name: #{@name}" +
      " Content: #{@content || "<Empty>"} " +
      " Parent: #{(is_root?() ? "<None>" : @parent.name)} " +
      " Children: #{@children.length}" +
      " Total Nodes: #{size()}"
   end

Hi,

Is there a way to find an item named foo in the tree and, if the foo item isn't unique, a method to find all of its occurrences ?

I need to create a dependency tree and because a dependency can exist multiple time, I need to find all it's occurrence to add it's dependencies.

Both this and netaddr gem have top-level files called tree.rb. require 'tree' then doesn't load the rubytree's tree.rb

We could resolve this by adding a file called rubytree.rb that requires the tree.rb from the local path.

There are inconsistencies with how Ruby on Rails and how this gem interpret what is and what isn't a valid Hash which trigger the argument error in the hash_converter.rb

pry(main)> ActiveSupport::HashWithIndifferentAccess.new({}).is_a?(Hash)
=> true
pry(main)> children = ActiveSupport::HashWithIndifferentAccess.new({})
=> {}
pry(main)> [Hash, NilClass].include?(children.class)
=> false

Example

[33] pry(main)> test_arr = [
  {
    title: 'string hash (indifferent, new key, hash value)',
    hash: { 'key' => nil }.with_indifferent_access.tap do |h|
      h['key2'] = { 'key3' => nil }
    end
  }
]
=> [{:title=>"string hash (indifferent, new key, hash value)", :hash=>{"key"=>nil, "key2"=>{"key3"=>nil}}}]

[34] pry(main)> test_arr.each do |test|
  puts test[:title]
  puts JSON.pretty_generate(test[:hash])
  Tree::TreeNode.new(:root).tap do |tree|
    tree.add_from_hash(sorted_hash_for_tree_load(test[:hash]))
  end.print_tree; 0
rescue => e
  puts e.message
string hash (indifferent, new key, hash value)
{
  "key": null,
  "key2": {
    "key3": null
  }
}
Invalid child. Must be nil or hash.
=> [{:title=>"string hash (indifferent, new key, hash value)", :hash=>{"key"=>nil, "key2"=>{"key3"=>nil}}}]

I think RubyTree should have convenience methods to convert built-in hierarchical structures to trees. I propose Tree.create_from_hash(hash) as a class method. After all, you have JSON input/output, why not built-in data structures. I'd like for it to work with arbitrary nested hashes.

A few questions:
Is it OK as a class method? I think it makes sense.
Naming: do you prefer Tree.create_from_hash() or Tree.from_hash()?
Would you want it directly in the Tree class or split out into utility class like JSON is?