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 ########################################################################