Module: DataStructuresRMolinari::SegmentTree

Defined in:
lib/data_structures_rmolinari/segment_tree.rb,
lib/data_structures_rmolinari/segment_tree.rb,
ext/c_segment_tree_template/segment_tree_template.c

Overview

A namespace to hold the various bits and bobs related to the SegmentTree implementation

Defined Under Namespace

Classes: CSegmentTreeTemplate, IndexOfMaxValSegmentTree, MaxValSegmentTree, SegmentTreeTemplate, SumSegmentTree

Class Method Summary collapse

Class Method Details

.construct(data, operation, lang) ⇒ Object

A convenience method to construct a Segment Tree that, for a given array A(0…size), answers questions of the kind given by operation, using the template written in lang

  • @param data: the array A.

    • It must respond to #size and to #[] with non-negative integer arguments.

  • @param operation: a supported “style” of Segment Tree

    • for now, must be one of these (but you can write your own concrete version)

      • :max: implementing max_on(i, j), returning the maximum value in A(i..j)

      • :index_of_max: implementing index_of_max_val_on(i, j), returning an index corresponding to the maximum value in A(i..j).

  • @param lang: the language in which the underlying “template” is written

    • :c or :ruby

    • the C version will run faster but for now may be buggier and harder to debug



38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/data_structures_rmolinari/segment_tree.rb', line 38

module_function def construct(data, operation, lang)
  operation.must_be_in [:max, :index_of_max, :sum]
  lang.must_be_in [:ruby, :c]

  klass = case operation
          when :max then MaxValSegmentTree
          when :index_of_max then IndexOfMaxValSegmentTree
          when :sum then SumSegmentTree
          else raise ArgumentError, "Unknown operation #{operation}"
          end
  template = lang == :ruby ? SegmentTreeTemplate : CSegmentTreeTemplate

  klass.new(template, data)
end