Class: Sycamore::Tree

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/sycamore/tree.rb

Overview

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

See README for a general introduction.

Direct Known Subclasses

NothingTree

CQS reflection collapse

ADDITIVE_COMMAND_METHODS =

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

%i[add << replace add_node_with_empty_child
clear_child_of_node] << :[]=
DESTRUCTIVE_COMMAND_METHODS =

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

%i[delete >> clear compact replace
clear_child_of_node] << :[]=
PURE_ADDITIVE_COMMAND_METHODS =

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

ADDITIVE_COMMAND_METHODS - DESTRUCTIVE_COMMAND_METHODS
PURE_DESTRUCTIVE_COMMAND_METHODS =

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

DESTRUCTIVE_COMMAND_METHODS - ADDITIVE_COMMAND_METHODS
COMMAND_METHODS =

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

ADDITIVE_COMMAND_METHODS + DESTRUCTIVE_COMMAND_METHODS +
%i[freeze]
PREDICATE_METHODS =

the names of all query methods, which return a boolean

%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? === ==]
QUERY_METHODS =

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

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] << :[]

Construction collapse

Construction collapse

Absence and Nothing predicates collapse

Element access collapse

Comparison collapse

Conversion collapse

Other standard Ruby methods collapse

Constructor Details

#initialize ⇒ Tree

Creates a new empty Tree.



65
66
 
# File 'lib/sycamore/tree.rb', line 65

def initialize
end

Instance Attribute Details

#data ⇒ Object (readonly, protected)

the internal hash representation of this tree



11
12
13
 
# File 'lib/sycamore/tree.rb', line 11

protected def data
  @data ||= {}
end

Class Method Details

.tree_like?(object) ⇒ Boolean Also known as: like?

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

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.

Parameters:

  • object (Object)

Returns:

  • (Boolean) 


1423
1424
1425
1426
1427
1428
1429
1430
 
# File 'lib/sycamore/tree.rb', line 1423

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

.with(*args) ⇒ Tree Also known as: from, []

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

Examples:

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]

Returns:



88
89
90
91
92
 
# File 'lib/sycamore/tree.rb', line 88

def self.with(*args)
  tree = new
  tree.add((args.size == 1) ? args.first : args) unless args.empty?
  tree
end

Instance Method Details

#<(other) ⇒ Boolean

Checks if this tree is a subtree of another tree.

Examples:

tree1 = Tree[a: 1, b: 2]
tree2 = Tree[a: 1, b: 2, c: 3]
tree1 < tree2  # => true
tree2 < tree1  # => false
tree1 < tree1  # => false

Parameters:

  • other (Object)

Returns:

  • (Boolean) 


1216
1217
1218
 
# File 'lib/sycamore/tree.rb', line 1216

def <(other)
  (other.is_a?(Tree) or other.is_a?(Absence)) and other.include?(self) and self != other
end

#<=(other) ⇒ Boolean

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

Examples:

tree1 = Tree[a: 1, b: 2]
tree2 = Tree[a: 1, b: 2, c: 3]
tree1 <= tree2  # => true
tree2 <= tree1  # => false
tree1 <= tree1  # => true

Parameters:

  • other (Object)

Returns:

  • (Boolean) 


1233
1234
1235
 
# File 'lib/sycamore/tree.rb', line 1233

def <=(other)
  (other.is_a?(Tree) or other.is_a?(Absence)) and other.include?(self)
end

#==(other) ⇒ Boolean

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

Examples:

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

Parameters:

  • other (Object)

Returns:

  • (Boolean) 


1196
1197
1198
1199
1200
1201
 
# File 'lib/sycamore/tree.rb', line 1196

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) ⇒ Boolean

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

Examples:

tree1 = Tree[a: 1, b: 2]
tree2 = Tree[a: 1, b: 2, c: 3]
tree1 > tree2  # => false
tree2 > tree1  # => true
tree1 > tree1  # => false

Parameters:

  • other (Object)

Returns:

  • (Boolean) 


1267
1268
1269
 
# File 'lib/sycamore/tree.rb', line 1267

def >(other)
  (other.is_a?(Tree) or other.is_a?(Absence)) and include?(other) and self != other
end

#>=(other) ⇒ Boolean

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

Examples:

tree1 = Tree[a: 1, b: 2]
tree2 = Tree[a: 1, b: 2, c: 3]
tree1 >= tree2  # => false
tree2 >= tree1  # => true
tree1 >= tree1  # => true

Parameters:

  • other (Object)

Returns:

  • (Boolean) 


1250
1251
1252
 
# File 'lib/sycamore/tree.rb', line 1250

def >=(other)
  (other.is_a?(Tree) or other.is_a?(Absence)) and include?(other)
end

#[]=(*path, node) ⇒ Object #[]=(*path, node_collection) ⇒ Object #[]=(*path, tree_structure) ⇒ Object #[]=(*path, another_object) ⇒ Object

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]

Examples:

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

Overloads:

  • #[]=(*path, node) ⇒ Object

    Replaces the contents of the child at the given path with a single node.

    Parameters:

    • path (Array<Object>, Sycamore::Path) —

      a path as a sequence of nodes or a Path object

    • node (Object)
  • #[]=(*path, node_collection) ⇒ Object

    Replaces the contents of the child at the given path with multiple nodes.

    Parameters:

    • path (Array<Object>, Sycamore::Path) —

      a path as a sequence of nodes or a Path object

    • node_collection (Enumerable)
  • #[]=(*path, tree_structure) ⇒ Object

    Replaces the contents of the child at the given path with a tree structure of nodes.

    Parameters:

    • path (Array<Object>, Sycamore::Path) —

      a path as a sequence of nodes or a Path object

    • tree_structure (Hash, Tree)
  • #[]=(*path, another_object) ⇒ Object

    Replaces the contents of the child at the given path with another path of nodes.

    Parameters:

Returns:

  • the rvalue as for any Ruby assignment

Raises:



474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
 
# File 'lib/sycamore/tree.rb', line 474

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

#_search(query, current_path: Path::ROOT, results: []) ⇒ Object (protected) 



944
945
946
947
948
949
950
 
# File 'lib/sycamore/tree.rb', line 944

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

#absent? ⇒ Boolean

Checks if this is an unresolved Absence or Nothing.

Returns:

  • (Boolean) 


134
135
136
 
# File 'lib/sycamore/tree.rb', line 134

def absent?
  false
end

#add(node) ⇒ Object #add(node_collection) ⇒ Object #add(tree_structure) ⇒ Object #add(path) ⇒ Object Also known as: <<

Adds nodes or a tree structure to this tree.

Examples:

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

Overloads:

  • #add(node) ⇒ Object

    adds a single node

    Parameters:

    • node (Object)
  • #add(node_collection) ⇒ Object

    adds multiple nodes

    Parameters:

    • node_collection (Enumerable)
  • #add(tree_structure) ⇒ Object

    adds a tree structure of nodes

    Parameters:

    • tree_structure (Hash, Tree)
  • #add(path) ⇒ Object

    adds a Path of nodes

    Parameters:

Returns:

  • self as a proper command method

Raises:



206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
 
# File 'lib/sycamore/tree.rb', line 206

def add(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

#add_child(node, children) ⇒ Object (private) 



254
255
256
257
258
259
260
261
 
# File 'lib/sycamore/tree.rb', line 254

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

#add_node(node) ⇒ Object (protected) 



226
227
228
229
230
 
# File 'lib/sycamore/tree.rb', line 226

protected def add_node(node)
  data[node] ||= Nothing

  self
end

#add_node_with_empty_child(node) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future. 



244
245
246
247
248
249
250
251
252
 
# File 'lib/sycamore/tree.rb', line 244

def add_node_with_empty_child(node)
  valid_node! node

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

  self
end

#add_path(path) ⇒ Object (private) 



269
270
271
272
273
274
275
276
277
278
 
# File 'lib/sycamore/tree.rb', line 269

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

#add_tree(tree) ⇒ Object (private) 



263
264
265
266
267
 
# File 'lib/sycamore/tree.rb', line 263

private def add_tree(tree)
  tree.each { |node, child| add_child(node, child) }

  self
end

#child_at(*nodes) ⇒ Tree, Absence #child_at(path) ⇒ Tree, Absence Also known as: [], dig

TODO:

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

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.

Examples:

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}>"

Overloads:

  • #child_at(*nodes) ⇒ Tree, Absence

    Parameters:

    • nodes (Array<Object>) —

      a path as a sequence of nodes

  • #child_at(path) ⇒ Tree, Absence

    Parameters:

    • path (Path) —

      a path as a Path object

Returns:



642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
 
# File 'lib/sycamore/tree.rb', line 642

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..])
  end
end

#child_of(node) ⇒ Tree, Absence

TODO:

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

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.

Examples:

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}>"

Parameters:

  • node (Object)

Returns:

Raises:



614
615
616
617
618
 
# File 'lib/sycamore/tree.rb', line 614

def child_of(node)
  valid_node! node

  Nothing.like?(child = data[node]) ? Absence.at(self, node) : child
end

#clear ⇒ Object

Deletes all nodes and their children.

Examples:

tree = Tree[1, 2, 3]
tree.size  # => 3
tree.clear
tree.size  # => 0

Returns:

  • self as a proper command method



501
502
503
504
505
 
# File 'lib/sycamore/tree.rb', line 501

def clear
  data.clear

  self
end

#clear_child_of_node(node) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future. 



235
236
237
238
239
 
# File 'lib/sycamore/tree.rb', line 235

def clear_child_of_node(node)
  data[valid_node! node] = Nothing

  self
end

#clear_data ⇒ Object (protected) 



72
73
74
 
# File 'lib/sycamore/tree.rb', line 72

protected def clear_data
  @data = nil
end

#compact ⇒ Object

Deletes all empty child trees recursively.

Examples:

tree = Tree[foo: {bar: :baz}]
tree[:foo, :bar].clear
tree.to_h  # => {foo: {bar: []}}
tree.compact
tree.to_h  # => {foo: :bar}

Returns:

  • self as a proper command method



519
520
521
522
523
524
525
526
527
528
529
530
531
 
# File 'lib/sycamore/tree.rb', line 519

def 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

#delete(node) ⇒ Object #delete(node_collection) ⇒ Object #delete(tree_structure) ⇒ Object #delete(path) ⇒ Object Also known as: >>

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.

Examples:

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}

Overloads:

  • #delete(node) ⇒ Object

    deletes a single node

    Parameters:

    • node (Object)
  • #delete(node_collection) ⇒ Object

    deletes multiple nodes

    Parameters:

    • node_collection (Enumerable)
  • #delete(tree_structure) ⇒ Object

    deletes a tree structure of nodes

    Parameters:

    • tree_structure (Hash, Tree)
  • #delete(path) ⇒ Object

    deletes a Path of nodes

    Parameters:

Returns:

  • self as a proper command method

Raises:



320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
 
# File 'lib/sycamore/tree.rb', line 320

def delete(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

#delete_node(node) ⇒ Object (protected) 



339
340
341
342
343
 
# File 'lib/sycamore/tree.rb', line 339

protected def delete_node(node)
  data.delete(node)

  self
end

#delete_path(path) ⇒ Object (protected) 



370
371
372
373
374
375
376
377
378
379
380
381
 
# File 'lib/sycamore/tree.rb', line 370

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? && !path.parent.root?

  self
end

#delete_tree(tree) ⇒ Object (protected) 



345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
 
# File 'lib/sycamore/tree.rb', line 345

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) ||
        (child_to_delete.respond_to?(:empty?) && child_to_delete.empty?)
      delete_node node_to_delete
    else
      fetch(node_to_delete, Nothing).tap do |child|
        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

  self
end

#dup ⇒ Tree

Duplicates the whole tree.

Returns:



1445
1446
1447
 
# File 'lib/sycamore/tree.rb', line 1445

def dup
  self.class.new.add(self)
end

#each_node {|Object| ... } ⇒ Tree #each_node ⇒ Enumerator<Object> Also known as: each_key

Iterates over all nodes of this tree.

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

Examples:

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

> a
> b

Overloads:

  • #each_node {|Object| ... } ⇒ Tree

    Iterates over all nodes of this tree.

    Yields:

    • (Object) —

      each node

    Returns:

  • #each_node ⇒ Enumerator<Object>

    Returns an enumerator over all nodes of this tree.

    Returns:

    • (Enumerator<Object>) 


765
766
767
768
769
770
771
 
# File 'lib/sycamore/tree.rb', line 765

def each_node(&block)
  return enum_for(__callee__) unless block

  data.each_key(&block)

  self
end

#each_pair {|Object, Tree| ... } ⇒ Tree #each_pair ⇒ Enumerator<Array(Object, Tree)> Also known as: each

Iterates over all nodes and their child trees.

Examples:

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

> a => #<Tree[ 100 ]>
> b => #<Tree: Nothing>

Overloads:

  • #each_pair {|Object, Tree| ... } ⇒ Tree

    Iterates over all nodes and their child trees.

    Yields:

    • (Object, Tree) —

      each node-child pair

    Returns:

  • #each_pair ⇒ Enumerator<Array(Object, Tree)>

    Returns an enumerator over all nodes and their child trees.

    Returns:

    • (Enumerator<Array(Object, Tree)>) 


794
795
796
797
798
799
800
 
# File 'lib/sycamore/tree.rb', line 794

def each_pair(&block)
  return enum_for(__callee__) unless block

  data.each_pair(&block)

  self
end

#each_path {|path| ... } ⇒ Tree #each_path ⇒ Enumerator<Path> Also known as: paths

Iterates over the paths to all leaves of this tree.

Examples:

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>

Overloads:

  • #each_path {|path| ... } ⇒ Tree

    Iterates over the paths to all leaves of this tree.

    Yield Parameters:

    Returns:

  • #each_path ⇒ Enumerator<Path>

    Returns an enumerator over the paths to all leaves of this tree.

    Returns:

    • (Enumerator<Path>) 


824
825
826
827
828
829
830
831
832
833
834
835
836
 
# File 'lib/sycamore/tree.rb', line 824

def each_path(with_ancestor: Path::ROOT, &block)
  return enum_for(__callee__) unless block

  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

#empty? ⇒ Boolean Also known as: blank?

Checks if this tree is empty.

Examples:

Tree.new.empty?    # => true
Tree[a: 1].empty?  # => false

Returns:

  • (Boolean) 


1013
1014
1015
 
# File 'lib/sycamore/tree.rb', line 1013

def empty?
  data.empty?
end

#eql?(other) ⇒ Boolean

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

Examples:

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

Parameters:

  • other (Object)

Returns:

  • (Boolean) 


1176
1177
1178
1179
 
# File 'lib/sycamore/tree.rb', line 1176

def eql?(other)
  (other.instance_of?(self.class) and data.eql?(other.data)) or
    (other.instance_of?(Absence) and other.eql?(self))
end

#existent? ⇒ Boolean

Checks if this is not an Absence or Nothing.

Returns:

  • (Boolean) 


143
144
145
 
# File 'lib/sycamore/tree.rb', line 143

def existent?
  !absent?
end

#external? ⇒ Boolean #external?(*nodes) ⇒ Boolean Also known as: leaves?, flat?

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

Examples:

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

Overloads:

  • #external? ⇒ Boolean

    Checks if all #nodes of this tree have no children.

    Returns:

    • (Boolean)
  • #external?(*nodes) ⇒ Boolean

    Checks if all of the given nodes have no children.

    Parameters:

    • nodes (Array<Object, Path>) —

      splat of nodes or Path objects

    Returns:

    • (Boolean) 


1105
1106
1107
1108
1109
 
# File 'lib/sycamore/tree.rb', line 1105

def external?(*nodes)
  nodes = self.nodes if nodes.empty?

  nodes.all? { |node| leaf?(node) }
end

#fetch(node, *default, &block) ⇒ Tree, default

TODO:

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

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.

Examples:

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

Parameters:

  • node (Object, Path)
  • default (Object) —

    optional

Returns:

Raises:

  • (InvalidNode) —

    when given an Enumerable as node

  • (KeyError) —

    when the given node can’t be found

  • (ChildError) —

    when no child for the given node present



692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
 
# File 'lib/sycamore/tree.rb', line 692

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 = if block
      yield
    elsif !default.empty?
      default.first
    else
      raise ChildError, "node #{node.inspect} has no child tree"
    end
  end

  child
end

#fetch_path(path, *default, &block) ⇒ Tree, default

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.

Examples:

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

Parameters:

  • path (Array<Object>, Path)
  • default (Object) —

    optional

Returns:

Raises:

  • (InvalidNode) —

    when given an Enumerable as node

  • (KeyError) —

    when the given node can’t be found

  • (ChildError) —

    when no child for the given node present



733
734
735
736
737
738
739
740
741
742
 
# File 'lib/sycamore/tree.rb', line 733

def fetch_path(path, *default, &block)
  default_case = block || !default.empty?
  path.inject(self) do |tree, node|
    if default_case
      tree.fetch(node) { return block ? yield : default.first }
    else
      tree.fetch(node)
    end
  end
end

#freeze ⇒ Object

Deep freezes the whole tree.

See Also:



1463
1464
1465
1466
1467
 
# File 'lib/sycamore/tree.rb', line 1463

def freeze
  data.freeze
  each { |_, child| child.freeze }
  super
end

#hash ⇒ Fixnum

A hash code of this tree.

Returns:

  • (Fixnum) 


1157
1158
1159
 
# File 'lib/sycamore/tree.rb', line 1157

def hash
  data.hash ^ self.class.hash
end

#height ⇒ Fixnum

The length of the longest path of this tree.

Examples:

tree = Tree[a: 1, b: {2 => 3}]
tree.height  # => 3

Returns:

  • (Fixnum) 


999
1000
1001
1002
 
# File 'lib/sycamore/tree.rb', line 999

def height
  return 0 if empty?
  paths.map(&:length).max
end

#include?(*elements) ⇒ Boolean

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

Examples:

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

Parameters:

  • elements (Object, Array, Tree, Hash)

Returns:

  • (Boolean)

Raises:

  • (ArgumentError) 


905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
 
# File 'lib/sycamore/tree.rb', line 905

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

#include_node?(node) ⇒ Boolean Also known as: member?, has_key?, key?

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

Examples:

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

Parameters:

  • node (Object, Path)

Returns:

  • (Boolean) 


881
882
883
884
885
 
# File 'lib/sycamore/tree.rb', line 881

def include_node?(node)
  return include_path?(node) if node.is_a? Path

  data.include?(node)
end

#include_path?(*args) ⇒ Boolean Also known as: path?

Checks if a path of nodes exists in this tree.

Examples:

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

Parameters:

  • args (Array<Object>, Path) —

    a splat of nodes, an array of nodes or a Path object

Returns:

  • (Boolean) 


853
854
855
856
857
858
859
860
861
862
863
864
865
866
 
# File 'lib/sycamore/tree.rb', line 853

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

#initialize_clone(other) ⇒ Object

Clones the whole tree.



1452
1453
1454
1455
1456
 
# File 'lib/sycamore/tree.rb', line 1452

def initialize_clone(other)
  super
  clear_data
  add other
end

#inspect ⇒ String

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

Returns:

  • (String) 


1377
1378
1379
1380
 
# File 'lib/sycamore/tree.rb', line 1377

def inspect
  "#<#{self.class}:0x#{object_id.to_s(16)} #{
        to_h(sleaf_child_as: Sycamore::NothingTree::NestedString).inspect}>"
end

#internal? ⇒ Boolean #internal?(*nodes) ⇒ Boolean Also known as: nested?

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.

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

Examples:

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

Overloads:

  • #internal? ⇒ Boolean

    Checks if all #nodes of this tree have children.

    Returns:

    • (Boolean)
  • #internal?(*nodes) ⇒ Boolean

    Checks if all of the given nodes have children.

    Parameters:

    • nodes (Array<Object, Path>) —

      splat of nodes or Path objects

    Returns:

    • (Boolean) 


1139
1140
1141
1142
1143
1144
 
# File 'lib/sycamore/tree.rb', line 1139

def internal?(*nodes)
  return false if empty?
  nodes = self.nodes if nodes.empty?

  nodes.all? { |node| !leaf?(node) and include_node?(node) }
end

#leaf?(node) ⇒ Boolean

Checks if the given node has no children.

Examples:

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

Parameters:

  • node (Object, Path)

Returns:

  • (Boolean) 


1032
1033
1034
 
# File 'lib/sycamore/tree.rb', line 1032

def leaf?(node)
  include_node?(node) && child_at(node).empty?
end

#matches?(other) ⇒ Boolean Also known as: ===

TODO:

This should probably apply a less strict equivalence comparison on the nodes. Problem: Requires a solution which doesn’t use Hash#include?.

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

Examples:

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

Parameters:

  • other (Object)

Returns:

  • (Boolean) 


1285
1286
1287
1288
1289
1290
1291
1292
1293
 
# File 'lib/sycamore/tree.rb', line 1285

def matches?(other)
  if Tree.like?(other)
    matches_tree?(other)
  elsif other.is_a?(Enumerable)
    matches_enumerable?(other)
  else
    matches_atom?(other)
  end
end

#matches_atom?(other) ⇒ Boolean (private)

Returns:

  • (Boolean) 


1297
1298
1299
 
# File 'lib/sycamore/tree.rb', line 1297

private def matches_atom?(other)
  !other.nil? and (size == 1 and nodes.first == other and leaf? other)
end

#matches_enumerable?(other) ⇒ Boolean (private)

Returns:

  • (Boolean) 


1301
1302
1303
1304
 
# File 'lib/sycamore/tree.rb', line 1301

private def matches_enumerable?(other)
  size == other.size and
    all? { |node, child| child.empty? and other.include?(node) }
end

#matches_tree?(other) ⇒ Boolean (private)

Returns:

  • (Boolean) 


1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
 
# File 'lib/sycamore/tree.rb', line 1306

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)
                                       !other_child or
                                         (other_child.respond_to?(:empty?) and other_child.empty?)
        end
      else
        child.matches? other[node]
      end
    }
end

#new_child(parent_node, *args) ⇒ Tree

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

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.

Parameters:

  • parent_node (Object) —

    of the child tree to be created

Returns:



112
113
114
 
# File 'lib/sycamore/tree.rb', line 112

def new_child(parent_node, *args)
  self.class.new(*args)
end

#node ⇒ Object?

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

Examples:

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]"

Returns:

  • (Object, nil) —

    the single present node or nil, if no nodes present

Raises:

See Also:



568
569
570
571
572
573
 
# File 'lib/sycamore/tree.rb', line 568

def node
  nodes = self.nodes
  raise NonUniqueNodeSet, "multiple nodes present: #{nodes}" if nodes.size > 1

  nodes.first
end

#node! ⇒ Object

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

Examples:

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]"

Returns:

  • (Object) —

    the single present node

Raises:

See Also:



591
592
593
594
 
# File 'lib/sycamore/tree.rb', line 591

def node!
  raise EmptyNodeSet, "no node present" if empty?
  node
end

#nodes ⇒ Array<Object> Also known as: keys

The nodes of this tree (without their children).

Examples:

tree = Tree[foo: [:bar, :baz]]
tree.nodes        # => [:foo]
tree[:foo].nodes  # => [:bar, :baz]

Returns:

  • (Array<Object>) 


547
548
549
 
# File 'lib/sycamore/tree.rb', line 547

def nodes
  data.keys
end

#nothing? ⇒ Boolean

Checks if this is the Nothing tree.

Returns:

  • (Boolean) 


125
126
127
 
# File 'lib/sycamore/tree.rb', line 125

def nothing?
  false
end

#present? ⇒ Boolean

Note:

This is not the negation of #absent?, since this would result in a different behaviour than ActiveSupports present? method. For the negation of #absent?, see #existent?.

Checks if this is not blank, i.e. empty.

Returns:

  • (Boolean) 


156
157
158
 
# File 'lib/sycamore/tree.rb', line 156

def present?
  !blank?
end

#replace(node) ⇒ Object #replace(node_collection) ⇒ Object #replace(tree_structure) ⇒ Object #replace(path) ⇒ Object

Replaces the contents of this tree.

Examples:

tree = Tree[ "a" => 100, "b" => 200, "d" => {foo: [:bar, :baz]} ]
tree.replace(new: :content)
tree.to_h  # => {new: :content}

Overloads:

  • #replace(node) ⇒ Object

    Replaces the contents of this tree with a single node.

    Parameters:

    • node (Object)
  • #replace(node_collection) ⇒ Object

    Replaces the contents of this tree with multiple nodes.

    Parameters:

    • node_collection (Enumerable)
  • #replace(tree_structure) ⇒ Object

    Replaces the contents of this tree with a tree structure of nodes.

    Parameters:

    • tree_structure (Hash, Tree)
  • #replace(path) ⇒ Object

    Replaces the contents of this tree with a path of nodes.

    Parameters:

Returns:

  • self as a proper command method

Raises:



411
412
413
 
# File 'lib/sycamore/tree.rb', line 411

def replace(nodes_or_tree)
  clear.add(nodes_or_tree)
end

#search(nodes_or_tree) ⇒ Array<Path>

Searches the tree for one or multiple nodes or a complete tree.

Examples:

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            # => []

Parameters:

  • nodes_or_tree (Object, Array, Tree, Hash)

Returns:



940
941
942
 
# File 'lib/sycamore/tree.rb', line 940

def search(nodes_or_tree)
  _search(nodes_or_tree)
end

#size ⇒ Fixnum

The number of nodes in this tree.

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

Examples:

tree = Tree[ "d" => 100, "a" => 200, "v" => 300, "e" => [400, 500] ]
tree.size  # => 4
tree.delete("a")
tree.size  # => 3
tree["e"].size  # => 2

Returns:

  • (Fixnum) 


966
967
968
 
# File 'lib/sycamore/tree.rb', line 966

def size
  data.size
end

#strict_leaf?(node) ⇒ Boolean Also known as: sleaf?

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

Examples:

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

Parameters:

  • node (Object)

Returns:

  • (Boolean) 


1049
1050
1051
 
# File 'lib/sycamore/tree.rb', line 1049

def strict_leaf?(node)
  include_node?(node) && child_at(node).absent?
end

#strict_leaves? ⇒ Boolean #strict_leaves?(*nodes) ⇒ Boolean Also known as: sleaves?

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

Examples:

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

Overloads:

  • #strict_leaves? ⇒ Boolean

    Returns if all #nodes of this tree have no children, even not an empty child tree.

    Returns:

    • (Boolean)
  • #strict_leaves?(*nodes) ⇒ Boolean

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

    Parameters:

    • nodes (Array<Object, Path>) —

      splat of nodes or Path objects

    Returns:

    • (Boolean) 


1076
1077
1078
1079
1080
 
# File 'lib/sycamore/tree.rb', line 1076

def strict_leaves?(*nodes)
  nodes = self.nodes if nodes.empty?

  nodes.all? { |node| strict_leaf?(node) }
end

#to_h ⇒ Hash

A hash representation of this tree.

Returns:

  • (Hash) 


1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
 
# File 'lib/sycamore/tree.rb', line 1346

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

#to_native_object(sleaf_child_as: nil, special_nil: false) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

A native Ruby object representing the content of the tree.

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



1331
1332
1333
1334
1335
1336
1337
1338
1339
 
# File 'lib/sycamore/tree.rb', line 1331

def to_native_object(sleaf_child_as: nil, special_nil: false)
  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

#to_s ⇒ String

A string representation of this tree.

Returns:

  • (String) 


1364
1365
1366
1367
1368
1369
1370
 
# File 'lib/sycamore/tree.rb', line 1364

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 ⇒ Fixnum Also known as: tsize

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

Examples:

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

Returns:

  • (Fixnum) 


982
983
984
985
986
 
# File 'lib/sycamore/tree.rb', line 982

def total_size
  total = size
  data.each { |_, child| total += child.total_size }
  total
end

#valid_node!(node) ⇒ Object (private)

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Raises:



1405
1406
1407
1408
1409
 
# File 'lib/sycamore/tree.rb', line 1405

private def valid_node!(node)
  raise InvalidNode, "#{node} is not a valid tree node" if node.is_a? Enumerable

  node
end

#valid_node_element!(node) ⇒ Object (private)

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Raises:



1396
1397
1398
1399
1400
1401
 
# File 'lib/sycamore/tree.rb', line 1396

private def valid_node_element!(node)
  raise InvalidNode, "#{node} is not a valid tree node" if
    node.is_a?(Enumerable) && !node.is_a?(Path) && !Tree.like?(node)

  node
end

#valid_tree!(tree) ⇒ Object (private)

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future. 



1384
1385
1386
1387
1388
1389
1390
1391
1392
 
# File 'lib/sycamore/tree.rb', line 1384

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