Class: Tree::TreeNode

Inherits:

Object

• Object
• Tree::TreeNode

show all

Includes:

Enumerable

Defined in:

lib/tree.rb

Overview

                +------------+
                |    ROOT    |
                +-----+------+
        +-------------+------------+
        |                          |
+-------+-------+          +-------+-------+
|  CHILD 1      |          |  CHILD 2      |
+-------+-------+          +---------------+
        |
        |
+-------+-------+
| GRANDCHILD 1  |
+---------------+

# ..... Example starts.
require 'tree'                 # Load the library

# ..... Create the root node first.  Note that every node has a name and an optional content payload.
root_node = Tree::TreeNode.new("ROOT", "Root Content")
root_node.print_tree

# ..... Now insert the child nodes.  Note that you can "chain" the child insertions for a given path to any depth.
root_node << Tree::TreeNode.new("CHILD1", "Child1 Content") << Tree::TreeNode.new("GRANDCHILD1", "GrandChild1 Content")
root_node << Tree::TreeNode.new("CHILD2", "Child2 Content")

# ..... Lets print the representation to stdout.  This is primarily used for debugging purposes.
root_node.print_tree

# ..... Lets directly access children and grandchildren of the root.  The can be "chained" for a given path to any depth.
child1       = root_node["CHILD1"]
grand_child1 = root_node["CHILD1"]["GRANDCHILD1"]

# ..... Now lets retrieve siblings of the current node as an array.
siblings_of_child1 = child1.siblings

# ..... Lets retrieve immediate children of the root node as an array.
children_of_root = root_node.children

# ..... This is a depth-first and L-to-R pre-ordered traversal.
root_node.each { |node| node.content.reverse }

# ..... Lets remove a child node from the root node.
root_node.remove!(child1)

Instance Attribute Summary (collapse)

• - (Integer) breadth readonly

  Breadth of the tree at the receiver node's level.

• - (Array<Tree::TreeNode>) children {|child| ... }

  An array of all the immediate children of the receiver node.

• - (Object) content

  Content of this node.

• - (Tree::TreeNode) first_child

  First child of the receiver node.

• - (Tree::TreeNode) first_sibling

  First sibling of the receiver node.

• - (Integer) in_degree readonly

  The incoming edge-count of the receiver node.

• - (Tree::TreeNode) last_child

  Last child of the receiver node.

• - (Tree::TreeNode) last_sibling

  Last sibling of the receiver node.

• - (Object) name readonly

  Name of this node.

• - (Tree::treeNode) next_sibling

  Next sibling for the receiver node.

• - (Integer) node_depth (also: #level) readonly

  Depth of the receiver node in its tree.

• - (Integer) node_height readonly

  Height of the (sub)tree from the receiver node.

• - (Integer) out_degree readonly

  The outgoing edge-count of the receiver node.

• - (Object) parent readonly

  Parent of this node.

• - (Array^?) parentage readonly

  An array of ancestors of the receiver node in reversed order (the first element is the immediate parent of the receiver).

• - (Tree::treeNode) previous_sibling

  Previous sibling of the receiver node.

• - (Tree::TreeNode) root

  root node for the (sub)tree to which the receiver node belongs.

• - (Array<Tree::TreeNode>) siblings {|sibling| ... }

  An array of siblings for the receiver node.

• - (Integer) size readonly

  Total number of nodes in this (sub)tree, including the receiver node.

Node Creation (collapse)

• - (Tree::TreeNode) detached_copy

  Returns a copy of the receiver node, with its parent and children links removed.

• - (Tree::TreeNode) detached_subtree_copy (also: #dup)

  Returns a copy of entire (sub-)tree from receiver node.

• - (TreeNode) initialize(name, content = nil) constructor

  Creates a new node with a name and optional content.

Structure Modification (collapse)

• - (Tree::TreeNode) <<(child)

  Convenience synonym for #add method.

• - (Tree::TreeNode) add(child, at_index = -1))

  Adds the specified child node to the receiver node.

• - (Boolean) has_content?

  Returns true if the receiver node has content.

• - (Tree::TreeNode) remove!(child)

  Removes the specified child node from the receiver node.

• - (Tree::TreeNode) remove_all!

  Removes all children from the receiver node.

• - (Tree:TreeNode) remove_from_parent!

  Removes the receiver node from its parent.

Tree Traversal (collapse)

• - (Tree::TreeNode) [](name_or_index, num_as_name = false)

  Returns the requested node from the set of immediate children.

• - (Object) breadth_each {|child| ... }

  Performs breadth-first traversal of the (sub)tree rooted at the receiver node.

• - (Object) each {|child| ... }

  Traverses each node (including the receiver node) of the (sub)tree rooted at this node by yielding the nodes to the specified block.

• - (Object) each_leaf {|node| ... }

  Yields every leaf node of the (sub)tree rooted at the receiver node to the specified block.

• - (Object) preordered_each {|child| ... }

  Traverses the (sub)tree rooted at the receiver node in pre-ordered sequence.

Class Method Summary (collapse)

• + (Tree::TreeNode) json_create(json_hash)

  Helper method to create a Tree::TreeNode instance from the JSON hash representation.

Instance Method Summary (collapse)

• - (Integer) <=>(other)

  Provides a comparision operation for the nodes.

• - (Object) as_json(options = {})

  Creates a JSON ready Hash for the #to_json method.

• - (Integer) depth deprecated Deprecated.

  This method returns an incorrect value. Use the 'node_depth' method instead.

• - (Object) freeze_tree!

  Freezes all nodes in the (sub)tree rooted at the receiver node.

• - (Boolean) has_children?

  Returns true if the receiver node has any child node.

• - (Boolean) is_first_sibling?

  Returns true if the receiver node is the first sibling at its level.

• - (Boolean) is_last_sibling?

  Returns true if the receiver node is the last sibling at its level.

• - (Boolean) is_leaf?

  Returns true if the receiver node is a 'leaf' - i.e., one without any children.

• - (Boolean) is_only_child?

  Returns true if the receiver node is the only child of its parent.

• - (Boolean) is_root?

  Returns true if the receiver is a root node.

• - (Integer) length deprecated Deprecated.

  This method name is ambiguous and may be removed. Use TreeNode#size instead.

• - (Object) marshal_dump

  Returns a marshal-dump represention of the (sub)tree rooted at the receiver node.

• - (Object) marshal_load(dumped_tree_array)

  Loads a marshalled dump of a tree and returns the root node of the reconstructed tree.

• - (Object) method_missing(meth, *args, &blk)

  Allow the deprecated CamelCase method names.

• - (Object) print_tree(level = 0)

  Pretty prints the (sub)tree rooted at the receiver node.

• - (Object) to_json(*a)

  Creates a JSON representation of this node including all it's children.

• - (String) to_s

  Returns string representation of the receiver node.

181
182
183
184
185
186
187
188
189
190
191
192
193

# File 'lib/tree.rb', line 181

def initialize(name, content = nil)
  raise ArgumentError, "Node name HAS to be provided!" if name == nil
  @name, @content = name, content

  if name.kind_of?(Integer)
    warn StandardWarning,
         "Using integer as node name. Semantics of TreeNode[] may not be what you expect! #{name} #{content}"
  end

  self.set_as_root!
  @children_hash = Hash.new
  @children = []
end

928
929
930
931
932
933
934
935

# File 'lib/tree.rb', line 928

def method_missing(meth, *args, &blk)
  if self.respond_to?(new_method_name = underscore(meth))
    warn DeprecatedMethodWarning, "The camelCased methods are deprecated. Please use #{new_method_name} instead of #{meth}"
    return send(new_method_name, *args, &blk)
  else
    super
  end
end

946
947
948

# File 'lib/tree.rb', line 946

def breadth
  is_root? ? 1 : parent.children.size
end

433
434
435
436
437
438
439

# File 'lib/tree.rb', line 433

def children
  if block_given?
    @children.each {|child| yield child}
  else
    @children
  end
end

155
156
157

# File 'lib/tree.rb', line 155

def content
  @content
end

446
447
448

# File 'lib/tree.rb', line 446

def first_child
  children.first
end

637
638
639

# File 'lib/tree.rb', line 637

def first_sibling
  is_root? ? self : parent.children.first
end

960
961
962

# File 'lib/tree.rb', line 960

def in_degree
  is_root? ? 0 : 1
end

455
456
457

# File 'lib/tree.rb', line 455

def last_child
  children.last
end

662
663
664

# File 'lib/tree.rb', line 662

def last_sibling
  is_root? ? self : parent.children.last
end

147
148
149

# File 'lib/tree.rb', line 147

def name
  @name
end

722
723
724
725
726
727

# File 'lib/tree.rb', line 722

def next_sibling
  return nil if is_root?

  myidx = parent.children.index(self)
  parent.children.at(myidx + 1) if myidx
end

898
899
900
901

# File 'lib/tree.rb', line 898

def node_depth
  return 0 if is_root?
  1 + parent.node_depth
end

882
883
884
885

# File 'lib/tree.rb', line 882

def node_height
  return 0 if is_leaf?
  1 + @children.collect { |child| child.node_height }.max
end

971
972
973

# File 'lib/tree.rb', line 971

def out_degree
  is_leaf? ? 0 : children.size
end

160
161
162

# File 'lib/tree.rb', line 160

def parent
  @parent
end

241
242
243
244
245
246
247
248
249
250
251
252

# File 'lib/tree.rb', line 241

def parentage
  return nil if is_root?

  parentage_array = []
  prev_parent = self.parent
  while (prev_parent)
    parentage_array << prev_parent
    prev_parent = prev_parent.parent
  end

  parentage_array
end

739
740
741
742
743
744

# File 'lib/tree.rb', line 739

def previous_sibling
  return nil if is_root?

  myidx = parent.children.index(self)
  parent.children.at(myidx - 1) if myidx && myidx > 0
end

620
621
622
623
624

# File 'lib/tree.rb', line 620

def root
  root = self
  root = root.parent while !root.is_root?
  root
end

689
690
691
692
693
694
695
696
697
698
699

# File 'lib/tree.rb', line 689

def siblings
  return [] if is_root?

  if block_given?
    parent.children.each { |sibling| yield sibling if sibling != self }
  else
    siblings = []
    parent.children {|my_sibling| siblings << my_sibling if my_sibling != self}
    siblings
  end
end

582
583
584

# File 'lib/tree.rb', line 582

def size
  @children.inject(1) {|sum, node| sum + node.size}
end

861
862
863
864
865
866
867
868
869
870
871

# File 'lib/tree.rb', line 861

def self.json_create(json_hash)

  node = new(json_hash["name"], json_hash["content"])

  json_hash["children"].each do |child|
    node << child
  end if json_hash["children"]

  return node

end

root << child << grand_child

279
280
281

# File 'lib/tree.rb', line 279

def <<(child)
  add(child)
end

753
754
755
756

# File 'lib/tree.rb', line 753

def <=>(other)
  return +1 if other == nil
  self.name <=> other.name
end

559
560
561
562
563
564
565
566
567
568
569
570

# File 'lib/tree.rb', line 559

def [](name_or_index, num_as_name=false)
  raise ArgumentError, "Name_or_index needs to be provided!" if name_or_index == nil

  if name_or_index.kind_of?(Integer) and not num_as_name
    @children[name_or_index]
  else
    if num_as_name and not name_or_index.kind_of?(Integer)
      warn StandardWarning, "Redundant use of the `num_as_name` flag for non-integer node name"
    end
    @children_hash[name_or_index]
  end
end

-children.size..children.size

313
314
315
316
317
318
319
320
321
322
323
324
325
326
327

# File 'lib/tree.rb', line 313

def add(child, at_index = -1)
  raise ArgumentError, "Attempting to add a nil node" unless child # Only handles the immediate child scenario
  raise ArgumentError, "Attempting add node to itself" if self == child
  raise "Child #{child.name} already added!" if @children_hash.has_key?(child.name)

  if insertion_range.include?(at_index)
    @children.insert(at_index, child)
  else
    raise "Attempting to insert a child at a non-existent location (#{at_index}) when only positions from #{insertion_range.min} to #{insertion_range.max} exist."
  end

  @children_hash[child.name]  = child
  child.parent = self
  return child
end

813
814
815
816
817
818
819
820
821
822
823
824
825
826
827

# File 'lib/tree.rb', line 813

def as_json(options = {})

    json_hash = {
      "name"         => name,
      "content"      => content,
      JSON.create_id => self.class.name
    }

    if has_children?
      json_hash["children"] = children
    end

    return json_hash

end

497
498
499
500
501
502
503
504
505
506
507

# File 'lib/tree.rb', line 497

def breadth_each(&block)
  node_queue = [self]       # Create a queue with self as the initial entry

  # Use a queue to do breadth traversal
  until node_queue.empty?
    node_to_traverse = node_queue.shift
    yield node_to_traverse
    # Enqueue the children from left to right.
    node_to_traverse.children { |child| node_queue.push child }
  end
end

919
920
921
922
923
924

# File 'lib/tree.rb', line 919

def depth
  warn DeprecatedMethodWarning, 'This method is deprecated.  Please use node_depth() or node_height() instead (bug # 22535)'

  return 1 if is_leaf?
  1 + @children.collect { |child| child.depth }.max
end

199
200
201

# File 'lib/tree.rb', line 199

def detached_copy
  Tree::TreeNode.new(@name, @content ? @content.clone : nil)
end

209
210
211
212
213

# File 'lib/tree.rb', line 209

def detached_subtree_copy
  new_node = detached_copy
  children { |child| new_node << child.detached_subtree_copy }
  new_node
end

471
472
473
474

# File 'lib/tree.rb', line 471

def each(&block)             # :yields: node
  yield self
  children { |child| child.each(&block) }
end

519
520
521
522
523
524
525

# File 'lib/tree.rb', line 519

def each_leaf &block
  if block_given?
    self.each { |node| yield(node) if node.is_leaf? }
  else
    self.select { |node| node.is_leaf?}
  end
end

762
763
764

# File 'lib/tree.rb', line 762

def freeze_tree!
  each {|node| node.freeze}
end

407
408
409

# File 'lib/tree.rb', line 407

def has_children?
  @children.length != 0
end

381
382
383

# File 'lib/tree.rb', line 381

def has_content?
  @content != nil
end

647
648
649

# File 'lib/tree.rb', line 647

def is_first_sibling?
  first_sibling == self
end

672
673
674

# File 'lib/tree.rb', line 672

def is_last_sibling?
  last_sibling == self
end

417
418
419

# File 'lib/tree.rb', line 417

def is_leaf?
  !has_children?
end

708
709
710

# File 'lib/tree.rb', line 708

def is_only_child?
  is_root? ? true : parent.children.size == 1
end

398
399
400

# File 'lib/tree.rb', line 398

def is_root?
  @parent == nil
end

592
593
594

# File 'lib/tree.rb', line 592

def length
  size()
end

767
768
769

# File 'lib/tree.rb', line 767

def marshal_dump
  self.collect { |node| node.create_dump_rep }
end

783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800

# File 'lib/tree.rb', line 783

def marshal_load(dumped_tree_array)
  nodes = { }
  dumped_tree_array.each do |node_hash|
    name        = node_hash[:name]
    parent_name = node_hash[:parent]
    content     = Marshal.load(node_hash[:content])

    if parent_name then
      nodes[name] = current_node = Tree::TreeNode.new(name, content)
      nodes[parent_name].add current_node
    else
      # This is the root node, hence initialize self.
      initialize(name, content)

      nodes[name] = self    # Add self to the list of nodes
    end
  end
end

484
485
486

# File 'lib/tree.rb', line 484

def preordered_each(&block)  # :yields: node
  each(&block)
end

599
600
601
602
603
604
605
606
607
608
609
610
611
612
613

# File 'lib/tree.rb', line 599

def print_tree(level = 0)
  if is_root?
    print "*"
  else
    print "|" unless parent.is_last_sibling?
    print(' ' * (level - 1) * 4)
    print(is_last_sibling? ? "+" : "|")
    print "---"
    print(has_children? ? "+" : ">")
  end

  puts " #{name}"

  children { |child| child.print_tree(level + 1)}
end

343
344
345
346
347
348
349
350

# File 'lib/tree.rb', line 343

def remove!(child)
  return nil unless child

  @children_hash.delete(child.name)
  @children.delete(child)
  child.set_as_root!
  child
end

370
371
372
373
374
375
376

# File 'lib/tree.rb', line 370

def remove_all!
  @children.each { |child| child.set_as_root! }

  @children_hash.clear
  @children.clear
  self
end

359
360
361

# File 'lib/tree.rb', line 359

def remove_from_parent!
  @parent.remove!(self) unless is_root?
end

841
842
843

# File 'lib/tree.rb', line 841

def to_json(*a)
  as_json.to_json(*a)
end

226
227
228
229
230
231
232

# File 'lib/tree.rb', line 226

def to_s
  "Node Name: #{@name}" +
    " Content: " + (@content.to_s || "<Empty>") +
    " Parent: " + (is_root?()  ? "<None>" : @parent.name.to_s) +
    " Children: #{@children.length}" +
    " Total Nodes: #{size()}"
end