lib/sycamore/tree.rb in sycamore-0.2.1 vs lib/sycamore/tree.rb in sycamore-0.3.0
- old
+ new
@@ -44,11 +44,11 @@
eql? matches? === ==]
# the names of all methods, which side-effect-freeze return only a value
QUERY_METHODS = PREDICATE_METHODS +
%i[new_child dup hash to_native_object to_h to_s inspect
- node node! nodes keys child_of child_at dig fetch search
+ node node! nodes keys child_of child_at dig fetch fetch_path search
size total_size tsize height
each each_path paths each_node each_key each_pair] << :[]
%i[COMMAND_METHODS QUERY_METHODS PREDICATE_METHODS
ADDITIVE_COMMAND_METHODS DESTRUCTIVE_COMMAND_METHODS
@@ -175,81 +175,78 @@
#
# @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: {baz: 2}
+ # 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}}
#
- # @todo support Paths
- #
def add(nodes_or_tree)
case
- when Tree.like?(nodes_or_tree) then add_tree(nodes_or_tree)
- when nodes_or_tree.is_a?(Enumerable) then add_nodes(nodes_or_tree)
- else add_node(nodes_or_tree)
+ 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
alias << add
- private def add_node(node)
- return self if node.equal? Nothing
- return add_tree(node) if Tree.like? node
- raise InvalidNode, "#{node} is not a valid tree node" if node.is_a? Enumerable
-
+ protected def add_node(node)
@data[node] ||= Nothing
self
end
- private def add_nodes(nodes)
- nodes.each { |node| add_node(node) }
+ ##
+ # @api private
+ #
+ def clear_child_of_node(node)
+ @data[valid_node! node] = Nothing
self
end
##
# @api private
#
def add_node_with_empty_child(node)
- raise InvalidNode, "#{node} is not a valid tree node" if node.is_a? Enumerable
+ valid_node! node
if @data.fetch(node, Nothing).nothing?
@data[node] = new_child(node)
end
self
end
- ##
- # @api private
- #
- def clear_child_of_node(node)
- raise InvalidNode, "#{node} is not a valid tree node" if node.is_a? Enumerable
-
- @data[node] = Nothing
-
- self
- end
-
private def add_child(node, children)
return add_node(node) if Nothing.like?(children)
add_node_with_empty_child(node)
@data[node] << children
@@ -261,10 +258,21 @@
tree.each { |node, child| add_child(node, child) }
self
end
+ private 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
+
##
# 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.
@@ -279,10 +287,14 @@
#
# @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
@@ -293,57 +305,75 @@
# 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}
#
- # @todo support Paths
- #
def delete(nodes_or_tree)
case
- when Tree.like?(nodes_or_tree) then delete_tree(nodes_or_tree)
- when nodes_or_tree.is_a?(Enumerable) then delete_nodes(nodes_or_tree)
- else delete_node(nodes_or_tree)
+ 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
alias >> delete
- private def delete_node(node)
- return delete_tree(node) if Tree.like? node
- raise InvalidNode, "#{node} is not a valid tree node" if node.is_a? Enumerable
-
+ protected def delete_node(node)
@data.delete(node)
self
end
- private def delete_nodes(nodes)
- nodes.each { |node| delete_node(node) }
-
- self
- end
-
- private def delete_tree(tree)
- tree.each { |node, child| # using a {} block to circumvent this Rubinius issue: https://github.com/rubinius/rubinius-code/issues/7
- raise InvalidNode, "#{node} is not a valid tree node" if node.is_a? Enumerable
- next unless include? node
- if Nothing.like?(child) or (child.respond_to?(:empty?) and child.empty?)
- delete_node node
+ protected 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
- child_of(node).tap do |this_child|
- this_child.delete child
- delete_node(node) if this_child.empty?
+ 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
+ protected 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
+
##
# Replaces the contents of this tree.
#
# @overload replace(node)
# Replaces the contents of this tree with a single node.
@@ -355,10 +385,14 @@
#
# @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
@@ -400,10 +434,15 @@
# @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
@@ -417,12 +456,14 @@
# 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 => :baz}
+ # tree.to_h # => {:foo => nil, 1 => {2 => 3}}
#
def []=(*args)
path, nodes_or_tree = args[0..-2], args[-1]
raise ArgumentError, 'wrong number of arguments (given 1, expected 2)' if path.empty?
@@ -560,11 +601,11 @@
# 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?
#
def child_of(node)
- raise InvalidNode, "#{node} is not a valid tree node" if node.is_a? Enumerable
+ valid_node! node
Nothing.like?(child = @data[node]) ? Absence.at(self, node) : child
end
##
@@ -616,45 +657,82 @@
# node can’t be found or a {ChildError} exception (which is a subclass of
# +KeyError+) 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]
+ # @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]
+ # 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(: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?
#
def fetch(node, *default, &block)
- raise InvalidNode, "#{node} is not a valid tree node" if node.is_a? Enumerable
+ 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} has no child tree"
+ 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
+ #
+ 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
+
+ ##
# Iterates over all {#nodes nodes} of this tree.
#
# Note that does not include the nodes of the child trees.
#
# @overload each_node
@@ -760,37 +838,40 @@
# tree.include_path? "c", :foo, :bar # => true
# tree.include_path? ["c", :foo, :bar] # => true
# tree.include_path? Sycamore::Path["c", :foo, :bar] # => true
#
def include_path?(*args)
- raise ArgumentError, 'wrong number of arguments (given 0, expected 1+)' if args.count == 0
- first = args.first
- if first.is_a? Enumerable
- return include_path?(*first) if args.count == 1
- raise InvalidNode, "#{first} is not a valid tree node"
+ 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 args.count == 1
- include? first
+ if path.is_a? Path
+ fetch_path(path.parent) { return false }.include? path.node
else
- include?(first) and child_of(first).include_path?(args[1..-1])
+ fetch_path(path[0..-2]) { return false }.include? path.last
end
end
alias path? include_path?
##
# Checks if a node exists in the {#nodes nodes} set of this tree.
#
- # @param node [Object]
+ # @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
#
def include_node?(node)
+ return include_path?(node) if node.is_a? Path
+
@data.include?(node)
end
alias member? include_node? # Hash compatibility
alias has_key? include_node? # Hash compatibility
@@ -926,21 +1007,22 @@
alias blank? empty?
##
# Checks if the given node has no children.
#
- # @param node [Object]
+ # @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
#
def leaf?(node)
- include_node?(node) && child_of(node).empty?
+ include_node?(node) && child_at(node).empty?
end
##
# Checks if the given node has no children, even not an empty child tree.
#
@@ -950,13 +1032,14 @@
# @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
#
def strict_leaf?(node)
- include_node?(node) && child_of(node).absent?
+ include_node?(node) && child_at(node).absent?
end
alias sleaf? strict_leaf?
##
@@ -966,19 +1049,21 @@
# 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>] splat of nodes
+ # @param nodes [Array<Object, Path>] splat of nodes or Path objects
# @return [Boolean]
#
# @example
# Tree[1,2,3].strict_leaves? # => true
- # tree = Tree[a: :foo, b: :bar, c: []]
+ # 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
#
def strict_leaves?(*nodes)
nodes = self.nodes if nodes.empty?
nodes.all? { |node| strict_leaf?(node) }
@@ -993,19 +1078,21 @@
# 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>] splat of nodes
+ # @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.leaves? # => false
- # tree.leaves?(:x, :y) # => false
- # tree.leaves?(:y, :z) # => true
+ # 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
#
def external?(*nodes)
nodes = self.nodes if nodes.empty?
nodes.all? { |node| leaf?(node) }
@@ -1021,20 +1108,22 @@
# 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>] splat of nodes
+ # @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.
#
def internal?(*nodes)
@@ -1278,10 +1367,40 @@
def inspect
"#<#{self.class}:0x#{object_id.to_s(16)} #{
to_h(sleaf_child_as: Sycamore::NothingTree::NestedString).inspect}>"
end
+ # @api private
+ #
+ private 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
+
+ # @api private
+ #
+ private 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
+ #
+ private def valid_node!(node)
+ raise InvalidNode, "#{node} is not a valid tree node" if node.is_a? Enumerable
+
+ node
+ 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
@@ -1302,10 +1421,9 @@
end
class << self
alias like? tree_like?
end
-
########################################################################
# @group Other standard Ruby methods
########################################################################