lib/sycamore/tree.rb in metaractor-sycamore-0.4.2 vs lib/sycamore/tree.rb in metaractor-sycamore-0.4.3
- old
+ new
@@ -1,14 +1,12 @@
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
@@ -17,15 +15,15 @@
# @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] << :[]=
+ 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] << :[]=
+ 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
@@ -36,25 +34,25 @@
%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? === ==]
+ 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] << :[]
+ 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]
+ 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
########################################################################
@@ -66,11 +64,11 @@
#
def initialize
end
protected def data
- @data ||= Hash.new
+ @data ||= {}
end
protected def clear_data
@data = nil
end
@@ -87,17 +85,17 @@
# 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.add((args.size == 1) ? args.first : args) unless args.empty?
tree
end
class << self
- alias from with
- alias [] with
+ alias_method :from, :with
+ alias_method :[], :with
end
##
# Creates a new tree meant to be used as a child.
#
@@ -113,11 +111,10 @@
#
def new_child(parent_node, *args)
self.class.new(*args)
end
-
########################################################################
# @group Absence and Nothing predicates
########################################################################
##
@@ -142,11 +139,11 @@
# Checks if this is not an {Absence} or {Nothing}.
#
# @return [Boolean]
#
def existent?
- not absent?
+ !absent?
end
##
# Checks if this is not {#blank? blank}, i.e. {#empty? empty}.
#
@@ -155,14 +152,13 @@
# method. For the negation of {#absent?}, see {#existent?}.
#
# @return [Boolean]
#
def present?
- not blank?
+ !blank?
end
-
########################################################################
# @group Element access
########################################################################
#####################
@@ -206,25 +202,28 @@
# 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)
+ if nodes_or_tree.equal?(Nothing) # do nothing
+ elsif nodes_or_tree.is_a?(Tree)
+ add_tree(nodes_or_tree)
+ elsif Tree.like?(nodes_or_tree)
+ add_tree(valid_tree!(nodes_or_tree))
+ elsif nodes_or_tree.is_a?(Path)
+ add_path(nodes_or_tree)
+ elsif 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
+ alias_method :<<, :add
protected def add_node(node)
data[node] ||= Nothing
self
@@ -317,48 +316,50 @@
# 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)
+ if nodes_or_tree.is_a?(Tree)
+ delete_tree(nodes_or_tree)
+ elsif Tree.like?(nodes_or_tree)
+ delete_tree(valid_tree!(nodes_or_tree))
+ elsif nodes_or_tree.is_a?(Path)
+ delete_path(nodes_or_tree)
+ elsif 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
+ alias_method :>>, :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?)
+ if Nothing.like?(child_to_delete) ||
+ (child_to_delete.respond_to?(:empty?) && 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
+ if child.empty?
+ next
+ elsif Tree.like?(child_to_delete)
+ child.delete_tree(child_to_delete)
+ elsif 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
@@ -366,17 +367,17 @@
self
end
protected def delete_path(path)
case path.length
- when 0 then return self
- when 1 then return delete_node(path.node)
+ 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?
+ delete_path(path.parent) if parent.empty? && !path.parent.root?
self
end
##
@@ -470,11 +471,11 @@
# 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?
+ 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
@@ -514,21 +515,23 @@
# 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
+ data.each do |node, child|
+ if child.nothing?
+ next
+ elsif child.empty?
+ clear_child_of_node(node)
+ else
+ child.compact
end
end
self
end
-
#####################
# query methods #
#####################
##
@@ -543,13 +546,12 @@
#
def nodes
data.keys
end
- alias keys nodes # Hash compatibility
+ alias_method :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
#
@@ -585,11 +587,11 @@
# tree[:bar].node! # => raise Sycamore::NonUniqueNodeSet, "multiple nodes present: [2, 3]"
#
# @see Tree#node
#
def node!
- raise EmptyNodeSet, 'no node present' if empty?
+ raise EmptyNodeSet, "no node present" if empty?
node
end
##
# The child tree of a node.
@@ -638,25 +640,25 @@
# @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
+ 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(first).child_at(*path[1..-1])
+ child_of(*path)
+ end
+ else
+ child_of(first).child_at(*path[1..])
end
end
- alias [] child_at
- alias dig child_at # Hash compatibility
+ alias_method :[], :child_at
+ alias_method :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:
@@ -691,14 +693,16 @@
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"
+ child = if block
+ yield
+ elsif !default.empty?
+ default.first
+ else
+ raise ChildError, "node #{node.inspect} has no child tree"
end
end
child
end
@@ -725,14 +729,14 @@
# 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?
+ default_case = block || !default.empty?
path.inject(self) do |tree, node|
if default_case
- tree.fetch(node) { return block_given? ? yield : default.first }
+ tree.fetch(node) { return block ? yield : default.first }
else
tree.fetch(node)
end
end
end
@@ -757,18 +761,18 @@
#
# > a
# > b
#
def each_node(&block)
- return enum_for(__callee__) unless block_given?
+ return enum_for(__callee__) unless block
data.each_key(&block)
self
end
- alias each_key each_node # Hash compatibility
+ alias_method :each_key, :each_node # Hash compatibility
##
# Iterates over all {#nodes nodes} and their child trees.
#
# @overload each_pair
@@ -786,18 +790,18 @@
#
# > a => #<Tree[ 100 ]>
# > b => #<Tree: Nothing>
#
def each_pair(&block)
- return enum_for(__callee__) unless block_given?
+ return enum_for(__callee__) unless block
data.each_pair(&block)
self
end
- alias each each_pair
+ alias_method :each, :each_pair
##
# Iterates over the {Path paths} to all leaves of this tree.
#
# @overload each_path
@@ -816,11 +820,11 @@
# > #<Path: /a/100>
# > #<Path: /b/foo/bar>
# > #<Path: /b/foo/baz>
#
def each_path(with_ancestor: Path::ROOT, &block)
- return enum_for(__callee__) unless block_given?
+ return enum_for(__callee__) unless block
each do |node, child|
if child.empty?
yield Path[with_ancestor, node]
else
@@ -829,11 +833,11 @@
end
self
end
- alias paths each_path
+ alias_method :paths, :each_path
##
# 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
@@ -846,24 +850,24 @@
# 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)
+ 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?
+ alias_method :path?, :include_path?
##
# Checks if a node exists in the {#nodes nodes} set of this tree.
#
# @param node [Object, Path]
@@ -878,13 +882,13 @@
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
+ alias_method :member?, :include_node? # Hash compatibility
+ alias_method :has_key?, :include_node? # Hash compatibility
+ alias_method :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]
@@ -897,28 +901,27 @@
# 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
+ 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
+ if Tree.like?(elements)
+ elements.all? do |node, child|
+ include_node?(node) and (child.nil? or child.equal?(Nothing) or
+ child_of(node).include?(child))
+ end
+ elsif elements.is_a?(Path)
+ include_path? elements
+ elsif 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.
@@ -939,11 +942,11 @@
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)
+ child._search(query, current_path: current_path / node, results: results)
end
results
end
##
@@ -980,11 +983,11 @@
total = size
data.each { |_, child| total += child.total_size }
total
end
- alias tsize total_size
+ alias_method :tsize, :total_size
##
# The length of the longest path of this tree.
#
# @return [Fixnum]
@@ -1009,11 +1012,11 @@
#
def empty?
data.empty?
end
- alias blank? empty?
+ alias_method :blank?, :empty?
##
# Checks if the given node has no children.
#
# @param node [Object, Path]
@@ -1045,11 +1048,11 @@
#
def strict_leaf?(node)
include_node?(node) && child_at(node).absent?
end
- alias sleaf? strict_leaf?
+ alias_method :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?()
@@ -1074,11 +1077,11 @@
nodes = self.nodes if nodes.empty?
nodes.all? { |node| strict_leaf?(node) }
end
- alias sleaves? strict_leaves?
+ alias_method :sleaves?, :strict_leaves?
##
# Checks if all given nodes or that of the tree have no children.
#
# @overload external?
@@ -1103,12 +1106,12 @@
nodes = self.nodes if nodes.empty?
nodes.all? { |node| leaf?(node) }
end
- alias leaves? external?
- alias flat? external?
+ alias_method :leaves?, :external?
+ alias_method :flat?, :external?
##
# Checks if all given nodes or that of the tree have children.
#
# @overload internal?
@@ -1132,19 +1135,18 @@
#
# @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?
+ return false if empty?
nodes = self.nodes if nodes.empty?
- nodes.all? { |node| not leaf?(node) and include_node?(node) }
+ nodes.all? { |node| !leaf?(node) and include_node?(node) }
end
- alias nested? internal?
+ alias_method :nested?, :internal?
-
########################################################################
# @group Comparison
########################################################################
##
@@ -1244,11 +1246,11 @@
# tree1 >= tree2 # => false
# tree2 >= tree1 # => true
# tree1 >= tree1 # => true
#
def >=(other)
- (other.is_a?(Tree) or other.is_a?(Absence)) and self.include?(other)
+ (other.is_a?(Tree) or other.is_a?(Absence)) and include?(other)
end
##
# Checks if another tree is a subtree or equal to this tree.
#
@@ -1261,11 +1263,11 @@
# 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
+ (other.is_a?(Tree) or other.is_a?(Absence)) and include?(other) and self != other
end
##
# Checks if another object matches this tree structurally and by content.
#
@@ -1279,21 +1281,23 @@
#
# @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)
+ if Tree.like?(other)
+ matches_tree?(other)
+ elsif other.is_a?(Enumerable)
+ matches_enumerable?(other)
+ else
+ matches_atom?(other)
end
end
- alias === matches?
+ alias_method :===, :matches?
private def matches_atom?(other)
- not other.nil? and (size == 1 and nodes.first == other and leaf? other)
+ !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) }
@@ -1302,19 +1306,19 @@
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?)
+ !other_child or
+ (other_child.respond_to?(:empty?) and other_child.empty?)
end
else
child.matches? other[node]
- end }
+ end
+ }
end
-
########################################################################
# @group Conversion
########################################################################
##
@@ -1323,17 +1327,16 @@
# 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)
+ if empty?
+ []
+ elsif 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.
@@ -1390,16 +1393,15 @@
# @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.is_a?(Enumerable) && !node.is_a?(Path) && !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
@@ -1418,19 +1420,19 @@
#
# @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 ...
+ when Hash, Tree, Absence # ... ?!
+ true
+ else
+ (object.respond_to? :tree_like? and object.tree_like?) # or ...
end
end
class << self
- alias like? tree_like?
+ alias_method :like?, :tree_like?
end
########################################################################
# @group Other standard Ruby methods
########################################################################
@@ -1439,12 +1441,11 @@
# Duplicates the whole tree.
#
# @return [Tree]
#
def dup
- duplicate = self.class.new.add(self)
- duplicate
+ self.class.new.add(self)
end
##
# Clones the whole tree.
#
@@ -1462,8 +1463,7 @@
def freeze
data.freeze
each { |_, child| child.freeze }
super
end
-
end # Tree
end # Sycamore