「や」の字: 【Boost Advent Calendar 2011】 18日目 Boost.ICL の紹介

本記事は Boost Advent Calendar 2011 18日目の記事となります。

前振り

C++ の魅力の一つとしてライブラリによってあたかも言語機能が拡張されたかのようなことを実現できる、というものがあると思います。Boost Advent Calendar を読まれる／書かれるような方もそういった言語機能寄りの部分に興味を持たれている方が多いのかなぁ、という印象を持っていたりします。そうした中でそれなりに応用寄りでありながら取り上げられる機会が多いライブラリとして Boost.Graph が挙げられます。これは多くの問題がグラフの問題に帰着され応用寄りといいつつ広く使えるライブラリであること、C++ 的な generic なデザインであることが理由ではないかと思います。Boost.ICL (Interval Container Library)も応用寄りでありながら広く使えそうなライブラリで、かつ、C++ らしいライブラリだと思うのですが、なぜか記事が少ないようです。ということで僭越ながら（自分だってほとんど使ってなかったりしますが）簡単な紹介を書いてみたいと思います。

で ICL って何？

今ひとつ取り上げられない ICL ですが、その理由の一つとして名前が分かりにくい、という点が挙げられると思います（ドキュメントが数学寄りってのもある気がします）。Spirit や Wave のように内容を表現することを初めから放棄している変態ライブラリではないにも関わらず ICL だとさっぱり分からず Interval Container Library でもやっぱり良く分からないわけです。

interval とは区間のことです。Boost には別に Interval というライブラリもありこちらは区間演算を対象としたライブラリです（参考：Boost.勉強会 #7 東京での @pepshiso さんの発表資料 Boost.Intervalで区間演算）。しかし ICL は Interval とは直接の関係はありません。interval では単一の区間に対する数値演算を対象としていましたが、ICL では区間の集合を取り扱います。

まだ良く分かりませんね。こうした区間（の集合）について最も使われやすいのは時間でしょう。カレンダーなり手帳なりそこにはスケジュールが書いてあると思います。何時から何時まで予定、何時から何時まで予定。そう、これが区間の集合です。

それでは、予定のリストから順に衝突しない予定を登録していく、というコードを書いてみましょう。

#include <boost/icl/interval_set.hpp>

// Date_Time の posix_time とアダプタコード
#include <boost/icl/ptime.hpp> 

#include <string>
#include <iostream>

std::string requests[][2] = {
 { "2011-12-18 15:00", "2011-12-18 16:00" },
 { "2011-12-18 14:00", "2011-12-18 15:30" },
 { "2011-12-18 10:00", "2011-12-18 12:00" },
 { "2011-12-18 14:00", "2011-12-18 15:00" },
 { "2011-12-18 13:00", "2011-12-18 14:00" },
};

int main(void)
{
 using boost::posix_time::ptime;
 using boost::posix_time::time_from_string;
 
 using boost::icl::interval_set;
 using boost::icl::discrete_interval;

 interval_set<ptime> reserved;

 for(std::size_t i = 0; i < sizeof(requests) / sizeof(requests[0]); ++i) {
  discrete_interval<ptime> request = discrete_interval<ptime>::right_open(
    time_from_string(requests[i][0]),
    time_from_string(requests[i][1])
  );
  if(disjoint(reserved, request)) {
   reserved += request;
   std::cout << "RESERVED:     " << request << std::endl;
   std::cout << "STATUS:       " << reserved << std::endl;
  } else {
   std::cout << "NOT RESERVED: " << request << std::endl;
  }
 }

 return 0;
}

ほぼ自明なコードだと思います。interval_set が区間の集合、連続値ではなく離散値であるため discrete_interval を使っています。right_open は右開区間、left <= x < right な区間の作成です。disjoint により予定が衝突しているかを判別し、+= によって区間を集合に追加しています。出力結果は以下の通り。

RESERVED:     [2011-Dec-18 15:00:00,2011-Dec-18 16:00:00)
STATUS:       {[2011-Dec-18 15:00:00,2011-Dec-18 16:00:00)}
NOT RESERVED: [2011-Dec-18 14:00:00,2011-Dec-18 15:30:00)
RESERVED:     [2011-Dec-18 10:00:00,2011-Dec-18 12:00:00)
STATUS:       {[2011-Dec-18 10:00:00,2011-Dec-18 12:00:00)[2011-Dec-18 15:00:00,2011-Dec-18 16:00:00)}
RESERVED:     [2011-Dec-18 14:00:00,2011-Dec-18 15:00:00)
STATUS:       {[2011-Dec-18 10:00:00,2011-Dec-18 12:00:00)[2011-Dec-18 14:00:00,2011-Dec-18 16:00:00)}
RESERVED:     [2011-Dec-18 13:00:00,2011-Dec-18 14:00:00)
STATUS:       {[2011-Dec-18 10:00:00,2011-Dec-18 12:00:00)[2011-Dec-18 13:00:00,2011-Dec-18 16:00:00)}

14:00-15:00 を追加したときに interval_set 中で 15:00-16:00 と区間が統合されて 14:00-16:00 となっているのが見てとれます。この挙動は集合の型を変えることにより変更が可能です。interval_set の代わりに separate_interval_set を使った場合、出力は以下のようになります。

RESERVED:     [2011-Dec-18 15:00:00,2011-Dec-18 16:00:00)
STATUS:       {[2011-Dec-18 15:00:00,2011-Dec-18 16:00:00)}
NOT RESERVED: [2011-Dec-18 14:00:00,2011-Dec-18 15:30:00)
RESERVED:     [2011-Dec-18 10:00:00,2011-Dec-18 12:00:00)
STATUS:       {[2011-Dec-18 10:00:00,2011-Dec-18 12:00:00)[2011-Dec-18 15:00:00,2011-Dec-18 16:00:00)}
RESERVED:     [2011-Dec-18 14:00:00,2011-Dec-18 15:00:00)
STATUS:       {[2011-Dec-18 10:00:00,2011-Dec-18 12:00:00)[2011-Dec-18 14:00:00,2011-Dec-18 15:00:00)[2011-Dec-18 15:00:00,2011-Dec-18 16:00:00)}
RESERVED:     [2011-Dec-18 13:00:00,2011-Dec-18 14:00:00)
STATUS:       {[2011-Dec-18 10:00:00,2011-Dec-18 12:00:00)[2011-Dec-18 13:00:00,2011-Dec-18 14:00:00)[2011-Dec-18 14:00:00,2011-Dec-18 15:00:00)[2011-Dec-18 15:00:00,2011-Dec-18 16:00:00)}

隣接した区間でも統合されていないのが分かります。ちなみに right_open の代わりに closed (閉区間) を使うと（interval_set か separate_interval_set かに関わらず）出力はこうなります。閉区間なので端だけが衝突している場合でも登録できなくなります。

RESERVED:     [2011-Dec-18 15:00:00,2011-Dec-18 16:00:00]
STATUS:       {[2011-Dec-18 15:00:00,2011-Dec-18 16:00:00]}
NOT RESERVED: [2011-Dec-18 14:00:00,2011-Dec-18 15:30:00]
RESERVED:     [2011-Dec-18 10:00:00,2011-Dec-18 12:00:00]
STATUS:       {[2011-Dec-18 10:00:00,2011-Dec-18 12:00:00][2011-Dec-18 15:00:00,2011-Dec-18 16:00:00]}
NOT RESERVED: [2011-Dec-18 14:00:00,2011-Dec-18 15:00:00]
RESERVED:     [2011-Dec-18 13:00:00,2011-Dec-18 14:00:00]
STATUS:       {[2011-Dec-18 10:00:00,2011-Dec-18 12:00:00][2011-Dec-18 13:00:00,2011-Dec-18 14:00:00][2011-Dec-18 15:00:00,2011-Dec-18 16:00:00]}

今度は2人の予定から（就業時間中に）両方が開いている時間帯を求めるイメージのコードです。

#include <boost/icl/interval_set.hpp>

// Date_Time の posix_time とアダプタコード
#include <boost/icl/ptime.hpp> 

#include <string>
#include <iostream>

std::string worktime[][2] = {
 { "2011-12-18 08:30", "2011-12-18 12:00" },
 { "2011-12-18 13:00", "2011-12-18 17:30" },
};

std::string schedule1[][2] = {
 { "2011-12-18 09:00", "2011-12-18 10:30" },
 { "2011-12-18 11:00", "2011-12-18 12:00" },
 { "2011-12-18 15:00", "2011-12-18 16:00" },
 { "2011-12-18 17:00", "2011-12-18 21:00" },
};

std::string schedule2[][2] = {
 { "2011-12-18 08:30", "2011-12-18 11:00" },
 { "2011-12-18 13:00", "2011-12-18 14:00" },
 { "2011-12-18 15:00", "2011-12-18 16:00" },
};

template<typename T, std::size_t N>
void read(T& t, std::string (&spec)[N][2])
{
 using boost::posix_time::ptime;
 using boost::posix_time::time_from_string;
 using boost::icl::discrete_interval;

 for(std::size_t i = 0; i < N; ++i) {
  discrete_interval<ptime> duration = discrete_interval<ptime>::right_open(
    time_from_string(spec[i][0]),
    time_from_string(spec[i][1])
  );
  t += duration;
 }
}

int main(void)
{
 using boost::posix_time::ptime;
 using boost::icl::interval_set;

 interval_set<ptime> available, reserved1, reserved2;

 read(available, worktime);
 read(reserved1, schedule1);
 read(reserved2, schedule2);

 std::cout << (available - reserved1 - reserved2) << std::endl;

 return 0;
}

{[2011-Dec-18 14:00:00,2011-Dec-18 15:00:00)[2011-Dec-18 16:00:00,2011-Dec-18 17:00:00)}

集合演算で正味1行です。(available - (reserved1 | reserved2)) でも同じ結果になります。なお今までの所、interval_set 全体を単純にストリーム出力していますが普通にコンテナなので begin(), end() でループも回せますし algorithm にも渡せます。

map もあるよ！

ここまででも十分使い道のあるライブラリだと言えると思いますがもうひとつ特筆すべきなのは map の存在です。当初 ICL を見ていた時「set は分かる、しかし map ってどうなんねん」と思ったものでした。区間が重複しない場合は特に問題はありませんが区間が重複している場合はどう処理するのか。答えは処理を選択可能である、です。数値に対するデフォルトでは追加、削除によって値を＋－します。ということで、ある時間帯に何人が来るかというデータから最大人数になる時間帯を求めてみましょう。ただし人数が同じ時間帯がある場合は、最も長い時間帯を、長さも同じ場合は開始時間が早い時間帯とします。

#include <boost/icl/interval_map.hpp>

// Date_Time の posix_time とアダプタコード
#include <boost/icl/ptime.hpp> 

#include <boost/lambda/lambda.hpp>

#include <string>
#include <iostream>
#include <algorithm>
#include <utility>

// 入力データ用型
struct spec
{
 std::string from, to;
 int count;
};

// 入力データ
spec input[] = {
 { "2011-12-18 14:30", "2011-12-18 15:30", 4 },
 { "2011-12-18 11:00", "2011-12-18 18:00", 1 },
 { "2011-12-18 10:00", "2011-12-18 16:00", 3 },
 { "2011-12-18 13:00", "2011-12-18 15:00", 2 },
 { "2011-12-18 12:30", "2011-12-18 13:30", 4 },
};

// typedef
typedef boost::icl::interval_map<boost::posix_time::ptime, int> map_type;
typedef map_type::value_type value_type;
typedef map_type::iterator iterator;

// 読み込み用ヘルパ
template<std::size_t N>
void read(map_type& t, spec (&specs)[N])
{
 using boost::posix_time::ptime;
 using boost::posix_time::time_from_string;
 using boost::icl::discrete_interval;

 for(std::size_t i = 0; i < N; ++i) {
  discrete_interval<ptime> duration = discrete_interval<ptime>::right_open(
    time_from_string(specs[i].from),
    time_from_string(specs[i].to)
  );
  t += std::make_pair(duration, specs[i].count);
 }
}

// 比較用関数オブジェクト
// 1) 人数が小さい方
// 2) 人数が同じ場合は、期間が短い方
// 3) 人数、期間が同じ場合は、開始時間が遅い方
struct compare
{
 bool operator()(const value_type &v1, const value_type &v2) const
 {
  const value_type::first_type & key1 = v1.first;
  const value_type::first_type & key2 = v2.first;
  const value_type::second_type & value1 = v1.second;
  const value_type::second_type & value2 = v2.second;

  return value1 <  value2 ||
    (value1 == value2 && key1.upper() - key1.lower() <  key2.upper() - key2.lower()) ||
    (value1 == value2 && key1.upper() - key1.lower() == key2.upper() - key2.lower() && 
   key1.lower() > key2.lower());
 }
};

int main(void)
{
 map_type sum;

 read(sum, input);
 iterator it = max_element(sum.begin(), sum.end(), compare());
 std::cout << it->first << ':' << it->second << std::endl;

 return 0;
}

出力結果と図示は以下のイメージになります。

[2011-Dec-18 13:00:00,2011-Dec-18 13:30:00):10

単純に区間とそれに紐づけられた値（参加人数）を += していき基準に合わせて max_element を呼んでいるだけです。前述の通り、紐づけられた値が数値なのでデフォルトでは + で集計されますが、例えば interval_map<key, set<T> > だったりすると和集合、差集合になりますし、interval_map の第 5 template 引数に functor を渡してやることでカスタマイズも可能です。例えば inplace_max を渡すと最大値をとるようになったりします。

#include <boost/icl/interval_map.hpp>

// Date_Time の posix_time とアダプタコード
#include <boost/icl/ptime.hpp> 

#include <boost/lambda/lambda.hpp>

#include <string>
#include <iostream>
#include <algorithm>
#include <utility>

// 入力データ用型
struct spec
{
 std::string from, to;
 int count;
};

// 入力データ
spec input[] = {
 { "2011-12-18 14:30", "2011-12-18 15:30", 4 },
 { "2011-12-18 11:00", "2011-12-18 18:00", 1 },
 { "2011-12-18 10:00", "2011-12-18 16:00", 3 },
 { "2011-12-18 13:00", "2011-12-18 15:00", 2 },
 { "2011-12-18 12:30", "2011-12-18 13:30", 4 },
};

// typedef
typedef boost::icl::interval_map<boost::posix_time::ptime, int,
                                 boost::icl::partial_absorber, std::less,
                                 boost::icl::inplace_max> map_type;
typedef map_type::iterator iterator;

// 読み込み用ヘルパ
template<std::size_t N>
void read(map_type& t, spec (&specs)[N])
{
 using boost::posix_time::ptime;
 using boost::posix_time::time_from_string;
 using boost::icl::discrete_interval;

 for(std::size_t i = 0; i < N; ++i) {
  discrete_interval<ptime> duration = discrete_interval<ptime>::right_open(
    time_from_string(specs[i].from),
    time_from_string(specs[i].to)
  );
  t += std::make_pair(duration, specs[i].count);
 }
}

int main(void)
{
 map_type peak;

 read(peak, input);
 for(iterator it = peak.begin(); it != peak.end(); ++it)
 {
  std::cout << it->first << " : " << it->second << std::endl;
 }
 return 0;
}

出力結果と図示は以下のイメージになります。

[2011-Dec-18 10:00:00,2011-Dec-18 12:30:00) : 3
[2011-Dec-18 12:30:00,2011-Dec-18 13:30:00) : 4
[2011-Dec-18 13:30:00,2011-Dec-18 14:30:00) : 3
[2011-Dec-18 14:30:00,2011-Dec-18 15:30:00) : 4
[2011-Dec-18 15:30:00,2011-Dec-18 16:00:00) : 3
[2011-Dec-18 16:00:00,2011-Dec-18 18:00:00) : 1

まとめ

ほんのさわりですが、ICL について簡単に紹介しました。元々 ICL はドイツの Cortex Software GmbH が病院情報システムの開発をする際に開発した Interval Template Library を Boost に提案したものです。出自からも実用性は保証済みと言っても良いでしょう。こうした区間に対する処理は情報処理システムではどこにでも出てくるようなものです。皆さんも ICL を使ってみてはいかがでしょうか？

これで Boost Advent Calendar 2011 18 日目は終了です。19 日目は id:phi16(@phi16_) さん担当になります。

「や」の字

2011年12月18日日曜日

【Boost Advent Calendar 2011】 18日目 Boost.ICL の紹介

前振り

で ICL って何？

map もあるよ！

まとめ

0 件のコメント:

コメントを投稿