Class: Tree::TreeNode

Description

TreeNode Class Description

The node class for the tree representation. the nodes are named and have a place-holder for the node data (i.e., the `content’ of the node). The node names are expected to be unique. In addition, the node provides navigation methods to traverse the tree.

The nodes can have any number of child nodes attached to it. Note that while this implementation does not support directed graphs, the class itself makes no restrictions on associating a node‘s CONTENT with multiple parent nodes.

Example

 The following code-snippet implements this tree structure:

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

require ‘tree‘

myTreeRoot = Tree::TreeNode.new("ROOT", "Root Content")

myTreeRoot << Tree::TreeNode.new("CHILD1", "Child1 Content") << Tree::TreeNode.new("GRANDCHILD1", "GrandChild1 Content")

myTreeRoot << Tree::TreeNode.new("CHILD2", "Child2 Content")

myTreeRoot.printTree

child1 = myTreeRoot["CHILD1"]

grandChild1 = myTreeRoot["CHILD1"]["GRANDCHILD1"]

siblingsOfChild1Array = child1.siblings

immediateChildrenArray = myTreeRoot.children

# Process all nodes

myTreeRoot.each { |node| node.content.reverse }

myTreeRoot.remove!(child1) # Remove the child

Attributes

NameRead/write?Description
content R
content W
name R
parent R

Public Class methods

new (name, content = nil)

Constructor which expects the name of the node

Name of the node is expected to be unique across the tree.

The content can be of any type, and is defaulted to nil. 

     # File lib/tree.rb, line 118
118:     def initialize(name, content = nil)
119:       raise "Node name HAS to be provided" if name == nil
120:       @name = name
121:       @content = content
122:       self.setAsRoot!
123: 
124:       @childrenHash = Hash.new
125:       @children = []
126:     end

Public Instance methods

<< (child)

Convenience synonym for TreeNode#add method. This method allows a convenient method to add children hierarchies in the tree.

E.g. root << child << grand_child 

     # File lib/tree.rb, line 167
167:     def <<(child)
168:       add(child)
169:     end

<=> (other)

Provides a comparision operation for the nodes. Comparision is based on the natural character-set ordering for the node names. 

     # File lib/tree.rb, line 417
417:     def <=>(other)
418:       return +1 if other == nil
419:       self.name <=> other.name
420:     end

[] (name_or_index)

Returns the requested node from the set of immediate children.

If the parameter is numeric, then the in-sequence array of children is accessed (see Tree#children). If the parameter is not numeric, then it is assumed to be the name of the child node to be returned. 

     # File lib/tree.rb, line 301
301:     def [](name_or_index)
302:       raise "Name_or_index needs to be provided" if name_or_index == nil
303: 
304:       if name_or_index.kind_of?(Integer)
305:         @children[name_or_index]
306:       else
307:         @childrenHash[name_or_index]
308:       end
309:     end

add (child)

Adds the specified child node to the receiver node. The child node‘s parent is set to be the receiver. The child is added as the last child in the current list of children for the receiver node. 

     # File lib/tree.rb, line 174
174:     def add(child)
175:       raise "Child already added" if @childrenHash.has_key?(child.name)
176: 
177:       @childrenHash[child.name]  = child
178:       @children << child
179:       child.parent = self
180:       return child
181: 
182:     end

breadth ()

Returns breadth of the tree at this node level. A single node has a breadth of 1. 

     # File lib/tree.rb, line 467
467:     def breadth
468:       return 1 if isRoot?
469:       parent.children.size
470:     end

breadth_each () {|node_to_traverse| ...}

Performs breadth first traversal of the tree rooted at this node. The traversal in a given level is from left to right. 

     # File lib/tree.rb, line 277
277:     def breadth_each &block
278:       node_queue = [self]       # Create a queue with self as the initial entry
279: 
280:       # Use a queue to do breadth traversal
281:       until node_queue.empty?
282:         node_to_traverse = node_queue.shift
283:         yield node_to_traverse
284:         # Enqueue the children from left to right.
285:         node_to_traverse.children { |child| node_queue.push child }
286:       end
287:     end

children () {|child| ...}

Returns an array of all the immediate children. If a block is given, yields each child node to the block. 

     # File lib/tree.rb, line 241
241:     def children
242:       if block_given?
243:         @children.each {|child| yield child}
244:       else
245:         @children
246:       end
247:     end

depth ()

Returns depth of the tree from this node. A single leaf node has a depth of 1. 

     # File lib/tree.rb, line 460
460:     def depth
461:       return 1 if isLeaf?
462:       1 + @children.collect { |child| child.depth }.max
463:     end

detached_copy ()

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

     # File lib/tree.rb, line 129
129:     def detached_copy
130:       Tree::TreeNode.new(@name, @content ? @content.clone : nil)
131:     end

each () {|self| ...}

Returns every node (including the receiver node) from the tree to the specified block. The traversal is depth first and from left to right in pre-ordered sequence. 

     # File lib/tree.rb, line 264
264:     def each &block
265:       yield self
266:       children { |child| child.each(&block) }
267:     end

each_leaf () {|node| ...}

Yields all leaf nodes from this node to the specified block. May yield this node as well if this is a leaf node. Leaf traversal depth first and left to right. 

     # File lib/tree.rb, line 292
292:     def each_leaf &block
293:       self.each { |node| yield(node) if node.isLeaf? }
294:     end

firstChild ()

Returns the first child of this node. Will return nil if no children are present. 

     # File lib/tree.rb, line 251
251:     def firstChild
252:       children.first
253:     end

firstSibling ()

Returns the first sibling for this node. If this is the root node, returns itself. 

     # File lib/tree.rb, line 349
349:     def firstSibling
350:       if isRoot?
351:         self
352:       else
353:         parent.children.first
354:       end
355:     end

freezeTree! ()

Freezes all nodes in the tree 

     # File lib/tree.rb, line 423
423:     def freezeTree!
424:       each {|node| node.freeze}
425:     end

hasChildren? ()

Indicates whether this node has any immediate child nodes. 

     # File lib/tree.rb, line 229
229:     def hasChildren?
230:       @children.length != 0
231:     end

hasContent? ()

Indicates whether this node has any associated content. 

     # File lib/tree.rb, line 213
213:     def hasContent?
214:       @content != nil
215:     end

isFirstSibling? ()

Returns true if this node is the first sibling. 

     # File lib/tree.rb, line 358
358:     def isFirstSibling?
359:       firstSibling == self
360:     end

isLastSibling? ()

Returns true if his node is the last sibling 

     # File lib/tree.rb, line 373
373:     def isLastSibling?
374:       lastSibling == self
375:     end

isLeaf? ()

Indicates whether this node is a ‘leaf’ - i.e., one without any children 

     # File lib/tree.rb, line 235
235:     def isLeaf?
236:       !hasChildren?
237:     end

isOnlyChild? ()

Returns true if this node is the only child of its parent 

     # File lib/tree.rb, line 394
394:     def isOnlyChild?
395:       parent.children.size == 1
396:     end

isRoot? ()

Indicates whether this node is a root node. Note that orphaned children will also be reported as root nodes. 

     # File lib/tree.rb, line 224
224:     def isRoot?
225:       @parent == nil
226:     end

lastChild ()

Returns the last child of this node. Will return nil if no children are present. 

     # File lib/tree.rb, line 257
257:     def lastChild
258:       children.last
259:     end

lastSibling ()

Returns the last sibling for this node. If this node is the root, returns itself. 

     # File lib/tree.rb, line 364
364:     def lastSibling
365:       if isRoot?
366:         self
367:       else
368:         parent.children.last
369:       end
370:     end

length ()

Convenience synonym for Tree#size 

     # File lib/tree.rb, line 318
318:     def length
319:       size()
320:     end

marshal_dump ()

Creates the marshal-dump represention of the tree rooted at this node. 

     # File lib/tree.rb, line 428
428:     def marshal_dump
429:       self.collect { |node| node.createDumpRep }
430:     end

marshal_load (dumped_tree_array)

Loads a marshalled dump of the tree and returns the root node of the reconstructed tree. See the Marshal class for additional details. 

     # File lib/tree.rb, line 439
439:     def marshal_load(dumped_tree_array)
440:       nodes = { }
441:       for node_hash in dumped_tree_array do
442:         name        = node_hash[:name]
443:         parent_name = node_hash[:parent]
444:         content     = Marshal.load(node_hash[:content])
445: 
446:         if parent_name then
447:           nodes[name] = current_node = Tree::TreeNode.new(name, content)
448:           nodes[parent_name].add current_node
449:         else
450:           # This is the root node, hence initialize self.
451:           initialize(name, content)
452: 
453:           nodes[name] = self    # Add self to the list of nodes
454:          end
455:       end
456:     end

nextSibling ()

Returns the next sibling for this node. Will return nil if no subsequent node is present. 

     # File lib/tree.rb, line 400
400:     def nextSibling
401:       if myidx = parent.children.index(self)
402:         parent.children.at(myidx + 1)
403:       end
404:     end

parentage ()

Returns an array of ancestors in reversed order (the first element is the immediate parent). Returns nil if this is a root node. 

     # File lib/tree.rb, line 144
144:     def parentage
145:       return nil if isRoot?
146: 
147:       parentageArray = []
148:       prevParent = self.parent
149:       while (prevParent)
150:         parentageArray << prevParent
151:         prevParent = prevParent.parent
152:       end
153: 
154:       parentageArray
155:     end

preordered_each (&block)

Traverses the tree in a pre-ordered sequence. This is equivalent to TreeNode#each 

     # File lib/tree.rb, line 271
271:     def preordered_each &block
272:       each(&block)
273:     end

previousSibling ()

Returns the previous sibling for this node. Will return nil if no subsequent node is present. 

     # File lib/tree.rb, line 408
408:     def previousSibling
409:       if myidx = parent.children.index(self)
410:         parent.children.at(myidx - 1) if myidx > 0
411:       end
412:     end

printTree (level = 0)

Pretty prints the tree starting with the receiver node. 

     # File lib/tree.rb, line 323
323:     def printTree(level = 0)
324: 
325:       if isRoot?
326:         print "*"
327:       else
328:         print "|" unless parent.isLastSibling?
329:         print(' ' * (level - 1) * 4)
330:         print(isLastSibling? ? "+" : "|")
331:         print "---"
332:         print(hasChildren? ? "+" : ">")
333:       end
334: 
335:       puts " #{name}"
336: 
337:       children { |child| child.printTree(level + 1)}
338:     end

remove! (child)

Removes the specified child node from the receiver node. The removed children nodes are orphaned but available if an alternate reference exists.

Returns the child node. 

     # File lib/tree.rb, line 189
189:     def remove!(child)
190:       @childrenHash.delete(child.name)
191:       @children.delete(child)
192:       child.setAsRoot! unless child == nil
193:       return child
194:     end

removeAll! ()

Removes all children from the receiver node. 

     # File lib/tree.rb, line 203
203:     def removeAll!
204:       for child in @children
205:         child.setAsRoot!
206:       end
207:       @childrenHash.clear
208:       @children.clear
209:       self
210:     end

removeFromParent! ()

Removes this node from its parent. If this is the root node, then does nothing. 

     # File lib/tree.rb, line 198
198:     def removeFromParent!
199:       @parent.remove!(self) unless isRoot?
200:     end

root ()

Returns the root for this tree. Root‘s root is itself. 

     # File lib/tree.rb, line 341
341:     def root
342:       root = self
343:       root = root.parent while !root.isRoot?
344:       root
345:     end

siblings () {|sibling if sibling != self| ...}

Returns an array of siblings for this node. If a block is provided, yields each of the sibling nodes to the block. The root always has nil siblings. 

     # File lib/tree.rb, line 380
380:     def siblings
381:       return nil if isRoot?
382:       if block_given?
383:         for sibling in parent.children
384:           yield sibling if sibling != self
385:         end
386:       else
387:         siblings = []
388:         parent.children {|sibling| siblings << sibling if sibling != self}
389:         siblings
390:       end
391:     end

size ()

Returns the total number of nodes in this tree, rooted at the receiver node. 

     # File lib/tree.rb, line 313
313:     def size
314:       @children.inject(1) {|sum, node| sum + node.size}
315:     end

to_s ()

Print the string representation of this node. 

     # File lib/tree.rb, line 134
134:     def to_s
135:       "Node Name: #{@name}" +
136:         " Content: " + (@content || "<Empty>") +
137:         " Parent: " + (isRoot?()  ? "<None>" : @parent.name) +
138:         " Children: #{@children.length}" +
139:         " Total Nodes: #{size()}"
140:     end

Protected Instance methods

createDumpRep ()

Creates a dump representation and returns the same as a hash. 

     # File lib/tree.rb, line 433
433:     def createDumpRep
434:       { :name => @name, :parent => (isRoot? ? nil : @parent.name),  :content => Marshal.dump(@content)}
435:     end

parent= (parent)

Protected method to set the parent node. This method should NOT be invoked by client code. 

     # File lib/tree.rb, line 159
159:     def parent=(parent)
160:       @parent = parent
161:     end

setAsRoot! ()

Protected method which sets this node as a root node. 

     # File lib/tree.rb, line 218
218:     def setAsRoot!
219:       @parent = nil
220:     end