Class: Tree::TreeNode

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

Overview

The Tree node class implementation. Mixes in the Enumerable module.

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

grandChild1 = myTreeRoot[“GRANDCHILD1”]

siblingsOfChild1Array = child1.siblings

immediateChildrenArray = myTreeRoot.children

# Process all nodes

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

myTreeRoot.remove!(child1) # Remove the child

Constant Summary collapse

@@fieldSep = 
'|'
@@recordSep = 
"\n"

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(name, content = nil) ⇒ TreeNode

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.



105
106
107
108
109
110
111
112
113
114
115
116
 
# File 'lib/tree.rb', line 105

def initialize(name, content = nil)

        raise "Node name HAS to be provided" if name == nil

        @name = name
        @content = content

        self.setAsRoot!

        @childrenHash = Hash.new
        @children = []
end

Instance Attribute Details

#content ⇒ Object

Returns the value of attribute content.



93
94
95
 
# File 'lib/tree.rb', line 93

def content
  @content
end

#name ⇒ Object (readonly)

Returns the value of attribute name.



93
94
95
 
# File 'lib/tree.rb', line 93

def name
  @name
end

#parent ⇒ Object

Returns the value of attribute parent.



93
94
95
 
# File 'lib/tree.rb', line 93

def parent
  @parent
end

Class Method Details

._load(str) ⇒ Object

Loads a dump representation of the tree from the specified string.



322
323
324
 
# File 'lib/tree.rb', line 322

def TreeNode._load(str)
    loadDumpRep(str)
end

Instance Method Details

#<<(child) ⇒ Object

Convenience synonym for Tree#add method. This method allows a convenient method to add children hierarchies in the tree. E.g. root << child << grand_child



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

def <<(child)
    add(child)
end

#<=>(other) ⇒ Object

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



280
281
282
283
 
# File 'lib/tree.rb', line 280

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

#[](key) ⇒ Object

Returns the requested node from the set of immediate children.

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



227
228
229
230
231
232
233
234
235
 
# File 'lib/tree.rb', line 227

def [](key)
    raise "Key needs to be provided" if key == nil

    if key.kind_of?(Integer)
        @children[key]
    else
        @childrenHash[key]
    end
end

#_dump(depth) ⇒ Object 



297
298
299
300
301
 
# File 'lib/tree.rb', line 297

def _dump(depth)
    strRep = String.new
    each {|node| strRep << node.createDumpRep}
    strRep
end

#add(child) ⇒ Object

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.



145
146
147
148
149
150
151
152
153
 
# File 'lib/tree.rb', line 145

def add(child)
    raise "Child already added" if @childrenHash.has_key?(child.name)

    @childrenHash[child.name]  = child
    @children << child
    child.parent = self
    return child

end

#children ⇒ Object

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



205
206
207
208
209
210
211
 
# File 'lib/tree.rb', line 205

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

#createDumpRep ⇒ Object

Creates a dump representation and returns the same as a string



291
292
293
294
295
 
# File 'lib/tree.rb', line 291

def createDumpRep
    strRep = String.new
    strRep << @name << @@fieldSep << (isRoot? ? @name : @parent.name)
    strRep << @@fieldSep << Marshal.dump(@content) << @@recordSep
end

#each {|_self| ... } ⇒ Object

Returns every node (including the receiver node) from the tree to the specified block.

Yields:

  • (_self)

Yield Parameters:



215
216
217
218
 
# File 'lib/tree.rb', line 215

def each &block
    yield self
    children { |child| child.each(&block) }
end

#freezeTree! ⇒ Object

Freezes all nodes in the tree



286
287
288
 
# File 'lib/tree.rb', line 286

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

#hasChildren? ⇒ Boolean

Indicates whether this node has any immediate child nodes.

Returns:

  • (Boolean) 


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

def hasChildren?
    @children.length != 0
end

#hasContent? ⇒ Boolean

Indicates whether this node has any associated content.

Returns:

  • (Boolean) 


183
184
185
 
# File 'lib/tree.rb', line 183

def hasContent?
    @content != nil
end

#isRoot? ⇒ Boolean

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

Returns:

  • (Boolean) 


194
195
196
 
# File 'lib/tree.rb', line 194

def isRoot?
    @parent == nil
end

#length ⇒ Object

Convenience synonym for Tree#size



244
245
246
 
# File 'lib/tree.rb', line 244

def length
    size()
end

#printTree(tab = 0) ⇒ Object

Pretty prints the tree starting with the receiver node.



249
250
251
252
 
# File 'lib/tree.rb', line 249

def printTree(tab = 0)
    puts((' ' * tab) + self.to_s)
    children {|child| child.printTree(tab + 4)}
end

#remove!(child) ⇒ Object

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.



159
160
161
162
163
164
 
# File 'lib/tree.rb', line 159

def remove!(child)
    @childrenHash.delete(child.name)
    @children.delete(child)
    child.setAsRoot! unless child == nil
    return child
end

#removeAll! ⇒ Object

Removes all children from the receiver node.



173
174
175
176
177
178
179
180
 
# File 'lib/tree.rb', line 173

def removeAll!
    for child in @children
        child.setAsRoot!
    end
    @childrenHash.clear
    @children.clear
    self
end

#removeFromParent! ⇒ Object

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



168
169
170
 
# File 'lib/tree.rb', line 168

def removeFromParent!
    @parent.remove!(self) unless isRoot?
end

#root ⇒ Object

Returns the root for this tree.



255
256
257
258
259
 
# File 'lib/tree.rb', line 255

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

#siblings ⇒ Object

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.



264
265
266
267
268
269
270
271
272
273
274
275
 
# File 'lib/tree.rb', line 264

def siblings
    return nil if isRoot?
    if block_given?
        for sibling in parent.children
                      yield sibling if sibling != self
        end
    else
        siblings = []
        parent.children {|sibling| siblings << sibling if sibling != self}
        siblings
    end
end

#size ⇒ Object

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



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

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

#to_s ⇒ Object

Print the string representation of this node.



119
120
121
122
123
124
125
 
# File 'lib/tree.rb', line 119

def to_s
        s = size()
        "Node ID: #{@name} Content: #{@content} Parent: " +
                (isRoot?()  ? "ROOT" : "#{@parent.name}") +
                " Children: #{@children.length}" +
                " Total Nodes: #{s}"
end