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.



67
68
 
# File 'lib/sycamore/tree.rb', line 67

def initialize
end

Instance Attribute Details

#data ⇒ Object (readonly, protected)

the internal hash representation of this tree



13
14
15
 
# File 'lib/sycamore/tree.rb', line 13

protected def data
  @data ||= Hash.new
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) 


1421
1422
1423
1424
1425
1426
1427
1428
 
# 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

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



90
91
92
93
94
 
# 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

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) 


1214
1215
1216
 
# 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

#<=(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) 


1231
1232
1233
 
# File 'lib/sycamore/tree.rb', line 1231

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) 


1194
1195
1196
1197
1198
1199
 
# 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) ⇒ 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) 


1265
1266
1267
 
# 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) ⇒ 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) 


1248
1249
1250
 
# File 'lib/sycamore/tree.rb', line 1248

def >=(other)
  (other.is_a?(Tree) or other.is_a?(Absence)) and self.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:



473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
 
# 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

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



941
942
943
944
945
946
947
 
# File 'lib/sycamore/tree.rb', line 941

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) 


137
138
139
 
# File 'lib/sycamore/tree.rb', line 137

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:



210
211
212
213
214
215
216
217
218
219
220
221
222
223
 
# 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

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



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

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) 



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

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. 



245
246
247
248
249
250
251
252
253
 
# 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

#add_path(path) ⇒ Object (private) 



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

private def add_path(path)
  return self if path.root?

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

  self
end

#add_tree(tree) ⇒ Object (private) 



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

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:



640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
 
# 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

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



612
613
614
615
616
 
# 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 ⇒ 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



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

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. 



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

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

  self
end

#clear_data ⇒ Object (protected) 



74
75
76
 
# File 'lib/sycamore/tree.rb', line 74

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



518
519
520
521
522
523
524
525
526
527
 
# 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(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:



321
322
323
324
325
326
327
328
329
330
331
332
333
334
 
# 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

#delete_node(node) ⇒ Object (protected) 



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

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

  self
end

#delete_path(path) ⇒ Object (protected) 



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

protected def delete_path(path)
  case path.length
    when 0 then return self
    when 1 then return delete_node(path.node)
  end

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

  self
end

#delete_tree(tree) ⇒ Object (protected) 



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

protected def delete_tree(tree)
  tree.each { |node_to_delete, child_to_delete| # using a {} block to circumvent this Rubinius issue: https://github.com/rubinius/rubinius-code/issues/7
    next unless include? node_to_delete
    if Nothing.like?(child_to_delete) or
        (child_to_delete.respond_to?(:empty?) and child_to_delete.empty?)
      delete_node node_to_delete
    else
      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

#dup ⇒ Tree

Duplicates the whole tree.

Returns:



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

def dup
  duplicate = self.class.new.add(self)
  duplicate.taint if tainted?
  duplicate
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>) 


761
762
763
764
765
766
767
 
# File 'lib/sycamore/tree.rb', line 761

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

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


790
791
792
793
794
795
796
 
# File 'lib/sycamore/tree.rb', line 790

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

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


820
821
822
823
824
825
826
827
828
829
830
831
832
 
# 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

#empty? ⇒ Boolean Also known as: blank?

Checks if this tree is empty.

Examples:

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

Returns:

  • (Boolean) 


1010
1011
1012
 
# File 'lib/sycamore/tree.rb', line 1010

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) 


1174
1175
1176
1177
 
# 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? ⇒ Boolean

Checks if this is not an Absence or Nothing.

Returns:

  • (Boolean) 


146
147
148
 
# File 'lib/sycamore/tree.rb', line 146

def existent?
  not 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) 


1102
1103
1104
1105
1106
 
# File 'lib/sycamore/tree.rb', line 1102

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



690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
 
# 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, &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



729
730
731
732
733
734
735
736
737
738
 
# 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

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


1155
1156
1157
 
# File 'lib/sycamore/tree.rb', line 1155

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) 


996
997
998
999
 
# File 'lib/sycamore/tree.rb', line 996

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) 


901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
 
# 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) ⇒ 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) 


877
878
879
880
881
 
# File 'lib/sycamore/tree.rb', line 877

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) 


849
850
851
852
853
854
855
856
857
858
859
860
861
862
 
# 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

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


1374
1375
1376
1377
 
# 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? ⇒ 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) 


1136
1137
1138
1139
1140
1141
 
# 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

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


1029
1030
1031
 
# File 'lib/sycamore/tree.rb', line 1029

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) 


1283
1284
1285
1286
1287
1288
1289
 
# 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

#matches_atom?(other) ⇒ Boolean (private)

Returns:

  • (Boolean) 


1293
1294
1295
 
# File 'lib/sycamore/tree.rb', line 1293

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

#matches_enumerable?(other) ⇒ Boolean (private)

Returns:

  • (Boolean) 


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

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) 


1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
 
# File 'lib/sycamore/tree.rb', line 1302

private def matches_tree?(other)
  size == other.size and
    all? { |node, child|
      if child.nothing?
        other.include?(node) and begin other_child = other.fetch(node, nil)
          not other_child or
            (other_child.respond_to?(:empty?) and other_child.empty?)
        end
      else
        child.matches? other[node]
      end }
end

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



114
115
116
 
# File 'lib/sycamore/tree.rb', line 114

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:



566
567
568
569
570
571
 
# 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! ⇒ 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:



589
590
591
592
 
# File 'lib/sycamore/tree.rb', line 589

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


544
545
546
 
# File 'lib/sycamore/tree.rb', line 544

def nodes
  data.keys
end

#nothing? ⇒ Boolean

Checks if this is the Nothing tree.

Returns:

  • (Boolean) 


128
129
130
 
# File 'lib/sycamore/tree.rb', line 128

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) 


159
160
161
 
# File 'lib/sycamore/tree.rb', line 159

def present?
  not 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:



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

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:



937
938
939
 
# File 'lib/sycamore/tree.rb', line 937

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) 


963
964
965
 
# File 'lib/sycamore/tree.rb', line 963

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) 


1046
1047
1048
 
# File 'lib/sycamore/tree.rb', line 1046

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) 


1073
1074
1075
1076
1077
 
# File 'lib/sycamore/tree.rb', line 1073

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

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

#to_h(*args) ⇒ Hash

A hash representation of this tree.

Returns:

  • (Hash) 


1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
 
# 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) ⇒ 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.



1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
 
# 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 ⇒ String

A string representation of this tree.

Returns:

  • (String) 


1361
1362
1363
1364
1365
1366
1367
 
# 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 ⇒ 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) 


979
980
981
982
983
 
# File 'lib/sycamore/tree.rb', line 979

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:



1403
1404
1405
1406
1407
 
# File 'lib/sycamore/tree.rb', line 1403

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:



1393
1394
1395
1396
1397
1398
 
# File 'lib/sycamore/tree.rb', line 1393

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

  node
end

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



1381
1382
1383
1384
1385
1386
1387
1388
1389
 
# File 'lib/sycamore/tree.rb', line 1381

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

  tree
end