前回のエントリで「ソースからシンクへとデータを流し続けるような場合」の例として、コンテナからシンクオブジェクトへとデータを流すコードを書きました。
よくよく考えてみると、「コンテナそのものを渡すよりもイテレータで範囲を渡す方がよい（STLもこの考え方にそって作られています）」「シンクオブジェクトもイテレータとして実装できる」ということに気がつきました。
入出力をイテレータに抽象化することで入出力の形式にとらわれることなく処理を書けるはずです。
せっかくなのでもう一段。キーブレイクの判定、初期値の設定、集計計算も外から指定できるようにすれば、入力するデータの型、出力するデータの型からも独立することができるはず。
以上を踏まえて、書き直してみたのがこれ。
#ifndef SUMMARY_H #define SUMMARY_H // begin から end までの入力を得て、その集計結果を sink へ出力する関数テンプレート template< typename SourceType, typename SinkType, typename InputIterator, typename OutputIterator, typename Translator, typename Comparator, typename Accumulator > void summary( const InputIterator& begin, // 入力元の先頭 const InputIterator& end, // 入力元の末尾 OutputIterator out, // 出力先 Translator translate, // 入力したデータを出力するデータの型に変換する関数 Comparator isKeyBroken, // キーブレイクを検出する関数 Accumulator accumulate ) // 集計の計算をする関数 { // 入力がなければすぐに終了 if(begin == end) { return; } InputIterator i = begin; // １番目の要素を積算の初期値にする SinkType sink = translate(*i); ++i; // ２番目以降の要素の処理 while(i != end) { if(isKeyBroken(sink, *i)) { // キーブレイクしたら、 // それまでの集計結果を出力する out++ = sink; // 新しいキーの要素を初期値にする sink = translate(*i); } else { // キーブレイクしていないなら、集計を続ける accumulate(sink, *i); } ++i; } // 最後に集計していた結果を出力する out++ = sink; } #endif//KEYBREAK_H
こうやって書き下してみると。これは入力するデータ列を出力するデータ列へと変換するフィルタそのもの。grepやuniqと同列で考えることができそうです。事前にソートしておく必要があるところなんかuniqとそっくりかも。
実例、その１
vectorに格納してある入力データを集計してvectorに書き出す例。
集計した結果を最後に標準出力に出力しています。
#include "summary.h" #include <iostream> #include <string> #include <vector> #include <iterator> #include <algorithm> // 入力を得るデータの型 struct Source { std::string code; std::string name; int value; Source(const std::string& code, const std::string& name, int value) : code(code), name(name), value(value) {} }; // 出力するデータの型 struct Sink { std::string code; int sum; Sink(const std::string& code, int sum) : code(code), sum(sum) {} }; // Sink を出力するための挿入演算子（ostream_iterator で使用する） std::ostream& operator << (std::ostream& out, const Sink& sink) { return out << sink.code << ", " << sink.sum; } // キーブレイクを判定する（キーブレイクしたら true 、していなければ false を返す） bool isKeyBroken(const Sink& sink, const Source& source) { return source.code != sink.code; } // 入力したデータを出力するデータの型に変換する Sink translate(const Source& source) { return Sink(source.code, source.value); } // 入力したデータを集計する（第１引数に集計結果を保存するデータ、第２引数に集計する入力データ） void accumulate(Sink& sink, const Source& source) { sink.sum += source.value; } int main(int, char* []) { std::vector<Source> source; std::vector<Sink> sink; // 入力するデータを作る source.push_back(Source("A01", "hoge", 100)); source.push_back(Source("A01", "piyo", 200)); source.push_back(Source("A02", "hoge", 300)); source.push_back(Source("A03", "hoge", 400)); source.push_back(Source("A03", "piyo", 500)); // 集計する summary<Source, Sink>( source.begin(), source.end(), std::back_inserter(sink), translate, isKeyBroken, accumulate ); // 集計結果を出力する std::copy(sink.begin(), sink.end(), std::ostream_iterator<Sink>(std::cout, "\n")); return 0; }
実行結果。前回と同じなので省略。
実例、その２
標準入力から直接入力を得て、集計結果を標準出力へ直接出力します。
#include "summary.h" #include <iostream> #include <string> #include <vector> #include <iterator> #include <algorithm> struct Source { std::string code; std::string name; int value; }; struct Sink { std::string code; int sum; Sink(const std::string& code, int sum) : code(code), sum(sum) {} }; std::istream& operator >> (std::istream& in, Source& source) { return in >> source.code >> source.name >> source.value; } std::ostream& operator << (std::ostream& out, const Sink& sink) { return out << sink.code << ", " << sink.sum; } bool isKeyBroken(const Sink& sink, const Source& source) { return source.code != sink.code; } Sink translate(const Source& source) { return Sink(source.code, source.value); } void accumulate(Sink& sink, const Source& source) { sink.sum += source.value; } int main(int, char* []) { std::istream_iterator<Source> begin(std::cin); // 標準入力から入力イテレータを作る std::istream_iterator<Source> end; // 入力イテレータの終端を作る std::ostream_iterator<Sink> out(std::cout, "\n"); // 標準出力から出力イテレータを作る summary<Source, Sink>( begin, end, out, translate, isKeyBroken, accumulate ); return 0; }
実行結果。
$ cat source.txt A01 hoge 100 A01 piyo 200 A02 hoge 300 A03 hoge 400 A03 piyo 500 $ ./summary2 < source.txt > sink.txt $ cat sink.txt A01, 300 A02, 300 A03, 900
実例、Haskellでは？
抽象化ならばHaskellが得意とするところなんじゃないだろうか、と、考え始めたまではいいんですが、スキル不足で途中から先に進めなくなってしまいました。
summary関数をghciに読み込ませて関数の型を見ているとこんな感じになります。
Prelude Summary> :t summary summary :: (Monad m) => (t -> t1) -> (t1 -> t -> Bool) -> (t1 -> t -> t1) -> (t1 -> m a) -> m a -> [t] -> m a
出力の型は任意のモナドにすることができたようなのですが、入力にはリストを要求しています。これも任意のモナドにできないかとしばらく考えたんですが挫折。モナドの理解が不充分。入力がないときのための値を用意しないといけないのも、なんか不格好ですし。
ともかく。できたところまで晒しておきます。
module Summary where summary _ _ _ _ nosource [] = nosource summary translate isKeyBroken accumulate output _ (s:ss) = summary_ (translate s) ss where summary_ sink [] = output sink summary_ sink (s:ss) | isKeyBroken sink s = output sink >> summary_ (translate s) ss | otherwise = summary_ (accumulate sink s) ss
標準入力から入力を得て、集計結果を直接標準出力へ出力します。
module Main where import Summary data Source = Source String String Integer data Sink = Sink String Integer translate (Source c n v) = Sink c v isKeyBroken (Sink c1 _) (Source c2 _ _) = c1 /= c2 accumulate (Sink c1 s) (Source _ _ v) = Sink c1 (s + v) output (Sink c s) = putStrLn $ c ++ " " ++ show s toSource [] = [] toSource [""] = [] toSource (c:n:v:ss) = (Source c n (read v::Integer)):(toSource ss) main = getContents >>= return.toSource.words >>= summary translate isKeyBroken accumulate output (return ())
