module Sycamore ## # A tree data structure as a recursively nested set of {#nodes nodes} of immutable values. # # See {file:README.md} for a general introduction. # class Tree include Enumerable # the internal hash representation of this tree attr_reader :data protected :data ######################################################################## # @group CQS reflection ######################################################################## # the names of all command methods, which add elements to a Tree ADDITIVE_COMMAND_METHODS = %i[add << replace add_node_with_empty_child clear_child_of_node] << :[]= # the names of all command methods, which delete elements from a Tree DESTRUCTIVE_COMMAND_METHODS = %i[delete >> clear compact replace clear_child_of_node] << :[]= # the names of all additive command methods, which only add elements from a Tree PURE_ADDITIVE_COMMAND_METHODS = ADDITIVE_COMMAND_METHODS - DESTRUCTIVE_COMMAND_METHODS # the names of all destructive command methods, which only delete elements from a Tree PURE_DESTRUCTIVE_COMMAND_METHODS = DESTRUCTIVE_COMMAND_METHODS - ADDITIVE_COMMAND_METHODS # the names of all methods, which change the state of a Tree COMMAND_METHODS = ADDITIVE_COMMAND_METHODS + DESTRUCTIVE_COMMAND_METHODS + %i[freeze] # the names of all query methods, which return a boolean PREDICATE_METHODS = %i[nothing? absent? existent? present? blank? empty? include? include_node? member? key? has_key? include_path? path? >= > < <= leaf? leaves? internal? external? flat? nested? sleaf? sleaves? strict_leaf? strict_leaves? 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 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 PURE_ADDITIVE_COMMAND_METHODS PURE_DESTRUCTIVE_COMMAND_METHODS] .each do |method_set| define_singleton_method(method_set.downcase) { const_get method_set } end ######################################################################## # @group Construction ######################################################################## ## # Creates a new empty Tree. # def initialize end protected def data @data ||= Hash.new end protected def clear_data @data = nil 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] # def self.with(*args) tree = new tree.add( args.size == 1 ? args.first : args ) unless args.empty? tree end class << self alias from with alias [] with 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 # def new_child(parent_node, *args) self.class.new(*args) end ######################################################################## # @group Absence and Nothing predicates ######################################################################## ## # Checks if this is the {Nothing} tree. # # @return [Boolean] # def nothing? false end ## # Checks if this is an unresolved {Absence} or {Nothing}. # # @return [Boolean] # def absent? false end ## # Checks if this is not an {Absence} or {Nothing}. # # @return [Boolean] # def existent? not absent? 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] # def present? not blank? end ######################################################################## # @group Element access ######################################################################## ##################### # command methods # ##################### ## # 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}} # 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 alias << add protected def add_node(node) data[node] ||= Nothing self end ## # @api private # def clear_child_of_node(node) data[valid_node! node] = Nothing self end ## # @api private # def add_node_with_empty_child(node) valid_node! node if data.fetch(node, Nothing).nothing? data[node] = new_child(node) end 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 self end private def add_tree(tree) tree.each { |node, child| add_child(node, child) } self end private def add_path(path) return self if path.root? path.parent.inject(self) do |tree, node| tree.add_node_with_empty_child(node) tree[node] end.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. # # @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} # 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 alias >> delete protected def delete_node(node) data.delete(node) self end protected def delete_tree(tree) tree.each do |node_to_delete, child_to_delete| 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 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. # @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} # def replace(nodes_or_tree) clear.add(nodes_or_tree) 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, 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, 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, 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, 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}} # 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 ## # 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 # def clear data.clear 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} # 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 ##################### # query methods # ##################### ## # The nodes of this tree (without their children). # # @return [Array] # # @example # tree = Tree[foo: [:bar, :baz]] # tree.nodes # => [:foo] # tree[:foo].nodes # => [:bar, :baz] # def nodes data.keys end alias keys nodes # Hash compatibility ## # 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! # 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 # def node! raise EmptyNodeSet, 'no node present' if empty? node 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 # "#nil}>" # tree.child_of(:bar).inspect # "absent child of node :bar in #1}>" # # @todo Should we differentiate the case of a leaf and a not present node? How? # def child_of(node) valid_node! node Nothing.like?(child = data[node]) ? Absence.at(self, node) : child 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] 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 # "#1}>" # tree[:foo, :bar].inspect # "#nil}>" # tree[:foo, :baz].inspect # "absent child of node :baz in #1}>" # # @todo Should we differentiate the case of a leaf and a not present node? How? # 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 alias [] child_at alias dig child_at # Hash compatibility ## # 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 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, 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) # # # 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) 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, 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 # 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] # # @example # tree = Tree[ "a" => 100, "b" => 200 ] # tree.each_node {|node| puts node } # # > a # > b # def each_node(&block) return enum_for(__callee__) unless block_given? data.each_key(&block) self end alias each_key each_node # Hash compatibility ## # 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] # # @example # tree = Tree[ "a" => 100, "b" => nil ] # tree.each_pair {|node, child| puts "#{node} => #{child}" } # # > a => # # > b => # # def each_pair(&block) return enum_for(__callee__) unless block_given? data.each_pair(&block) self end alias each each_pair ## # 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] # # @example # tree = Tree[ "a" => 100, "b" => { foo: [:bar, :baz] } ] # tree.each_path { |path| puts path } # # > # # > # # > # # 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 alias paths each_path ## # Checks if a path of nodes exists in this tree. # # @param args [Array, 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 # 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 alias path? include_path? ## # 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 # 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 alias key? include_node? # Hash compatibility ## # 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 # 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 ## # Searches the tree for one or multiple nodes or a complete tree. # # @param nodes_or_tree [Object, Array, Tree, Hash] # @return [Array] # # @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 # => [] # def search(nodes_or_tree) _search(nodes_or_tree) end protected 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 ## # 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 # def size data.size 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 # def total_size total = size data.each { |_, child| total += child.total_size } total end alias tsize total_size ## # The length of the longest path of this tree. # # @return [Fixnum] # # @example # tree = Tree[a: 1, b: {2 => 3}] # tree.height # => 3 # def height return 0 if empty? paths.map(&:length).max end ## # Checks if this tree is empty. # # @return [Boolean] # # @example # Tree.new.empty? # => true # Tree[a: 1].empty? # => false # def empty? data.empty? end alias blank? empty? ## # 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 # def leaf?(node) include_node?(node) && child_at(node).empty? 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 # def strict_leaf?(node) include_node?(node) && child_at(node).absent? end alias sleaf? strict_leaf? ## # 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] 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 # def strict_leaves?(*nodes) nodes = self.nodes if nodes.empty? nodes.all? { |node| strict_leaf?(node) } end alias sleaves? strict_leaves? ## # 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] 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 # def external?(*nodes) nodes = self.nodes if nodes.empty? nodes.all? { |node| leaf?(node) } end alias leaves? external? alias flat? external? ## # 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] 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) return false if self.empty? nodes = self.nodes if nodes.empty? nodes.all? { |node| not leaf?(node) and include_node?(node) } end alias nested? internal? ######################################################################## # @group Comparison ######################################################################## ## # A hash code of this tree. # # @return [Fixnum] # def hash data.hash ^ self.class.hash 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 # 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 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 # 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 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 # 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 # def <=(other) (other.is_a?(Tree) or other.is_a?(Absence)) and other.include?(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 # => true # def >=(other) (other.is_a?(Tree) or other.is_a?(Absence)) and self.include?(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 # => false # def >(other) (other.is_a?(Tree) or other.is_a?(Absence)) and self.include?(other) and self != other 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?+. # 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 alias === matches? private def matches_atom?(other) not other.nil? and (size == 1 and nodes.first == other and leaf? other) end private def matches_enumerable?(other) size == other.size and all? { |node, child| child.empty? and other.include?(node) } end private 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 ######################################################################## # @group Conversion ######################################################################## ## # 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 # 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 hash representation of this tree. # # @return [Hash] # def to_h(...) 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(...) end hash end ## # A string representation of this tree. # # @return [String] # 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 ## # A developer-friendly string representation of this tree in the usual Ruby +Object#inspect+ style. # # @return [String] # 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 do |node, child| next if child.nil? valid_node!(node) valid_tree!(child) if Tree.like?(child) end 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 # content with this. # # @param object [Object] # @return [Boolean] # # @api private # 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 class << self alias like? tree_like? end ######################################################################## # @group Other standard Ruby methods ######################################################################## ## # Duplicates the whole tree. # # @return [Tree] # def dup duplicate = self.class.new.add(self) duplicate.taint if tainted? duplicate end ## # Clones the whole tree. # def initialize_clone(other) super clear_data add other end ## # Deep freezes the whole tree. # # @see http://ruby-doc.org/core/Object.html#method-i-freeze # def freeze data.freeze each { |_, child| child.freeze } super end end # Tree end # Sycamore