- メインページ
- モジュール
- ネームスペース
- データ構造
- ファイル

- データ構造
- データ構造索引
- クラス階層
- データフィールド

データ構造 | Public 型 | Public メソッド
クラス テンプレート interval_tree< S, V >
Interval-tree

区間の集合から任意の値が含まれる区間のみを高速に探索するためのクラス [詳細]

`#include <interval_tree.h>`

## データ構造
class | node
| Interval-treeのノードを表すクラス（interval_treeクラスの内部でのみ使用） [詳細]

## Public 型
typedef S | section_type
| 区間を表す型
typedef S::min_max_type | min_max_type
| 区間の両端の値を表す型
typedef S::tag_type | tag_type
| 区間のタグ情報をを表す型
typedef V | value_type
| 区間の探索の際に入力される値を表す型

## Public メソッド
void | find (const value_type &val, std::vector< tag_type > &tags)
| 入力された値が含まれる区間の探索
bool | construct (const std::vector< section_type > &secs)
| Interval-treeの構築
void | destruct ()
| Interval-treeの破棄
| interval_tree ()
| デフォルトコンストラクタ
| interval_tree (const std::vector< section_type > &secs)
| コンストラクタ（Interval-treeの構築）
| interval_tree (const interval_tree< section_type, value_type > &it)
| コピーコンストラクタ
| ~interval_tree ()
| デストラクタ
interval_tree & | operator= (const interval_tree< section_type, value_type > &it)
| 代入演算子

## 説明

### template<typename S, typename V>
class interval_tree< S, V >

区間の集合から任意の値が含まれる区間のみを高速に探索するためのクラス

区間の集合から2分木を構築し、通常O(n)かかる探索時間をO(log n)に削減する． 線分や面分の重なり判定などに有効．

注意
  mist::tagged_section< M, T >型のstd::vetorを入力とする．
  mist::tagged_section< M, T >::tag_type型のstd::vetorを探索結果の出力とする．

引数

  S | … 区間のデータ型（ mist::tagged_section< M, T >型 ）
  V | … 区間の探索の際に入力する任意の値のデータ型（ double や float など，mist::rgb< M, T >::min_max_typeと同じか、あるいはより精度の高い型 ）

使用例
// 区間の集合の用意
typedef mist::tagged_section< int, size_t > section_type;
std::vector< section_type > secs; // int型の最大値，最小値にはさまれた区間の集合，各区間にはsize_t型のタグが付けられる．
secs.push_back( section_type( -1, 5, 0 ) );// タグ0が付いた区間[ -1, 5 )を集合に追加．
/*
区間の集合へ追加処理
*/
// Interval-treeの構築
typedef mist::interval_tree< section_type, double > i_tree_type;
mist::i_tree_type i_tree( secs );
// 任意の値が含まれる区間のタグの集合を高速に探索
std::vector< section_type::tag_type > tags;
i_tree.find( 0.0, tags ); // 0.0 が含まれる区間のタグの集合を得る
// 探索結果の表示
for( size_t i = 0 ; i < tags.size( ) ; i ++ )
{
std::cout << secs[ tags[ i ] ] << std::endl;
}

## コンストラクタとデストラクタ

template<typename S, typename V>

interval_tree< S, V >::interval_tree | ( | const std::vector< section_type > & | secs | ) |
| inline

コンストラクタ（Interval-treeの構築）

引数

  [in] | secs | … 区間集合

template<typename S, typename V>

interval_tree< S, V >::interval_tree | ( | const interval_tree< section_type, value_type > & | it | ) |
| inline

コピーコンストラクタ

引数

  [in] | it | … interval_treeオブジェクト

## 関数

template<typename S, typename V>

bool interval_tree< S, V >::construct | ( | const std::vector< section_type > & | secs | ) |
| inline

Interval-treeの構築

引数

  [in] | secs | … 区間の集合

戻り値
  木が正しく構築された場合に真を返す

参照元 interval_tree< section_type, float_type >::interval_tree().

template<typename S, typename V>

void interval_tree< S, V >::find | ( | const value_type & | val,
|  | std::vector< tag_type > & | tags
| ) |  |
| inline

入力された値が含まれる区間の探索

引数

  [in] | val | … 入力（この値を間に含む区間を探索）
  [out] | tags | … 探索された区間のタグ情報の集合

template<typename S, typename V>

interval_tree& interval_tree< S, V >::operator= | ( | const interval_tree< section_type, value_type > & | it | ) |
| inline

代入演算子

引数

  [in] | it | … interval_treeオブジェクト

このクラスの説明は次のファイルから生成されました:

- interval_tree.h