nlib
|
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 |
オブジェクトをコンストラクタが呼ばれた直後の状態にします。 | |
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.h の 39 行目に定義があります。
|
inlinenoexcept |
|
inlinenoexcept |
|
inlinenoexcept |
値が集合に含まれているかどうかをテストします。
[in] | idx | 32bit符号なし整数 |
idx
が含まれている場合はtrue
SmartBitmap.h の 52 行目に定義があります。
|
inlinenoexcept |
値が集合に含まれているかどうかをテストします。
[in] | idx | 32bit符号なし整数 |
idx
が含まれている場合はtrue
SmartBitmap.h の 60 行目に定義があります。
|
inlinenoexcept |
Rank
操作を行います。
[in] | idx | 32bit符号なし整数 |
idx
以下の値の数idx
以下の値で集合に含まれない要素の数を返します。 すわなち、ビットデータ[0 .. idx]
内に含まれる1の数を返します。 この操作は定数時間で行われます。 SmartBitmap.h の 66 行目に定義があります。
|
inlinenoexcept |
Rank
操作を行います。
[in] | idx | 32bit符号なし整数 |
idx
以下の値の数idx
以下の値の数を返します。 すわなち、ビットデータ[0 .. idx]
内に含まれる1の数を返します。 この操作は定数時間で行われます。 SmartBitmap.h の 61 行目に定義があります。
|
inlinenoexcept |
nth
番目の0ビットの場所を返します。nth
は0から開始します。
[in] | nth | 0以上の整数 |
nth
番目(基数は0)の要素が存在するならばその値。なければ-1nth
番目のOFFになっっているビットの位置を返します。 この操作は内部でRank1()
を利用して二分探索で行われます。 SmartBitmap.h の 75 行目に定義があります。
|
inlinenoexcept |
nth
番目の1ビットの場所を返します。nth
は0から開始します。
[in] | nth | 0以上の整数 |
nth
番目(基数は0)の要素が存在するならばその値。なければ-1nth
番目のONになっっているビットの位置を返します。 この操作は内部でRank1()
を利用して二分探索で行われます。 Select
操作を \(O(1)\)でサポートするnn::nlib::succinct::Sbv
を利用してください。 SmartBitmap.h の 70 行目に定義があります。
|
inlinenoexcept |
集合に32bit符号なし整数を追加します。
[in] | idx | 集合に加える整数 |
true
idx
に該当する部分をONにします。 SmartBitmap.h の 80 行目に定義があります。
|
inlinenoexcept |
ビットデータのビットを設定します。
[in] | idx | ON/OFFする場所 |
[in] | value | ビットのON/OFF |
true
idx
に該当する部分をON/OFFします。 SmartBitmap.h の 103 行目に定義があります。
|
inlinenoexcept |
集合に32bit符号なし整数を追加します。
[in] | idx | 集合に加える整数 |
true
idx
に該当する部分をONにします。 Set(idx)
と同じです。 SmartBitmap.h の 91 行目に定義があります。
|
inlinenoexcept |
集合から32bit符号なし整数を取り除きます。
[in] | idx | 集合に加える整数 |
true
idx
に該当する部分をOFFにします。 SmartBitmap.h の 92 行目に定義があります。
© 2012-2016 Nintendo Co., Ltd. All rights reserved.