Class: PEROBS::BigArrayNode

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

Overview

The BigArrayNode class provides the BTree nodes for the BigArray objects. A node can either be a branch node or a leaf node. Branch nodes don’t store values, only offsets and references to child nodes. Leaf nodes don’t have child nodes but store the actual values. The leaf nodes always contain at least node_size / 2 number of consecutive values. The index of the first value in the BigArray is the sum of the offsets stored in the parent nodes. Branch nodes store the offsets and the corresponding child node references. The first offset is always 0. Consecutive offsets are set to the previous offset plus the total number of values stored in the previous child node. The leaf nodes don’t contain wholes. A concatenation of all leaf node values represents the stored Array.

Root Node -------------------------------- Offsets | 0 11 | Children | |

v                            v

Level 1 --------------------------+————————–+ Offsets | 0 4 7 || 0 2 5 | Children | | | | | |

v         v         v         v          v         v

Leaves ---------+——-----------——-----------——-+ Values | A B C D || E F G || H I J K || L M || N O P || Q R |

Index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

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

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

Parameters:

  • p (Handle)
  • tree (BigArray) —

    The tree this node should belong to

  • is_leaf (Boolean) —

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

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

    Parent node

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

    Previous sibling

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

    Next sibling



72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
 
# File 'lib/perobs/BigArrayNode.rb', line 72

def initialize(p, tree, is_leaf, parent = nil,
               prev_sibling = nil, next_sibling = nil)
  super(p)
  self.tree = tree
  self.parent = parent

  if is_leaf
    # Create a new leaf node. It stores values and has no children.
    self.values = @store.new(PEROBS::Array)
    self.children = self.offsets = nil

    # Link the neighboring siblings to the newly inserted node.  If the
    # node has no sibling on a side we also must register it as first or
    # last leaf with the BigArray object.
    if (self.prev_sibling = prev_sibling)
      @prev_sibling.next_sibling = myself
    else
      @tree.first_leaf = myself
    end
    if (self.next_sibling = next_sibling)
      @next_sibling.prev_sibling = myself
    else
      @tree.last_leaf = myself
    end
  else
    # Create a new branch node. It stores keys and child node references
    # but no values.
    self.offsets = @store.new(PEROBS::Array)
    self.children = @store.new(PEROBS::Array)
    self.values = nil
    # Branch nodes don't need sibling links.
    self.prev_sibling = self.next_sibling = nil
  end
end

Instance Method Details

#adjust_offsets(after_child, delta) ⇒ Object

This method takes care of adjusting the offsets in tree in case elements were inserted or removed. All nodes that hold children after the insert/remove operation need to be adjusted. Since child nodes get their offsets via their parents, only the parent node and the direct ancestor followers need to be adjusted.

Parameters:

  • after_child (BigArrayNode) —

    specifies the modified leaf node

  • delta (Integer) —

    specifies how many elements were inserted or removed.



668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
 
# File 'lib/perobs/BigArrayNode.rb', line 668

def adjust_offsets(after_child, delta)
  node = self

  while node
    adjust = false
    0.upto(node.children.size - 1) do |i|
      # Iterate over the children until we have found the after_child
      # node. Then turn on adjustment mode. The offsets of the following
      # entries will be adjusted by delta.
      if adjust
        node.offsets[i] += delta
      elsif node.children[i] == after_child
        adjust = true
      end
    end

    unless adjust
      node.fatal "Could not find child #{after_child._id}"
    end

    after_child = node
    node = node.parent
  end
end

#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



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
 
# File 'lib/perobs/BigArrayNode.rb', line 284

def check
  branch_depth = nil

  traverse do |node, position, stack|
    if position == 0
      # Nodes should have between min_size() and
      # @tree.node_size children or values. Only the root node may have
      # less.
      if node.size > @tree.node_size
        node.error "BigArray node #{node._id} is too large. It has " +
          "#{node.size} nodes instead of max. #{@tree.node_size}."
        return false
      end
      if node.parent && node.size < min_size
        node.error "BigArray node #{node._id} is too small"
        return false
      end

      if node.is_leaf?
        # All leaf nodes must have same distance from root node.
        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

        return false unless node.check_leaf_node_links

        if node.children
          node.error "children must be nil for a leaf node"
          return false
        end
      else
        unless node.children.size == node.offsets.size
          node.error "Offset count (#{node.offsets.size}) must be equal " +
            "to children count (#{node.children.size})"
            return false
        end

        if node.values
          node.error "values must be nil for a branch node"
          return false
        end

        unless @prev_sibling.nil? && @next_sibling.nil?
          node.error "prev_sibling and next_sibling must be nil for " +
            "branch nodes"
        end

        return false unless node.check_offsets

        return false unless node.check_child_nodes(stack)
      end
    elsif position <= node.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.first_index + index,
                                    node.values[index])
        end
      end
    end
  end

  true
end

#check_child_nodes(stack) ⇒ Object 



415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
 
# File 'lib/perobs/BigArrayNode.rb', line 415

def check_child_nodes(stack)
  if @children.uniq.size != @children.size
    error "Node #{@_id} has multiple identical children"
    return false
  end

  @children.each_with_index do |child, i|
    unless child.is_a?(BigArrayNode)
      error "Child #{@_id} is of class #{child.class} " +
        "instead of BigArrayNode"
      return false
    end

    unless child.parent.is_a?(BigArrayNode)
      error "Parent reference of child #{i} is of class " +
        "#{child.class} instead of BigArrayNode"
      return false
    end

    if child.parent != self
      error "Child node #{child._id} has wrong parent " +
        "#{child.parent._id}. It should be #{@_id}."
      return false
    end

    if child == self
      error "Child #{i} point to self"
      return false
    end

    if stack.include?(child)
      error "Child #{i} points to ancester node"
      return false
    end

    unless child.parent == self
      error "Child #{i} does not have parent pointing " +
        "to this node"
      return false
    end
  end

  true
end

#check_leaf_node_links ⇒ Object 



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
 
# File 'lib/perobs/BigArrayNode.rb', line 357

def check_leaf_node_links
  if @prev_sibling.nil?
    if @tree.first_leaf != self
      error "Leaf node #{@_id} has no previous sibling " +
        "but is not the first leaf of the tree"
      return false
    end
  elsif @prev_sibling.next_sibling != self
    error "next_sibling of previous sibling does not point to " +
      "this node"
    return false
  end

  if @next_sibling.nil?
    if @tree.last_leaf != self
      error "Leaf node #{@_id} has no next sibling " +
        "but is not the last leaf of the tree"
      return false
    end
  elsif @next_sibling.prev_sibling != self
    error "previous_sibling of next sibling does not point to " +
      "this node"
    return false
  end

  true
end

#check_offsets ⇒ Object 



385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
 
# File 'lib/perobs/BigArrayNode.rb', line 385

def check_offsets
  return true if @parent.nil? && @offsets.empty?

  if @offsets[0] != 0
    error "First offset is not 0: #{@offsets.inspect}"
    return false
  end

  last_offset = nil
  @offsets.each_with_index do |offset, i|
    if i > 0
      if offset < last_offset
        error "Offsets are not strictly monotoneously " +
          "increasing: #{@offsets.inspect}"
        return false
      end
      expected_offset = last_offset + @children[i - 1].values_count
      if offset != expected_offset
        error "Offset #{i} must be #{expected_offset} " +
          "but is #{offset}."
        return false
      end
    end

    last_offset = offset
  end

  true
end

#consolidate_child_nodes(child) ⇒ Object 



585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
 
# File 'lib/perobs/BigArrayNode.rb', line 585

def consolidate_child_nodes(child)
  unless (child_index = @children.index(child))
    error "Cannot find child to consolidate"
  end

  if child_index == 0
    # Consolidate with successor if it exists.
    return unless (succ = @children[child_index + 1])

    if child.size + succ.size <= @tree.node_size
      # merge child with successor
      merge_child_with_next(child_index)
    else
      move_first_element_of_successor_to_child(child_index)
    end
  else
    # consolidate with predecessor
    pred = @children[child_index - 1]

    if pred.size + child.size <= @tree.node_size
      # merge child with predecessor
      merge_child_with_next(child_index - 1)
    else
      move_last_element_of_predecessor_to_child(child_index)
    end
  end
end

#delete_at(index) ⇒ Object

Delete the element at the specified index, returning that element, or nil if the index is out of range.

Parameters:

  • index (Integer) —

    Index in the BigArray

Returns:

  • (Object) —

    found value or nil



230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
 
# File 'lib/perobs/BigArrayNode.rb', line 230

def delete_at(index)
  node = self
  deleted_value = nil

  while node do
    if node.is_leaf?
      deleted_value = node.values.delete_at(index)
      if node.parent
        node.parent.adjust_offsets(node, -1)
        if node.size < min_size
          node.parent.consolidate_child_nodes(node)
        end
      end

      return deleted_value
    else
      # Descend into the right child node to add the value to.
      cidx = (node.offsets.bsearch_index { |o| o > index } ||
              node.offsets.length) - 1
      if (index -= node.offsets[cidx]) < 0
        node.fatal "Index (#{index}) became negative"
      end
      node = node.children[cidx]
    end
  end

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

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

Iterate over all the values of the node.

Yields:

  • (value) 


262
263
264
265
266
267
268
 
# File 'lib/perobs/BigArrayNode.rb', line 262

def each
  return nil unless is_leaf?

  @values.each do |v|
    yield(v)
  end
end

#error(msg) ⇒ Object

Print and log an error message for the node.



806
807
808
809
810
 
# File 'lib/perobs/BigArrayNode.rb', line 806

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

#fatal(msg) ⇒ Object

Print and log an error message for the node.



813
814
815
816
817
 
# File 'lib/perobs/BigArrayNode.rb', line 813

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

#first_index ⇒ Object 



630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
 
# File 'lib/perobs/BigArrayNode.rb', line 630

def first_index
  # TODO: This is a very expensive method. Find a way to make this way
  # faster.
  node = parent
  child = myself
  while node
    if (index = node.children.index(child)) && index > 0
      return node.offsets[index - 1]
    end
    child = node
    node = node.parent
  end

  0
end

#get(index) ⇒ Integer or nil

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

Parameters:

  • index (Integer) —

    Position to insert at

Returns:

  • (Integer or nil) —

    value that matches the key



203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
 
# File 'lib/perobs/BigArrayNode.rb', line 203

def get(index)
  node = self

  # Traverse the tree to find the right node to add or replace the value.
  while node do
    # Once we have reached a leaf node we can insert or replace the value.
    if node.is_leaf?
      return node.values[index]
    else
      # Descend into the right child node to add the value to.
      cidx = (node.offsets.bsearch_index { |o| o > index } ||
              node.offsets.length) - 1
      if (index -= node.offsets[cidx]) < 0
        node.fatal "Index (#{index}) became negative"
      end
      node = node.children[cidx]
    end
  end

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

#index_in_parent_node ⇒ Object

node. If the node is the root node, nil is returned.

Returns:

  • The index of the current node in the children list of the parent



624
625
626
627
628
 
# File 'lib/perobs/BigArrayNode.rb', line 624

def index_in_parent_node
 return nil unless @parent

 @parent.children.find_index(self)
end

#insert(index, value) ⇒ Object

Insert the given value at the given index. All following values will be pushed to a higher index.

Parameters:

  • index (Integer) —

    Position to insert at

  • value (Integer) —

    value to insert



165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
 
# File 'lib/perobs/BigArrayNode.rb', line 165

def insert(index, value)
  node = self
  cidx = nil

  # 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.size >= @tree.node_size
      # Re-add the index from the last parent node since we will descent
      # into one of the split nodes.
      index += node.parent.offsets[cidx] if node.parent
      node = node.split_node
    end

    # Once we have reached a leaf node we can insert or replace the value.
    if node.is_leaf?
      node.values.insert(index, value)
      node.parent.adjust_offsets(node, 1) if node.parent
      return
    else
      # Descend into the right child node to add the value to.
      cidx = node.search_child_index(index)
      if (index -= node.offsets[cidx]) < 0
        node.fatal "Index (#{index}) became negative"
      end
      node = node.children[cidx]
    end
  end

  node.fatal "Could not find proper node to insert the value while " +
    "looking for index #{index}"
end

#insert_child_after_peer(offset, node, peer = nil) ⇒ Object 



578
579
580
581
582
583
 
# File 'lib/perobs/BigArrayNode.rb', line 578

def insert_child_after_peer(offset, node, peer = nil)
  peer_index = @children.find_index(peer)
  cidx = peer_index ? peer_index + 1 : 0
  @offsets.insert(cidx, @offsets[peer_index] + offset)
  @children.insert(cidx, node)
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.



108
109
110
 
# File 'lib/perobs/BigArrayNode.rb', line 108

def is_leaf?
  @children.nil?
end

#reverse_each {|value| ... } ⇒ Object

Iterate over all the values of the node in reverse order.

Yields:

  • (value) 


272
273
274
275
276
277
278
 
# File 'lib/perobs/BigArrayNode.rb', line 272

def reverse_each
  return nil unless is_leaf?

  @values.reverse_each do |v|
    yield(v)
  end
end

#search_child_index(offset) ⇒ Integer

Returns Index of the matching offset or the insert position.

Parameters:

  • index (offset) —

    offset to search the child index for

Returns:

  • (Integer) —

    Index of the matching offset or the insert position.



615
616
617
618
619
620
 
# File 'lib/perobs/BigArrayNode.rb', line 615

def search_child_index(offset)
  # Handle special case for empty offsets list.
  return 0 if @offsets.empty? || offset <= @offsets.first

  (@offsets.bsearch_index { |o| o > offset } || @offsets.length) - 1
end

#set(index, value) ⇒ Object

Set the given value at the given index.

Parameters:

  • index (Integer) —

    Position to insert at

  • value (Integer) —

    value to insert



134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
 
# File 'lib/perobs/BigArrayNode.rb', line 134

def set(index, value)
  node = self

  # Traverse the tree to find the right node to add or replace the value.
  while node do
    # Once we have reached a leaf node we can insert or replace the value.
    if node.is_leaf?
      if index >= node.values.size
        node.fatal "Set index (#{index}) larger than values array " +
          "(#{node.values.size})."
      end
      node.values[index] = value
      return
    else
      # Descend into the right child node to add the value to.
      cidx = node.search_child_index(index)
      if (index -= node.offsets[cidx]) < 0
        node.fatal "Index (#{index}) became negative"
      end
      node = node.children[cidx]
    end
  end

  node.fatal "Could not find proper node to set the value while " +
    "looking for index #{index}"
end

#size ⇒ Object 



112
113
114
 
# File 'lib/perobs/BigArrayNode.rb', line 112

def size
  is_leaf? ? @values.size : @children.size
end

#split_node ⇒ BigArrayNode

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:



497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
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
544
545
546
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
 
# File 'lib/perobs/BigArrayNode.rb', line 497

def split_node
  unless @parent
    # The node is the root node. We need to create a parent node first.
    self.parent = @store.new(BigArrayNode, @tree, false)
    @parent.offsets[0] = 0
    @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(BigArrayNode, @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 = size / 2
  if is_leaf?
    # Before:
    #    +--------------------------+
    #    | 0         4         7    |
    #      |         |         |
    #      v         v         v
    # +---------++-------++----------+
    # | A B C D || E F G || H I J K  |
    #
    # After:
    #    +--------------------------+
    #    | 0    2       4         7 |
    #      |    |       |         |
    #      v    v       v         v
    # +-----++----++-------++----------+
    # | A B || C D || E F G || H I J K  |
    #
    #
    # Insert the middle element key into the parent node
    @parent.insert_child_after_peer(mid, sibling, self)
    # Copy the values from the mid element onwards into the new
    # sibling node.
    sibling.values += @values[mid..-1]
    # Delete the copied offsets and values from this node.
    @values.slice!(mid..-1)
  else
    # Before:
    #    +--------------+
    #    | 0         11 |
    #      |          |
    #      v          v
    # +----------++-------+
    # | 0 4 7 10 || 0 2 5 |
    #   | | | |     | | |
    #   v v v v     v v v
    #
    # After:
    #  +------------------+
    #  | 0      7      11 |
    #    |      |       |
    #    v      v       v
    # +-----++-----++-------+
    # | 0 4    0 3 || 0 2 5 |
    #   | |    | |    | | |
    #   v v    v v    v v v
    #
    # Insert the new sibling into the parent node.
    offset_delta = @offsets[mid]
    @parent.insert_child_after_peer(offset_delta, sibling, self)
    # Copy the offsets from after the mid value onwards to the new sibling
    # node. We substract the offset delta from each of them.
    sibling.offsets += @offsets[mid..-1].map{ |v| v - offset_delta }
    # Delete the copied offsets from this node.
    @offsets.slice!(mid..-1)
    # Same copy for the children.
    sibling.children += @children[mid..-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)
  end

  @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



730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
 
# File 'lib/perobs/BigArrayNode.rb', line 730

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.



461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
 
# File 'lib/perobs/BigArrayNode.rb', line 461

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.size == 0 ? '--' : 'v-'}#{node.tree_summary}\n"
      rescue => e
        str += "@@@@@@@@@@: #{e.message}\n"
      end
    else
      begin
        if node.is_leaf?
          if position <= node.size
            str += "#{node.tree_prefix}  " +
              "#{position == node.size ? '-' : '|'} " +
              "[ #{node.value_index(position - 1)}: " +
              "#{node.values[position - 1].nil? ?
              'nil' : node.values[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) 


698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
 
# File 'lib/perobs/BigArrayNode.rb', line 698

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



772
773
774
775
 
# File 'lib/perobs/BigArrayNode.rb', line 772

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.



751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
 
# File 'lib/perobs/BigArrayNode.rb', line 751

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.



778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
 
# File 'lib/perobs/BigArrayNode.rb', line 778

def tree_summary
  s = " @#{@_id}"
  if @parent
    begin
      s += " +#{@parent.offsets[index_in_parent_node]} ^#{@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

#value_index(idx) ⇒ Integer

Compute the array index of the value with the given index in the current node.

Parameters:

  • idx (Integer) —

    Index of the value in the current node

Returns:

  • (Integer) —

    Array index of the value



650
651
652
653
654
655
656
657
658
 
# File 'lib/perobs/BigArrayNode.rb', line 650

def value_index(idx)
  node = self
  while node.parent
    idx += node.parent.offsets[node.index_in_parent_node]
    node = node.parent
  end

  idx
end

#values_count ⇒ Integer

Returns the number of values stored in this node.

Returns:

  • (Integer) —

    the number of values stored in this node.



117
118
119
120
121
122
123
124
125
126
127
128
 
# File 'lib/perobs/BigArrayNode.rb', line 117

def values_count
  count = 0
  node = self
  while node
    if node.is_leaf?
      return count + node.values.size
    else
      count += node.offsets.last
      node = node.children.last
    end
  end
end