nlib
nn::nlib::SmartBitmapCrtp< N, Derived, BIT > クラステンプレート

Rank/Select操作つきのビットデータを保持するデータ構造です。 [詳解]

#include "nn/nlib/SmartBitmap.h"

公開メンバ関数

unsigned int GetBitVectorSize () const noexcept
 ビットデータのサイズを返します。 [詳解]
 
const BIT * GetBitVector () const noexcept
 ビットデータへのポインタを返します。 [詳解]
 
bool Has (unsigned int idx) const noexcept
 値が集合に含まれているかどうかをテストします。 [詳解]
 
bool operator[] (const unsigned int idx) const noexcept
 値が集合に含まれているかどうかをテストします。 [詳解]
 
unsigned int Rank1 (unsigned int idx) const noexcept
 Rank操作を行います。 [詳解]
 
unsigned int Rank0 (unsigned int idx) const noexcept
 Rank操作を行います。 [詳解]
 
int Select1 (unsigned int nth) const noexcept
 nth 番目の1ビットの場所を返します。nth は0から開始します。 [詳解]
 
int Select0 (unsigned int nth) const noexcept
 nth 番目の0ビットの場所を返します。nth は0から開始します。 [詳解]
 
bool Set (unsigned int idx) noexcept
 集合に32bit符号なし整数を追加します。 [詳解]
 
bool TurnOn (unsigned int idx) noexcept
 集合に32bit符号なし整数を追加します。 [詳解]
 
bool Unset (unsigned int idx) noexcept
 集合から32bit符号なし整数を取り除きます。 [詳解]
 
bool Set (unsigned int idx, bool value) noexcept
 ビットデータのビットを設定します。 [詳解]
 
void Reset () noexcept
 オブジェクトをコンストラクタが呼ばれた直後の状態にします。
 

詳解

template<size_t N, class Derived, class BIT>
class nn::nlib::SmartBitmapCrtp< N, Derived, BIT >

Rank/Select操作つきのビットデータを保持するデータ構造です。

テンプレート引数
Nビットデータのサイズ(N bits)
Derived派生クラスの型(CRTPを利用)
説明
SmartBitmapCrtp<N, Derived>クラスは元のビットデータに対して37.5パーセントのオーバーヘッドでNビットのビットデータに対するRank/Select操作を実現しています。
  • Rank操作とは指定された場所までの1(0)ビットの数を数える操作のことです。定数時間で動作します。
  • Select操作とはn番目の1(0)ビットが存在する場所を計算する操作のことです。 \(O(\log N)\)で動作します。
上記の操作を利用することでビットデータのコンパクト性を維持しつつ効率よく高度な操作を行うことが可能になります。 このクラスはクラス内部で新たにメモリをヒープから取得することはありません。
実際には派生クラスである、SmartBitmap, SmartBitmapPtrを構築して利用します。

SmartBitmap.h52 行目に定義があります。

関数詳解

◆ GetBitVector()

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::GetBitVector ( ) const
inlinenoexcept

ビットデータへのポインタを返します。

戻り値
ビットデータへのポインタ
説明
ビットデータはLSB(下の桁)から順番に格納されています。

SmartBitmap.h68 行目に定義があります。

◆ GetBitVectorSize()

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::GetBitVectorSize ( ) const
inlinenoexcept

ビットデータのサイズを返します。

戻り値
集合の定義域のサイズ(ビットデータのサイズ)

SmartBitmap.h67 行目に定義があります。

◆ Has()

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::Has ( unsigned int  idx) const
inlinenoexcept

値が集合に含まれているかどうかをテストします。

引数
[in]idx32bit符号なし整数
戻り値
集合にidx が含まれている場合はtrue

SmartBitmap.h69 行目に定義があります。

◆ operator[]()

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::operator[] ( const unsigned int  idx) const
inlinenoexcept

値が集合に含まれているかどうかをテストします。

引数
[in]idx32bit符号なし整数
戻り値
集合にidx が含まれている場合はtrue

SmartBitmap.h77 行目に定義があります。

◆ Rank0()

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::Rank0 ( unsigned int  idx) const
inlinenoexcept

Rank操作を行います。

引数
[in]idx32bit符号なし整数
戻り値
集合に含まれないidx 以下の値の数
説明
idx 以下の値で集合に含まれない要素の数を返します。 すわなち、ビットデータ[0 .. idx]内に含まれる1の数を返します。 この操作は定数時間で行われます。

SmartBitmap.h83 行目に定義があります。

◆ Rank1()

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::Rank1 ( unsigned int  idx) const
inlinenoexcept

Rank操作を行います。

引数
[in]idx32bit符号なし整数
戻り値
集合に含まれるidx 以下の値の数
説明
集合内のidx 以下の値の数を返します。 すわなち、ビットデータ[0 .. idx]内に含まれる1の数を返します。 この操作は定数時間で行われます。

SmartBitmap.h78 行目に定義があります。

◆ Select0()

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::Select0 ( unsigned int  nth) const
inlinenoexcept

nth 番目の0ビットの場所を返します。nth は0から開始します。

引数
[in]nth0以上の整数
戻り値
nth 番目(基数は0)の要素が存在するならばその値。なければ-1
説明
すなわち、ビットデータのnth 番目のOFFになっっているビットの位置を返します。 この操作は内部でRank1()を利用して二分探索で行われます。

SmartBitmap.h92 行目に定義があります。

◆ Select1()

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::Select1 ( unsigned int  nth) const
inlinenoexcept

nth 番目の1ビットの場所を返します。nth は0から開始します。

引数
[in]nth0以上の整数
戻り値
nth 番目(基数は0)の要素が存在するならばその値。なければ-1
説明
すなわち、ビットデータのnth 番目のONになっっているビットの位置を返します。 この操作は内部でRank1()を利用して二分探索で行われます。
通常の場合は、Select操作を \(O(1)\)でサポートするnn::nlib::succinct::Sbvを利用してください。

SmartBitmap.h87 行目に定義があります。

◆ Set() [1/2]

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::Set ( unsigned int  idx)
inlinenoexcept

集合に32bit符号なし整数を追加します。

引数
[in]idx集合に加える整数
戻り値
成功した場合はtrue
説明
具体的にはビットデータ内のidx に該当する部分をONにします。

SmartBitmap.h97 行目に定義があります。

◆ Set() [2/2]

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::Set ( unsigned int  idx,
bool  value 
)
inlinenoexcept

ビットデータのビットを設定します。

引数
[in]idxON/OFFする場所
[in]valueビットのON/OFF
戻り値
成功した場合はtrue
説明
具体的にはビットデータ内のidx に該当する部分をON/OFFします。

SmartBitmap.h120 行目に定義があります。

◆ TurnOn()

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::TurnOn ( unsigned int  idx)
inlinenoexcept

集合に32bit符号なし整数を追加します。

引数
[in]idx集合に加える整数
戻り値
成功した場合はtrue
説明
具体的にはビットデータ内のidx に該当する部分をONにします。 Set(idx)と同じです。

SmartBitmap.h108 行目に定義があります。

◆ Unset()

template<size_t N, class Derived, class BIT>
nn::nlib::SmartBitmapCrtp< N, Derived, BIT >::Unset ( unsigned int  idx)
inlinenoexcept

集合から32bit符号なし整数を取り除きます。

引数
[in]idx集合に加える整数
戻り値
成功した場合はtrue
説明
具体的にはビットデータ内のidx に該当する部分をOFFにします。

SmartBitmap.h109 行目に定義があります。


このクラス詳解は次のファイルから抽出されました: