class Sycamore::Tree

A tree data structure as a recursively nested set of {#nodes nodes} of immutable values.

See {file:README.md} for a general introduction.

Constants

ADDITIVE_COMMAND_METHODS

the names of all command methods, which add elements to a Tree

COMMAND_METHODS

the names of all methods, which change the state of a Tree

DESTRUCTIVE_COMMAND_METHODS

the names of all command methods, which delete elements from a Tree

PREDICATE_METHODS

the names of all query methods, which return a boolean

PURE_ADDITIVE_COMMAND_METHODS

the names of all additive command methods, which only add elements from a Tree

PURE_DESTRUCTIVE_COMMAND_METHODS

the names of all destructive command methods, which only delete elements from a Tree

QUERY_METHODS

the names of all methods, which side-effect-freeze return only a value

Attributes

data[R]

the internal hash representation of this tree

Public Class Methods

[](*args)
Alias for: with
from(*args)
Alias for: with
like?(object)
Alias for: tree_like?
new() click to toggle source

Creates a new empty Tree.

# File lib/sycamore/tree.rb, line 67
def initialize
end
tree_like?(object) click to toggle source

Checks if the given object can be converted into a Tree.

Ideally these would be implemented with Refinements, but since they aren't available anywhere (I'm looking at you, JRuby), we have to be content with this.

@param object [Object] @return [Boolean]

@api private

# File lib/sycamore/tree.rb, line 1421
def self.tree_like?(object)
  case object
    when Hash, Tree, Absence # ... ?!
      true
    else
      (object.respond_to? :tree_like? and object.tree_like?) # or ...
  end
end
Also aliased as: like?
with(*args) click to toggle source

Creates a new Tree and initializes it with the given data.

@param (see add) @return [Tree]

@example

Tree[1]
Tree[1, 2, 3]
Tree[1, 2, 2, 3]  # duplicates are ignored, so this results in the same tree as the previous
Tree[x: 1, y: 2]
# File lib/sycamore/tree.rb, line 90
def self.with(*args)
  tree = new
  tree.add( args.size == 1 ? args.first : args ) unless args.empty?
  tree
end
Also aliased as: from, []

Public Instance Methods

<(other) click to toggle source

Checks if this tree is a subtree of another tree.

@param other [Object] @return [Boolean]

@example

tree1 = Tree[a: 1, b: 2]
tree2 = Tree[a: 1, b: 2, c: 3]
tree1 < tree2  # => true
tree2 < tree1  # => false
tree1 < tree1  # => false
# File lib/sycamore/tree.rb, line 1214
def <(other)
  (other.is_a?(Tree) or other.is_a?(Absence)) and other.include?(self) and self != other
end
<<(nodes_or_tree)
Alias for: add
<=(other) click to toggle source

Checks if this tree is a subtree or equal to another tree.

@param other [Object] @return [Boolean]

@example

tree1 = Tree[a: 1, b: 2]
tree2 = Tree[a: 1, b: 2, c: 3]
tree1 <= tree2  # => true
tree2 <= tree1  # => false
tree1 <= tree1  # => true
# File lib/sycamore/tree.rb, line 1231
def <=(other)
  (other.is_a?(Tree) or other.is_a?(Absence)) and other.include?(self)
end
==(other) click to toggle source

Checks if this tree has the same content as another tree, but ignores empty child trees.

@param other [Object] @return [Boolean]

@example

tree1 = Tree[a: 1, b: 2]
tree2 = Tree[a: 1, b: 2, c: 3]
tree3 = Tree[b: 2, a: 1]
tree4 = Tree[a: 1, b: {2 => []}]
tree1 == tree2  # => false
tree1 == tree3  # => true
tree1 == tree4  # => true
# File lib/sycamore/tree.rb, line 1194
def ==(other)
  (other.instance_of?(self.class) and size == other.size and
    all? { |node, child| other.include?(node) and other[node] == child }) or
    ((other.equal?(Nothing) or other.instance_of?(Absence)) and
      other == self)
end
===(other)
Alias for: matches?
>(other) click to toggle source

Checks if another tree is a subtree or equal to this tree.

@param other [Object] @return [Boolean]

@example

tree1 = Tree[a: 1, b: 2]
tree2 = Tree[a: 1, b: 2, c: 3]
tree1 > tree2  # => false
tree2 > tree1  # => true
tree1 > tree1  # => false
# File lib/sycamore/tree.rb, line 1265
def >(other)
  (other.is_a?(Tree) or other.is_a?(Absence)) and self.include?(other) and self != other
end
>=(other) click to toggle source

Checks if another tree is a subtree or equal to this tree.

@param other [Object] @return [Boolean]

@example

tree1 = Tree[a: 1, b: 2]
tree2 = Tree[a: 1, b: 2, c: 3]
tree1 >= tree2  # => false
tree2 >= tree1  # => true
tree1 >= tree1  # => true
# File lib/sycamore/tree.rb, line 1248
def >=(other)
  (other.is_a?(Tree) or other.is_a?(Absence)) and self.include?(other)
end
>>(nodes_or_tree)
Alias for: delete
[](*path)
Alias for: child_at
[]=(*args) click to toggle source

Replaces the contents of a child tree.

As this is just a call of {#replace} on the child tree, you can assign content to not existing child trees. Just like {#child_at} you can reference a deeper node with a path of nodes.

Note that even if you assign a {Sycamore::Tree} directly the given tree will not become part of this tree by reference.

An exception is the assignment of nil or the {Nothing} tree: it will delete the child tree at the given path entirely. If you really want to overwrite the current child nodes with a single nil node, you'll have to assign an array containing only nil.

tree[:foo] = [nil]

@overload []=(*path, node)

Replaces the contents of the child at the given path with a single node.
@param path [Array<Object>, Sycamore::Path] a path as a sequence of nodes or a {Path} object
@param node [Object]

@overload []=(*path, node_collection)

Replaces the contents of the child at the given path with multiple nodes.
@param path [Array<Object>, Sycamore::Path] a path as a sequence of nodes or a {Path} object
@param node_collection [Enumerable]

@overload []=(*path, tree_structure)

Replaces the contents of the child at the given path with a tree structure of nodes.
@param path [Array<Object>, Sycamore::Path] a path as a sequence of nodes or a {Path} object
@param tree_structure [Hash, Tree]

@overload []=(*path, another_object)

Replaces the contents of the child at the given path with another path of nodes.
@param path [Array<Object>, Sycamore::Path] a path as a sequence of nodes or a {Path} object
@param path_object [Path]

@return the rvalue as for any Ruby assignment

@raise [InvalidNode] when given a nested node set

@example

tree = Tree[:foo]
tree[:foo] = :bar
tree.to_h  # => {:foo => :bar}
tree[:foo] = :baz
tree.to_h  # => {:foo => :baz}
tree[1][2][3] = 4
tree[1, 2, 3] = 4
tree.to_h  # => {:foo => :baz, 1 => {2 => {3 => 4}}}
tree[1] = tree[:foo]
tree.to_h  # => {:foo => :baz, 1 => :baz}
tree[:foo] << :bar
tree.to_h  # => {:foo => [:baz, :bar], 1 => :baz}
tree[1] = Sycamore::Path[2,3]
tree.to_h  # => {:foo => [:baz, :bar], 1 => {2 => 3}}
tree[:foo] = Sycamore::Nothing
tree.to_h  # => {:foo => nil, 1 => {2 => 3}}
# File lib/sycamore/tree.rb, line 473
def []=(*args)
  path, nodes_or_tree = args[0..-2], args[-1]
  raise ArgumentError, 'wrong number of arguments (given 1, expected 2)' if path.empty?

  if Nothing.like? nodes_or_tree
    if path.size == 1
      clear_child_of_node(path.first)
    else
      path, node = path[0..-2], path[-1]
      child_at(*path).clear_child_of_node(node)
    end
  else
    child_at(*path).replace(nodes_or_tree)
  end
end
absent?() click to toggle source

Checks if this is an unresolved {Absence} or {Nothing}.

@return [Boolean]

# File lib/sycamore/tree.rb, line 137
def absent?
  false
end
add(nodes_or_tree) click to toggle source

Adds nodes or a tree structure to this tree.

@overload add(node)

adds a single node
@param node [Object]

@overload add(node_collection)

adds multiple nodes
@param node_collection [Enumerable]

@overload add(tree_structure)

adds a tree structure of nodes
@param tree_structure [Hash, Tree]

@overload add(path)

adds a {Path} of nodes
@param path [Path]

@return self as a proper command method

@raise [InvalidNode] when given a nested node set

@example

tree = Tree.new
tree.add :foo
tree.add [:bar, :baz]
tree.add [:node, [:nested, :values]]  # => raise Sycamore::InvalidNode, "[:nested, :values] is not a valid tree node"
tree.add foo: 1, bar: {qux: 2}
tree.add foo: [:node, [:nested, :values]]  # => raise Sycamore::InvalidNode, "[:nested, :values] is not a valid tree node"
tree.add Sycamore::Path[1,2,3]
tree.to_h  # => {:foo=>1, :bar=>{:qux=>2}, :baz=>nil, 1=>{2=>3}}

tree = Tree.new
tree[:foo][:bar] << :baz
tree[:foo] << { bar: 1, qux: 2 }
tree.to_h  # => {:foo=>{:bar=>[:baz, 1], :qux=>2}}
# File lib/sycamore/tree.rb, line 210
def add(nodes_or_tree)
  case
    when nodes_or_tree.equal?(Nothing) then # do nothing
    when nodes_or_tree.is_a?(Tree)     then add_tree(nodes_or_tree)
    when Tree.like?(nodes_or_tree)     then add_tree(valid_tree! nodes_or_tree)
    when nodes_or_tree.is_a?(Path)     then add_path(nodes_or_tree)
    when nodes_or_tree.is_a?(Enumerable)
      nodes_or_tree.all? { |node| valid_node_element! node }
      nodes_or_tree.each { |node| add(node) }
    else add_node(nodes_or_tree)
  end

  self
end
Also aliased as: <<
add_node_with_empty_child(node) click to toggle source

@api private

# File lib/sycamore/tree.rb, line 245
def add_node_with_empty_child(node)
  valid_node! node

  if data.fetch(node, Nothing).nothing?
    data[node] = new_child(node)
  end

  self
end
blank?()
Alias for: empty?
child_at(*path) click to toggle source

The child tree of a node at a path.

When a child at the given node path is not a present, an {Absence} object representing the missing tree is returned.

@overload child_at(*nodes)

@param nodes [Array<Object>] a path as a sequence of nodes

@overload child_at(path)

@param path [Path] a path as a {Sycamore::Path} object

@return [Tree, Absence] the child tree at the given path if present, otherwise an {Absence}

@example

tree = Tree[foo: {bar: 1}]
tree[:foo].inspect        # "#<Sycamore::Tree:0x3fea48e24f10 {:bar=>1}>"
tree[:foo, :bar].inspect  # "#<Sycamore::Tree:0x3fea48e24ed4 {1=>nil}>"
tree[:foo, :baz].inspect  # "absent child of node :baz in #<Sycamore::Tree:0x3fea48e24f10 {:bar=>1}>"

@todo Should we differentiate the case of a leaf and a not present node? How?

# File lib/sycamore/tree.rb, line 640
def child_at(*path)
  first = path.first
  case path.length
    when 0
      raise ArgumentError, 'wrong number of arguments (given 0, expected 1+)'
    when 1
      if first.is_a? Enumerable
        child_at(*first)
      else
        child_of(*path)
      end
    else
      child_of(first).child_at(*path[1..-1])
  end
end
Also aliased as: [], dig
child_of(node) click to toggle source

The child tree of a node.

When a child to the given node is not a present, an {Absence} object representing the missing tree is returned.

@param node [Object] @return [Tree, Absence] the child tree of a node if present, otherwise an {Absence}

@raise [InvalidNode] when given an Enumerable

@example

tree = Tree[foo: 1]
tree.child_of(:foo).inspect  # "#<Sycamore::Tree:0x3fea48dd0e74 {1=>nil}>"
tree.child_of(:bar).inspect  # "absent child of node :bar in #<Sycamore::Tree:0x3fea48dd0f3c {:foo=>1}>"

@todo Should we differentiate the case of a leaf and a not present node? How?

# File lib/sycamore/tree.rb, line 612
def child_of(node)
  valid_node! node

  Nothing.like?(child = data[node]) ? Absence.at(self, node) : child
end
clear() click to toggle source

Deletes all nodes and their children.

@return self as a proper command method

@example

tree = Tree[1, 2, 3]
tree.size  # => 3
tree.clear
tree.size  # => 0
# File lib/sycamore/tree.rb, line 500
def clear
  data.clear

  self
end
clear_child_of_node(node) click to toggle source

@api private

# File lib/sycamore/tree.rb, line 236
def clear_child_of_node(node)
  data[valid_node! node] = Nothing

  self
end
compact() click to toggle source

Deletes all empty child trees recursively.

@return self as a proper command method

@example

tree = Tree[foo: {bar: :baz}]
tree[:foo, :bar].clear
tree.to_h  # => {foo: {bar: []}}
tree.compact
tree.to_h  # => {foo: :bar}
# File lib/sycamore/tree.rb, line 518
def compact
  data.each do |node, child| case
      when child.nothing? then next
      when child.empty?   then clear_child_of_node(node)
      else child.compact
    end
  end

  self
end
delete(nodes_or_tree) click to toggle source

Remove nodes or a tree structure from this tree.

If a given node is in the {#nodes} set, it gets deleted, otherwise it is silently ignored.

@overload delete(node)

deletes a single node
@param node [Object]

@overload delete(node_collection)

deletes multiple nodes
@param node_collection [Enumerable]

@overload delete(tree_structure)

deletes a tree structure of nodes
@param tree_structure [Hash, Tree]

@overload delete(path)

deletes a {Path} of nodes
@param path [Path]

@return self as a proper command method

@raise [InvalidNode] when given a nested node set

@example

tree = Tree[ "a" => 100, "b" => 200, "c" => 300, "d" => {foo: [:bar, :baz]} ]
tree.delete "a"
tree.to_h  # => {"b" => 200, "c" => 300, "d" => {foo: [:bar, :baz]}}
tree.delete ["a", "b", "c"]
tree.to_h  # => {"d" => {foo: [:bar, :baz]}}
tree.delete "d" => {foo: :bar}
tree.to_h  # => {"d" => {foo: :baz}}
tree.delete "d" => {foo: :baz}
tree.to_h  # => {}
tree = Tree[foo: {bar: :baz, qux: nil}]
tree.delete Sycamore::Path[:foo, :bar, :baz]
tree.to_h  # => {foo: :qux}
# File lib/sycamore/tree.rb, line 321
def delete(nodes_or_tree)
  case
    when nodes_or_tree.is_a?(Tree) then delete_tree(nodes_or_tree)
    when Tree.like?(nodes_or_tree) then delete_tree(valid_tree! nodes_or_tree)
    when nodes_or_tree.is_a?(Path) then delete_path(nodes_or_tree)
    when nodes_or_tree.is_a?(Enumerable)
      nodes_or_tree.all? { |node| valid_node_element! node }
      nodes_or_tree.each { |node| delete node }
    else
      delete_node valid_node!(nodes_or_tree)
  end

  self
end
Also aliased as: >>
dig(*path)
Alias for: child_at
dup() click to toggle source

Duplicates the whole tree.

@return [Tree]

# File lib/sycamore/tree.rb, line 1443
def dup
  duplicate = self.class.new.add(self)
  duplicate.taint if tainted?
  duplicate
end
each(&block)
Alias for: each_pair
each_key(&block)
Alias for: each_node
each_node(&block) click to toggle source

Iterates over all {#nodes nodes} of this tree.

Note that does not include the nodes of the child trees.

@overload each_node

Iterates over all {#nodes nodes} of this tree.
@yield [Object] each node
@return [Tree]

@overload each_node

Returns an enumerator over all {#nodes nodes} of this tree.
@return [Enumerator<Object>]

@example

tree = Tree[ "a" => 100, "b" => 200 ]
tree.each_node {|node| puts node }

> a
> b
# File lib/sycamore/tree.rb, line 761
def each_node(&block)
  return enum_for(__callee__) unless block_given?

  data.each_key(&block)

  self
end
Also aliased as: each_key
each_pair(&block) click to toggle source

Iterates over all {#nodes nodes} and their child trees.

@overload each_pair

Iterates over all {#nodes nodes} and their child trees.
@yield [Object, Tree] each node-child pair
@return [Tree] +self+

@overload each_pair

Returns an enumerator over all {#nodes nodes} and their child trees.
@return [Enumerator<Array(Object, Tree)>]

@example

tree = Tree[ "a" => 100, "b" => nil ]
tree.each_pair {|node, child| puts "#{node} => #{child}" }

> a => #<Tree[ 100 ]>
> b => #<Tree: Nothing>
# File lib/sycamore/tree.rb, line 790
def each_pair(&block)
  return enum_for(__callee__) unless block_given?

  data.each_pair(&block)

  self
end
Also aliased as: each
each_path(with_ancestor: Path::ROOT) { |Path| ... } click to toggle source

Iterates over the {Path paths} to all leaves of this tree.

@overload each_path

Iterates over the {Path paths} to all leaves of this tree.
@yieldparam [Path] path
@return [Tree] +self+

@overload each_path

Returns an enumerator over the {Path paths} to all leaves of this tree.
@return [Enumerator<Path>]

@example

tree = Tree[ "a" => 100, "b" => { foo: [:bar, :baz] } ]
tree.each_path { |path| puts path }

> #<Path: /a/100>
> #<Path: /b/foo/bar>
> #<Path: /b/foo/baz>
# File lib/sycamore/tree.rb, line 820
def each_path(with_ancestor: Path::ROOT, &block)
  return enum_for(__callee__) unless block_given?

  each do |node, child|
    if child.empty?
      yield Path[with_ancestor, node]
    else
      child.each_path(with_ancestor: with_ancestor.branch(node), &block)
    end
  end

  self
end
Also aliased as: paths
empty?() click to toggle source

Checks if this tree is empty.

@return [Boolean]

@example

Tree.new.empty?    # => true
Tree[a: 1].empty?  # => false
# File lib/sycamore/tree.rb, line 1010
def empty?
  data.empty?
end
Also aliased as: blank?
eql?(other) click to toggle source

Checks if this tree has the same content as another tree.

@param other [Object] @return [Boolean]

@example

tree1 = Tree[a: 1, b: 2]
tree2 = Tree[a: 1, b: 2, c: 3]
tree3 = Tree[b: 2, a: 1]
tree4 = Tree[a: 1, b: {2 => []}]
tree1.eql? tree2  # => false
tree1.eql? tree3  # => true
tree1.eql? tree4  # => false
# File lib/sycamore/tree.rb, line 1174
def eql?(other)
  (other.instance_of?(self.class) and data.eql?(other.data)) or
    (other.instance_of?(Absence) and other.eql?(self))
end
existent?() click to toggle source

Checks if this is not an {Absence} or {Nothing}.

@return [Boolean]

# File lib/sycamore/tree.rb, line 146
def existent?
  not absent?
end
external?(*nodes) click to toggle source

Checks if all given nodes or that of the tree have no children.

@overload external?

Checks if all {#nodes} of this tree have no children.
@return [Boolean]

@overload external?(*nodes)

Checks if all of the given nodes have no children.
@param nodes [Array<Object, Path>] splat of nodes or Path objects
@return [Boolean]

@example

Tree[1,2,3].leaves?  # => true
tree = Tree[x: 1, y: [], z: nil]
tree.external?          # => false
tree.external?(:x, :y)  # => false
tree.external?(:y, :z)  # => true
tree.external?(:y, :z)  # => true
tree.external?(Sycamore::Path[:x, 1], :y)  # => true
# File lib/sycamore/tree.rb, line 1102
def external?(*nodes)
  nodes = self.nodes if nodes.empty?

  nodes.all? { |node| leaf?(node) }
end
Also aliased as: leaves?, flat?
fetch(node, *default) { || ... } click to toggle source

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)               # #<Sycamore::Tree:0x3fc798a63854(1)>
tree.fetch(:y)               # => raise Sycamore::ChildError, "node :y has no child tree"
tree.fetch(:z)               # => raise KeyError, "key not found: :z"
tree.fetch(:z, :default)     # => :default
tree.fetch(:y, :default)     # => :default
tree.fetch(:z) { :default }  # => :default
tree.fetch(Sycamore::Path[:foo, :bar]).nodes          # => [:baz]
tree.fetch(Sycamore::Path[:foo, :missing], :default)  # => :default

@todo Should we differentiate the case of a leaf and a not present node? How?

# File lib/sycamore/tree.rb, line 690
def fetch(node, *default, &block)
  return fetch_path(node, *default, &block) if node.is_a? Path
  valid_node! node

  child = data.fetch(node, *default, &block)
  if child.equal? Nothing
    child = case
      when block_given?    then yield
      when !default.empty? then default.first
      else raise ChildError, "node #{node.inspect} has no child tree"
    end
  end

  child
end
fetch_path(path, *default) { |: first| ... } click to toggle source

The child tree of a node at a path.

If the node at the given path can’t be found or has no child tree, it behaves like {#fetch}.

@param path [Array<Object>, Path] @param default [Object] optional @return [Tree, default]

@raise [InvalidNode] when given an Enumerable as node @raise [KeyError] when the given node can't be found @raise [ChildError] when no child for the given node present

@example

tree = Tree[foo: {bar: :baz}]
tree.fetch_path([:foo, :bar]).nodes  # => [:baz]
tree.fetch_path [:foo, :bar, :baz]   # => raise Sycamore::ChildError, "node :baz has no child tree"
tree.fetch_path [:foo, :qux]         # => raise KeyError, "key not found: :qux"
tree.fetch_path([:a, :b], :default)            # => :default
tree.fetch_path([:a, :b]) { :default }         # => :default
tree.fetch_path([:foo, :bar, :baz], :default)  # => :default
# File lib/sycamore/tree.rb, line 729
def fetch_path(path, *default, &block)
  default_case = block_given? || !default.empty?
  path.inject(self) do |tree, node|
    if default_case
      tree.fetch(node) { return block_given? ? yield : default.first }
    else
      tree.fetch(node)
    end
  end
end
flat?(*nodes)
Alias for: external?
freeze() click to toggle source

Deep freezes the whole tree.

@see ruby-doc.org/core/Object.html#method-i-freeze

Calls superclass method
# File lib/sycamore/tree.rb, line 1463
def freeze
  data.freeze
  each { |_, child| child.freeze }
  super
end
has_key?(node)
Alias for: include_node?
hash() click to toggle source

A hash code of this tree.

@return [Fixnum]

# File lib/sycamore/tree.rb, line 1155
def hash
  data.hash ^ self.class.hash
end
height() click to toggle source

The length of the longest path of this tree.

@return [Fixnum]

@example

tree = Tree[a: 1, b: {2 => 3}]
tree.height  # => 3
# File lib/sycamore/tree.rb, line 996
def height
  return 0 if empty?
  paths.map(&:length).max
end
include?(*elements) click to toggle source

Checks if some nodes or a full tree-like structure is included in this tree.

@param elements [Object, Array, Tree, Hash] @return [Boolean]

@example

tree = Tree[ "a" => 100, "b" => 200, "c" => { foo: [:bar, :baz] } ]
tree.include?("a")                 # => true
tree.include?(:foo)                # => false
tree.include?(["a", "b"])          # => true
tree.include?("c" => {foo: :bar})  # => true
tree.include?("a", "b" => 200)     # => true
# File lib/sycamore/tree.rb, line 901
def include?(*elements)
  raise ArgumentError, 'wrong number of arguments (given 0, expected 1+)' if
    elements.size == 0
  return elements.all? { |element| include? element } if
    elements.size > 1

  elements = elements.first
  case
    when Tree.like?(elements)
      elements.all? do |node, child|
        include_node?(node) and ( child.nil? or child.equal?(Nothing) or
                                    self.child_of(node).include?(child) )
      end
    when elements.is_a?(Path)
      include_path? elements
    when elements.is_a?(Enumerable)
      elements.all? { |element| include_node? element }
    else
      include_node? elements
  end
end
include_node?(node) click to toggle source

Checks if a node exists in the {#nodes nodes} set of this tree.

@param node [Object, Path] @return [Boolean]

@example

Tree[1,2,3].include_node? 3   # => true
Tree[1 => 2].include_node? 2  # => false
Tree[1 => 2].include_node? Sycamore::Path[1,2]  # => true
# File lib/sycamore/tree.rb, line 877
def include_node?(node)
  return include_path?(node) if node.is_a? Path

  data.include?(node)
end
Also aliased as: member?, has_key?, key?
include_path?(*args) click to toggle source

Checks if a path of nodes exists in this tree.

@param args [Array<Object>, Path] a splat of nodes, an array of nodes or a {Path} object @return [Boolean]

@example

tree = Tree[ "a" => 100, "b" => 200, "c" => { foo: [:bar, :baz] } ]
tree.include_path? "a", 200  # => false
tree.include_path? "c", :foo, :bar  # => true
tree.include_path? ["c", :foo, :bar]  # => true
tree.include_path? Sycamore::Path["c", :foo, :bar]  # => true
# File lib/sycamore/tree.rb, line 849
def include_path?(*args)
  case args.count
    when 0 then raise ArgumentError, 'wrong number of arguments (given 0, expected 1+)'
    when 1 then path = args.first
           else return include_path?(args)
  end
  path = [path] unless path.is_a? Enumerable

  if path.is_a? Path
    fetch_path(path.parent) { return false }.include? path.node
  else
    fetch_path(path[0..-2]) { return false }.include? path.last
  end
end
Also aliased as: path?
initialize_clone(other) click to toggle source

Clones the whole tree.

Calls superclass method
# File lib/sycamore/tree.rb, line 1452
def initialize_clone(other)
  super
  clear_data
  add other
end
inspect() click to toggle source

A developer-friendly string representation of this tree in the usual Ruby +Object#inspect+ style.

@return [String]

# File lib/sycamore/tree.rb, line 1374
def inspect
  "#<#{self.class}:0x#{object_id.to_s(16)} #{
        to_h(sleaf_child_as: Sycamore::NothingTree::NestedString).inspect}>"
end
internal?(*nodes) click to toggle source

Checks if all given nodes or that of the tree have children.

@overload internal?

Checks if all {#nodes} of this tree have children.
@return [Boolean]

@overload internal?(*nodes)

Checks if all of the given nodes have children.
@param nodes [Array<Object, Path>] splat of nodes or Path objects
@return [Boolean]

@example

Tree[x: 1, y: 2].internal?  # => true
tree = Tree[x: 1, y: [], z: nil]
tree.internal?          # => false
tree.internal?(:x, :y)  # => false
tree.internal?(:y, :z)  # => false
tree.internal?(:x)      # => true
tree.internal?(:x)      # => true
tree.internal?(Sycamore::Path[:x, 1])  # => false

@todo Does it make sense to support the no arguments variant here and with this semantics?

One would expect it to be the negation of #external? without arguments.
# File lib/sycamore/tree.rb, line 1136
def internal?(*nodes)
  return false if self.empty?
  nodes = self.nodes if nodes.empty?

  nodes.all? { |node| not leaf?(node) and include_node?(node) }
end
Also aliased as: nested?
key?(node)
Alias for: include_node?
keys()
Alias for: nodes
leaf?(node) click to toggle source

Checks if the given node has no children.

@param node [Object, Path] @return [Boolean]

@example

tree = Tree[x: 1, y: [], z: nil]
tree.leaf?(:x)  # => false
tree.leaf?(:y)  # => true
tree.leaf?(:z)  # => true
tree.leaf?(Sycamore::Path[:x, 1])  # => true
# File lib/sycamore/tree.rb, line 1029
def leaf?(node)
  include_node?(node) && child_at(node).empty?
end
leaves?(*nodes)
Alias for: external?
matches?(other) click to toggle source

Checks if another object matches this tree structurally and by content.

@param other [Object] @return [Boolean]

@example

Tree[foo: :bar] === Hash[foo: :bar]  # => true
Tree[1, 2, 3]   === Array[1, 2, 3]   # => true
Tree[42]        === 42               # => true

@todo This should probably apply a less strict equivalence comparison on the nodes.

Problem: Requires a solution which doesn't use +Hash#include?+.
# File lib/sycamore/tree.rb, line 1283
def matches?(other)
  case
    when Tree.like?(other)       then matches_tree?(other)
    when other.is_a?(Enumerable) then matches_enumerable?(other)
                                 else matches_atom?(other)
  end
end
Also aliased as: ===
member?(node)
Alias for: include_node?
nested?(*nodes)
Alias for: internal?
new_child(parent_node, *args) click to toggle source

Creates a new tree meant to be used as a child.

This method is used for instantiation of child trees. When you want to a tree with different types child trees, maybe depending on the parent node, you can subclass {Sycamore::Tree} and override this method to your needs. By default it creates trees of the same type as this tree.

@param parent_node [Object] of the child tree to be created @return [Tree]

@api private

# File lib/sycamore/tree.rb, line 114
def new_child(parent_node, *args)
  self.class.new(*args)
end
node() click to toggle source

The only node of this tree or an exception, if more {#nodes nodes} present.

@return [Object, nil] the single present node or nil, if no nodes present

@raise [NonUniqueNodeSet] if more than one node present

@example

tree = Tree[foo: 1, bar: [2,3]]
tree[:foo].node  # => 1
tree[:baz].node  # => nil
tree[:bar].node  # => raise Sycamore::NonUniqueNodeSet, "multiple nodes present: [2, 3]"

@see Tree#node!

# File lib/sycamore/tree.rb, line 566
def node
  nodes = self.nodes
  raise NonUniqueNodeSet, "multiple nodes present: #{nodes}" if nodes.size > 1

  nodes.first
end
node!() click to toggle source

The only node of this tree or an exception, if none or more {#nodes nodes} present.

@return [Object] the single present node

@raise [EmptyNodeSet] if no nodes present @raise [NonUniqueNodeSet] if more than one node present

@example

tree = Tree[foo: 1, bar: [2,3]]
tree[:foo].node!  # => 1
tree[:baz].node!  # => raise Sycamore::EmptyNodeSet, "no node present"
tree[:bar].node!  # => raise Sycamore::NonUniqueNodeSet, "multiple nodes present: [2, 3]"

@see Tree#node

# File lib/sycamore/tree.rb, line 589
def node!
  raise EmptyNodeSet, 'no node present' if empty?
  node
end
nodes() click to toggle source

The nodes of this tree (without their children).

@return [Array<Object>]

@example

tree = Tree[foo: [:bar, :baz]]
tree.nodes        # => [:foo]
tree[:foo].nodes  # => [:bar, :baz]
# File lib/sycamore/tree.rb, line 544
def nodes
  data.keys
end
Also aliased as: keys
nothing?() click to toggle source

Checks if this is the {Nothing} tree.

@return [Boolean]

# File lib/sycamore/tree.rb, line 128
def nothing?
  false
end
path?(*args)
Alias for: include_path?
paths(with_ancestor: Path::ROOT, &block)
Alias for: each_path
present?() click to toggle source

Checks if this is not {#blank? blank}, i.e. {#empty? empty}.

@note This is not the negation of {#absent?}, since this would result in a

different behaviour than {http://api.rubyonrails.org/classes/Object.html#method-i-present-3F ActiveSupports present?}
method. For the negation of {#absent?}, see {#existent?}.

@return [Boolean]

# File lib/sycamore/tree.rb, line 159
def present?
  not blank?
end
replace(nodes_or_tree) click to toggle source

Replaces the contents of this tree.

@overload replace(node)

Replaces the contents of this tree with a single node.
@param node [Object]

@overload replace(node_collection)

Replaces the contents of this tree with multiple nodes.
@param node_collection [Enumerable]

@overload replace(tree_structure)

Replaces the contents of this tree with a tree structure of nodes.
@param tree_structure [Hash, Tree]

@overload replace(path)

Replaces the contents of this tree with a path of nodes.
@param path [Path]

@return self as a proper command method

@raise [InvalidNode] when given a nested node set

@example

tree = Tree[ "a" => 100, "b" => 200, "d" => {foo: [:bar, :baz]} ]
tree.replace(new: :content)
tree.to_h  # => {new: :content}
# File lib/sycamore/tree.rb, line 410
def replace(nodes_or_tree)
  clear.add(nodes_or_tree)
end
size() click to toggle source

The number of {#nodes nodes} in this tree.

Note, this does not count the nodes in the child trees.

@return [Fixnum]

@example

tree = Tree[ "d" => 100, "a" => 200, "v" => 300, "e" => [400, 500] ]
tree.size  # => 4
tree.delete("a")
tree.size  # => 3
tree["e"].size  # => 2
# File lib/sycamore/tree.rb, line 963
def size
  data.size
end
sleaf?(node)
Alias for: strict_leaf?
sleaves?(*nodes)
Alias for: strict_leaves?
strict_leaf?(node) click to toggle source

Checks if the given node has no children, even not an empty child tree.

@param node [Object] @return [Boolean]

@example

tree = Tree[x: 1, y: [], z: nil]
tree.strict_leaf?(:x)  # => false
tree.strict_leaf?(:y)  # => false
tree.strict_leaf?(:z)  # => true
tree.strict_leaf?(Sycamore::Path[:x, 1])  # => true
# File lib/sycamore/tree.rb, line 1046
def strict_leaf?(node)
  include_node?(node) && child_at(node).absent?
end
Also aliased as: sleaf?
strict_leaves?(*nodes) click to toggle source

Checks if all given nodes or that of the tree have no children, even not an empty child tree.

@overload strict_leaves?()

Returns if all {#nodes} of this tree have no children, even not an empty child tree.
@return [Boolean]

@overload strict_leaves?(*nodes)

Checks if all of the given nodes have no children, even not an empty child tree.
@param nodes [Array<Object, Path>] splat of nodes or Path objects
@return [Boolean]

@example

Tree[1,2,3].strict_leaves?  # => true
tree = Tree[x: 1, y: [], z: nil]
tree.strict_leaves?          # => false
tree.strict_leaves?(:x, :y)  # => false
tree.strict_leaves?(:y, :z)  # => false
tree.strict_leaves?(:y, :z)  # => false
tree.strict_leaves?(:z, Sycamore::Path[:x, 1])  # => true
# File lib/sycamore/tree.rb, line 1073
def strict_leaves?(*nodes)
  nodes = self.nodes if nodes.empty?

  nodes.all? { |node| strict_leaf?(node) }
end
Also aliased as: sleaves?
to_h(*args) click to toggle source

A hash representation of this tree.

@return [Hash]

# File lib/sycamore/tree.rb, line 1343
def to_h(*args)
  return {} if empty?

  # not the nicest, but fastest way to inject on hashes, as noted here:
  # http://stackoverflow.com/questions/3230863/ruby-rails-inject-on-hashes-good-style
  hash = {}
  data.each do |node, child|
    hash[node] = child.to_native_object(*args)
  end

  hash
end
to_native_object(sleaf_child_as: nil, special_nil: false) click to toggle source

A native Ruby object representing the content of the tree.

It is used by {#to_h} to produce flattened representations of child trees.

@api private

# File lib/sycamore/tree.rb, line 1327
def to_native_object(sleaf_child_as: nil, special_nil: false)
  case
    when empty?
      []
    when strict_leaves?
      size == 1 && (!special_nil || !nodes.first.nil?) ? nodes.first : nodes
    else
      to_h(sleaf_child_as: sleaf_child_as, special_nil: special_nil)
  end
end
to_s() click to toggle source

A string representation of this tree.

@return [String]

# File lib/sycamore/tree.rb, line 1361
def to_s
  if (content = to_native_object(special_nil: true)).is_a? Enumerable
    "Tree[#{content.inspect[1..-2]}]"
  else
    "Tree[#{content.inspect}]"
  end
end
total_size() click to toggle source

The number of {#nodes nodes} in this tree and all of their children.

@return [Fixnum]

@example

tree = Tree[ "d" => 100, "a" => 200, "v" => 300, "e" => [400, 500] ]
tree.total_size  # => 9
tree.delete("a")
tree.total_size  # => 7
tree["e"].total_size  # => 2
# File lib/sycamore/tree.rb, line 979
def total_size
  total = size
  data.each { |_, child| total += child.total_size }
  total
end
Also aliased as: tsize
tsize()
Alias for: total_size

Protected Instance Methods

add_node(node) click to toggle source
# File lib/sycamore/tree.rb, line 227
          def add_node(node)
  data[node] ||= Nothing

  self
end
clear_data() click to toggle source
# File lib/sycamore/tree.rb, line 74
          def clear_data
  @data = nil
end
delete_node(node) click to toggle source
# File lib/sycamore/tree.rb, line 338
          def delete_node(node)
  data.delete(node)

  self
end
delete_path(path) click to toggle source
# File lib/sycamore/tree.rb, line 369
          def delete_path(path)
  case path.length
    when 0 then return self
    when 1 then return delete_node(path.node)
  end

  parent = fetch_path(path.parent) { return self }
  parent.delete_node(path.node)
  delete_path(path.parent) if parent.empty? and not path.parent.root?

  self
end
delete_tree(tree) click to toggle source
# File lib/sycamore/tree.rb, line 344
          def delete_tree(tree)
  tree.each { |node_to_delete, child_to_delete| # using a {} block to circumvent this Rubinius issue: https://github.com/rubinius/rubinius-code/issues/7
    next unless include? node_to_delete
    if Nothing.like?(child_to_delete) or
        (child_to_delete.respond_to?(:empty?) and child_to_delete.empty?)
      delete_node node_to_delete
    else
      fetch(node_to_delete, Nothing).tap do |child|
        case
          when child.empty? then next
          when Tree.like?(child_to_delete)
            child.delete_tree(child_to_delete)
          when child_to_delete.is_a?(Enumerable)
            child_to_delete.each { |node| child.delete_node node }
          else
            child.delete_node child_to_delete
        end
        delete_node(node_to_delete) if child.empty?
      end
    end
  }

  self
end

Private Instance Methods

add_child(node, children) click to toggle source
# File lib/sycamore/tree.rb, line 255
        def add_child(node, children)
  return add_node(node) if Nothing.like?(children)

  add_node_with_empty_child(node)
  data[node] << children

  self
end
add_path(path) click to toggle source
# File lib/sycamore/tree.rb, line 270
        def add_path(path)
  return self if path.root?

  path.parent.inject(self) { |tree, node| # using a {} block to circumvent this Rubinius issue: https://github.com/rubinius/rubinius-code/issues/7
    tree.add_node_with_empty_child(node)
    tree[node]
  }.add_node path.node

  self
end
add_tree(tree) click to toggle source
# File lib/sycamore/tree.rb, line 264
        def add_tree(tree)
  tree.each { |node, child| add_child(node, child) }

  self
end
matches_atom?(other) click to toggle source
# File lib/sycamore/tree.rb, line 1293
        def matches_atom?(other)
  not other.nil? and (size == 1 and nodes.first == other and leaf? other)
end
matches_enumerable?(other) click to toggle source
# File lib/sycamore/tree.rb, line 1297
        def matches_enumerable?(other)
  size == other.size and
    all? { |node, child| child.empty? and other.include?(node) }
end
matches_tree?(other) click to toggle source
# File lib/sycamore/tree.rb, line 1302
        def matches_tree?(other)
  size == other.size and
    all? { |node, child|
      if child.nothing?
        other.include?(node) and begin other_child = other.fetch(node, nil)
          not other_child or
            (other_child.respond_to?(:empty?) and other_child.empty?)
        end
      else
        child.matches? other[node]
      end }
end
valid_node!(node) click to toggle source

@api private

# File lib/sycamore/tree.rb, line 1403
        def valid_node!(node)
  raise InvalidNode, "#{node} is not a valid tree node" if node.is_a? Enumerable

  node
end
valid_node_element!(node) click to toggle source

@api private

# File lib/sycamore/tree.rb, line 1393
        def valid_node_element!(node)
  raise InvalidNode, "#{node} is not a valid tree node" if
    node.is_a?(Enumerable) and not node.is_a?(Path) and not Tree.like?(node)

  node
end
valid_tree!(tree) click to toggle source

@api private

# File lib/sycamore/tree.rb, line 1381
        def valid_tree!(tree)
  tree.each { |node, child| # using a {} block to circumvent this Rubinius issue: https://github.com/rubinius/rubinius-code/issues/7
    next if child.nil?
    valid_node!(node)
    valid_tree!(child) if Tree.like?(child)
  }

  tree
end