class NgLib:: CompressedWaveletMatrix(T)

Included Modules

Defined in:

nglib/data_structure/wavelet_matrix.cr

Constructors

Instance Method Summary

Constructor Detail

def self. new (values : Array(T)) #

[ View source ]
def self. new (n : Int , & : Int32 -> T) #

[ View source ]

Instance Method Detail

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

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


[ View source ]
def count (range : Range( Int | Nil, Int | Nil), item : T) #

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


[ View source ]
def count (item : T) #

item の個数を返します。

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


[ View source ]
def 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

[ View source ]
def 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

[ View source ]
def 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

[ View source ]
def 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

[ View source ]
def next_value (range : Range( Int | Nil, Int | Nil), lower_bound) : T | Nil #

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

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


[ View source ]
def prev_value (range : Range( Int | Nil, Int | Nil), upper_bound) : T | Nil #

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

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


[ View source ]
def size (*args, **options) #

[ View source ]
def size (*args, **options, &) #

[ View source ]
def unsafe_fetch (index : Int ) #
Description copied from module Indexable(T)

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.


[ View source ]