class

NgLib::CompressedWaveletMatrix(T)

Inherits Indexable < Enumerable < Iterable < Reference < Object

Constructors

new(values : Array(T))

Source

new(n : Int, & : Int32 -> T)

Source

Instance methods

count(range : Range(Int | Nil, Int | Nil), bound : Range(T | Nil, T | Nil)) : Int32

range の表す区間に含まれる要素の中で bound が表す範囲の値の個数を返します。

Source

count(range : Range(Int | Nil, Int | Nil), item : T)

range の表す区間に含まれる要素の中で item の個数を返します。

Source

count(item : T)

item の個数を返します。

計算量は対数オーダーです。

Source

kth_largest(range : Range(Int | Nil, Int | Nil), kth : Int)

range の表す区間に含まれる要素のうち、kth 番目に大きい値を返します。

wm = WaveletMatrix.new([1, 3, 2, 5])
wm.kth_largest(1..2, 0) # => 3
wm.kth_largest(1..2, 1) # => 2

Source

kth_largest(kth : Int32)

kth 番目に大きい値を返します。

wm = WaveletMatrix.new([1, 3, 2, 5])
wm.kth_smallest(0) # => 5
wm.kth_smallest(1) # => 3
wm.kth_smallest(2) # => 2
wm.kth_smallest(3) # => 1

Source

kth_smallest(range : Range(Int | Nil, Int | Nil), kth : Int)

range の表す区間に含まれる要素のうち、kth 番目に小さい値を返します。

wm = WaveletMatrix.new([1, 3, 2, 5])
wm.kth_smallest(1..2, 0) # => 2
wm.kth_smallest(1..2, 1) # => 3

Source

kth_smallest(kth : Int32)

kth 番目に小さい値を返します。

wm = WaveletMatrix.new([1, 3, 2, 5])
wm.kth_smallest(0) # => 1
wm.kth_smallest(1) # => 2
wm.kth_smallest(2) # => 3
wm.kth_smallest(3) # => 5

Source

next_value(range : Range(Int | Nil, Int | Nil), lower_bound) : T | Nil

range の表す区間に含まれる要素のうち、lower_bound 以上の値の最小値を返します。

存在しない場合は nil を返します。

Source

prev_value(range : Range(Int | Nil, Int | Nil), upper_bound) : T | Nil

range の表す区間に含まれる要素のうち、upper_bound 未満の値の最大値を返します。

存在しない場合は nil を返します。

Source

size(*args, **options)

Source

size(*args, **options, &)

Source

unsafe_fetch(index : Int)

Returns the element at the given index, without doing any bounds check.

Indexable makes sure to invoke this method with index in 0...size, so converting negative indices to positive ones is not needed here.

Clients never invoke this method directly. Instead, they access elements with #[](index) and #[]?(index).

This method should only be directly invoked if you are absolutely sure the index is in bounds, to avoid a bounds check for a small boost of performance.

Source