Class: DataStructuresRMolinari::SegmentTree::CSegmentTreeTemplate

Inherits:
Object
  • Object
show all
Defined in:
lib/data_structures_rmolinari/segment_tree.rb,
ext/c_segment_tree_template/segment_tree_template.c

Overview

The underlying functionality of the Segment Tree data type, implemented in C as a Ruby extension.

See SegmentTreeTemplate for more information.

Implementation note

The functionality is entirely written in C. But we write the constructor in Ruby because keyword arguments are difficult to parse on the C side.

Instance Method Summary collapse

Constructor Details

#initialize(combine:, single_cell_array_val:, size:, identity:) ⇒ CSegmentTreeTemplate

Returns a new instance of CSegmentTreeTemplate.



152
153
154
155
 
# File 'lib/data_structures_rmolinari/segment_tree.rb', line 152

def initialize(combine:, single_cell_array_val:, size:, identity:)
  # having sorted out the keyword arguments, pass them more easily to the C layer.
  c_initialize(combine, single_cell_array_val, size, identity)
end

Instance Method Details

#c_initialize(combine, single_cell_array_val, size, identity) ⇒ Object

CSegmentTreeTemplate#c_initialize.

(see CSegmentTreeTemplate#initialize).



310
311
312
313
 
# File 'ext/c_segment_tree_template/segment_tree_template.c', line 310

static VALUE segment_tree_init(VALUE self, VALUE combine, VALUE single_cell_array_val, VALUE size, VALUE identity) {
  setup(unwrapped(self), combine, single_cell_array_val, size, identity);
  return self;
}

#query_on(left, right) ⇒ Object

The desired value (max, sum, etc.) on the subinterval left..right.

It must be that left..right is contained in 0…size.

The type of the return value depends on the concrete instance of the segment tree. We return the identity element provided at construction time if the interval is empty.

Parameters:

  • left —

    the left end of the subinterval.

  • right —

    the right end (inclusive) of the subinterval.



318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
 
# File 'ext/c_segment_tree_template/segment_tree_template.c', line 318

static VALUE segment_tree_query_on(VALUE self, VALUE left, VALUE right) {
  segment_tree_data* seg_tree = unwrapped(self);
  size_t c_left = checked_nonneg_fixnum(left);
  size_t c_right = checked_nonneg_fixnum(right);

  if (c_right >= seg_tree->size) {
    rb_raise(eSharedDataError, "Bad query interval %lu..%lu (size = %lu)", c_left, c_right, seg_tree->size);
  }

  if (left > right) {
    // empty interval.
    return seg_tree->identity;
  }

  return determine_val(seg_tree, TREE_ROOT, c_left, c_right, 0, seg_tree->size - 1);
}

#update_at(idx) ⇒ Object

Reflect the fact that the underlying array has been updated at the given idx

Note that we don’t need the updated value itself. We get that by calling the lambda single_cell_array_val supplied at construction.

Parameters:

  • idx —

    an index in the underlying data array.



338
339
340
341
342
343
344
345
346
347
348
349
 
# File 'ext/c_segment_tree_template/segment_tree_template.c', line 338

static VALUE segment_tree_update_at(VALUE self, VALUE idx) {
  segment_tree_data *seg_tree = unwrapped(self);
  size_t c_idx = checked_nonneg_fixnum(idx);

  if (c_idx >= seg_tree->size) {
    rb_raise(eSharedDataError, "Cannot update value at index %lu, size = %lu", c_idx, seg_tree->size);
  }

  update_val_at(seg_tree, c_idx, TREE_ROOT, 0, seg_tree->size - 1);

  return Qnil;
}