Class: PEROBS::BigTreeNode

Inherits:
Object show all
Defined in:
lib/perobs/BigTreeNode.rb

Overview

The BigTreeNode class provides the BTree nodes for the BigTree objects. A node can either be a branch node or a leaf node. Branch nodes don’t store values, only references to child nodes. Leaf nodes don’t have child nodes but store the actual values. All nodes store a list of keys that are used to naviate the tree and find the values. A key is either directly associated with a value or determines the lower key boundary for the following child node.

Constant Summary

Constants inherited from ObjectBase

ObjectBase::NATIVE_CLASSES

Instance Attribute Summary

Attributes inherited from Object

#attributes

Attributes inherited from ObjectBase

#_id, #myself, #store

Instance Method Summary collapse

Methods inherited from Object

#_delete_reference_to_id, #_deserialize, #_referenced_object_ids, #attr_init, attr_persist, #init_attr, #inspect, #mark_as_modified

Methods inherited from ObjectBase

#==, #_check_assignment_value, _finalize, #_initialize, #_restore, #_stash, #_sync, #_transfer, read, #restore

Constructor Details

#initialize(p, tree, is_leaf, parent = nil, prev_sibling = nil, next_sibling = nil) ⇒ BigTreeNode

Internal constructor. Use Store.new(BigTreeNode, …) instead.

Parameters:

  • p (Handle)
  • tree (BigTree) —

    The tree this node should belong to

  • is_leaf (Boolean) —

    True if a leaf node should be created, false for a branch node.

  • parent (BigTreeNode) (defaults to: nil) —

    Parent node

  • prev_sibling (BigTreeNode) (defaults to: nil) —

    Previous sibling

  • next_sibling (BigTreeNode) (defaults to: nil) —

    Next sibling



53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/perobs/BigTreeNode.rb', line 53

def initialize(p, tree, is_leaf, parent = nil, prev_sibling = nil,
               next_sibling = nil)
  super(p)
  self.tree = tree
  self.parent = parent
  self.keys = @store.new(PEROBS::Array)

  if is_leaf
    # Create a new leaf node. It stores values and has no children.
    self.values = @store.new(PEROBS::Array)
    self.children = nil
  else
    # Create a new tree node. It doesn't store values and can have child
    # nodes.
    self.children = @store.new(PEROBS::Array)
    self.values = nil
  end
  # Link the neighboring siblings to the newly inserted node. If the node
  # is a leaf node and has no sibling on a side we also must register it
  # as first or last leaf with the BigTree object.
  if (self.prev_sibling = prev_sibling)
    @prev_sibling.next_sibling = myself
  elsif is_leaf?
    @tree.first_leaf = myself
  end
  if (self.next_sibling = next_sibling)
    @next_sibling.prev_sibling = myself
  elsif is_leaf?
    @tree.last_leaf = myself
  end
end

Instance Method Details

#check {|key, value| ... } ⇒ Boolean

Check consistency of the node and all subsequent nodes. In case an error is found, a message is logged and false is returned.

Yields:

  • (key, value)

Returns:

  • (Boolean) —

    true if tree has no errors



251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
 
# File 'lib/perobs/BigTreeNode.rb', line 251

def check
  branch_depth = nil

  traverse do |node, position, stack|
    if position == 0
      if node.parent
        # After a split the nodes will only have half the maximum keys.
        # For branch nodes one of the split nodes will have even 1 key
        # less as this will become the branch key in a parent node.
        if node.keys.size < min_keys - (node.is_leaf? ? 0 : 1)
          node.error "BigTree node #{node._id} has too few keys"
          return false
        end
      end

      if node.keys.size > @tree.node_size
        node.error "BigTree node must not have more then " +
          "#{@tree.node_size} keys, but has #{node.keys.size} keys"
        return false
      end

      last_key = nil
      node.keys.each do |key|
        if last_key && key < last_key
          node.error "Keys are not increasing monotoneously: " +
            "#{node.keys.inspect}"
          return false
        end
        last_key = key
      end

      if node.is_leaf?
        if branch_depth
          unless branch_depth == stack.size
            node.error "All leaf nodes must have same distance from root"
            return false
          end
        else
          branch_depth = stack.size
        end
        if node.prev_sibling.nil?
          if @tree.first_leaf != node
            node.error "Leaf node #{node._id} has no previous sibling " +
              "but is not the first leaf of the tree"
            return false
          end
        elsif node.prev_sibling.next_sibling != node
          node.error "next_sibling of previous sibling does not point to " +
            "this node"
          return false
        end
        if node.next_sibling.nil?
          if @tree.last_leaf != node
            node.error "Leaf node #{node._id} has no next sibling " +
              "but is not the last leaf of the tree"
            return false
          end
        elsif node.next_sibling.prev_sibling != node
          node.error "previous_sibling of next sibling does not point to " +
            "this node"
          return false
        end
        unless node.keys.size == node.values.size
          node.error "Key count (#{node.keys.size}) and value " +
            "count (#{node.values.size}) don't match"
            return false
        end
        if node.children
          node.error "children must be nil for a leaf node"
          return false
        end
      else
        if node.values
          node.error "values must be nil for a branch node"
          return false
        end
        unless node.children.size == node.keys.size + 1
          node.error "Key count (#{node.keys.size}) must be one " +
            "less than children count (#{node.children.size})"
            return false
        end
        node.children.each_with_index do |child, i|
          unless child.is_a?(BigTreeNode)
            node.error "Child #{i} is of class #{child.class} " +
              "instead of BigTreeNode"
            return false
          end
          unless child.parent.is_a?(BigTreeNode)
            node.error "Parent reference of child #{i} is of class " +
              "#{child.class} instead of BigTreeNode"
            return false
          end
          if child == node
            node.error "Child #{i} point to self"
            return false
          end
          if stack.include?(child)
            node.error "Child #{i} points to ancester node"
            return false
          end
          unless child.parent == node
            node.error "Child #{i} does not have parent pointing " +
              "to this node"
            return false
          end
          if i > 0
            unless node.children[i - 1].next_sibling == child
              node.error "next_sibling of node " +
                "#{node.children[i - 1]._id} " +
                "must point to node #{child._id}"
              return false
            end
          end
          if i < node.children.length - 1
            unless child == node.children[i + 1].prev_sibling
              node.error "prev_sibling of node " +
                "#{node.children[i + 1]._id} " +
                "must point to node #{child._id}"
              return false
            end
          end
        end
      end
    elsif position <= node.keys.size
      # These checks are done after we have completed the respective child
      # node with index 'position - 1'.
      index = position - 1
      if node.is_leaf?
        if block_given?
          # If a block was given, call this block with the key and value.
          return false unless yield(node.keys[index], node.values[index])
        end
      else
        unless node.children[index].keys.last < node.keys[index]
          node.error "Child #{node.children[index]._id} " +
            "has too large key #{node.children[index].keys.last}. " +
            "Must be smaller than #{node.keys[index]}."
          return false
        end
        unless node.children[position].keys.first >= node.keys[index]
          node.error "Child #{node.children[position]._id} " +
            "has too small key #{node.children[position].keys.first}. " +
            "Must be larger than or equal to #{node.keys[index]}."
          return false
        end
      end
    end
  end

  true
end

#each {|key, value| ... } ⇒ Object

Iterate over all the key/value pairs in this node and all sub-nodes.

Yields:

  • (key, value) 


219
220
221
222
223
224
225
 
# File 'lib/perobs/BigTreeNode.rb', line 219

def each
  traverse do |node, position, stack|
    if node.is_leaf? && position < node.keys.size
      yield(node.keys[position], node.values[position])
    end
  end
end

#each_element {|key, value| ... } ⇒ Object

Iterate over all the key/value pairs of the node.

Yields:

  • (key, value) 


229
230
231
232
233
234
235
 
# File 'lib/perobs/BigTreeNode.rb', line 229

def each_element
  return unless is_leaf?

  0.upto(@keys.length - 1) do |i|
    yield(@keys[i], @values[i])
  end
end

#error(msg) ⇒ Object

Print and log an error message for the node.



778
779
780
781
782
 
# File 'lib/perobs/BigTreeNode.rb', line 778

def error(msg)
  msg = "Error in BigTree node @#{@_id}: #{msg}\n" + @tree.to_s
  $stderr.puts msg
  PEROBS.log.error msg
end

#get(key) ⇒ Integer or nil

Return the value that matches the given key or return nil if they key is unknown.

Parameters:

  • key (Integer) —

    key to search for

Returns:

  • (Integer or nil) —

    value that matches the key



120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
# File 'lib/perobs/BigTreeNode.rb', line 120

def get(key)
  node = self

  while node do
    # Find index of the entry that best fits the key.
    i = node.search_key_index(key)
    if node.is_leaf?
      # This is a leaf node. Check if there is an exact match for the
      # given key and return the corresponding value or nil.
      return node.keys[i] == key ? node.values[i] : nil
    end

    # Descend into the right child node to continue the search.
    node = node.children[i]
  end

  PEROBS.log.fatal "Could not find proper node to get from while " +
    "looking for key #{key}"
end

#has_key?(key) ⇒ Boolean

Return if given key is stored in the node.

Parameters:

  • key (Integer) —

    key to search for

Returns:

  • (Boolean) —

    True if key was found, false otherwise



169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
 
# File 'lib/perobs/BigTreeNode.rb', line 169

def has_key?(key)
  node = self

  while node do
    # Find index of the entry that best fits the key.
    i = node.search_key_index(key)
    if node.is_leaf?
      # This is a leaf node. Check if there is an exact match for the
      # given key and return the corresponding value or nil.
      return node.keys[i] == key
    end

    # Descend into the right child node to continue the search.
    node = node.children[i]
  end

  PEROBS.log.fatal "Could not find proper node to get from while " +
    "looking for key #{key}"
end

#insert(key, value) ⇒ Object

Insert or replace the given value by using the key as unique address.

Parameters:

  • key (Integer) —

    Unique key to retrieve the value

  • value (Integer) —

    value to insert



93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
# File 'lib/perobs/BigTreeNode.rb', line 93

def insert(key, value)
  node = myself

  # Traverse the tree to find the right node to add or replace the value.
  while node do
    # All nodes that we find on the way that are full will be split into
    # two half-full nodes.
    if node.keys.size >= @tree.node_size
      node = node.split_node
    end

    # Once we have reached a leaf node we can insert or replace the value.
    if node.is_leaf?
      return node.insert_element(key, value)
    else
      # Descend into the right child node to add the value to.
      node = node.children[node.search_key_index(key)]
    end
  end

  PEROBS.log.fatal "Could not find proper node to insert into"
end

#insert_element(key, child_or_value) ⇒ Boolean

Insert the given value or child into the current node using the key as index.

Parameters:

  • key (Integer) —

    key to address the value or child

  • child_or_value (Integer or BigTreeNode) —

    value or BigTreeNode

Returns:

  • (Boolean) —

    true if new element, false if override existing element



489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
 
# File 'lib/perobs/BigTreeNode.rb', line 489

def insert_element(key, child_or_value)
  if @keys.size >= @tree.node_size
    PEROBS.log.fatal "Cannot insert into a full BigTreeNode: #{@keys.size}"
  end

  i = search_key_index(key)
  if @keys[i] == key
    # Overwrite existing entries
    @keys[i] = key
    if is_leaf?
      @values[i] = child_or_value
    else
      @children[i + 1] = child_or_value
    end
  else
    # Create a new entry
    @keys.insert(i, key)
    if is_leaf?
      @values.insert(i, child_or_value)
      @tree.entry_counter += 1
    else
      @children.insert(i + 1, child_or_value)
    end
  end
end

#is_leaf? ⇒ Boolean

Returns True if this is a leaf node, false otherwise.

Returns:

  • (Boolean) —

    True if this is a leaf node, false otherwise.



86
87
88
 
# File 'lib/perobs/BigTreeNode.rb', line 86

def is_leaf?
  @children.nil?
end

#merge_with_branch_node(node) ⇒ Object 



604
605
606
607
608
609
610
611
612
613
614
615
616
 
# File 'lib/perobs/BigTreeNode.rb', line 604

def merge_with_branch_node(node)
  if @keys.length + 1 + node.keys.length > @tree.node_size
    PEROBS.log.fatal "Branch nodes are too big to merge"
  end

  index = @parent.search_node_index(node) - 1
  self.keys << @parent.keys[index]
  self.keys += node.keys
  node.children.each { |c| c.parent = myself }
  self.children += node.children

  node.parent.remove_child(node)
end

#merge_with_leaf_node(node) ⇒ Object 



593
594
595
596
597
598
599
600
601
602
 
# File 'lib/perobs/BigTreeNode.rb', line 593

def merge_with_leaf_node(node)
  if @keys.length + node.keys.length > @tree.node_size
    PEROBS.log.fatal "Leaf nodes are too big to merge"
  end

  self.keys += node.keys
  self.values += node.values

  node.parent.remove_child(node)
end

#node_chain(key) ⇒ Array of BigTreeNode

Return the node chain from the root to the leaf node storing the key/value pair.

Parameters:

  • key (Integer) —

    key to search for

Returns:



144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
 
# File 'lib/perobs/BigTreeNode.rb', line 144

def node_chain(key)
  node = myself
  list = [ node ]

  while node do
    # Find index of the entry that best fits the key.
    i = node.search_key_index(key)
    if node.is_leaf?
      # This is a leaf node. Check if there is an exact match for the
      # given key and return the corresponding value or nil.
      return node.keys[i] == key ? list : []
    end

    # Add current node to chain.
    list << node
    # Descend into the right child node to continue the search.
    node = node.children[i]
  end

  PEROBS.log.fatal "Could not find node chain for key #{key}"
end

#remove(key) ⇒ Object

Return the value that matches the given key and remove the value from the tree. Return nil if the key is unknown.

Parameters:

  • key (Integer) —

    key to search for

Returns:

  • (Object) —

    value that matches the key



193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
 
# File 'lib/perobs/BigTreeNode.rb', line 193

def remove(key)
  node = self

  while node do
    # Find index of the entry that best fits the key.
    i = node.search_key_index(key)
    if node.is_leaf?
      # This is a leaf node. Check if there is an exact match for the
      # given key and return the corresponding value or nil.
      if node.keys[i] == key
        @tree.entry_counter -= 1
        return node.remove_element(i)
      else
        return nil
      end
    end

    # Descend into the right child node to continue the search.
    node = node.children[i]
  end

  PEROBS.log.fatal 'Could not find proper node to remove from'
end

#remove_child(node) ⇒ Object

Remove the specified node from this branch node.

Parameters:



547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
 
# File 'lib/perobs/BigTreeNode.rb', line 547

def remove_child(node)
  unless (index = search_node_index(node))
    PEROBS.log.fatal "Cannot remove child #{node._id} from node #{@_id}"
  end

  if index == 0
    # Removing the first child is a bit more complicated as the
    # corresponding branch key is in a parent node.
    key = @keys.shift
    update_branch_key(key)
  else
    # For all other children we can just remove the corresponding key.
    @keys.delete_at(index - 1)
  end

  # Remove the child node link.
  child = @children.delete_at(index)
  # If we remove the first or last leaf node we must update the reference
  # in the BigTree object.
  @tree.first_leaf = child.next_sibling if child == @tree.first_leaf
  @tree.last_leaf = child.prev_sibling if child == @tree.last_leaf
  # Unlink the neighbouring siblings from the child
  child.prev_sibling.next_sibling = child.next_sibling if child.prev_sibling
  child.next_sibling.prev_sibling = child.prev_sibling if child.next_sibling

  if @keys.length < min_keys
    # The node has become too small. Try borrowing a node from an adjecent
    # sibling or merge with an adjecent node.
    if @prev_sibling && @prev_sibling.parent == @parent
      borrow_from_previous_sibling(@prev_sibling) ||
        @prev_sibling.merge_with_branch_node(myself)
    elsif @next_sibling && @next_sibling.parent == @parent
      borrow_from_next_sibling(@next_sibling) ||
        merge_with_branch_node(@next_sibling)
    end
  end

  if @parent.nil? && @children.length <= 1
    # If the node just below the root only has one child it will become
    # the new root node.
    new_root = @children.first
    new_root.parent = nil
    @tree.root = new_root
  end
end

#remove_element(index) ⇒ Object

Remove the element from a leaf node at the given index.

Parameters:

  • index (Integer) —

    The index of the entry to be removed

Returns:

  • (Object) —

    The removed value



518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
 
# File 'lib/perobs/BigTreeNode.rb', line 518

def remove_element(index)
  # Delete the key at the specified index.
  unless (key = @keys.delete_at(index))
    PEROBS.log.fatal "Could not remove element #{index} from BigTreeNode " +
      "@#{@_id}"
  end
  update_branch_key(key) if index == 0

  # Delete the corresponding value.
  removed_value = @values.delete_at(index)
  if @keys.length < min_keys
    if @prev_sibling && @prev_sibling.parent == @parent
      borrow_from_previous_sibling(@prev_sibling) ||
        @prev_sibling.merge_with_leaf_node(myself)
    elsif @next_sibling && @next_sibling.parent == @parent
      borrow_from_next_sibling(@next_sibling) ||
        merge_with_leaf_node(@next_sibling)
    elsif @parent
      PEROBS.log.fatal "Cannot not find adjecent leaf siblings"
    end
  end

  # The merge has potentially invalidated this node. After this method has
  # been called this copy of the node should no longer be used.
  removed_value
end

#reverse_each_element {|key, value| ... } ⇒ Object

Iterate over all the key/value pairs of the node in reverse order.

Yields:

  • (key, value) 


239
240
241
242
243
244
245
 
# File 'lib/perobs/BigTreeNode.rb', line 239

def reverse_each_element
  return unless is_leaf?

  (@keys.length - 1).downto(0) do |i|
    yield(@keys[i], @values[i])
  end
end

#search_key_index(key) ⇒ Integer

Search the keys of the node that fits the given key. The result is either the index of an exact match or the index of the position where the given key would have to be inserted.

Parameters:

  • key (Integer) —

    key to search for

Returns:

  • (Integer) —

    Index of the matching key or the insert position.



623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
 
# File 'lib/perobs/BigTreeNode.rb', line 623

def search_key_index(key)
  # Handle special case for empty keys list.
  return 0 if @keys.empty?

  # Keys are unique and always sorted. Use a binary search to find the
  # index that fits the given key.
  li = pi = 0
  ui = @keys.size - 1
  while li <= ui
    # The pivot element is always in the middle between the lower and upper
    # index.
    pi = li + (ui - li) / 2

    if key < @keys[pi]
      # The pivot element is smaller than the key. Set the upper index to
      # the pivot index.
      ui = pi - 1
    elsif key > @keys[pi]
      # The pivot element is larger than the key. Set the lower index to
      # the pivot index.
      li = pi + 1
    else
      # We've found an exact match. For leaf nodes return the found index.
      # For branch nodes we have to add one to the index since the larger
      # child is the right one.
      return is_leaf? ? pi : pi + 1
    end
  end
  # No exact match was found. For the insert operaton we need to return
  # the index of the first key that is larger than the given key.
  @keys[pi] < key ? pi + 1 : pi
end

#search_node_index(node) ⇒ Object 



656
657
658
659
660
661
662
663
 
# File 'lib/perobs/BigTreeNode.rb', line 656

def search_node_index(node)
  index = search_key_index(node.keys.first)
  unless @children[index] == node
    raise RuntimeError, "Child at index #{index} is not the requested node"
  end

  index
end

#split_node ⇒ BigTreeNode

Split the current node into two nodes. The upper half of the elements will be moved into a newly created node. This node will retain the lower half.

Returns:



442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
 
# File 'lib/perobs/BigTreeNode.rb', line 442

def split_node
  unless @parent
    # The node is the root node. We need to create a parent node first.
    self.parent = @store.new(BigTreeNode, @tree, false)
    @parent.children[0] = myself
    @tree.root = @parent
  end

  # Create the new sibling that will take the 2nd half of the
  # node content.
  sibling = @store.new(BigTreeNode, @tree, is_leaf?, @parent, myself,
                       @next_sibling)
  # Determine the index of the middle element that gets moved to the
  # parent. The node size must be an uneven number.
  mid = @keys.size / 2
  # Insert the middle element key into the parent node
  @parent.insert_element(@keys[mid], sibling)
  if is_leaf?
    # Copy the keys and values from the mid element onwards into the new
    # sibling node.
    sibling.keys += @keys[mid..-1]
    sibling.values += @values[mid..-1]
    # Delete the copied keys and values from this node.
    @values.slice!(mid..-1)
  else
    # Copy the keys from after the mid value onwards to the new sibling
    # node.
    sibling.keys += @keys[mid + 1..-1]
    # Same for the children.
    sibling.children += @children[mid + 1..-1]
    # Reparent the children to the new sibling parent.
    sibling.children.each { |c| c.parent = sibling }
    # And delete the copied children references.
    @children.slice!(mid + 1..-1)
  end
  # Delete the copied keys from this node.
  @keys.slice!(mid..-1)

  @parent
end

#statistics(stats) ⇒ Object

Gather some statistics about the node and all sub nodes.

Parameters:

  • stats (Stats) —

    Data structure that stores the gathered data



702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
 
# File 'lib/perobs/BigTreeNode.rb', line 702

def statistics(stats)
  traverse do |node, position, stack|
    if position == 0
      if node.is_leaf?
        stats.leaf_nodes += 1
        depth = stack.size + 1
        if stats.min_depth.nil? || stats.min_depth < depth
          stats.min_depth = depth
        end
        if stats.max_depth.nil? || stats.max_depth > depth
          stats.max_depth = depth
        end
      else
        stats.branch_nodes += 1
      end
    end
  end
end

#to_s ⇒ String

Returns Human reable form of the sub-tree.

Returns:

  • (String) —

    Human reable form of the sub-tree.



404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
 
# File 'lib/perobs/BigTreeNode.rb', line 404

def to_s
  str = ''

  traverse do |node, position, stack|
    if position == 0
      begin
        str += "#{node.parent ? node.parent.tree_prefix + '  +' : 'o'}" +
          "#{node.tree_branch_mark}-" +
          "#{node.keys.first.nil? ? '--' : 'v-'}#{node.tree_summary}\n"
      rescue => e
        str += "@@@@@@@@@@: #{e.message}\n"
      end
    else
      begin
        if node.is_leaf?
          if node.keys[position - 1]
            str += "#{node.tree_prefix}  |" +
              "[#{node.keys[position - 1]}, " +
              "#{node.values[position - 1]}]\n"
          end
        else
          if node.keys[position - 1]
            str += "#{node.tree_prefix}  #{node.keys[position - 1]}\n"
          end
        end
      rescue => e
        str += "@@@@@@@@@@: #{e.message}\n"
      end
    end
  end

  str
end

#traverse {|node, position, stack| ... } ⇒ Object

This is a generic tree iterator. It yields before it descends into the child node and after (which is identical to before the next child descend). It yields the node, the position and the stack of parent nodes.

Yields:

  • (node, position, stack) 


670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
 
# File 'lib/perobs/BigTreeNode.rb', line 670

def traverse
  # We use a non-recursive implementation to traverse the tree. This stack
  # keeps track of all the known still to be checked nodes.
  stack = [ [ self, 0 ] ]

  while !stack.empty?
    node, position = stack.pop

    # Call the payload method. The position marks where we are in the node
    # with respect to the traversal. 0 means we've just entered the node
    # for the first time and are about to descent to the first child.
    # Position 1 is after the 1st child has been processed and before the
    # 2nd child is being processed. If we have N children, the last
    # position is N after we have processed the last child and are about
    # to return to the parent node.
    yield(node, position, stack)

    if position <= node.keys.size
      # Push the next position for this node onto the stack.
      stack.push([ node, position + 1 ])

      if !node.is_leaf? && node.children[position]
        # If we have a child node for this position, push the linked node
        # and the starting position onto the stack.
        stack.push([ node.children[position], 0 ])
      end
    end
  end
end

#tree_branch_mark ⇒ Object

Branch node decoration for the inspection method.



744
745
746
747
 
# File 'lib/perobs/BigTreeNode.rb', line 744

def tree_branch_mark
  return '' unless @parent
  '-'
end

#tree_prefix ⇒ Object

Return the decoration that marks the tree structure of this node for the inspection method.



723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
 
# File 'lib/perobs/BigTreeNode.rb', line 723

def tree_prefix
  node = self
  str = ''

  while node
    is_last_child = false
    if node.parent
      is_last_child = node.parent.children.last == node
    else
      # Don't add lines for the top-level.
      break
    end

    str = (is_last_child ? '   ' : '  |') + str
    node = node.parent
  end

  str
end

#tree_summary ⇒ Object

Text for the node line for the inspection method.



750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
 
# File 'lib/perobs/BigTreeNode.rb', line 750

def tree_summary
  s = " @#{@_id}"
  if @parent
    begin
      s += " ^#{@parent._id}"
    rescue
      s += ' ^@'
    end
  end
  if @prev_sibling
    begin
      s += " <#{@prev_sibling._id}"
    rescue
      s += ' <@'
    end
  end
  if @next_sibling
    begin
      s += " >#{@next_sibling._id}"
    rescue
      s += ' >@'
    end
  end

  s
end