class Sycamore::Tree
A tree data structure as a recursively nested set of {#nodes nodes} of immutable values.
See {file:README.md} for a general introduction.
Constants
- ADDITIVE_COMMAND_METHODS
the names of all command methods, which add elements to a
Tree
- COMMAND_METHODS
the names of all methods, which change the state of a
Tree
- DESTRUCTIVE_COMMAND_METHODS
the names of all command methods, which delete elements from a
Tree
- PREDICATE_METHODS
the names of all query methods, which return a boolean
- PURE_ADDITIVE_COMMAND_METHODS
the names of all additive command methods, which only add elements from a
Tree
- PURE_DESTRUCTIVE_COMMAND_METHODS
the names of all destructive command methods, which only delete elements from a
Tree
- QUERY_METHODS
the names of all methods, which side-effect-freeze return only a value
Attributes
the internal hash representation of this tree
Public Class Methods
Creates a new empty Tree
.
# File lib/sycamore/tree.rb, line 67 def initialize end
Checks if the given object can be converted into a Tree
.
Ideally these would be implemented with Refinements, but since they aren't available anywhere (I'm looking at you, JRuby), we have to be content with this.
@param object [Object] @return [Boolean]
@api private
# File lib/sycamore/tree.rb, line 1421 def self.tree_like?(object) case object when Hash, Tree, Absence # ... ?! true else (object.respond_to? :tree_like? and object.tree_like?) # or ... end end
Creates a new Tree
and initializes it with the given data.
@param (see add
) @return [Tree]
@example
Tree[1] Tree[1, 2, 3] Tree[1, 2, 2, 3] # duplicates are ignored, so this results in the same tree as the previous Tree[x: 1, y: 2]
# File lib/sycamore/tree.rb, line 90 def self.with(*args) tree = new tree.add( args.size == 1 ? args.first : args ) unless args.empty? tree end
Public Instance Methods
Checks if this tree is a subtree of another tree.
@param other [Object] @return [Boolean]
@example
tree1 = Tree[a: 1, b: 2] tree2 = Tree[a: 1, b: 2, c: 3] tree1 < tree2 # => true tree2 < tree1 # => false tree1 < tree1 # => false
# File lib/sycamore/tree.rb, line 1214 def <(other) (other.is_a?(Tree) or other.is_a?(Absence)) and other.include?(self) and self != other end
Checks if this tree is a subtree or equal to another tree.
@param other [Object] @return [Boolean]
@example
tree1 = Tree[a: 1, b: 2] tree2 = Tree[a: 1, b: 2, c: 3] tree1 <= tree2 # => true tree2 <= tree1 # => false tree1 <= tree1 # => true
# File lib/sycamore/tree.rb, line 1231 def <=(other) (other.is_a?(Tree) or other.is_a?(Absence)) and other.include?(self) end
Checks if this tree has the same content as another tree, but ignores empty child trees.
@param other [Object] @return [Boolean]
@example
tree1 = Tree[a: 1, b: 2] tree2 = Tree[a: 1, b: 2, c: 3] tree3 = Tree[b: 2, a: 1] tree4 = Tree[a: 1, b: {2 => []}] tree1 == tree2 # => false tree1 == tree3 # => true tree1 == tree4 # => true
# File lib/sycamore/tree.rb, line 1194 def ==(other) (other.instance_of?(self.class) and size == other.size and all? { |node, child| other.include?(node) and other[node] == child }) or ((other.equal?(Nothing) or other.instance_of?(Absence)) and other == self) end
Checks if another tree is a subtree or equal to this tree.
@param other [Object] @return [Boolean]
@example
tree1 = Tree[a: 1, b: 2] tree2 = Tree[a: 1, b: 2, c: 3] tree1 > tree2 # => false tree2 > tree1 # => true tree1 > tree1 # => false
# File lib/sycamore/tree.rb, line 1265 def >(other) (other.is_a?(Tree) or other.is_a?(Absence)) and self.include?(other) and self != other end
Checks if another tree is a subtree or equal to this tree.
@param other [Object] @return [Boolean]
@example
tree1 = Tree[a: 1, b: 2] tree2 = Tree[a: 1, b: 2, c: 3] tree1 >= tree2 # => false tree2 >= tree1 # => true tree1 >= tree1 # => true
# File lib/sycamore/tree.rb, line 1248 def >=(other) (other.is_a?(Tree) or other.is_a?(Absence)) and self.include?(other) end
Replaces the contents of a child tree.
As this is just a call of {#replace} on the child tree, you can assign content to not existing child trees. Just like {#child_at} you can reference a deeper node with a path of nodes.
Note that even if you assign a {Sycamore::Tree} directly the given tree will not become part of this tree by reference.
An exception is the assignment of nil
or the {Nothing} tree: it will delete the child tree at the given path entirely. If you really want to overwrite the current child nodes with a single nil
node, you'll have to assign an array containing only nil
.
tree[:foo] = [nil]
@overload []=(*path, node)
Replaces the contents of the child at the given path with a single node. @param path [Array<Object>, Sycamore::Path] a path as a sequence of nodes or a {Path} object @param node [Object]
@overload []=(*path, node_collection)
Replaces the contents of the child at the given path with multiple nodes. @param path [Array<Object>, Sycamore::Path] a path as a sequence of nodes or a {Path} object @param node_collection [Enumerable]
@overload []=(*path, tree_structure)
Replaces the contents of the child at the given path with a tree structure of nodes. @param path [Array<Object>, Sycamore::Path] a path as a sequence of nodes or a {Path} object @param tree_structure [Hash, Tree]
@overload []=(*path, another_object)
Replaces the contents of the child at the given path with another path of nodes. @param path [Array<Object>, Sycamore::Path] a path as a sequence of nodes or a {Path} object @param path_object [Path]
@return the rvalue as for any Ruby assignment
@raise [InvalidNode] when given a nested node set
@example
tree = Tree[:foo] tree[:foo] = :bar tree.to_h # => {:foo => :bar} tree[:foo] = :baz tree.to_h # => {:foo => :baz} tree[1][2][3] = 4 tree[1, 2, 3] = 4 tree.to_h # => {:foo => :baz, 1 => {2 => {3 => 4}}} tree[1] = tree[:foo] tree.to_h # => {:foo => :baz, 1 => :baz} tree[:foo] << :bar tree.to_h # => {:foo => [:baz, :bar], 1 => :baz} tree[1] = Sycamore::Path[2,3] tree.to_h # => {:foo => [:baz, :bar], 1 => {2 => 3}} tree[:foo] = Sycamore::Nothing tree.to_h # => {:foo => nil, 1 => {2 => 3}}
# File lib/sycamore/tree.rb, line 473 def []=(*args) path, nodes_or_tree = args[0..-2], args[-1] raise ArgumentError, 'wrong number of arguments (given 1, expected 2)' if path.empty? if Nothing.like? nodes_or_tree if path.size == 1 clear_child_of_node(path.first) else path, node = path[0..-2], path[-1] child_at(*path).clear_child_of_node(node) end else child_at(*path).replace(nodes_or_tree) end end
Checks if this is an unresolved {Absence} or {Nothing}.
@return [Boolean]
# File lib/sycamore/tree.rb, line 137 def absent? false end
Adds nodes or a tree structure to this tree.
@overload add(node)
adds a single node @param node [Object]
@overload add(node_collection)
adds multiple nodes @param node_collection [Enumerable]
@overload add(tree_structure)
adds a tree structure of nodes @param tree_structure [Hash, Tree]
@overload add(path)
adds a {Path} of nodes @param path [Path]
@return self
as a proper command method
@raise [InvalidNode] when given a nested node set
@example
tree = Tree.new tree.add :foo tree.add [:bar, :baz] tree.add [:node, [:nested, :values]] # => raise Sycamore::InvalidNode, "[:nested, :values] is not a valid tree node" tree.add foo: 1, bar: {qux: 2} tree.add foo: [:node, [:nested, :values]] # => raise Sycamore::InvalidNode, "[:nested, :values] is not a valid tree node" tree.add Sycamore::Path[1,2,3] tree.to_h # => {:foo=>1, :bar=>{:qux=>2}, :baz=>nil, 1=>{2=>3}} tree = Tree.new tree[:foo][:bar] << :baz tree[:foo] << { bar: 1, qux: 2 } tree.to_h # => {:foo=>{:bar=>[:baz, 1], :qux=>2}}
# File lib/sycamore/tree.rb, line 210 def add(nodes_or_tree) case when nodes_or_tree.equal?(Nothing) then # do nothing when nodes_or_tree.is_a?(Tree) then add_tree(nodes_or_tree) when Tree.like?(nodes_or_tree) then add_tree(valid_tree! nodes_or_tree) when nodes_or_tree.is_a?(Path) then add_path(nodes_or_tree) when nodes_or_tree.is_a?(Enumerable) nodes_or_tree.all? { |node| valid_node_element! node } nodes_or_tree.each { |node| add(node) } else add_node(nodes_or_tree) end self end
@api private
# File lib/sycamore/tree.rb, line 245 def add_node_with_empty_child(node) valid_node! node if data.fetch(node, Nothing).nothing? data[node] = new_child(node) end self end
The child tree of a node at a path.
When a child at the given node path is not a present, an {Absence} object representing the missing tree is returned.
@overload child_at
(*nodes)
@param nodes [Array<Object>] a path as a sequence of nodes
@overload child_at
(path)
@param path [Path] a path as a {Sycamore::Path} object
@return [Tree, Absence] the child tree at the given path if present, otherwise an {Absence}
@example
tree = Tree[foo: {bar: 1}] tree[:foo].inspect # "#<Sycamore::Tree:0x3fea48e24f10 {:bar=>1}>" tree[:foo, :bar].inspect # "#<Sycamore::Tree:0x3fea48e24ed4 {1=>nil}>" tree[:foo, :baz].inspect # "absent child of node :baz in #<Sycamore::Tree:0x3fea48e24f10 {:bar=>1}>"
@todo Should we differentiate the case of a leaf and a not present node? How?
# File lib/sycamore/tree.rb, line 640 def child_at(*path) first = path.first case path.length when 0 raise ArgumentError, 'wrong number of arguments (given 0, expected 1+)' when 1 if first.is_a? Enumerable child_at(*first) else child_of(*path) end else child_of(first).child_at(*path[1..-1]) end end
The child tree of a node.
When a child to the given node is not a present, an {Absence} object representing the missing tree is returned.
@param node [Object] @return [Tree, Absence] the child tree of a node if present, otherwise an {Absence}
@raise [InvalidNode] when given an Enumerable
@example
tree = Tree[foo: 1] tree.child_of(:foo).inspect # "#<Sycamore::Tree:0x3fea48dd0e74 {1=>nil}>" tree.child_of(:bar).inspect # "absent child of node :bar in #<Sycamore::Tree:0x3fea48dd0f3c {:foo=>1}>"
@todo Should we differentiate the case of a leaf and a not present node? How?
# File lib/sycamore/tree.rb, line 612 def child_of(node) valid_node! node Nothing.like?(child = data[node]) ? Absence.at(self, node) : child end
Deletes all nodes and their children.
@return self
as a proper command method
@example
tree = Tree[1, 2, 3] tree.size # => 3 tree.clear tree.size # => 0
# File lib/sycamore/tree.rb, line 500 def clear data.clear self end
@api private
# File lib/sycamore/tree.rb, line 236 def clear_child_of_node(node) data[valid_node! node] = Nothing self end
Deletes all empty child trees recursively.
@return self
as a proper command method
@example
tree = Tree[foo: {bar: :baz}] tree[:foo, :bar].clear tree.to_h # => {foo: {bar: []}} tree.compact tree.to_h # => {foo: :bar}
# File lib/sycamore/tree.rb, line 518 def compact data.each do |node, child| case when child.nothing? then next when child.empty? then clear_child_of_node(node) else child.compact end end self end
Remove nodes or a tree structure from this tree.
If a given node is in the {#nodes} set, it gets deleted, otherwise it is silently ignored.
@overload delete(node)
deletes a single node @param node [Object]
@overload delete(node_collection)
deletes multiple nodes @param node_collection [Enumerable]
@overload delete(tree_structure)
deletes a tree structure of nodes @param tree_structure [Hash, Tree]
@overload delete(path)
deletes a {Path} of nodes @param path [Path]
@return self
as a proper command method
@raise [InvalidNode] when given a nested node set
@example
tree = Tree[ "a" => 100, "b" => 200, "c" => 300, "d" => {foo: [:bar, :baz]} ] tree.delete "a" tree.to_h # => {"b" => 200, "c" => 300, "d" => {foo: [:bar, :baz]}} tree.delete ["a", "b", "c"] tree.to_h # => {"d" => {foo: [:bar, :baz]}} tree.delete "d" => {foo: :bar} tree.to_h # => {"d" => {foo: :baz}} tree.delete "d" => {foo: :baz} tree.to_h # => {} tree = Tree[foo: {bar: :baz, qux: nil}] tree.delete Sycamore::Path[:foo, :bar, :baz] tree.to_h # => {foo: :qux}
# File lib/sycamore/tree.rb, line 321 def delete(nodes_or_tree) case when nodes_or_tree.is_a?(Tree) then delete_tree(nodes_or_tree) when Tree.like?(nodes_or_tree) then delete_tree(valid_tree! nodes_or_tree) when nodes_or_tree.is_a?(Path) then delete_path(nodes_or_tree) when nodes_or_tree.is_a?(Enumerable) nodes_or_tree.all? { |node| valid_node_element! node } nodes_or_tree.each { |node| delete node } else delete_node valid_node!(nodes_or_tree) end self end
Duplicates the whole tree.
@return [Tree]
# File lib/sycamore/tree.rb, line 1443 def dup duplicate = self.class.new.add(self) duplicate.taint if tainted? duplicate end
Iterates over all {#nodes nodes} of this tree.
Note that does not include the nodes of the child trees.
@overload each_node
Iterates over all {#nodes nodes} of this tree. @yield [Object] each node @return [Tree]
@overload each_node
Returns an enumerator over all {#nodes nodes} of this tree. @return [Enumerator<Object>]
@example
tree = Tree[ "a" => 100, "b" => 200 ] tree.each_node {|node| puts node } > a > b
# File lib/sycamore/tree.rb, line 761 def each_node(&block) return enum_for(__callee__) unless block_given? data.each_key(&block) self end
Iterates over all {#nodes nodes} and their child trees.
@overload each_pair
Iterates over all {#nodes nodes} and their child trees. @yield [Object, Tree] each node-child pair @return [Tree] +self+
@overload each_pair
Returns an enumerator over all {#nodes nodes} and their child trees. @return [Enumerator<Array(Object, Tree)>]
@example
tree = Tree[ "a" => 100, "b" => nil ] tree.each_pair {|node, child| puts "#{node} => #{child}" } > a => #<Tree[ 100 ]> > b => #<Tree: Nothing>
# File lib/sycamore/tree.rb, line 790 def each_pair(&block) return enum_for(__callee__) unless block_given? data.each_pair(&block) self end
Iterates over the {Path paths} to all leaves of this tree.
@overload each_path
Iterates over the {Path paths} to all leaves of this tree. @yieldparam [Path] path @return [Tree] +self+
@overload each_path
Returns an enumerator over the {Path paths} to all leaves of this tree. @return [Enumerator<Path>]
@example
tree = Tree[ "a" => 100, "b" => { foo: [:bar, :baz] } ] tree.each_path { |path| puts path } > #<Path: /a/100> > #<Path: /b/foo/bar> > #<Path: /b/foo/baz>
# File lib/sycamore/tree.rb, line 820 def each_path(with_ancestor: Path::ROOT, &block) return enum_for(__callee__) unless block_given? each do |node, child| if child.empty? yield Path[with_ancestor, node] else child.each_path(with_ancestor: with_ancestor.branch(node), &block) end end self end
Checks if this tree is empty.
@return [Boolean]
@example
Tree.new.empty? # => true Tree[a: 1].empty? # => false
# File lib/sycamore/tree.rb, line 1010 def empty? data.empty? end
Checks if this tree has the same content as another tree.
@param other [Object] @return [Boolean]
@example
tree1 = Tree[a: 1, b: 2] tree2 = Tree[a: 1, b: 2, c: 3] tree3 = Tree[b: 2, a: 1] tree4 = Tree[a: 1, b: {2 => []}] tree1.eql? tree2 # => false tree1.eql? tree3 # => true tree1.eql? tree4 # => false
# File lib/sycamore/tree.rb, line 1174 def eql?(other) (other.instance_of?(self.class) and data.eql?(other.data)) or (other.instance_of?(Absence) and other.eql?(self)) end
Checks if this is not an {Absence} or {Nothing}.
@return [Boolean]
# File lib/sycamore/tree.rb, line 146 def existent? not absent? end
Checks if all given nodes or that of the tree have no children.
@overload external?
Checks if all {#nodes} of this tree have no children. @return [Boolean]
@overload external?(*nodes)
Checks if all of the given nodes have no children. @param nodes [Array<Object, Path>] splat of nodes or Path objects @return [Boolean]
@example
Tree[1,2,3].leaves? # => true tree = Tree[x: 1, y: [], z: nil] tree.external? # => false tree.external?(:x, :y) # => false tree.external?(:y, :z) # => true tree.external?(:y, :z) # => true tree.external?(Sycamore::Path[:x, 1], :y) # => true
# File lib/sycamore/tree.rb, line 1102 def external?(*nodes) nodes = self.nodes if nodes.empty? nodes.all? { |node| leaf?(node) } end
The child tree of a node.
If the node can’t be found or has no child tree, there are several options:
-
With no other arguments, it will raise a
KeyError
exception when the node can’t be found or a {ChildError} exception (which is a subclass ofKeyError
) when the node has no child tree -
if
default
is given, then that will be returned; -
if the optional code block is specified, then that will be run and its result returned.
@param node [Object, Path] @param default [Object] optional @return [Tree, default]
@raise [InvalidNode] when given an Enumerable
as node @raise [KeyError] when the given node
can't be found @raise [ChildError] when no child for the given node
present
@example
tree = Tree[x: 1, y: nil, foo: {bar: :baz}] tree.fetch(:x) # #<Sycamore::Tree:0x3fc798a63854(1)> tree.fetch(:y) # => raise Sycamore::ChildError, "node :y has no child tree" tree.fetch(:z) # => raise KeyError, "key not found: :z" tree.fetch(:z, :default) # => :default tree.fetch(:y, :default) # => :default tree.fetch(:z) { :default } # => :default tree.fetch(Sycamore::Path[:foo, :bar]).nodes # => [:baz] tree.fetch(Sycamore::Path[:foo, :missing], :default) # => :default
@todo Should we differentiate the case of a leaf and a not present node? How?
# File lib/sycamore/tree.rb, line 690 def fetch(node, *default, &block) return fetch_path(node, *default, &block) if node.is_a? Path valid_node! node child = data.fetch(node, *default, &block) if child.equal? Nothing child = case when block_given? then yield when !default.empty? then default.first else raise ChildError, "node #{node.inspect} has no child tree" end end child end
The child tree of a node at a path.
If the node at the given path can’t be found or has no child tree, it behaves like {#fetch}.
@param path [Array<Object>, Path] @param default [Object] optional @return [Tree, default]
@raise [InvalidNode] when given an Enumerable
as node @raise [KeyError] when the given node
can't be found @raise [ChildError] when no child for the given node
present
@example
tree = Tree[foo: {bar: :baz}] tree.fetch_path([:foo, :bar]).nodes # => [:baz] tree.fetch_path [:foo, :bar, :baz] # => raise Sycamore::ChildError, "node :baz has no child tree" tree.fetch_path [:foo, :qux] # => raise KeyError, "key not found: :qux" tree.fetch_path([:a, :b], :default) # => :default tree.fetch_path([:a, :b]) { :default } # => :default tree.fetch_path([:foo, :bar, :baz], :default) # => :default
# File lib/sycamore/tree.rb, line 729 def fetch_path(path, *default, &block) default_case = block_given? || !default.empty? path.inject(self) do |tree, node| if default_case tree.fetch(node) { return block_given? ? yield : default.first } else tree.fetch(node) end end end
Deep freezes the whole tree.
@see ruby-doc.org/core/Object.html#method-i-freeze
# File lib/sycamore/tree.rb, line 1463 def freeze data.freeze each { |_, child| child.freeze } super end
A hash code of this tree.
@return [Fixnum]
# File lib/sycamore/tree.rb, line 1155 def hash data.hash ^ self.class.hash end
The length of the longest path of this tree.
@return [Fixnum]
@example
tree = Tree[a: 1, b: {2 => 3}] tree.height # => 3
# File lib/sycamore/tree.rb, line 996 def height return 0 if empty? paths.map(&:length).max end
Checks if some nodes or a full tree-like structure is included in this tree.
@param elements [Object, Array, Tree
, Hash] @return [Boolean]
@example
tree = Tree[ "a" => 100, "b" => 200, "c" => { foo: [:bar, :baz] } ] tree.include?("a") # => true tree.include?(:foo) # => false tree.include?(["a", "b"]) # => true tree.include?("c" => {foo: :bar}) # => true tree.include?("a", "b" => 200) # => true
# File lib/sycamore/tree.rb, line 901 def include?(*elements) raise ArgumentError, 'wrong number of arguments (given 0, expected 1+)' if elements.size == 0 return elements.all? { |element| include? element } if elements.size > 1 elements = elements.first case when Tree.like?(elements) elements.all? do |node, child| include_node?(node) and ( child.nil? or child.equal?(Nothing) or self.child_of(node).include?(child) ) end when elements.is_a?(Path) include_path? elements when elements.is_a?(Enumerable) elements.all? { |element| include_node? element } else include_node? elements end end
Checks if a node exists in the {#nodes nodes} set of this tree.
@param node [Object, Path] @return [Boolean]
@example
Tree[1,2,3].include_node? 3 # => true Tree[1 => 2].include_node? 2 # => false Tree[1 => 2].include_node? Sycamore::Path[1,2] # => true
# File lib/sycamore/tree.rb, line 877 def include_node?(node) return include_path?(node) if node.is_a? Path data.include?(node) end
Checks if a path of nodes exists in this tree.
@param args [Array<Object>, Path] a splat of nodes, an array of nodes or a {Path} object @return [Boolean]
@example
tree = Tree[ "a" => 100, "b" => 200, "c" => { foo: [:bar, :baz] } ] tree.include_path? "a", 200 # => false tree.include_path? "c", :foo, :bar # => true tree.include_path? ["c", :foo, :bar] # => true tree.include_path? Sycamore::Path["c", :foo, :bar] # => true
# File lib/sycamore/tree.rb, line 849 def include_path?(*args) case args.count when 0 then raise ArgumentError, 'wrong number of arguments (given 0, expected 1+)' when 1 then path = args.first else return include_path?(args) end path = [path] unless path.is_a? Enumerable if path.is_a? Path fetch_path(path.parent) { return false }.include? path.node else fetch_path(path[0..-2]) { return false }.include? path.last end end
Clones the whole tree.
# File lib/sycamore/tree.rb, line 1452 def initialize_clone(other) super clear_data add other end
A developer-friendly string representation of this tree in the usual Ruby +Object#inspect+ style.
@return [String]
# File lib/sycamore/tree.rb, line 1374 def inspect "#<#{self.class}:0x#{object_id.to_s(16)} #{ to_h(sleaf_child_as: Sycamore::NothingTree::NestedString).inspect}>" end
Checks if all given nodes or that of the tree have children.
@overload internal?
Checks if all {#nodes} of this tree have children. @return [Boolean]
@overload internal?(*nodes)
Checks if all of the given nodes have children. @param nodes [Array<Object, Path>] splat of nodes or Path objects @return [Boolean]
@example
Tree[x: 1, y: 2].internal? # => true tree = Tree[x: 1, y: [], z: nil] tree.internal? # => false tree.internal?(:x, :y) # => false tree.internal?(:y, :z) # => false tree.internal?(:x) # => true tree.internal?(:x) # => true tree.internal?(Sycamore::Path[:x, 1]) # => false
@todo Does it make sense to support the no arguments variant here and with this semantics?
One would expect it to be the negation of #external? without arguments.
# File lib/sycamore/tree.rb, line 1136 def internal?(*nodes) return false if self.empty? nodes = self.nodes if nodes.empty? nodes.all? { |node| not leaf?(node) and include_node?(node) } end
Checks if the given node has no children.
@param node [Object, Path] @return [Boolean]
@example
tree = Tree[x: 1, y: [], z: nil] tree.leaf?(:x) # => false tree.leaf?(:y) # => true tree.leaf?(:z) # => true tree.leaf?(Sycamore::Path[:x, 1]) # => true
# File lib/sycamore/tree.rb, line 1029 def leaf?(node) include_node?(node) && child_at(node).empty? end
Checks if another object matches this tree structurally and by content.
@param other [Object] @return [Boolean]
@example
Tree[foo: :bar] === Hash[foo: :bar] # => true Tree[1, 2, 3] === Array[1, 2, 3] # => true Tree[42] === 42 # => true
@todo This should probably apply a less strict equivalence comparison on the nodes.
Problem: Requires a solution which doesn't use +Hash#include?+.
# File lib/sycamore/tree.rb, line 1283 def matches?(other) case when Tree.like?(other) then matches_tree?(other) when other.is_a?(Enumerable) then matches_enumerable?(other) else matches_atom?(other) end end
Creates a new tree meant to be used as a child.
This method is used for instantiation of child trees. When you want to a tree with different types child trees, maybe depending on the parent node, you can subclass {Sycamore::Tree} and override this method to your needs. By default it creates trees of the same type as this tree.
@param parent_node [Object] of the child tree to be created @return [Tree]
@api private
# File lib/sycamore/tree.rb, line 114 def new_child(parent_node, *args) self.class.new(*args) end
The only node of this tree or an exception, if more {#nodes nodes} present.
@return [Object, nil] the single present node or nil
, if no nodes present
@raise [NonUniqueNodeSet] if more than one node present
@example
tree = Tree[foo: 1, bar: [2,3]] tree[:foo].node # => 1 tree[:baz].node # => nil tree[:bar].node # => raise Sycamore::NonUniqueNodeSet, "multiple nodes present: [2, 3]"
@see Tree#node!
# File lib/sycamore/tree.rb, line 566 def node nodes = self.nodes raise NonUniqueNodeSet, "multiple nodes present: #{nodes}" if nodes.size > 1 nodes.first end
The only node of this tree or an exception, if none or more {#nodes nodes} present.
@return [Object] the single present node
@raise [EmptyNodeSet] if no nodes present @raise [NonUniqueNodeSet] if more than one node present
@example
tree = Tree[foo: 1, bar: [2,3]] tree[:foo].node! # => 1 tree[:baz].node! # => raise Sycamore::EmptyNodeSet, "no node present" tree[:bar].node! # => raise Sycamore::NonUniqueNodeSet, "multiple nodes present: [2, 3]"
@see Tree#node
# File lib/sycamore/tree.rb, line 589 def node! raise EmptyNodeSet, 'no node present' if empty? node end
The nodes of this tree (without their children).
@return [Array<Object>]
@example
tree = Tree[foo: [:bar, :baz]] tree.nodes # => [:foo] tree[:foo].nodes # => [:bar, :baz]
# File lib/sycamore/tree.rb, line 544 def nodes data.keys end
Checks if this is the {Nothing} tree.
@return [Boolean]
# File lib/sycamore/tree.rb, line 128 def nothing? false end
Checks if this is not {#blank? blank}, i.e. {#empty? empty}.
@note This is not the negation of {#absent?}, since this would result in a
different behaviour than {http://api.rubyonrails.org/classes/Object.html#method-i-present-3F ActiveSupports present?} method. For the negation of {#absent?}, see {#existent?}.
@return [Boolean]
# File lib/sycamore/tree.rb, line 159 def present? not blank? end
Replaces the contents of this tree.
@overload replace(node)
Replaces the contents of this tree with a single node. @param node [Object]
@overload replace(node_collection)
Replaces the contents of this tree with multiple nodes. @param node_collection [Enumerable]
@overload replace(tree_structure)
Replaces the contents of this tree with a tree structure of nodes. @param tree_structure [Hash, Tree]
@overload replace(path)
Replaces the contents of this tree with a path of nodes. @param path [Path]
@return self
as a proper command method
@raise [InvalidNode] when given a nested node set
@example
tree = Tree[ "a" => 100, "b" => 200, "d" => {foo: [:bar, :baz]} ] tree.replace(new: :content) tree.to_h # => {new: :content}
# File lib/sycamore/tree.rb, line 410 def replace(nodes_or_tree) clear.add(nodes_or_tree) end
Searches the tree for one or multiple nodes or a complete tree.
@param nodes_or_tree [Object, Array, Tree
, Hash] @return [Array<Path>]
@example
tree = Tree[ "a" => [:foo, 100], "b" => { foo: [:bar, :baz] } ] tree.search :bar # => [Sycamore::Path["b", :foo]] tree.search :foo # => [Sycamore::Path["a"], Sycamore::Path["b"]] tree.search [:bar, :baz] # => [Sycamore::Path["b", :foo]] tree.search foo: :bar # => [Sycamore::Path["b"]] tree.search 42 # => []
# File lib/sycamore/tree.rb, line 937 def search(nodes_or_tree) _search(nodes_or_tree) end
The number of {#nodes nodes} in this tree.
Note, this does not count the nodes in the child trees.
@return [Fixnum]
@example
tree = Tree[ "d" => 100, "a" => 200, "v" => 300, "e" => [400, 500] ] tree.size # => 4 tree.delete("a") tree.size # => 3 tree["e"].size # => 2
# File lib/sycamore/tree.rb, line 963 def size data.size end
Checks if the given node has no children, even not an empty child tree.
@param node [Object] @return [Boolean]
@example
tree = Tree[x: 1, y: [], z: nil] tree.strict_leaf?(:x) # => false tree.strict_leaf?(:y) # => false tree.strict_leaf?(:z) # => true tree.strict_leaf?(Sycamore::Path[:x, 1]) # => true
# File lib/sycamore/tree.rb, line 1046 def strict_leaf?(node) include_node?(node) && child_at(node).absent? end
Checks if all given nodes or that of the tree have no children, even not an empty child tree.
@overload strict_leaves?()
Returns if all {#nodes} of this tree have no children, even not an empty child tree. @return [Boolean]
@overload strict_leaves?(*nodes)
Checks if all of the given nodes have no children, even not an empty child tree. @param nodes [Array<Object, Path>] splat of nodes or Path objects @return [Boolean]
@example
Tree[1,2,3].strict_leaves? # => true tree = Tree[x: 1, y: [], z: nil] tree.strict_leaves? # => false tree.strict_leaves?(:x, :y) # => false tree.strict_leaves?(:y, :z) # => false tree.strict_leaves?(:y, :z) # => false tree.strict_leaves?(:z, Sycamore::Path[:x, 1]) # => true
# File lib/sycamore/tree.rb, line 1073 def strict_leaves?(*nodes) nodes = self.nodes if nodes.empty? nodes.all? { |node| strict_leaf?(node) } end
A hash representation of this tree.
@return [Hash]
# File lib/sycamore/tree.rb, line 1343 def to_h(*args) return {} if empty? # not the nicest, but fastest way to inject on hashes, as noted here: # http://stackoverflow.com/questions/3230863/ruby-rails-inject-on-hashes-good-style hash = {} data.each do |node, child| hash[node] = child.to_native_object(*args) end hash end
A native Ruby object representing the content of the tree.
It is used by {#to_h} to produce flattened representations of child trees.
@api private
# File lib/sycamore/tree.rb, line 1327 def to_native_object(sleaf_child_as: nil, special_nil: false) case when empty? [] when strict_leaves? size == 1 && (!special_nil || !nodes.first.nil?) ? nodes.first : nodes else to_h(sleaf_child_as: sleaf_child_as, special_nil: special_nil) end end
A string representation of this tree.
@return [String]
# File lib/sycamore/tree.rb, line 1361 def to_s if (content = to_native_object(special_nil: true)).is_a? Enumerable "Tree[#{content.inspect[1..-2]}]" else "Tree[#{content.inspect}]" end end
The number of {#nodes nodes} in this tree and all of their children.
@return [Fixnum]
@example
tree = Tree[ "d" => 100, "a" => 200, "v" => 300, "e" => [400, 500] ] tree.total_size # => 9 tree.delete("a") tree.total_size # => 7 tree["e"].total_size # => 2
# File lib/sycamore/tree.rb, line 979 def total_size total = size data.each { |_, child| total += child.total_size } total end
Protected Instance Methods
# File lib/sycamore/tree.rb, line 941 def _search(query, current_path: Path::ROOT, results: []) results << current_path if include?(query) each do |node, child| child._search(query, current_path: current_path/node, results: results) end results end
# File lib/sycamore/tree.rb, line 227 def add_node(node) data[node] ||= Nothing self end
# File lib/sycamore/tree.rb, line 74 def clear_data @data = nil end
# File lib/sycamore/tree.rb, line 338 def delete_node(node) data.delete(node) self end
# File lib/sycamore/tree.rb, line 369 def delete_path(path) case path.length when 0 then return self when 1 then return delete_node(path.node) end parent = fetch_path(path.parent) { return self } parent.delete_node(path.node) delete_path(path.parent) if parent.empty? and not path.parent.root? self end
# File lib/sycamore/tree.rb, line 344 def delete_tree(tree) tree.each { |node_to_delete, child_to_delete| # using a {} block to circumvent this Rubinius issue: https://github.com/rubinius/rubinius-code/issues/7 next unless include? node_to_delete if Nothing.like?(child_to_delete) or (child_to_delete.respond_to?(:empty?) and child_to_delete.empty?) delete_node node_to_delete else fetch(node_to_delete, Nothing).tap do |child| case when child.empty? then next when Tree.like?(child_to_delete) child.delete_tree(child_to_delete) when child_to_delete.is_a?(Enumerable) child_to_delete.each { |node| child.delete_node node } else child.delete_node child_to_delete end delete_node(node_to_delete) if child.empty? end end } self end
Private Instance Methods
# File lib/sycamore/tree.rb, line 255 def add_child(node, children) return add_node(node) if Nothing.like?(children) add_node_with_empty_child(node) data[node] << children self end
# File lib/sycamore/tree.rb, line 270 def add_path(path) return self if path.root? path.parent.inject(self) { |tree, node| # using a {} block to circumvent this Rubinius issue: https://github.com/rubinius/rubinius-code/issues/7 tree.add_node_with_empty_child(node) tree[node] }.add_node path.node self end
# File lib/sycamore/tree.rb, line 264 def add_tree(tree) tree.each { |node, child| add_child(node, child) } self end
# File lib/sycamore/tree.rb, line 1293 def matches_atom?(other) not other.nil? and (size == 1 and nodes.first == other and leaf? other) end
# File lib/sycamore/tree.rb, line 1297 def matches_enumerable?(other) size == other.size and all? { |node, child| child.empty? and other.include?(node) } end
# File lib/sycamore/tree.rb, line 1302 def matches_tree?(other) size == other.size and all? { |node, child| if child.nothing? other.include?(node) and begin other_child = other.fetch(node, nil) not other_child or (other_child.respond_to?(:empty?) and other_child.empty?) end else child.matches? other[node] end } end
@api private
# File lib/sycamore/tree.rb, line 1403 def valid_node!(node) raise InvalidNode, "#{node} is not a valid tree node" if node.is_a? Enumerable node end
@api private
# File lib/sycamore/tree.rb, line 1393 def valid_node_element!(node) raise InvalidNode, "#{node} is not a valid tree node" if node.is_a?(Enumerable) and not node.is_a?(Path) and not Tree.like?(node) node end
@api private
# File lib/sycamore/tree.rb, line 1381 def valid_tree!(tree) tree.each { |node, child| # using a {} block to circumvent this Rubinius issue: https://github.com/rubinius/rubinius-code/issues/7 next if child.nil? valid_node!(node) valid_tree!(child) if Tree.like?(child) } tree end