株式会社エス・スリー・フォー

Archive for the ‘misc’ Category

<stx/functional>

Wednesday, April 5th, 2006

DDJ-J 1998年5月号で紹介したSTL拡張コンポーネント”STX”の改版です。
初版で定義した関数のうち、使用頻度の少ないもの、
既存の関数オブジェクトで簡単に置き換えられるものを除き、新たにいくつか追加しました。

単項比較演算
範囲比較
二項算術演算
単項算術演算
ビット演算
単項ビット演算
合成関数
- unary_compose / compose1
- binary_compose / compose2
三項演算
- unary_tern / tern1
- binary_tern / tern2

unary_equal_to / eq

template<class T>
class unary_equal_to : std::unary_function<T,bool> {
private:
  T value;
public:
  explicit unary_equal_to(const T& v)
    : value(v) {}
  bool operator()(const T& x) const
    { return x == value; }
};

bool operator()(const T& x) const

x == v の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_equal_to<int> f(3);
cout << boolalpha;
cout << f(3) << endl; // true
cout << f(4) << endl; // false

template<class T>
unary_equal_to<T>
eq(const T& value) {
  return unary_equal_to<T>(value);
}

unary_equal_to<T>(value)を返します。

// sample
int array[] = { 1, 2, 3, 4, 5 };
int n = count_if(array, array+5, stx::eq(3)); // n = 1

unary_not_equal_to / ne

template<class T>
class unary_not_equal_to : std::unary_function<T,bool> {
  T value;
public:
  explicit unary_not_equal_to(const T& v) : value(v) {}
  bool operator()(const T& x) const
    { return !(x == value); }
};

bool operator()(const T& x) const

!(x == v) の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_not_equal_to<int> f(3);
cout << boolalpha;
cout << f(3) << endl; // false
cout << f(4) << endl; // true

template<class T>
unary_not_equal_to<T>
ne(const T& value) {
  return unary_not_equal_to<T>(value);
}

unary_not_equal_to<T>(value)を返します。

// sample
int array[] = { 1, 2, 3, 4, 5 };
int n = count_if(array, array+5, stx::ne(3)); // n = 4

unary_less / lt

template<class T>
class unary_less : std::unary_function<T,bool> {
  T value;
public:
  explicit unary_less(const T& v) : value(v) {}
  bool operator()(const T& x) const
    { return x < value; }
};

bool operator()(const T& x) const

x < v の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_less<int> f(3);
cout << boolalpha;
cout << f(2) << endl; // true
cout << f(3) << endl; // false

template<class T>
unary_less<T>
lt(const T& value) {
  return unary_less<T>(value);
}

unary_less<T>(value)を返します。

// sample
int array[] = { 1, 2, 3, 4, 5 };
int n = count_if(array, array+5, stx::ne(3)); // n = 2

unary_greater / gt

template<class T>
class unary_greater : std::unary_function<T,bool> {
  T value;
public:
  explicit unary_greater(const T& v) : value(v) {}
  bool operator()(const T& x) const
    { return value < x; }
};

bool operator()(const T& x) const

v < x の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_greater<int> f(3);
cout << boolalpha;
cout << f(3) << endl; // false
cout << f(4) << endl; // true

template<class T>
unary_greater<T>
gt(const T& value) {
  return unary_greater<T>(value);
}

unary_greater<T>(value)を返します。

// sample
int array[] = { 1, 2, 3, 4, 5 };
int n = count_if(array, array+5, stx::gt(3)); // n = 2

unary_less_equal / le

template<class T>
class unary_less_equal : std::unary_function<T,bool> {
  T value;
public:
  explicit unary_less_equal(const T& v) : value(v) {}
  bool operator()(const T& x) const
    { return !(value < x); }
};

bool operator()(const T& x) const

!(v < x) の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_less_equal<int> f(3);
cout << boolalpha;
cout << f(3) << endl; // true
cout << f(4) << endl; // false

template<class T>
unary_less_equal<T>
le(const T& value) {
  return unary_less_equal<T>(value);
}

unary_less_equal<T>(value)を返します。

// sample
int array[] = { 1, 2, 3, 4, 5 };
int n = count_if(array, array+5, stx::le(3)); // n = 3

unary_greater_equal / ge

template<class T>
class unary_greater_equal : std::unary_function<T,bool> {
  T value;
public:
  explicit unary_greater_equal(const T& v) : value(v) {}
  bool operator()(const T& x) const
    { return !(x < value); }
};

bool operator()(const T& x) const

!(x < v) の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_greater_equal<int> f(3);
cout << boolalpha;
cout << f(2) << endl; // false
cout << f(3) << endl; // true

template<class T>
unary_greater_equal<T>
ge(const T& value) {
  return unary_greater_equal<T>(value);
}

unary_greater_equal<T>(value)を返します。

// sample
int array[] = { 1, 2, 3, 4, 5 };
int n = count_if(array, array+5, stx::ge(3)); // n = 3

in_range_cc / range_cc

template<class T>
class in_range_cc : std::unary_function<T,bool> {
  T lo;
  T hi;
public:
  in_range_cc(const T& l, const T& h) : lo(l), hi(h) {}
  bool operator()(const T& x) const
    { return !(x < lo) && !(hi < x); }
};

bool operator()(const T& x) const

l <= x <= h ならtrueを返します。 l,h はコンストラクタに与えた値です。

// sample
int array[] = { 1, 2, 3, 4, 5 };
ostream_iterator<int> out(cout," ");
stx::in_range_cc<int> f(2,4);
stx::select_copy_if(array, array+5, out, f); // "2 3 4 "

template<class T>
in_range_cc<T>
range_cc(const T& lo, const T& hi) {
  return in_range_cc<T>(lo,hi);
}

in_range_cc<T>(lo,hi)を返します。

// sample
int array[] = { 1, 2, 3, 4, 5 };
ostream_iterator<int> out(cout," ");
stx::select_copy_if(array, array+5, out, stx::range_cc(2,4)); // "2 3 4 "

in_range_co / range_co

template<class T>
class in_range_co : std::unary_function<T,bool> {
  T lo;
  T hi;
public:
  in_range_co(const T& l, const T& h) : lo(l), hi(h) {}
  bool operator()(const T& x) const
    { return !(x < lo) &&  (x < hi); }
};

bool operator()(const T& x) const

l <= x < h ならtrueを返します。 l,h はコンストラクタに与えた値です。

// sample
int array[] = { 1, 2, 3, 4, 5 };
ostream_iterator<int> out(cout," ");
stx::in_range_co<int> f(2,4);
stx::select_copy_if(array, array+5, out, f); // "2 3 "

template<class T>
inline
in_range_co<T>
range_co(const T& lo, const T& hi) {
  return in_range_co<T>(lo,hi);
}

in_range_co<T>(lo,hi)を返します。

// sample
int array[] = { 1, 2, 3, 4, 5 };
ostream_iterator<int> out(cout," ");
stx::select_copy_if(array, array+5, out, stx::range_co(2,4)); // "2 3 "

in_range_oc / range_oc

template<class T>
class in_range_oc : std::unary_function<T,bool> {
  T lo;
  T hi;
public:
  in_range_oc(const T& l, const T& h) : lo(l), hi(h) {}
  bool operator()(const T& x) const
    { return  (lo < x) && !(hi < x); }
};

bool operator()(const T& x) const

l < x <= h ならtrueを返します。 l,h はコンストラクタに与えた値です。

// sample
int array[] = { 1, 2, 3, 4, 5 };
ostream_iterator<int> out(cout," ");
stx::in_range_oc<int> f(2,4);
stx::select_copy_if(array, array+5, out, f); // "3 4 "

template<class T>
in_range_oc<T>
range_oc(const T& lo, const T& hi) {
  return in_range_oc<T>(lo,hi);
}

in_range_co<T>(lo,hi)を返します。

// sample
int array[] = { 1, 2, 3, 4, 5 };
ostream_iterator<int> out(cout," ");
stx::select_copy_if(array, array+5, out, stx::range_oc(2,4)); // "3 4 "

in_range_oo / range_oo

template<class T>
class in_range_oo : std::unary_function<T,bool> {
  T lo;
  T hi;
public:
  in_range_oo(const T& l, const T& h) : lo(l), hi(h) {}
  bool operator()(const T& x) const
    { return  (lo < x) &&  (x < hi); }
};

bool operator()(const T& x) const

l < x < h ならtrueを返します。 l,h はコンストラクタに与えた値です。

// sample
int array[] = { 1, 2, 3, 4, 5 };
ostream_iterator<int> out(cout," ");
stx::in_range_oo<int> f(2,4);
stx::select_copy_if(array, array+5, out, f); // "3 "

template<class T>
in_range_oo<T>
range_oo(const T& lo, const T& hi) {
  return in_range_oo<T>(lo,hi);
}

in_range_oo<T>(lo,hi)を返します。

// sample
int array[] = { 1, 2, 3, 4, 5 };
ostream_iterator<int> out(cout," ");
stx::select_copy_if(array, array+5, out, stx::range_oo(2,4)); // "3 "

out_of_range_cc / nrange_cc

template<class T>
class out_of_range_cc : std::unary_function<T,bool> {
  T lo;
  T hi;
public:
  out_of_range_cc(const T& l, const T& h) : lo(l), hi(h) {}
  bool operator()(const T& x) const
    { return  (x < lo) ||  (hi < x); }
};

bool operator()(const T& x) const

l <= x <= h でないならtrueを返します。 l,h はコンストラクタに与えた値です。

// sample
int array[] = { 1, 2, 3, 4, 5 };
ostream_iterator<int> out(cout," ");
stx::out_of_range_cc<int> f(2,4);
stx::select_copy_if(array, array+5, out, f); // "1 5 "

template<class T>
out_of_range_cc<T>
nrange_cc(const T& lo, const T& hi) {
  return out_of_range_cc<T>(lo,hi);
}

out_of_range_cc<T>(lo,hi)を返します。

// sample
int array[] = { 1, 2, 3, 4, 5 };
ostream_iterator<int> out(cout," ");
stx::select_copy_if(array, array+5, out, stx::nrange_cc(2,4)); // "1 5 "

out_of_range_co / nrange_co

template<class T>
class out_of_range_co : std::unary_function<T,bool> {
  T lo;
  T hi;
public:
  out_of_range_co(const T& l, const T& h) : lo(l), hi(h) {}
  bool operator()(const T& x) const
    { return  (x < lo) || !(x < hi); }
};

bool operator()(const T& x) const

l <= x < h でないならtrueを返します。 l,h はコンストラクタに与えた値です。

// sample
int array[] = { 1, 2, 3, 4, 5 };
ostream_iterator<int> out(cout," ");
stx::out_of_range_co<int> f(2,4);
stx::select_copy_if(array, array+5, out, f); // "1 4 5 "

template<class T>
out_of_range_co<T>
nrange_co(const T& lo, const T& hi) {
  return out_of_range_co<T>(lo,hi);
}

out_of_range_co<T>(lo,hi)を返します。

// sample
int array[] = { 1, 2, 3, 4, 5 };
ostream_iterator<int> out(cout," ");
stx::select_copy_if(array, array+5, out, stx::nrange_co(2,4)); // "1 4 5 "

out_of_range_oc / nrange_oc

template<class T>
class out_of_range_oc : std::unary_function<T,bool> {
  T lo;
  T hi;
public:
  out_of_range_oc(const T& l, const T& h) : lo(l), hi(h) {}
  bool operator()(const T& x) const
    { return !(lo < x) ||  (hi < x); }
};

bool operator()(const T& x) const

l < x <= h でないならtrueを返します。 l,h はコンストラクタに与えた値です。

// sample
int array[] = { 1, 2, 3, 4, 5 };
ostream_iterator<int> out(cout," ");
stx::out_of_range_oc<int> f(2,4);
stx::select_copy_if(array, array+5, out, f); // "1 2 5 "

template<class T>
out_of_range_oc<T>
nrange_oc(const T& lo, const T& hi) {
  return out_of_range_oc<T>(lo,hi);
}

out_of_range_oc<T>(lo,hi)を返します。

// sample
int array[] = { 1, 2, 3, 4, 5 };
ostream_iterator<int> out(cout," ");
stx::select_copy_if(array, array+5, out, stx::nrange_oc(2,4)); // "1 2 5 "

out_of_range_oo / nrange_oo

template<class T>
class out_of_range_oo : std::unary_function<T,bool> {
  T lo;
  T hi;
public:
  out_of_range_oo(const T& l, const T& h) : lo(l), hi(h) {}
  bool operator()(const T& x) const
    { return !(lo < x) || !(x < hi); }
};

bool operator()(const T& x) const

l < x < h でないならtrueを返します。 l,h はコンストラクタに与えた値です。

// sample
int array[] = { 1, 2, 3, 4, 5 };
ostream_iterator<int> out(cout," ");
stx::out_of_range_oo<int> f(2,4);
stx::select_copy_if(array, array+5, out, f); // "1 2 4 5 "

template<class T>
out_of_range_oo<T>
nrange_oo(const T& lo, const T& hi) {
  return out_of_range_oo<T>(lo,hi);
}

out_of_range_oo<T>(lo,hi)を返します。

// sample
int array[] = { 1, 2, 3, 4, 5 };
ostream_iterator<int> out(cout," ");
stx::select_copy_if(array, array+5, out, stx::nrange_oo(2,4)); // "1 2 4 5 "

inv_minus

template<class T>
struct inv_minus : std::binary_function<T,T,T> {
  T operator()(const T& x, const T& y) const {
    return y - x;
  }
};

T operator()(const T& x, const T& y) const

y - x の結果を返します。

// sample
stx::inv_minus<int> f(2);
cout << f(3); // "1"

inv_divides

template<class T>
struct inv_divides : std::binary_function<T,T,T> {
  T operator()(const T& x, const T& y) const {
    return y / x;
  }
};

T operator()(const T& x, const T& y) const

y / x の結果を返します。

// sample
stx::inv_divides<int> f;
cout << f(2,6); // "3"

inv_modulus

template<class T>
struct inv_modulus : std::binary_function<T,T,T> {
  T operator()(const T& x, const T& y) const {
    return y % x;
  }
};

T operator()(const T& x, const T& y) const

y % x の結果を返します。

// sample
stx::inv_modulus<int> f;
cout << f(3,5); // "2"

unary_plus / u_plus

template<class T>
class unary_plus : std::unary_function<T,T> {
  T value;
public:
  explicit unary_plus(const T& v) : value(v) {}
  T operator()(const T& x) const
    { return x + value; }
};

bool operator()(const T& x) const

x + v の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_plus<int> f(2);
cout << f(3); // "5"

template<class T>
unary_plus<T>
u_plus(const T& v) {
  return unary_plus<T>(v);
}

unary_plus<T>(v)を返します。

// sample
int array[] = { 1, 2, 3 };
ostream_iterator<int> out(cout," ");
transform(array, array+3, out, stx::u_plus(2)); // "3 4 5 "

unary_minus / u_minus

template<class T>
class unary_minus : std::unary_function<T,T> {
  T value;
public:
  explicit unary_minus(const T& v) : value(v) {}
  T operator()(const T& x) const
    { return x - value; }
};

bool operator()(const T& x) const

x - v の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_minus<int> f(2);
cout << f(3); // "1"

template<class T>
unary_minus<T>
u_minus(const T& v) {
  return unary_minus<T>(v);
}

unary_minus<T>(v)を返します。

// sample
int array[] = { 1, 2, 3 };
ostream_iterator<int> out(cout," ");
transform(array, array+3, out, stx::u_minus(2)); // "-1 0 1 "

unary_inv_minus / u_iminus

template<class T>
class unary_inv_minus : std::unary_function<T,T> {
  T value;
public:
  explicit unary_inv_minus(const T& v) : value(v) {}
  T operator()(const T& x) const
    { return value - x; }
};

bool operator()(const T& x) const

v - x の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_inv_minus<int> f(2);
cout << f(3); // "-1"

template<class T>
unary_inv_minus<T>
u_iminus(const T& v) {
  return unary_inv_minus<T>(v);
}

unary_inv_minus<T>(v)を返します。

// sample
int array[] = { 1, 2, 3 };
ostream_iterator<int> out(cout," ");
transform(array, array+3, out, stx::u_iminus(2)); // "1 0 -1 "

unary_multiplies / u_multiplies

template<class T>
class unary_multiplies : std::unary_function<T,T> {
  T value;
public:
  explicit unary_multiplies(const T& v) : value(v) {}
  T operator()(const T& x) const
    { return x * value; }
};

bool operator()(const T& x) const

x * v の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_multiplies<int> f(2);
cout << f(3); // "6"

template<class T>
unary_multiplies<T>
u_multiplies(const T& v) {
  return unary_multiplies<T>(v);
}

unary_multiplies<T>(v)を返します。

// sample
int array[] = { 1, 2, 3 };
ostream_iterator<int> out(cout," ");
transform(array, array+3, out, stx::u_multiplies(2)); // "2 4 6 "

unary_divides / u_divides

template<class T>
class unary_divides : std::unary_function<T,T> {
  T value;
public:
  explicit unary_divides(const T& v) : value(v) {}
  T operator()(const T& x) const
    { return x / value; }
};

bool operator()(const T& x) const

x / v の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_divides<int> f(2);
cout << f(4); // "2"

template<class T>
unary_divides<T>
u_divides(const T& v) {
  return unary_divides<T>(v);
}

unary_divides<T>(v)を返します。

// sample
int array[] = { 1, 2, 3 };
ostream_iterator<int> out(cout," ");
transform(array, array+3, out, stx::u_multiplies(2)); // "0 1 1 "

unary_inv_divides / u_idivides

template<class T>
class unary_inv_divides : std::unary_function<T,T> {
  T value;
public:
  explicit unary_inv_divides(const T& v) : value(v) {}
  T operator()(const T& x) const
    { return value / x; }
};

bool operator()(const T& x) const

v / x の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_divides<int> f(4);
cout << f(2); // "2"

template<class T>
unary_inv_divides<T>
u_idivides(const T& v) {
  return unary_inv_divides<T>(v);
}

unary_inv_divides<T>(v)を返します。

// sample
int array[] = { 1, 2, 3 };
ostream_iterator<int> out(cout," ");
transform(array, array+3, out, stx::u_idivides(6)); // "6 3 2 "

unary_modulus / u_modulus

template<class T>
class unary_modulus : std::unary_function<T,T> {
  T value;
public:
  explicit unary_modulus(const T& v) : value(v) {}
  T operator()(const T& x) const
    { return x % value; }
};

bool operator()(const T& x) const

x % v の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_divides<int> f(3);
cout << f(4); // "1"

template<class T>
unary_modulus<T>
u_modulus(const T& v) {
  return unary_modulus<T>(v);
}

unary_modulus<T>(v)を返します。

// sample
int array[] = { 1, 2, 3 };
ostream_iterator<int> out(cout," ");
transform(array, array+3, out, stx::u_modulus(2)); // "1 0 1 "

unary_inv_modulus / u_imodulus

template<class T>
class unary_inv_modulus : std::unary_function<T,T> {
  T value;
public:
  explicit unary_inv_modulus(const T& v) : value(v) {}
  T operator()(const T& x) const
    { return value % x; }
};

bool operator()(const T& x) const

v % x の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_divides<int> f(3);
cout << f(4); // "3"

template<class T>
unary_inv_modulus<T>
u_imodulus(const T& v) {
  return unary_inv_modulus<T>(v);
}

unary_inv_modulus<T>(v)を返します。

// sample
int array[] = { 1, 2, 3 };
ostream_iterator<int> out(cout," ");
transform(array, array+3, out, stx::u_imodulus(2)); // "1 0 2 "

bitwise_and

template<class T>
struct bitwise_and : std::binary_function<T,T,T> {
  T operator()(const T& x, const T& y) const
    { return x & y; }
};

T operator()(const T& x, const T& y) const

x & y の結果を返します。

// sample
stx::bitwise_and<int> f;
cout << showbase << hex << f(0x03,0x75); // "0x1"

bitwise_or

template<class T>
struct bitwise_or : std::binary_function<T,T,T> {
  T operator()(const T& x, const T& y) const
    { return x | y; }
};

T operator()(const T& x, const T& y) const

x | y の結果を返します。

// sample
stx::bitwise_or<int> f;
cout << showbase << hex << f(0x03,0x75); // "0x77"

bitwise_xor

template<class T>
struct bitwise_xor : std::binary_function<T,T,T> {
  T operator()(const T& x, const T& y) const
    { return x ^ y; }
};

T operator()(const T& x, const T& y) const

x ^ y の結果を返します。

// sample
stx::bitwise_xor<int> f;
cout << showbase << hex << f(0x03,0x75); // "0x76"

bitwise_not

template<class T>
struct bitwise_not : std::unary_function<T,T> {
  T operator()(const T& x) const
    { return ~x; }
};

T operator()(const T& x, const T& y) const

~x の結果を返します。

// sample
stx::bitwise_not<int> f;
cout << showbase << hex << f(0x03); // "0xfffffffc"

unary_bitwise_and / and_mask

template<class T>
class unary_bitwise_and : std::unary_function<T,T> {
  T value;
public:
  explicit unary_bitwise_and(const T& v) : value(v) {}
  T operator()(const T& x) const
    { return x & value; }
};

T operator()(const T& x) const

x & v の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_bitwise_and<int> f(0x03);
cout << showbase << hex << f(0x75); // "0x1"

template<class T>
unary_bitwise_and<T>
and_mask(const T& x) {
  return unary_bitwise_and<T>(x);
}

unary_bitwise_and<T>(x) を返します。

// sample
int array[] = { 4, 5, 6 };
ostream_iterator<int> out(cout," ");
transform(array, array+3, out, stx::and_mask(0x03)); // "0 1 2 "

unary_bitwise_or / or_mask

template<class T>
class unary_bitwise_or : std::unary_function<T,T> {
  T value;
public:
  explicit unary_bitwise_or(const T& v) : value(v) {}
  T operator()(const T& x) const
    { return x | value; }
};

T operator()(const T& x) const

x | v の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_bitwise_or<int> f(0x03);
cout << showbase << hex << f(0x75); // "0x77"

template<class T>
unary_bitwise_or<T>
or_mask(const T& x) {
  return unary_bitwise_or<T>(x);
}

unary_bitwise_or<T>(x) を返します。

// sample
int array[] = { 4, 5, 6 };
ostream_iterator<int> out(cout," ");
transform(array, array+3, out, stx::or_mask(0x03)); // "7 7 7 "

unary_bitwise_xor / xor_mask

template<class T>
class unary_bitwise_xor : std::unary_function<T,T> {
  T value;
public:
  explicit unary_bitwise_xor(const T& v) : value(v) {}
  T operator()(const T& x) const
    { return x ^ v_; }
};

T operator()(const T& x) const

x ^ v の結果を返します。 v はコンストラクタに与えた値です。

// sample
stx::unary_bitwise_xor<int> f(0x03);
cout << showbase << hex << f(0x75); // "0x76"

template<class T>
unary_bitwise_xor<T>
xor_mask(const T& x) {
  return unary_bitwise_xor<T>(x);
}

unary_bitwise_xor<T>(x) を返します。

// sample
int array[] = { 4, 5, 6 };
ostream_iterator<int> out(cout," ");
transform(array, array+3, out, stx::xor_mask(0x03)); // "7 6 5 "

unary_compose / compose1

template<class UnaryFunction1, class UnaryFunction2>
class unary_compose
  : public std::unary_function<UnaryFunction2::argument_type,
                               UnaryFunction1::result_type> {
protected:
  UnaryFunction1 fn1_;
  UnaryFunction2 fn2_;
public:
  unary_compose(const UnaryFunction1& f1, const UnaryFunction2& f2)
    : fn1_(f1), fn2_(f2) {}
  result_type operator()(const argument_type& x) const
    { return fn1_(fn2_(x)); }
};

result_type operator()(const argument_type& x) const

f1(f2(x)) の結果を返します。f1,f2はコンストラクタに与えた関数オブジェクトです。

// sample
template<class T>
struct square : unary_function<T,T>
{ T operator()(const T& x) const { return x * x; } };

stx::unary_compose< negate<int>,square<int> >
  f(negate<int>(), square<int>());
cout << f(3); // "-9"

template<class UnaryFunction1, class UnaryFunction2>
unary_compose<UnaryFunction1,UnaryFunction2>
compose1(const UnaryFunction1& fn1, const UnaryFunction2& fn2) {
  return unary_compose<UnaryFunction1,UnaryFunction2>(fn1,fn2);
}

unary_compose<UnaryFunction1,UnaryFunction2>(fn1,fn2)を返します。

// sample
template<class T>
struct square : unary_function<T,T>
{ T operator()(const T& x) const { return x * x; } };

int array[] = { 1, 2, 3 };
ostream_iterator<int> out(cout," ");
transform(array, array+3, out, stx::compose1(negate<int>(),square<int>()) ); // &-1 -4 -9 &

binary_compose / compose2

template<class BinaryFunction1, class UnaryFunction2, class UnaryFunction3>
class binary_compose
  : public std::unary_function<typename UnaryFunction2::argument_type,
                               typename BinaryFunction1::result_type> {
protected:
  BinaryFunction1 fn1_;
  UnaryFunction2 fn2_;
  UnaryFunction3 fn3_;
public:
  binary_compose(const BinaryFunction1& f1,
                 const UnaryFunction2& f2, const UnaryFunction3& f3)
    : fn1_(f1), fn2_(f2), fn3_(f3) { }
  result_type operator()(const argument_type& x) const
    { return fn1_(fn2_(x), fn3_(x)); }
};

result_type operator()(const argument_type& x)const

f1(f2(x),f3(x)) の結果を返します。f1,f2はコンストラクタに与えた関数オブジェクトです。

// sample
template<class T>
struct square : unary_function<T,T>
{ T operator()(const T& x) const { return x * x; } };

stx::binary_compose< plus<int>,square<int>,negate<int> >
  f(plus<int>(),square<int>(),negate<int>()); // f(x) = x*x - x
cout << f(3) << endl; // "6"

template<class BinaryFunction1, class UnaryFunction2, class UnaryFunction3>
binary_compose<BinaryFunction1,UnaryFunction2,UnaryFunction3>
compose2(const BinaryFunction1& f1,
         const UnaryFunction2& f2, const UnaryFunction3& f3) {
  return binary_compose<BinaryFunction1,UnaryFunction2,UnaryFunction3>(f1,f2,f3);
}

binary_compose<BinaryFunction1,UnaryFunction2,UnaryFunction3>(f1,f2,f3)を返します。

// sample
template<class T>
struct square : unary_function<T,T>
{ T operator()(const T& x) const { return x * x; } };

int array[] = { 1, 2, 3 };
ostream_iterator<int> out(cout," ");
transform(array, array+3, out,
          stx::compose2(plus<int>(),square<int>(),negate<int>()) ); // "0 2 6 "

unary_tern / tern1

template<class Predicate, class Function1, class Function2>
class unary_tern : public std::unary_function<Predicate::argument_type, Function1::result_type> {
  Predicate pr_;
  Function1 f1_;
  Function2 f2_;
public:
  explicit unary_tern(const Predicate& pr, const Function1& f1, const Function2& f2)
    : pr_(pr), f1_(f1), f2_(f2) {}
  result_type operator()(const argument_type& x) const
    { return pr_(x) ? f1_(x) : f2_(x); }
};

result_type operator()(const argument_type& x)

pr(x) が真なら f1(x) を、偽なら f2(x) を返します。 pr, f1, f2 はコンストラクタに与えた関数オブジェクトです。

// sample
template<class T>
struct square : unary_function<T,T>
{ T operator()(const T& x) const { return x * x; } };

stx::unary_tern< stx::unary_less<int>, negate<int>, square<int> >
  f(stx::unary_less<int>(0), negate<int>(), square<int>());
cout << f(-2) << endl; // "2"
cout << f(2) << endl; // "4"

template<class Predicate, class Function1, class Function2>
unary_tern<Predicate,Function1,Function2>
tern1(const Predicate& pr, const Function1& f1, const Function2& f2) {
  return unary_tern<Predicate,Function1,Function2>(pr,f1,f2);
}

unary_tern<Predicate,Function1,Function2>(pr,f1,f2) を返します。

// sample
template<class T>
struct square : unary_function<T,T>
{ T operator()(const T& x) const { return x * x; } };

int array[] = { -2, 0, 2 };
ostream_iterator<int> out(cout," ");
transform(array, array+3, out,
          stx::tern1(stx::unary_less<int>(0), negate<int>(), square<int>()) ); // "2 0 4 "

binary_tern / tern2

template<class Predicate, class Function1, class Function2>
class binary_tern : public std::binary_function<Predicate::first_argument_type,
                                Predicate::second_argument_type,
                                Function1::result_type> {
  Predicate pr_;
  Function1 f1_;
  Function2 f2_;
public:
  explicit binary_tern(const Predicate& pr, const Function1& f1, const Function2& f2)
    : pr_(pr), f1_(f1), f2_(f2) {}
  result_type operator()(const first_argument_type& x, const second_argument_type& y) const
    { return pr_(x,y) ? f1_(x,y) : f2_(x,y); }
};

result_type operator()(const first_argument_type& x,
const second_argument_type& y) const

pr(x,y) が真なら f1(x,y) を、偽なら f2(x,y) を返します。 pr, f1, f2 はコンストラクタに与えた関数オブジェクトです。

// sample
stx::binary_tern< less<int>, stx::inv_minus<int>, minus<int> >
  f(less<int>(), stx::inv_minus<int>(), minus<int>());
cout << f(1,3) << endl; // "2"
cout << f(3,1) << endl; // "2"

template<class Predicate, class Function1, class Function2>
binary_tern<Predicate,Function1,Function2>
tern2(const Predicate& pr, const Function1& f1, const Function2& f2) {
  return binary_tern<Predicate,Function1,Function2>(pr,f1,f2);
}

binary_tern<Predicate,Function1,Function2>(pr,f1,f2) を返します。

// sample
int array1[] = { 1, 2, 3 };
int array2[] = { 3, 2, 1 };
ostream_iterator<int> out(cout," ");
transform(array1, array1+3, array2, out,
          stx::tern2(less<int>(), stx::inv_minus<int>(), minus<int>()) ); // "2 0 2 "

Posted in misc | No Comments »

stx::bag<Key,Compare,Allocator>

Wednesday, April 5th, 2006

‘bag’について

‘bag’とはmultisetとmapの’あいのこ’です。multisetは要素の重複を許します。たとえば、

multiset<int> ints;
for ( int i = 0; i < 1000; ++i )
  ints.insert(1);

このコードでは、intsの中に1が1000個格納されます。

ここに紹介するクラス’bag’は要素とその個数を管理することにより、格納される要素の個数を最小限に抑えるコンテナです。

bagによる金種計算プログラムを書いてみました。

/*
 * bag demonstration : 金種計算
 */

#include <iostream>       // cout, endl
#include <iomanip>        // setw
#include <set>            // set<T>
#include "bag" // bag<T>

using namespace std;
using namespace stx;

int main() {

  set<int> cash;
  cash.insert(10000);  // 1万円札
  cash.insert( 5000);  // 5千円札
//cash.insert( 2000);  // 2千円札
  cash.insert( 1000);  //  千円札
  cash.insert(  500);  // 5百円玉
  cash.insert(  100);  //  百円玉
  cash.insert(   50);  //  50円玉
  cash.insert(   10);  //  10円玉
  cash.insert(    5);  //   5円玉
  cash.insert(    1);  //   1円玉

  bag<int> kind;

  while ( true ) {
    int price;
    cout << "金額を入力してください (0 で終了) :" << flush;
    cin >> price;
    if ( price <= 0 ) break;
    for ( set<int>::reverse_iterator it = cash.rbegin();
          it != cash.rend(); ++it ) {
      int n = price / *it;
      price %= *it;
      kind.insert_n(n, *it);
      if ( n > 0 ) cout << setw(5) << *it << " : "
                        << setw(3) << n << endl;
    }
  }

  cout << "総計..." << endl;
  for ( set<int>::reverse_iterator it = cash.rbegin();
          it != cash.rend(); ++it ) {
    cout << setw(5) << *it << " : "
         << setw(3) << kind.count(*it) << endl;
  }

  return 0;
}

コンストラクタ

explicit bag(const Compare& comp =Compare(), const Allocator& alloc =Allocator());

デフォルトコンストラクタ。

// sample
bag<string> b;
int n = b.size(); // n = 0

template<class InputIterator>
bag(InputIterator first, InputIterator last, const Compare& comp=Compare(), const Allocator& alloc =Allocator());

シーケンス[first,last)からなるbagを作ります。

// sample
string s = "hello";
bag<char> b(s.begin(), s.end()); // b = { e h l l o }

bag(const bag& x);

コピーコンストラクタ。 x の全要素がコピーされます。

// sample
bag<string> b1;
b1.insert_n(2,"apple");
b1.insert("banana"); // b1 = { apple apple banana }
bag<string> b2(b1);// b2 = { apple apple banana }

デストラクタ

~bag();

デストラクタ。全要素を廃棄します。

コピー

bag& operator=(const bag& x );

全要素を廃棄し、新たに x の全要素がコピーされます。

// sample
bag<string> b1;
bag<string> b2;
b1.insert_n(2,"apple");
b1.insert("banana"); // b1 = { apple apple banana }
b2 = b1;// b2 = { apple apple banana }

イテレータ

iterator begin();
const_iterator begin() const;

最初の要素を指すイテレータを返します。

iterator end();
const_iterator end() const;

最後の要素の直後を指すイテレータを返します。

// sample
bag<string> b;
b.insert_n(2,"apple");
b.insert("banana");
bag<string>::iterator i = b.begin();
while ( i != b.end() ) { // output : apple apple banana
  cout << *i << ' ';
  ++i;
}

reverse_iterator rbegin();
const_reverse_iterator rbegin() const;

最後の要素の直後を指す反転イテレータを返します。

reverse_iterator rend();
const_reverse_iterator rend() const;

最初の要素を指す反転イテレータを返します。

// sample
bag<string> b;
b.insert_n(2,"apple");
b.insert("banana");
bag<string>::reverse_iterator i = b.rbegin();
while ( i != b.rend() ) { // output : banana apple apple
  cout << *i << ' ';
  ++i;
}

empty / size / max_size

bool empty() const;

要素数が 0 なら true を返します。

// sample
bag<string> b;
bool t0 = b.empty(); // t0 = true
b.insert("apple");
bool t1 = b.empty(); // t1 = false

size_type size() const;

要素数を返します。

// sample
bag<string> b;
b.insert_n(2,"apple");
b.insert("banana");
int s = b.size(); // s = 3

size_type max_size() const;

格納できる最大要素数を返します。

insert

void insert_n(iterator position, size_type n, const key_type& x);

要素 x を n 個追加します。 position に意味はありません。

// sample
bag<string> b;
b.insert_n(b.begin(), 5, "apple"); // "apple"を5個追加
int s = b.size() // s = 5

void insert(iterator position, const key_type& x);

要素 x を 1 個追加します。 position に意味はありません。

// sample
bag<string> b;
b.insert(b.begin(), "apple"); // "apple"を1個追加
int s = b.size() // s = 1

void insert_n(size_type n, const key_type& x);

要素 x を n 個追加します。

// sample
bag<string> b;
b.insert_n(5, "apple"); // "apple"を5個追加
int s = b.size() // s = 5

void insert(const key_type& x);

要素 x を 1 個追加します。

// sample
bag<string> b;
b.insert("apple"); // "apple"を1個追加
int s = b.size() // s = 1

template<class InputIterator>
void insert(InputIterator first, InputIterator last);

シーケンス[first,last)を追加します。

// sample
string s = "hello";
bag<char> b;
b.insert(s.begin(), s.end()); // b = { e h l l o }

erase / clear / swap

void erase(iterator position);

position が指す要素を削除します。

// sample
bag<string> b;
b.insert_n(3,"apple");
b.erase(b.begin()); // 最初の要素を削除
int s = b.size(); // s = 2

size_type erase_all(const key_type& x);

x と等しい要素をすべて削除します。削除した数を返します。

// sample
bag<string> b;
b.insert_n(3,"apple");
b.erase_all("apple"); // "apple"をすべて削除
int n = b.count("apple"); // n = 0

size_type erase_n(size_type n, const key_type& x);

x と等しい要素を最大 n 個削除します。削除した数を返します。

// sample
bag<string> b;
b.insert_n(3,"apple");
b.erase_n(2,"apple"); // "apple"を2個削除
int n = b.count("apple"); // n = 1

size_type erase(const key_type& x);

x と等しい要素を最大 1 個削除します。削除した数を返します。

// sample
bag<string> b;
b.insert_n(3,"apple");
b.erase("apple"); // "apple"を1個削除
int n = b.count("apple"); // n = 2

void erase(iterator first, iterator last);

シーケンス[first,last)を削除します。

// sample
bag<string> b;
b.insert_n(2,"apple");
b.insert_n(2,"banana");
b.insert_n(2,"cherry"); // b = { apple apple banana banana cherry cherry }
bag<string>::iterator f = b.find("banana");
bag<string>::iterator l = b.find("cherry"); ++l; // [f,l) = { banana banana cherry }
b.erase(f,l); // b = { apple apple cherry }

void clear();

全要素を削除します。erase(begin(), end()) と等価です。

// sample
bag<string> b;
b.insert("apple");
b.insert("banana"); // b = { apple banana }
b.clear(); // b = { }
int s = b.size(); // s = 0

void swap(bag& x);

*this と x の全要素を交換します。

// sample
bag<string> b1;
b1.insert_n("apple"); // b1 = { apple apple }
bag<string> b2;
b2.insert_n("banana"); // b2 = { banana banana }
b1.swap(b2); // b1 = { banana banana } , b2 = { apple apple }

replace / unique / unique_copy

bool replace(const key_type& x);

x と等しい要素を x に置き換えます。x と等しい要素がないときは false を返します。

// sample
struct abs_less : binary_function<int,int,bool> {
  // 絶対値で比較
  bool operator()(int x, int y) const
    { return abs(x) < abs(y); }
};

bag<int,abs_less> b;
b.insert(1);
b.insert(2);
b.insert(-2); // b = { 1 2 2 }
b.replace(-2); // b = { 1 -2 -2 }

bool unique(const key_type& x);

x と等しい要素の個数を 1 にします。x と等しい要素がないときは false を返します。

// sample
bag<string> b;
b.insert_n(2,"apple");
b.insert("apple");
b.insert("banana"); // b = { apple apple apple banana }
b.unique("apple"); // b = { apple banana }
int n = b.count("apple"); // n = 1

void unique();

全要素の個数を 1 にします。

// sample
bag<string> b;
b.insert_n(3,"apple");
b.insert("banana"); // b = { apple apple apple banana }
b.unique(); // b = { apple banana }
int s = b.size(); // s = 2

template<class OutputIterator>
OutputIterator unique_copy(OutputIterator result) const;

unique()の結果が [result,RET) にコピーされます(*thisの内容は変化しません)。RETはこの関数の戻り値です。

// sample
bag<string> b;
b.insert_n(3,"apple");
b.insert("banana"); // b = { apple apple apple banana }
vector<string> v;
b.unique_copy(back_inserter(v)); // v = { apple banana }

count / entries / find /lower_bound / upper_bound / equal_range

size_type count(const key_type& x) const;

x と等しい要素の個数を返します。

// sample
bag<string> b;
b.insert_n(2,"apple");
b.insert("apple");
b.insert("banana"); // b = { apple apple apple banana }
int n = b.count("apple"); // n = 3

size_type entries() const;

互いに異なる要素の個数を返します。

// sample
bag<string> b;
b.insert_n(3,"apple");
b.insert("banana"); // b = { apple apple apple banana }
int n = b.entries(); // n = 2

iterator find(const key_type& x) const;

x と等しい要素を指すイテレータを返します。見つからないときはend()を返します。

// sample
bag<string> b;
b.insert("apple");
b.insert("apple");
b.insert("banana"); // b = { apple apple banana }
bag<string>::iterator i = b.find("apple"); // *i = apple
if ( i != b.end() ) cout << *i << endl;

iterator lower_bound(const key_type& x) const;

x より小さくない最初の要素を指すイテレータを返します。

iterator upper_bound(const key_type& x) const;

x より大きい最初の要素を指すイテレータを返します。

// sample
bag<string> b;
b.insert_n(2,"apple");
b.insert_n(2,"banana");
b.insert_n(2,"cherry"); // b = { apple apple banana banana cherry cherry }
bag<string>::iterator l = b.lower_bound("banana"); // *l = banana
bag<string>::iterator u = b.upper_bound("banana"); // *u = cherry
// [l,u) = { banana banana }

std::pair<iterator,iterator>
equal_range(const key_type& x) const;

lower_bound(x), upper_boud(x)の組を返します。

// sample
bag<string> b;
b.insert_n(2,"apple");
b.insert_n(2,"banana");
b.insert_n(2,"cherry"); // b = { apple apple banana banana cherry cherry }
std::pair<bag<string>::iterator,bag<string>::iterator> r
  = b.equal_range("banana");
// [r.first, r.second) = { banana banana }

ソースコード

#ifndef __STX_BAG_H__
#define __STX_BAG_H__

/*
 * 'bag' class template
 *
 * Microsoft Visual C++ v6.0
 * でのコンパイル/実行を確認した。
 *
 *          επιστημη
 */

#include <set>

namespace stx {

  template<class Key, class Compare=std::less<Key>, class Allocator=std::allocator<std::pair<Key,size_t> > >
  class bag {

  public:

    typedef Key                               key_type;
    typedef key_type                          value_type;

  private:

    /* bag<Key> はその内部に set< pair<Key,size_t> > を内包することで要素とその個数を管理する。
     * このとき、set< pair<Key,size_t> > に与える比較オブジェクトは
     * pair<Key,size_t>.first すなわち Key を比較対象としなければならない。
     */
    struct bag_compare {

      Compare comp;

      bag_compare(Compare c)
        : comp(c) {}

      typename Compare::result_type operator()(const std::pair<Key,size_t>& x, const std::pair<Key,size_t>& y) const
        { return comp(x.first, y.first); }

    };

  public:

    typedef std::set<std::pair<Key,size_t>, bag_compare, Allocator> container;
    typedef container::difference_type        difference_type;

    // const_iterator

    class const_iterator : public std::iterator<std::bidirectional_iterator_tag, key_type,difference_type> {

      friend bag;
      container::const_iterator i;
      size_t              c;

      explicit const_iterator(container::const_iterator ci, size_t cc)
        : i(ci), c(cc) {}

    public:

      const_iterator()
        {}

      const_iterator(const const_iterator& it)
        : i(it.i), c(it.c) {}

      const value_type& operator*() const
        { return i->first; }

      const value_type* operator->() const
        { return &(i->first); }

      const_iterator& operator++()
        { if ( i->second <= c ) { ++i; c = 1; } else ++c; return *this; }

      const_iterator operator++(int)
        { const_iterator tmp(*this); ++(*this); return tmp; }

      const_iterator& operator--()
        { if ( c <= 1 ) { --i; c = i->second; } else --c; return *this; }

      const_iterator operator--(int)
        { const_iterator tmp(*this); --(*this); return tmp; }

      bool operator==(const const_iterator& x) const
        { return i == x.i && c == x.c; }

      bool operator!=(const const_iterator& x) const
        { return i != x.i || c != x.c; }

    };

    // const_reverse_iteartor

    class const_reverse_iterator : std::iterator<std::bidirectional_iterator_tag,key_type,difference_type> {

      friend bag;
      container::const_iterator i;
      size_t c;

      explicit const_reverse_iterator(container::const_iterator ci, size_t cc)
        : i(ci), c(cc) {}

    public:

      const_reverse_iterator()
        {}

      const_reverse_iterator(const const_reverse_iterator& it)
        : i(it.i), c(it.c) {}

      const value_type& operator*()
        { const_reverse_iterator tmp(*this); ++tmp; return tmp.i->first; }

      const value_type* operator->()
        { const_reverse_iterator tmp(*this); ++tmp; return &tmp.i->first; }

      const_reverse_iterator& operator++()
        { if ( c <= 1 ) { --i; c = i->second; } else --c; return *this; }

      const_reverse_iterator operator++(int)
        { const_reverse_iterator tmp(*this); ++(*this); return tmp; }

      const_reverse_iterator& operator--()
        { if ( i->second <= c ) { ++i; c = 1 } else ++c; return *this; }

      const_reverse_iterator operator--(int)
        { const_reverse_iterator tmp(*this); --(*this); return tmp; }

      bool operator==(const const_reverse_iterator& x) const
        { return i == x.i && c == x.c; }

      bool operator!=(const const_reverse_iterator& x) const
        { return i != x.i || c != x.c; }

    };

    // iterator / reverse_iterator

    /* イテレータを介してbag内の要素を書き換えることは(要素の大小関係を狂わせるので)許されない。
     * したがって、const_iterator / reverse_const_iterator のみを定義し、
     * iterator / reverse_iterator は それぞれ
     * const_iterator / reverse_const_iterator の typedef である。
     */
    typedef const_iterator                          iterator;
    typedef const_reverse_iterator                  reverse_iterator;

    // types:

    typedef container::key_compare            key_compare;
    typedef container::value_compare          value_compare;
    typedef container::allocator_type         allocator_type;
    typedef container::reference              reference;
    typedef container::const_reference        const_reference;
    typedef container::size_type              size_type;

    // constructor/copy/destroy:

    explicit bag(const Compare& comp =Compare(), const Allocator& alloc =Allocator())
      : c(value_compare(comp),alloc) {}

    template<class InputIterator>
    bag(InputIterator first, InputIterator last, const Compare& comp=Compare(), const Allocator& alloc =Allocator())
      : c(value_compare(comp),alloc) { for ( ;first != last; ++first ) insert(*first); }

    bag(const bag& x)
      { c = x.c; }

    bag& operator=(const bag& x )
      { c = x.c; return *this; }

    ~bag()
      {}

    allocator_type get_allocator() const
      { return c.get_allocator(); }

    // iterators:

    iterator begin()
      { return iterator(c.begin(),1); }

    const_iterator begin() const
      { return const_iterator(c.begin(),1); }

    reverse_iterator rbegin()
      { return reverse_iterator(c.end(),1); }

    const_reverse_iterator rbegin() const
      { return const_reverse_iterator(c.end(),1); }

    iterator end()
      { return iterator(c.end(),1); }

    const_iterator end() const
      { return const_iterator(c.end(),1); }

    reverse_iterator rend()
      { return reverse_iterator(c.begin(),1); }

    const_reverse_iterator rend() const
      { return const_reverse_iterator(c.end(),1); }

    // capacity:

    bool empty() const
      { return c.empty(); }

    /* 以下の実装では、size() の時間計算量が O(N)となり、望ましくない...
     */
    size_type size() const
      { size_type n = 0;
        for ( container::iterator it = c.begin(); it != c.end(); ++it )
          n += it->second;
        return n;
      }

    size_type max_size() const
      { return c.max_size(); }

    // insert:

    void insert_n(iterator position, size_type n, const key_type& x)
      { if ( n == 0 ) return;
	    container::key_type tmp(x,n);
        container::iterator it = c.find(tmp);
        if ( it == c.end() ) c.insert(position.i, tmp);
        else const_cast<size_t&>(it->second) += n;
      }

    void insert(iterator position, const key_type& x)
      { insert_n(position, 1, x); }

    void insert_n(size_type n, const key_type& x)
      { insert_n(begin(), n, x); }

    void insert(const key_type& x)
      { insert_n(begin(), 1, x); }

    template<class InputIterator>
    void insert(InputIterator first, InputIterator last)
      { for ( ;first != last; ++first ) insert(*first); }

    // erase:

/*  stdc++ では set::erase(iterator) の戻り値は void であるため、
 *  以下の実装は誤りである...
 *
 *  iterator erase(iterator position)
 *    { container::iterator it = position.i;
 *      if ( it->second <= 1 ) { it = c.erase(it); return iterator(it,1); }
 *      else { --const_cast<size_t&>(it->second); ++position; }
 *      return position;
 *    }
 */
    void erase(iterator position)
      { container::iterator it = position.i;
        if ( it->second <= 1 ) c.erase(it);
        else --const_cast<size_t&>(it->second);
      }

    size_type erase_all(const key_type& x)
      { size_type n = 0;
        container::iterator it = c.find(container::value_type(x,1));
        if ( it != c.end() ) { n = it->second; c.erase(it); }
        return n;
      }

    size_type erase_n(size_type n, const key_type& x)
      { if ( n == 0 ) return 0;
	    container::iterator it = c.find(container::value_type(x,1));
        if ( it != c.end() ) {
          size_type t = it->second;
          if ( t <= n ) { c.erase(it); n = t; }
          else const_cast<size_t&>(it->second) -= n;
        }
        return n;
      }

    size_type erase(const key_type& x)
      { return erase_n(1,x); }

/*  stdc++ では set::erase(iterator) の戻り値は void であるため、
 *  以下の実装は誤りである...
 *
 *  void erase(iterator first, iterator last)
 *    { while ( first != last ) first = erase(first); }
 */

    void erase(iterator first, iterator last)
      { container tmp(c.key_comp(), c.get_allocator());
        container::iterator i;
        for( ; first != last; ++first ) {
          container::value_type v(*first,1);
          i = tmp.find(v);
          if ( i == tmp.end() ) tmp.insert(v);
          else ++const_cast<size_t&>(i->second);
        }
        for ( i = tmp.begin(); i != tmp.end(); ++i )
          erase(i->second, i->first);
      }

    // other modifiers:

    void swap(bag& x)
      { c.swap(x.c); }

    void clear()
      { c.clear(); }

    // observers:

    key_compare key_comp() const
      { return c.key_comp(); }

    value_compare value_comp() const
      { return c.value_comp(); }

    // bag operations:

    bool replace(const key_type& x)
      { container::iterator it = c.find(container::key_type(x,1));
        if ( it != c.end() ) const_cast<key_type&>(it->first) = x;
        return it != c.end();
      }

    void unique()
      { for ( container::iterator it = c.begin(); it != c.end(); ++it )
          const_cast<size_t&>(it->second) = 1;
      }

    template<class OutputIterator>
    OutputIterator unique_copy(OutputIterator result) const
      { for ( container::const_iterator it = c.begin(); it != c.end(); ++it ) {
          *result = it->first;
          ++result;
        }
        return result;
      }

    size_type count(const key_type& x) const
      { container::const_iterator it = c.find(container::value_type(x,1));
        return it == c.end() ? 0 : it->second;
      }

    size_type entries() const
      { return c.size(); }

    iterator find(const key_type& x) const
      { return iterator(c.find(container::value_type(x,1)),1); }

    iterator lower_bound(const key_type& x) const
      { return iterator(c.lower_bound(container::value_type(x,1)),1); }

    iterator upper_bound(const key_type& x) const
      { return iterator(c.upper_bound(container::value_type(x,1)),1); }

    std::pair<iterator,iterator>
    equal_range(const key_type& x) const
      { std::pair<container::iterator,container::iterator> r = c.equal_range(container::value_type(x,1));
        return std::pair<iterator,iterator>(iterator(r.first,1),iterator(r.second,1));
      }

    // rel-ops:

    friend bool operator==(const bag& x, const bag& y)
      { return x.c == y.c; }

    friend bool operator!=(const bag& x, const bag& y)
      { return x.c != y.c; }

    friend bool operator<(const bag& x, const bag& y)
      { return x.c < y.c; }

    friend bool operator<=(const bag& x, const bag& y)
      { return x.c <= y.c; }

    friend bool operator>(const bag& x, const bag& y)
      { return x.c > y.c; }

    friend bool operator>=(const bag& x, const bag& y)
      { return x.c >= y.c; }

    // swap:

    friend void swap(bag& x, bag& y)
      { x.c.swap(y.c); }

  protected:

    container c;

  };

}

#endif

Posted in misc | No Comments »

<stx/algorithm>

Wednesday, April 5th, 2006

DDJ-J 1998年5月号で紹介したSTL拡張コンポーネント”STX”の改版です。
初版で定義した関数のうち、使用頻度の少ないもの、
既存のアルゴリズムで簡単に置き換えられるものを除き、新たにいくつか追加しました。

for_each
for_each_backward
find_last
find_last_if
find_backward
find_backward_if
binary_find
some
some_if
every
every_if
select_copy
select_copy_if
transform_if
inject_1st
inject_2nd
partition_copy
is_sorted
lexicographical_compare_3way

for_each

template<class InputIterator1,
           class InputIterator2,
           class BinaryFunction>
  BinaryFunction
  for_each(InputIterator1 first1,
           InputIterator1 last1,
           InputIterator2 first2,
           BinaryFunction f)
  {
    while ( first1 != last1 ) {
      f(*first1,*first2);
      ++first1;
      ++first2;
    }
    return f;
  }

0 <= i < (last-first) に対し、f(*(first1+i), *(first2+i)) を行ないます。このとき f() の戻り値は棄てられます。

// sample
void f(int x, int y) {
  cout << (x*y) << endl;
}

vector<int> v;
list<int> l;
for ( int i = 1; i < 10; ++i ) {
  v.push_back(i);
  l.push_back(i);
}
// 1*1 2*2 ... 9*9 の答を出力
stx::for_each(v.begin(), v.end(), l.begin(), l.end(), f);

for_each_backward

  template<class BidirectionalIterator,
           class UnaryFunction>
  UnaryFunction
  for_each_backward(BidirectionalIterator first,
                    BidirectionalIterator last,
                    UnaryFunction f)
  {
    while ( first != last ) {
      --last;
      f(*last);
    }
    return f;
  }

std::for_each(first,last,f)の逆順すなわち、

 f(*(last-1));
 f(*(last-2));
 ...
 f(*first);

を行ないます。

// sample
void f(int x, int y) {
  cout << (x*y) << endl;
}

vector<int> v;
list<int> l;
for ( int i = 1; i < 10; ++i ) {
  v.push_back(i);
  l.push_back(i);
}
// 9*9 8*8 ... 1*1の答を出力
stx::for_each_backward(v.begin(), v.end(), l.begin(), l.end(), f);

find_last

template<class InputIterator,
           class T>
  InputIterator
  find_last(InputIterator first,
            InputIterator last,
            const T&      value)
  {
    InputIterator it = first;
    while ( first != last ) {
      if ( *first == value ) {
        it = first;
      }
      ++first;
    }
    return it;
  }

first <= i < last に対し、*i == value となる最後のiを返します。該当する i が見つからないときは last を返します。※必ず(last – first)回の比較が行なわれます。

// sample
int array[] = { 0, 1, 2, 4, 5 };
int* p = stx::find_last(array, array+5, 4);
cout << (p-array) << endl; // p = &array[3]

find_last_if

template<class InputIterator,
           class UnaryPredicate>
  InputIterator
  find_last_if(InputIterator  first,
               InputIterator  last,
               UnaryPredicate pred)
  {
    InputIterator it = first;
    while ( first != last ) {
      if ( pred(*first) ) {
        it = first;
      }
      ++first;
    }
    return it;
  }

first <= i < last に対し、pred(*i) != false となる最後のiを返します。該当する i が見つからないときは last を返します。必ず (last – first) 回の比較が行なわれます。

// sample
bool gt1(int x) {
 return x > 1;
}

int array[] = { 0, 1, 2, 4, 5 };
int* p = stx::find_last_if(array, array+5, gt1);
cout << (p-array) << endl; // p = &array[2]

find_backward

template<class BidirectionalIterator,
           class T>
  BidirectionalIterator
  find_backward(BidirectionalIterator first,
                BidirectionalIterator last,
                const T&              value)
  {
    BidirectionalIterator it = last;
    while ( first != last ) {
      --last;
      if ( *last == value ) {
        return last;
      }
    }
    return it;
  }

first <= i < last に対し、*i == value となる最後のiを返します。該当する i が見つからないときは last を返します。find_last()と異なり、シーケンスを逆順(last-1からfirstに向かって)検索します。

// sample
int array[] = { 0, 1, 2, 2, 5 };
int* p = stx::find_backward(array, array+5, 2);
cout << (p-array) << endl; // p = &array[3]

find_backward_if

template<class BidirectionalIterator,
           class UnaryPredicate>
  BidirectionalIterator
  find_backward_if(BidirectionalIterator first,
                   BidirectionalIterator last,
                   UnaryPredicate        pred)
  {
    BidirectionalIterator it = last;
    while ( first != last ) {
      --last;
      if ( pred(*last) ) {
        return last;
      }
    }
    return it;
  }

first <= i < last に対し、pred(*i) != false となる最後のiを返します。該当する i が見つからないときは last を返します。find_last()と異なり、シーケンスを逆順(last-1からfirstに向かって)検索します。

// sample
bool gt1(int x) {
 return x > 1;
}

int array[] = { 0, 1, 2, 2, 5 };
int* p = stx::find_backward_if(array, array+5, gt1);
cout << (p-array) << endl; // p = &array[4]

binary_find

template<class ForwardIterator,
           class T>
  ForwardIterator
  binary_find(ForwardIterator first,
              ForwardIterator last,
              const T&        value)
  {
    ForwardIterator t = std::lower_bound(first,last,value);
    return ( t == last || value < *t ) ? last : t;
  }

ソートされたシーケンス[first,last)からvalueと等しい要素を探し、それを指すイテレータを返します。該当する要素が見つからないときは last を返します。バイナリサーチを行なうため、時間計算量は log(last - first) です。

// sample
int array[] = { 0, 1, 2, 2, 5 };
int* p = stx::binary_find(array, array+5, 2);
cout << (p-array) << endl; // p = &array[2]

template<class ForwardIterator,
           class T,
           class BinaryPredicate>
  ForwardIterator
  binary_find(ForwardIterator first,
              ForwardIterator last,
              const T&        value,
              BinaryPredicate pred)
  {
    ForwardIterator t = std::lower_bound(first,last,value,pred);
    return ( t == last || pred(value,*t) ) ? last : t;
  }

predに従ってソートされたシーケンス[first,last)からvalueと等しい要素を探し、それを指すイテレータを返します。該当する要素が見つからないときは last を返します。バイナリサーチを行なうため、時間計算量は log(last - first) です。

// sample
int array[] = { 5, 2, 2, 1, 0 };
int* p = stx::find_backward(array, array+5, 2, greater<int>());
cout << (p-array) << endl; // p = &array[1]

some

template<class InputIterator,
           class T>
  bool
  some(InputIterator first,
       InputIterator last,
       const T&      val)
  {
    while ( first != last ) {
      if ( *first == val ) {
        return true;
      }
      ++first;
    }
    return false;
  }

first <= i < last に対し、*i == value となる i が少なくともひとつあれば true を返します。

// sample
int array[] = { 5, 2, 2, 1, 0 };
bool t = stx::some(array, array+5, 1); // t = true;

some_if

template<class InputIterator,
           class UnaryPredicate>
  bool
  some_if(InputIterator  first,
          InputIterator  last,
          UnaryPredicate pred)
  {
    while ( first != last ) {
      if ( pred(*first) ) {
        return true;
      }
      ++first;
    }
    return false;
  }

first <= i < last に対し、pred(*i) != false となる i が少なくともひとつあれば true を返します。

// sample
bool gt1(int x) {
 return x > 1;
}

int array[] = { 0, 1, 0, 1, 0 };
bool t = stx:some_if(array, array+5, gt1); // t = false;

every

template<class InputIterator,
           class T>
  bool
  every(InputIterator first,
        InputIterator last,
        const T&      val)
  {
    while ( first != last ) {
      if ( !(*first == val) ) {
        return false;
      }
      ++first;
    }
    return true;
  }

first <= i < last であるすべての i に対し、*i == value であれば true を返します。

// sample
int array[] = { 2, 3, 4, 5, 6 };
bool t = stx::every(array, array+5, 3); // t = false;

every_if

template<class InputIterator,
           class UnaryPredicate>
  bool
  every_if(InputIterator  first,
           InputIterator  last,
           UnaryPredicate pred)
  {
    while ( first != last ) {
      if ( !pred(*first) ) {
        return false;
      }
      ++first;
    }
    return true;
  }

first <= i < last であるすべての i に対し、pred(*i) != false であれば true を返します。

// sample
bool gt1(int x) {
 return x > 1;
}

int array[] = { 2, 3, 4, 5, 6 };
bool t = stx::every(array, array+5, 3); // t = true;

select_copy

template<class InputIterator,
           class OutputIterator,
           class T>
  OutputIterator
  select_copy(InputIterator  first,
              InputIterator  last,
              OutputIterator result,
              const T&       value)
  {
    while ( first != last ) {
      if ( *first == value ) {
        *result = *first;
        ++result;
      }
      ++first;
    }
    return result;
  }

first <= i < last に対し、*i == value となる *i を [result,RET)にコピーします。RET は select_copy の戻り値です。

// sample
int array[] = { 5, 1, 2, 1, 0 };
vector<int> v;
stx::select_copy(array, array+5,back_inserter(V), 1); // v = { 1, 1 }

select_copy_if

template<class InputIterator,
           class OutputIterator,
           class UnaryPredicate>
  OutputIterator
  select_copy_if(InputIterator first,
                 InputIterator last,
                 OutputIterator result,
                 UnaryPredicate pred)
  {
    while ( first != last ) {
      if ( pred(*first) ) {
        *result = *first;
        ++result;
      }
      ++first;
    }
    return result;
  }

first <= i < last に対し、pred(*i) != false となる *i を [result,RET)にコピーします。RET は select_copy の戻り値です。

// sample
bool gt1(int x) {
 return x > 1;
}

int array[] = { 5, 1, 2, 1, 0 };
vector<int> v;
stx::select_copy_if(array, array+5,back_inserter(V), gt1); // v = { 5, 2 }

transform_if

template<class InputIterator,
           class OutputIterator,
           class UnaryFunction,
           class UnaryPredicate>
  OutputIterator
  transform_if(InputIterator  first,
               InputIterator  last,
               OutputIterator result,
               UnaryFunction  fn,
               UnaryPredicate pred)
  {
    while ( first != last ) {
      if ( pred(*first) ) {
         *result = fn(*first);
         ++result;
      }
      ++first;
    }
    return result;
  }

first <= i < last , pred(*i) != false となる i に対し、fn(*i)を [result,RET)にコピーします。RET は select_copy の戻り値です。

// sample
bool positive(int x) {
  return x > 0;
}

int twice(int x) {
  return x*2;
}

int array[] = { -2,  1,  0,  3,  2 };
vector<int> v;
stx::transform_if(array, array+5,back_inserter(V), twice, positive); // v = { 1*2,  3*2, 2*2 }

template<class InputIterator1,
           class InputIterator2,
           class OutputIterator,
           class BinaryFunction,
           class BinaryPredicate>
  OutputIterator
  transform_if(InputIterator1  first1,
               InputIterator1  last1,
               InputIterator2  first2,
               OutputIterator  result,
               BinaryFunction  fn,
               BinaryPredicate pred)
  {
    while ( first1 != last1 ) {
      if ( pred(*first1,*first2) ) {
         *result = fn(*first1,*first2);
         ++result;
      }
      ++first1;
      ++first2;
    }
    return result;
  }

0 <= i < (last1 - first1), pred(*(first1+i),*(first2+i)) != false となる i に対し、fn(*(first1+i),*(first2+i))を [result,RET)にコピーします。RET は select_copy の戻り値です。

// sample
bool positive(int x, int y) {
  return x * y > 0;
}

int array1[] = { -2,  1,  0,  3, -2 };
int array2[] = { -2, -1,  0,  4,  2 };
vector&lt;int&gt; v;
stx::transform_if(array1, array1+5,
                    array2, back_inserter(V),
                    multiplies<int>(), positive); // v = { 2*-2,  3*4 }

inject_1st

template<class InputIterator,
           class BinaryFunction,
           class T>
  T
  inject_1st(InputIterator  first,
             InputIterator  last,
             BinaryFunction fn,
             const T&       init)
  {
    T result(init);
    while ( first != last ) {
      result = fn(result,*first);
      ++first;
    }
    return result;
  }

first <= i < last に対し、x = fn(x,*i); を順に適用し、最終的に選られたxを返します。x の型は T, 初期値は init です。

// sample
int array[] = { 1, 2, 3, 4, 5 };
int n = stx::inject_1st(array, array+5, plus<int>(), 0); // n = 15

inject_2nd

template<class InputIterator,
           class BinaryFunction,
           class T>
  T
  inject_2nd(InputIterator  first,
             InputIterator  last,
             BinaryFunction fn,
             const T&       init)
  {
    T result(init);
    while ( first != last ) {
      result = fn(*first,result);
      ++first;
    }
    return result;
  }

first <= i < last に対し、x = fn(*i,x); を順に適用し、最終的に選られたxを返します。x の型は T, 初期値は init です。

// sample
int array[] = { 1, 2, 3, 4, 5 };
int n = stx::inject_2nd(array, array+5, plus<int>(), 0); // n = 15

partition_copy

template<class InputIterator,
           class OutputIterator1,
           class OutputIterator2,
           class UnaryPredicate>
  std::pair<OutputIterator1,OutputIterator2>
  partition_copy(InputIterator first,
                 InputIterator last,
                 OutputIterator1 result1,
                 OutputIterator2 result2,
                 UnaryPredicate pred)
  {
    while ( first != last ) {
      if ( pred(*first) ) {
        *result1 = *first;
        ++result1;
      } else {
        *result2 = *first;
        ++result2;
      }
      ++first;
    }
    return std::pair<OutputIterator1,OutputIterator2>(result1,result2);
  }

first < i <= last に対し、pred(*i) != false ならば [result1,RET.first)に、pred(*i) == false ならば [result2,RET.second)に *iをコピーします。RET は partition_copy() の戻り値です。

// sample
bool positive(int x) {
  return x > 0;
}

int array[] = { 1, -2, 3, -4, 5 };
vector<int> v;
list<int> l;
stx::partition_copy(array, array+5,
                      back_inserter(v), back_insserter(l),
                      positive); // v = { 1, 3, 5 }, l = { -2, -4 }

is_sorted

template<class InputIterator>
  bool
  is_sorted(InputIterator first,
            InputIterator last)
  {
    if ( first == last ) {
      return true;
    }
    InputIterator next = first;
    ++next;
    while ( next != last ) {
      if ( *next < *first ) {
        return false;
      }
      ++first;
      ++next;
    }
    return true;
  }

first <= i , i+1 <= last なるすべての i,i+1 に対し、*i < *(i+1) であれば true を返します。

// sample
int array[] = { 0, 1, 1, 2, 3 };
bool t = stx::is_sorted(array, array+5); // t = true;

template<class InputIterator,
           class BinaryFunction>
  bool
  is_sorted(InputIterator first,
            InputIterator last,
            BinaryFunction comp)
  {
    if ( first == last ) {
      return true;
    }
    InputIterator next = first;
    ++next;
    while ( next != last ) {
      if ( comp(*next,*first) ) {
        return false;
      }
      ++first;
      ++next;
    }
    return true;
  }

first <= i , i+1 <= last なるすべての i,i+1 に対し、comp(*(i+1),*i) == false であれば true を返します。

// sample
int array[] = { 3, 2, 2, 1, 0 };
bool t = stx::is_sorted(array, array+5, greater<int>()); // t = true;

lexicographical_compare_3way

template <class InputIterator1,
            class InputIterator2>
  int
  lexicographical_compare_3way(InputIterator1 first1,
                               InputIterator1 last1,
                               InputIterator2 first2,
                               InputIterator2 last2)
  {
    while (first1 != last1 && first2 != last2) {
      if (*first1 < *first2) {
        return -1;
      }
      if (*first2 < *first1) {
        return 1;
      }
      ++first1;
      ++first2;
    }
    if (first2 == last2) {
      return !(first1 == last1);
    } else {
      return -1;
    }
  }

2つのシーケンス[first1,last1), [first2,last2)を辞書順に比較し、[first1,last1) < [first2,last2) ならば -1、[first1,last1) = [first2,last2) ならば 0、[first1,last1) > [first2,last2) ならば 1 を返します。

// sample
string s1 = "apple";
const char* s2 = "apple";
int t = stx::lexicographical_compare_3way(s1.begin(), s1.end(), s2, s2+strlen(s2)); // t = 0

template <class InputIterator1,
            class InputIterator2,
            class BinaryPredicate>
  int
  lexicographical_compare_3way(InputIterator1 first1,
                               InputIterator1 last1,
                               InputIterator2 first2,
                               InputIterator2 last2,
                               BinaryPredicate pred)
  {
    while (first1 != last1 && first2 != last2) {
      if ( pred(*first1,*first2) ) {
        return -1;
      }
      if ( pred(*first2,*first1) ) {
        return 1;
      }
      ++first1;
      ++first2;
    }
    if (first2 == last2) {
      return !(first1 == last1);
    } else {
      return -1;
    }
  }

2つのシーケンス[first1,last1), [first2,last2)をpredに従って辞書順に比較し、[first1,last1) < [first2,last2) ならば -1、[first1,last1) = [first2,last2) ならば 0、[first1,last1) > [first2,last2) ならば 1 を返します。

// sample
bool ignorecase_less(char x, char y) {
  return toupper(x) < toupper(y);
}

string s1 = "apple";
const char* s2 = "APPLA";
int t = stx::lexicographical_compare_3way(s1.begin(), s1.end(), s2, s2+strlen(s2),
                                              ignorecase_less); // t = -1

Posted in misc | No Comments »

Mockppとは…

単体テストのフレームワーク CppUnit による自動テストはモジュールの品質を高め、安全/確実なソフトウェアの構築に大きな効果をもたらします。しかしながら CppUnitがうまく適用できないシチュエーションにも少なからず直面します。

ナビゲータ(class Navigator)の実装を考えてみましょう。ユーザはナビゲータに適当な複数のキーワードを与えます。ナビゲータはあらかじめ用意されたDatabaseにそのキーワードを食わせると、その検索結果としてURLが得られるものとします。さらにWebブラウザを制御するクラス:Browserも提供され、これにURLを与えるとブラウザに引き渡してくれるとしましょう。

つまり、Navigatorはその機能の実現にDatabaseとBrowserを利用することになります。DatabaseおよびBrowserは以下のようなヘッダが用意されています：

Database.h

#ifndef DATABASE_H__
#define DATABASE_H__

#include <string>
#include <vector>

class Database {
public:
  virtual ~Database() {}
  virtual std::string find(const std::vector<std::string>& keywords) =0;
};

#endif

Browser.h

#ifndef BROWSER_H__
#define BROWSER_H__

#include <string>

class Browser {
public:
  virtual ~Browser() {}
  virtual void show(const std::string& url) =0;
};

#endif

上記のクラスを利用したNavigatorのインタフェースは以下のようになります。

Navigator.h

#ifndef NAVIGATOR_H__
#define NAVIGATOR_H__

#include <string>

class Database;
class Browser;

class Navigator {
  Database* db_;
  Browser* br_;
public:
  Navigator(Database* db, Browser* br);
  bool navigate(const std::string& input);
};

#endif

コンストラクタでDatabaseとBrowserを与えておきます。ユーザからの入力0個以上のキーワードを空白で繋いだものをnavigateの引数に与えることにしましょう。

Navigator::navigate()で行なう処理はおおむね以下のとおりです:

inputを空白を区切り文字として複数の文字列に分割し、std::vector<std::string>keywords に格納する。
keywordsをDatabase::find()に与え、URLを得る。(ただしこのURLには先頭の"http://"が付いていない)
URLが空文字列であったらfalseを返す。そうでなければBrowser::show()を呼び出す。

テスト・ファースト・デザインの流儀に則れば、ここでテスト対象であるNavigatorのテストを書き、テストを繰り返しながらテスト項目をすべてパスするように実装を進めます。しかし、ここでDatabaseおよびBrowserが未実装であったとき、テストできません。こんなとき、Database/Browserの動作を真似する'偽物(Mock)'を用意することで解決できます。Mockpp(MockObject for C++:http://mockpp.sf.net/)は、この'偽物(Mock)'を作るためのライブラリです。

Mockの作り方

Mockppを使って、Databaseのニセモノ:MockDatabaseを作ってみましょう。

MockDatabase.h

#ifndef MOCKDATABASE_H__
#define MOCKDATABASE_H__

#include "Database.h"
#include <mockpp/MockObject.h>
#include <mockpp/ExpectationList.h>
#include <mockpp/ReturnObjectList.h>

class MockDatabase : public Database, public mockpp::MockObject { // [1]

public:

  virtual std::string find(const std::vector<std::string>& keywords) {
    for ( std::vector<std::string>::size_type i = 0;
          i < keywords.size(); ++i ) {
      args.addActual(keywords[i]); // [4]
    }
    return rets.nextReturnObject(); // [5]
  }

  MockDatabase():mockpp::MockObject("Database"), args("arguments",this), rets("returns",this) { // [3]
  }

  mockpp::ExpectationList<std::string>  args; // [2]
  mockpp::ReturnObjectList<std::string> rets; // [2]
};

#endif

MockDatabaseは本物のインタフェース Database とmockpp::MockObjectから導出します。
メソッドfindに飛び込む引数の正当性を検証する ExpectedList、そして findの戻り値を格納しておく ReturnObjectList とをメンバ変数に用意します。
コンストラクタでは[2]のそれぞれに名前を付けておきます。
ExpectedList,ReturnObjectListのコンストラクタにはそれらを包含するMockObjectのポインタを(第二引数に)与えます。
そしてExpectedListをMockに登録する。
メソッドfindでは与えられた引数をひとつづつ取り出し、ExpectedList::addActualに与えます。このとき期待した値と異なれば、例外をthrowすることによってテストが失敗します。
あらかじめ用意しておいた値を返します。

ニセモノBrowser: MockBrowser も同様です。メソッド show の戻り値は void なのでReturnObjectList は必要ありません。

MockBrowser.h

#ifndef MOCKBROWSER_H__
#define MOCKBROWSER_H__

#include "Browser.h"
#include <mockpp/MockObject.h>
#include <mockpp/ExpectationList.h>

class MockBrowser : public Browser, public mockpp::MockObject {
public:
  virtual void show(const std::string& url) {
    args.addActual(url);
  }

  MockBrowser() : mockpp::MockObject("Browser"), args("arguments",this) {
  }

  mockpp::ExpectationList<std::string> args;
};

#endif

CppUnitによるテストコード

NavigatorTest.cpp

//CUPPA:include=+
#include "Navigator.h"
#include "MockDatabase.h"
#include "MockBrowser.h"
//CUPPA:include=-
#include <cppunit/extensions/HelperMacros.h>
#include <cppunit/TestAssert.h>

//CUPPA:namespace=+
//CUPPA:namespace=-

class NavigatorTest : public CppUnit::TestFixture {
private:

  Navigator*     navigator;
  MockDatabase*  database;  MockBrowser*   browser;

public:

  virtual void setUp() {
    database  = new MockDatabase();
    browser   = new MockBrowser();
    navigator = new Navigator(database,browser);
  }
  virtual void tearDown() {
    delete database;
    delete browser;
    delete navigator;
  }

//CUPPA:decl=+
  void testOK() {
    database->args.addExpected("大阪"); // [1]
    database->args.addExpected("software"); // [1]
    database->rets.addObjectToReturn("www.s34.co.jp"); // [2]
    browser->args.addExpected("http://www.s34.co.jp"); // [3]
    CPPUNIT_ASSERT(  navigator->navigate("大阪 software") ); // [4]
    database->verify(); // [5]
    browser->verify(); // [6]
  }
  void testNG() {
    database->args.addExpected("東京");
    database->args.addExpected("hardware");
    database->rets.addObjectToReturn("");
    CPPUNIT_ASSERT( !navigator->navigate("東京 hardware") );
    database->verify();
    browser->verify();
  }
//CUPPA:decl=-
  CPPUNIT_TEST_SUITE(NavigatorTest);
//CUPPA:suite=+
  CPPUNIT_TEST(testOK);
  CPPUNIT_TEST(testNG);
//CUPPA:suite=-
  CPPUNIT_TEST_SUITE_END();
};

//CUPPA:impl=+
//CUPPA:impl=-

CPPUNIT_TEST_SUITE_REGISTRATION(NavigatorTest);

testOKではDatabase::findに"大阪"と"software"が与えられることを期待し(1)、そのとき"www.s34.co.jp"を返すこと(2)。
引き続いてNavigator::showに"http://www.s34.co.jp"が与えられることを期待しています(3)。
次にNavigator::navigateを呼んでみて、trueが返ってくればテストをパスしたことになります。

testNGも同様です。期待する引数、そのときの戻り値を設定し、テスト対象メソッドを呼び出します。こちらはnavigateの結果がfalseであるはずです。

テストと実装

これでようやくNavigator の実装に着手できます。
まずは最小限コンパイル/リンク/実行できるだけの'いいかげん'なコードからはじめましょう。

Navigator.cpp

#include "Navigator.h"
#include "Database.h"
#include "Browser.h"

Navigator::Navigator(Database* db, Browser* br) : db_(db), br_(br) {
}

bool Navigator::navigate(const std::string& input) {
  std::vector<std::string> keywords;
  keywords.push_back(input);
  std::string url = db_->find(keywords);
  br_->show(url);
  return true;
}

コンパイル/リンクし、実行すると次のような結果が得られます:

!!!FAILURES!!!
Test Results:
Run:  2   Failures: 0   Errors: 2

1) test: NavigatorTest::testOK (E)
uncaught exception of type mockpp::AssertionFailedError
- arguments added item does not match. 大阪 != 大阪 software.

2) test: NavigatorTest::testNG (E)
uncaught exception of type mockpp::AssertionFailedError
- arguments added item does not match. 東京 != 東京 hardware.

この結果は、Database::findへの引数が"大阪"であることを期待していたのに、実際は"大阪］software"であったことを報告しています。入力文字列を空白で分割していないので当然です。

では'空白を区切りとした分割'をNavigator.cppに追加しましょう。

Navigator.cpp

#include "Navigator.h"
#include "Database.h"
#include "Browser.h"

Navigator::Navigator(Database* db, Browser* br) : db_(db), br_(br) {
}

bool Navigator::navigate(const std::string& input) {
  std::vector<std::string> keywords;
  std::string::size_type beginPos = 0;
  std::string::size_type endPos = 0;
  while ( (beginPos = input.find_first_not_of(" ", endPos)) != std::string::npos ) {
    endPos = input.find_first_of(" ", beginPos);
    keywords.push_back(input.substr(beginPos, endPos-beginPos));
  }
  std::string url = db_->find(keywords);
  br_->show(url);
  return true;
}

実行結果は以下のようになります:

!!!FAILURES!!!
Test Results:
Run:  2   Failures: 1   Errors: 1

1) test: NavigatorTest::testOK (E)
uncaught exception of type mockpp::AssertionFailedError
- arguments added item does not match. http://www.s34.co.jp != www.s34.co.jp.

2) test: NavigatorTest::testNG (F) line: 46 NavigatorTest.cpp
assertion failed
- Expression: !navigator->navigate("東京 hardware")

…Browser::showの引数(URL)に"http://"をくっつけるのを忘れているようです…

このように、Mockppを使えば、'本物'なしでテスト・ファースト・デザインに則ったテスト/実装が可能になります。

Posted in misc | No Comments »

CUnit 導入ガイド

Wednesday, April 5th, 2006

CUnit 導入ガイド

ダウンロードとインストール

CUnitは http://sourceforge.net/projects/cunit/
からダウンロードできます。 2003.06時点での最新版は1.1-0です。
zipもしくはtar+gzipで圧縮されているので、適当なディレクトリに展開してください。

以下の説明はWindows/Visual C++ v6.0 環境で、
CUnitのルート・ディレクトリを<CUNIT>と表記します。

ライブラリのビルド

CUnitはツール/ユーティリティの類ではありません。
テスト対象およびテストコードと一緒にリンクして実行モジュールを生成する’ライブラリ’です。

CUnitは様々なOS/処理系に対応しており、
その使用に先だってライブラリをビルドしなければなりません。

Visual Studio IDE から
プロジェクト:<CUNIT>\CUnit.dsw をオープンし、 Release/Debug
いずれかの設定でビルドします。
デフォルトではシングルスレッド版です。必要に応じてプロジェクト設定を変更してください。<CUNIT>\CUnitにライブラリ(CUnit.lib)が生成されます。
Release/Debugのいずれも同じ名前で生成されるので、これも必要に応じてプロジェクト設定を変更してください。

注意! CUnit-1.1-0にはマクロのバグがあります。
<CUNIT>\CUnit\Headers\CUnit.h に定義されたマクロ:

ASSERT_PTR_EQUAL
ASSERT_PTR_NOT_EQUAL
ASSERT_PTR_NULL
ASSERT_PTR_NOT_NULL

を、以下のように修正(下線部)してください。

CUnit.h 修正個所

#define ASSERT_PTR_EQUAL(actual, expected) ASSERT(((void*)(actual) == (void*)(expected)))
#define ASSERT_PTR_NOT_EQUAL(actual, expected) ASSERT(((void*)(actual) != (void*)(expected)))

#define ASSERT_PTR_NULL(value) ASSERT((NULL == (void*)(value)))
#define ASSERT_PTR_NOT_NULL(value) ASSERT((NULL != (void*)(value)))

テストコードの雛型

テストコードの雛型を示します。この雛型は様々なテストに応じて書き換えて利用してください。

XXXTest.c

/*
 * Test-group 'XXX'
 */

#include <TestDB.h>

int XXX_init(void) {
  /*
   * テスト・グループの初期化
   */
  return 0;
}

int XXX_term(void) {
  /*
   * テスト・グループの後始末
   */
  return 0;
}

/*
 * テスト
 */
void XXX_test_01(void) {
  ASSERT(0 == 1);
}

void XXX_test_02(void) {
  ASSERT_TRUE(0 == 1);
}

void XXX_test_03(void) {
  ASSERT_FALSE(0 == 0);
}

void XXX_test_04(void) {
  ASSERT_EQUAL(1,2);
}

void XXX_test_05(void) {
  ASSERT_NOT_EQUAL(1,1);
}

void XXX_test_06(void) {
  int i, j;
  ASSERT_PTR_EQUAL(&i,&j);
}

void XXX_test_07(void) {
  int i = 0;
  ASSERT_PTR_NOT_EQUAL(&i,&i);
}

void XXX_test_08(void) {
  int i = 0;
  ASSERT_PTR_NULL(&i);
}

void XXX_test_09(void) {
  int* p = NULL;
  ASSERT_PTR_NOT_NULL(p);
}

void XXX_test_10(void) {
  char* x = "x";
  char* y = "y";
  ASSERT_STRING_EQUAL(x,y);
}

void XXX_test_11(void) {
  char* x = "x";
  char* y = "x";
  ASSERT_STRING_NOT_EQUAL(x,y);
}

void XXX_test_12(void) {
  char* x = "abcde";
  char* y = "abcyz";
  ASSERT_NSTRING_EQUAL(x,y,4);
}

void XXX_test_13(void) {
  char* x = "abcde";
  char* y = "abcyz";
  ASSERT_NSTRING_NOT_EQUAL(x,y,3);
}

void XXX_test_14(void) {
  double x = 1.2;
  double y = 1.5;
  ASSERT_DOUBLE_EQUAL(x,y,0.2);
}

void XXX_test_15(void) {
  double x = 1.2;
  double y = 1.5;
  ASSERT_DOUBLE_NOT_EQUAL(x,y,0.4);
}

/*
 * テスト・グループの登録
 */
void XXX_register() {
 TestGroup* pGroup = NULL;
 TestCase*  pTest = NULL;

 pGroup = add_test_group("XXX", XXX_init, XXX_term);
 pTest = add_test_case(pGroup, "test_01", XXX_test_01);
 pTest = add_test_case(pGroup, "test_02", XXX_test_02);
 pTest = add_test_case(pGroup, "test_03", XXX_test_03);
 pTest = add_test_case(pGroup, "test_04", XXX_test_04);
 pTest = add_test_case(pGroup, "test_05", XXX_test_05);
 pTest = add_test_case(pGroup, "test_06", XXX_test_06);
 pTest = add_test_case(pGroup, "test_07", XXX_test_07);
 pTest = add_test_case(pGroup, "test_08", XXX_test_08);
 pTest = add_test_case(pGroup, "test_09", XXX_test_09);
 pTest = add_test_case(pGroup, "test_10", XXX_test_10);
 pTest = add_test_case(pGroup, "test_11", XXX_test_11);
 pTest = add_test_case(pGroup, "test_12", XXX_test_12);
 pTest = add_test_case(pGroup, "test_13", XXX_test_13);
 pTest = add_test_case(pGroup, "test_14", XXX_test_14);
 pTest = add_test_case(pGroup, "test_15", XXX_test_15);
}

ファイル名
慣習的に、テスト対象であるモジュール名の末尾に’Test’を付加します。
たとえば、’Counter’のテストコードは’CounterTest.c’のように。
インクルード
必要なインクルードをここに記述します。
テストクラス
テスト・グループはテスト対象に対するテスト・ケースの集合体で、
ファイル名と同じクラス名とするのが望ましいでしょう。
初期化/後始末
グループ毎の初期化と後始末は、いずれも引数なし/戻り値 int の関数です。
初期化/後始末に成功したら0を返してください。
テスト・ケース
テスト・ケースは引数/戻り値を持たない関数で、テスト項目毎に用意します。
テスト・グループ登録
テスト・グループの登録は add_test_group で行ないます。引数はそれぞれ、名前,
初期化関数, 後始末関数です。 add_test_group
はグループのポインタを返します。これを add_test_case
の引数として、グループにテストを登録します。引数は、グループのポインタ, 名前, テスト関数です。

アサート・マクロ

各テスト・ケースの中では、テスト対象が正常に機能しているかを検証するコードを記述します。

以下のアサート・マクロが用意されています。
各アサート・マクロはそれぞれ特定の条件を満たさないとき、
テスト失敗(failre)とみなしてそれ以降の処理をせずにテスト・ケースから脱出し、
次のテスト・ケースに移ります。

ASSERT( condition );
conditionが偽(0)であったとき、失敗します。
ASSERT_TRUE( condition );
conditionが偽であったとき、失敗します。
ASSERT_FALSE( condition );
conditionが真(!=0)であったとき、失敗します。
ASSERT_EQUAL( expected, actual );
得られた結果actualが期待する値expectedでなかったとき、すなわちexpected
!= actualのときに失敗します。
ASSERT_NOT_EQUAL( expected, actual );
得られた結果actualが期待する値expectedであったとき、すなわちexpected
== actualのときに失敗します。
ASSERT_PTR_EQUAL( expected, actual );
得られた結果actualが期待するポインタ値expectedでなかったとき、すなわちexpected
!= actualのときに失敗します。
ASSERT_PTR_NOT_EQUAL( expected, actual );
得られた結果actualが期待するポインタ値expectedであったとき、すなわちexpected
== actualのときに失敗します。
ASSERT_PTR_NULL( actual );
得られた結果actualがNULLポインタでなかったとき、失敗します。
ASSERT_PTR_NOT_NULL( actual );
得られた結果actualがNULLポインタであったとき、失敗します。
ASSERT_STRING_EQUAL( expected, actual );
得られた結果actualが期待する文字列expectedでなかったとき、
すなわちstrcmp(expected,actual) != 0
のときに失敗します。
ASSERT_STRING_NOT_EQUAL( expected, actual );
得られた結果actualが期待する文字列expectedと一致したとき、
すなわちstrcmp(expected,actual) == 0
のときに失敗します。
ASSERT_NSTRING_EQUAL( expected, actual, count );
得られた結果actualと期待する文字列expectedのcountが一致しなかったとき、

すなわちstrncmp(expected,actual, count)
!= 0 のときに失敗します。
ASSERT_NSTRING_NOT_EQUAL( expected, actual, count );
得られた結果actualと期待する文字列expectedのcountが一致したとき、

すなわちstrncmp(expected,actual, count)
== 0 のときに失敗します。
ASSERT_DOUBLE_EQUAL( expected, actual, delta );
得られた結果actualと期待する値expectedとの差がdeltaより大きいとき、失敗します。
ASSERT_DOUBLE_NOT_EQUAL( expected, actual, delta );
得られた結果actualと期待する値expectedとの差がdeltaより小さいとき、失敗します。

メイン・ルーチン

以上のようにして作られたいくつかのテストグループ登録関数をmainで呼び出すことで、そのテストグループがテストの対象となります。

できあがった実行モジュールはコンソール・アプリケーションとなります。

メイン・ルーチンの雛型と、実行結果を示します(下線部はユーザ入力

メイン・ルーチン

#include <Console.h>

int main() {
  void XXX_register();

  initialize_registry();
  XXX_register();
  console_run_tests();
  cleanup_registry();
  return 0;
}

実行結果

                        CUnit : A Unit testing framework for C.
                            http://cunit.sourceforge.net/

|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(R)un all, (S)elect group, (L)ist groups, Show (F)ailures, (Q)uit
Enter Command : r

Running Group : XXX
        Running test : test_01
        Running test : test_02
        Running test : test_03
        Running test : test_04
        Running test : test_05
        Running test : test_06
        Running test : test_07
        Running test : test_08
        Running test : test_09
        Running test : test_10
        Running test : test_11
        Running test : test_12
        Running test : test_13
        Running test : test_14
        Running test : test_15

--Completed 1 Groups, 15 Test run, 0 succeded and 15 failed.
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(R)un all, (S)elect group, (L)ist groups, Show (F)ailures, (Q)uit
Enter Command : f

============================= Test Case Failure List =========================
1>  XXXTest.c:25 : (XXX : test_01) : 0 == 1
2>  XXXTest.c:29 : (XXX : test_02) : ((0 == 1) != FALSE)
3>  XXXTest.c:33 : (XXX : test_03) : ((0 == 0) == FALSE)
4>  XXXTest.c:37 : (XXX : test_04) : ((1) == (2))
5>  XXXTest.c:41 : (XXX : test_05) : ((1) != (1))
6>  XXXTest.c:46 : (XXX : test_06) : ((void*)(&i) == (void*)(&j))
7>  XXXTest.c:51 : (XXX : test_07) : ((void*)(&i) != (void*)(&i))
8>  XXXTest.c:56 : (XXX : test_08) : (NULL == (void*)(&i))
9>  XXXTest.c:61 : (XXX : test_09) : (NULL != (void*)(p))
10>  XXXTest.c:67 : (XXX : test_10) : (0 == strcmp((const char*)x, (const char*)y))
11>  XXXTest.c:73 : (XXX : test_11) : (0 != strcmp((const char*)x, (const char*)y))
12>  XXXTest.c:79 : (XXX : test_12) : (0 == strncmp((const char*)x, (const char*)y, (size_t)4))
13>  XXXTest.c:85 : (XXX : test_13) : (0 != strncmp((const char*)x, (const char*)y, (size_t)3))
14>  XXXTest.c:91 : (XXX : test_14) : (fabs((double)x - y) <= fabs((double)0.2))
15>  XXXTest.c:97 : (XXX : test_15) : (fabs((double)x - y) > fabs((double)0.4))

=======================================
Total Number of Failures : 15
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(R)un all, (S)elect group, (L)ist groups, Show (F)ailures, (Q)uit
Enter Command : q

Posted in misc | No Comments »

バイナリ/テキスト相互変換(BASE64とQuoted-printable)

Wednesday, April 5th, 2006

電子メールによるバイナリファイルの送受信

インタネットの爆発的な普及に伴い、電子メール(e-mail)が至極アタリマエの通信メディアとして用いられるようになってきました。

e-mailはインタネットが今ほど一般的ではなく、コンピュータ間を公衆回線(一般電話網)を介して繋いでいた頃からのメディアです。ですから現在でもe-mailに含まれる文字は7bit-ASCIIであることが求められています。

文字だけの、いわゆる"お手紙"だけでなく、画像、音声、あるいはプログラムなどの"バイナリファイル"をe-mailでやりとりするには、送り手はバイナリファイルを構成するバイト(8bit=256文字)をASCII文字に変換し、受け手はそれを元に戻さなければなりません。

e-mail界で、バイナリ/ASCII相互の変換規則として一般的に用いられているのがBASE64とQuoted-printableです。

BASE64

BASE64は、バイナリデータすなわちバイト列を3byteすなわち24bitづつに分割します。そしてその24bitをさらに6bitの4つの組に分割します。そうすればそれぞれは0から63の(64種類の)数として表すことができます。

0〜63のそれぞれに対し、以下のように文字を割り当てます:

 0 : 'A'   1 : 'B'  ... 25 : 'Z'
26 : 'a'  27 : 'b'  ... 51 : 'z'
52 : '0'  53 : '1'  ... 61 : '9'
62 : '+'  63 : '/'

こうやって割り当てられた文字をe-mailのメッセージとして送り出すわけです。1文字が64進法での1桁に相当するため、BASE64の名が付いています。

送信したいバイナリデータのバイト数が3の倍数でないときは"パディング"が行われます。

1byte(8bit)余るとき、それに4bitの0を付加して12bit(6bit*2)にし、2文字分変換して'='を2つ追加します。
2byte(16bit)余るとき、それに2bitの0を付加して18bit(6bit*3)にし、3文字分変換して'='を1つ追加します。

BASE64ではバイナリの3文字がASCIIの4文字に変換されるため、転送されるデータの大きさは33%増加します。

Quoted-printable

Quoted-printbleは送りたいバイナリデータのほとんどがASCII文字で構成されている場合に用いられます。

Quoted-printableでは送りたいバイナリデータのひとつひとつがASCII文字であればそれをそのまま、そうでなければ'='に続く2桁の16進文字('0'-'9','A'-'F')に変換します。

エンコーダ・デコーダの実装

では前述の変換規則に基づいて、BASE64およびQuoted-printableによる変換/逆変換を行なうクラスを実装しましょう。

まず、ベースクラスでインタフェースを定義します。

template <class InputIterator, class OutputIterator>
class MimeCoder {
public:
  virtual OutputIterator filter(InputIterator first, InputIterator last,
                                OutputIterator result, bool fin =false) = 0;
  virtual OutputIterator finish(OutputIterator& result) = 0;
};

メソッドfilter(first,last,redult,fin)は、範囲[first,last)にあるすべてのバイナリに対して変換を行ない、結果をresultに出力します。最後のパラメータfinがtrueであれば、バイナリデータはこれで終わりとみなし、末尾のパディングを出力します。

メソッドfinish(result)はパディングをresultに出力します。

入力/出力先はtemplateで指定する方式としました。こうしておけばファイルだけでなく、バイト配列や文字列、さらにはバイトを要素とする任意のコンテナを入出力先として利用できるからです。

つぎにBASE64,Quoted-printableそれぞれのencoder/decoderをMimeCoderから導出します。

/*
 * Base64
 */
template <class InputIterator, class OutputIterator>
class Base64Encoder : public MimeCoder<InputIterator, OutputIterator> {
public:
  Base64Encoder() : len(0), linepos(0) {}
  virtual OutputIterator filter(InputIterator first, InputIterator last,
                                OutputIterator result, bool fin =false );
  virtual OutputIterator finish(OutputIterator& result );
private:
  int             linepos;
  unsigned char   curr[3];
  int             len;
  void encodeCurr(OutputIterator& result);
};

template <class InputIterator, class OutputIterator>
class Base64Decoder : public MimeCoder<InputIterator, OutputIterator> {
public:
  Base64Decoder() : len(0), ended(false) {}
  virtual OutputIterator filter(InputIterator first, InputIterator last,
                                OutputIterator result, bool fin =false );
  virtual OutputIterator finish(OutputIterator& result);
private:
  bool            ended;
  unsigned char   curr[4];
  int             len;
  int             err;
  void decodeCurr(OutputIterator& result);
};

/*
 * Quoted-Printable
 */
template <class InputIterator, class OutputIterator>
class QpEncoder : public MimeCoder<InputIterator, OutputIterator> {
public:
  QpEncoder() : linepos(0), prevCh('x') {}
  virtual OutputIterator filter(InputIterator first, InputIterator last,
                                OutputIterator result, bool fin =false);
  virtual OutputIterator finish(OutputIterator& result);
private:
  int             linepos;
  unsigned char   prevCh;
};

template <class InputIterator, class OutputIterator>
class QpDecoder : public MimeCoder<InputIterator, OutputIterator> {
public:
  QpDecoder() : hexlen(0) {}
  virtual OutputIterator filter(InputIterator first, InputIterator last,
                                OutputIterator result, bool fin =false );
  virtual OutputIterator finish(OutputIterator& result);
private:
  int             hexlen;
  unsigned char   hex2[2];
};

それぞれの実装は以下のようになります。変換規則を忠実にコードに落としました。

static const int cLineLen = 72;

/*
 * Base64Encoder
 */
static const char cBase64Codes[] =
  "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

template <class InputIterator, class OutputIterator>
OutputIterator Base64Encoder<InputIterator, OutputIterator>::filter(InputIterator first, InputIterator last, OutputIterator result, bool fin) {
  for(;;) {
    for(; linepos < cLineLen; linepos += 4) {
      for (; len < 3; len++) {
        if ( first == last ) {
          if ( fin )
            finish(result);
            return result;
        }
        curr[len] = *first;
        ++first;
      }
      encodeCurr(result);
      len = 0;
    }
    *result++ = 13;
    *result++ = 10;
    linepos = 0;
  } // for (;;)
}

template <class InputIterator, class OutputIterator>
OutputIterator Base64Encoder<InputIterator, OutputIterator>::finish(OutputIterator& result) {
  if ( len )
    encodeCurr(result);
  len = 0;
  linepos = 0;
  return result;
}

template <class InputIterator, class OutputIterator>
void Base64Encoder<InputIterator, OutputIterator>::encodeCurr(OutputIterator& result) {
  if ( len < 3 )
    curr[len] = 0;
  *result++ = cBase64Codes[ curr[0] >> 2 ];
  *result++ = cBase64Codes[ ((curr[0] & 0x03) << 4) |
                            ((curr[1] & 0xF0) >> 4) ];
  if ( len == 1 )
    *result++ = '=';
  else
    *result++ = cBase64Codes[ ((curr[1] & 0x0F) << 2) |
                              ((curr[2] & 0xC0) >> 6) ];
  if ( len < 3 )
    *result++ = '=';
  else
    *result++ = cBase64Codes[ curr[2] & 0x3F ];
}

/*
 * Base64Decoder
 */
#define XX 127

static const unsigned char cIndex64[256] = {
    XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
    XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
    XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,62, XX,XX,XX,63,
    52,53,54,55, 56,57,58,59, 60,61,XX,XX, XX,XX,XX,XX,
    XX, 0, 1, 2,  3, 4, 5, 6,  7, 8, 9,10, 11,12,13,14,
    15,16,17,18, 19,20,21,22, 23,24,25,XX, XX,XX,XX,XX,
    XX,26,27,28, 29,30,31,32, 33,34,35,36, 37,38,39,40,
    41,42,43,44, 45,46,47,48, 49,50,51,XX, XX,XX,XX,XX,
    XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
    XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
    XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
    XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
    XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
    XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
    XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
    XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
};

template <class InputIterator, class OutputIterator>
OutputIterator Base64Decoder<InputIterator, OutputIterator>::filter(InputIterator first, InputIterator last, OutputIterator result, bool fin) {
  unsigned char c;
  err = 0;
  for (;;) {
    while ( len < 4) {
      if ( first == last ) {
        if ( fin )
        finish(result);
        return result;
      }
      c = *first;
      if ((cIndex64[c] != XX) || (c == '='))
        curr[len++] = c;
      else
      if ((c != 13) && (c != 10))
        ++err; // error
      ++first;
    }
    decodeCurr(result);
    len = 0;
  }
}

template <class InputIterator, class OutputIterator>
OutputIterator Base64Decoder<InputIterator, OutputIterator>::finish(OutputIterator& result) {
  len = 0;
  if ( ended )
    return result;
  else {
    ended = false;
    return result;
  }
}

template <class InputIterator, class OutputIterator>
void Base64Decoder<InputIterator, OutputIterator>::decodeCurr(OutputIterator& result) {
  if ( ended ) {
    ++err;
    ended = false;
  }
  for (int i = 0; i < 2; i++)
    if ( curr[i] == '=') {
      ++err;
      return;
    } else
      curr[i] = cIndex64[curr[i]];
  *result++ = (curr[0] << 2) | ((curr[1] & 0x30) >> 4);
  if ( curr[2] == '=') {
    if ( curr[3] == '=')
      ended = true;
    else
      ++err;
  } else {
    curr[2] = cIndex64[curr[2]];
    *result++ = ((curr[1] & 0x0F) << 4) | ((curr[2] & 0x3C) >> 2);
    if ( curr[3] == '=' )
      ended = true;
    else
      *result++ = ((curr[2] & 0x03) << 6) | cIndex64[curr[3]];
  }
}

/*
 * QpEncoder
 */
static const char cBasisHex[] = "0123456789ABCDEF";

template <class InputIterator, class OutputIterator>
OutputIterator QpEncoder<InputIterator, OutputIterator>::filter(InputIterator first, InputIterator last, OutputIterator result, bool fin) {
  unsigned char c;
  for (; first != last; ++first ) {
    c = *first;
    if (c == '¥n') {
      if ( prevCh == ' ' || prevCh == '¥t') {
        *result++ = '='; // soft & hard lines
        *result++ = c;
      }
      *result++ = c;
      linepos = 0;
      prevCh = c;
    } else
    if ( (c < 32 && c != '¥t') || (c == '=') || (c >= 127)
          || ( linepos == 0 && c == '.') ) {
      *result++ = '=';
      *result++ = cBasisHex[c >> 4];
      *result++ = cBasisHex[c & 0xF];
      linepos += 3;
      prevCh = 'A';
    } else { // printable characters
      *result++ = prevCh = c;
      ++linepos;
    }

    if ( linepos > cLineLen) {
      *result++ = '=';
      *result++ = prevCh = '¥n';
      linepos = 0;
    }
  }
  if ( fin )
    finish(result);
  return result;
}

template <class InputIterator, class OutputIterator>
OutputIterator QpEncoder<InputIterator, OutputIterator>::finish(OutputIterator& result) {
  if ( linepos ) {
    *result++ = '=';
    *result++ = '¥n';
  }
  linepos = 0;
  prevCh = 'x';
  return result;
}

/*
 * QpDecoder
 */
static const unsigned char cIndexHex[256] = {
  XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
  XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
  XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
   0, 1, 2, 3,  4, 5, 6, 7,  8, 9,XX,XX, XX,XX,XX,XX,
  XX,10,11,12, 13,14,15,XX, XX,XX,XX,XX, XX,XX,XX,XX,
  XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
  XX,10,11,12, 13,14,15,XX, XX,XX,XX,XX, XX,XX,XX,XX,
  XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
  XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
  XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
  XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
  XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
  XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
  XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
  XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
  XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX, XX,XX,XX,XX,
};

template <class InputIterator, class OutputIterator>
OutputIterator QpDecoder<InputIterator, OutputIterator>::filter(InputIterator first, InputIterator last, OutputIterator result, bool fin) {
  unsigned char c, c1, c2;
  int errn = 0;

  for (; first != last; ++first) {
    if ( hexlen ) {
      if (*first == '¥n')
        hexlen = 0;
      else {
        hex2[hexlen-1] = *first;
        if ( hexlen++ == 2) {
          if (XX == (c1 = cIndexHex[hex2[0]]))
            ++errn;
          if (XX == (c2 = cIndexHex[hex2[1]]))
            ++errn;
          c = (c1 << 4) | c2;
          if (c != '¥r')
            *result++ = c;
          hexlen = 0;
        }
      }
    } else
    if (*first == '=')
      hexlen = 1;
    else
      *result++ = *first;
  }

  if ( fin )
    finish(result);
  return result;
}

template <class InputIterator, class OutputIterator>
OutputIterator QpDecoder<InputIterator, OutputIterator>::finish(OutputIterator& result) {
  if ( hexlen ) { // error
    hexlen = 0;
    return result;
  }
  return result;
}

#undef XX

できあがったencoder/decoderの動作確認コードを用意しました。char配列を入出力先として用いています。

using namespace std;

int main() {
  char c[256];
  char m[256];
  char* o;
  MimeCoder<char*, char*> *e, *d;

  cout << "Used base64 [b] or quoted-printable [q] ?¥n";
  cin >> c;
  if (c[0] == 'b' || c[0] == 'B') {
    e = new Base64Encoder<char*, char*>;
    d = new Base64Decoder<char*, char*>;
  } else {
    e = new QpEncoder<char*, char*>;
    d = new QpDecoder<char*, char*>;
  }

  cout << "Enter some text to encode.¥n";
  cin >> c;

  cout << "¥n¥nThe encoded text:¥n";
  o = e->filter(c, c + strlen(c), m, true);
  *o = '¥0';
  cout << m << flush;

  cout << "¥n¥nDecoded:¥n";
  o = d->filter(m, m + strlen(m), c, true);
  *o = '¥0';
  cout << c << flush;

  delete e;
  delete d;

  return 0;
}

複数パートからなるメールの形式 (multipart形式の例)

MIME規格にしたがって複数のファイルをメールに載せるには、'multipart'を用いる。

例としてmessage.txtをJIS,binary.lzhとpicture.gifをBASE64でメールに載せるときのformatを以下に示す。ただし、message.txtはファイルとしてではなく、メールのメッセージとしてメールリーダが出力することを想定している。また、(*..)は注釈であり、メールの中には記述されない。

To: どこそこ
Subject: どーのこーの
From: だれそれ
... なんやかんや ...
MIME-Version: 1.0
Content-Type: multipart/mixed;
boundary=NeverOccurred (*1)
--NeverOccurred (*2)
Content-Type: text/plain; charset=ISO-2022-JP
επιστημηです。
先日お約束していたbinary.lzh,picture.gifを送ります。
--NeverOccurred (*2)
Content-Type: application/octet-stream; name=binary.lzh (*3)
Content-Transfer-Encoding: base64 (*4)

(binary.lzhをBASE64で変換したテキストがここにある)
--NeverOccurred--NeverOccurred (*2)
Content-Type: application/octet-stream; name=picture.gif (*3)
Content-Transfer-Encoding: base64 (*4)

(picture.gifをBASE64で変換したテキストがここにある)

--NeverOccurred-- (*5)

※注釈

*1:Content-Type: multipart/mixed; boundary=NeverOccurred

'multipart': メッセージが複数のパートに別れている。

'mixed': 複数のパートそれぞれが互いに独立である。

'boundary': パートを区切る任意の文字列。

*2:--NeverOccurred

'boundary=...'で指定した文字列の頭に'--'を付加した文字列がパートの区切りとなる。

*3:Content-Type: application/octet-stream; name=binary.lzh

'application/octet-stream': バイナリ・データ。 'name': ファイル名。ただし、本パラメータは必須ではない。通常のメールリーダにおいては、このパラメータを'名前を付けてファイルの保存(Fileopen-dialog)'に渡すことになろう。

また、Content-Type:がimageやvideo,audioであったとき、テンポラリファイルを作成して、メールリーダにあらかじめ設定されたそれぞれのブラウザを起動する。設定されていなければファイルとしてsaveすることになるであろう。

*4:Content-Transfer-Encoding: base64

BASE64でencodeされている。Content-Transfar-Encodingが指定されていないとき、以下のボディはtext/plain; charset=us-asciiとみなす。

*5:--NeverOccurred--

multipartの最後の区切りはboundaryの前後に'--'を付加したものである。

メール送信のアルゴリズム

ヘッダを送信する。
空行を送信する。
ボディを送信する。
- textのとき: 指定したcharsetに従い、テキストを送信する。
- text以外のとき: 指定したEncoding(大抵BASE64)でファイルを送信する。
- multipartのとき、
  1. 送信したいファイルそれぞれについて:
    1. '--'とboundaryを送信する。
    2. ファイルを送信する(再帰!)。
  2. '--'とboundaryと'--'を送信する。

メール受信のアルゴリズム

空行を区切りとしてヘッダとボディに分割する。
ヘッダを解析し(Content-Type:)、
- multipartのとき: ボディをさらにboundaryで区切り、受信する(再帰!)。
- multipartでないとき:
  - textのとき: 指定されたcharsetに従いdecode/表示する。
  - text以外のとき: 指定されたencoding(大抵BASE64)に従いdecodeし、ファイルに出力する。

Content-Typeのいろいろ

Content-Type: **type**/**subtype**; **parameter**...
type	subtype	parameter
application	octet-stream/postscript	type/padding
audio	basic	(none)
image	jpeg/gif	(none)
message	rfc822/partial/external-body	...
multipart	mixed/alternative/digest/parallel	boundary
text	plain	charset
video	mpeg	(none)

Posted in misc | No Comments »

Making of C++ Technical Documents

Thursday, March 30th, 2006

HTMLを書いたことのある方はご存知でしょうが、HTMLの中にはタグと呼ばれる'<'と'>'で囲まれた書式指定がたくさん含まれています。

たとえばHTMLに <B>ボールド</B> と書けば ボールドと表示されます。

今あなたが読んでいる一連の&C++ Technical Documents&には大量のC++ソースコードが書かれています。C++のソースコードには'<'や'>'でいっぱいなので、これをそのままHTMLの中に書いちゃうとタグと誤認識されてしまいます。だから、

#include <iostream>
#include <algorithm>
#include "to_string.h"

using namespace std;

void std_count() {
  cout << "count, count_if" << endl;
  const int N = 6;
  int input[N] = { 2, 2, 4, 3, 2, 5 };
  cout << to_string(input, input+N) << " 内にある、" << endl
       << "   2 の数: " << count(input, input+N, 2) << endl;
}

は、HTMLでは:

<PRE>#include &lt;iostream&gt;
#include &lt;algorithm&gt;
#include &quot;to_string.h&quot;

using namespace std;

void std_count() {
  cout &lt;&lt; &quot;count, count_if&quot; &lt;&lt; endl;
  const int N = 6;
  int input[N] = { 2, 2, 4, 3, 2, 5 };
  cout &lt;&lt; to_string(input, input+N) &lt;&lt; &quot; 内にある、&quot; &lt;&lt; endl
       &lt;&lt; &quot;   2 の数: &quot; &lt;&lt; count(input, input+N, 2) &lt;&lt; endl;
}</PRE>

と書かねばなりません。すなわち、

'&' は '&' に、
'"' は '"' に、
'<' は '<' に、
'>' は '>' に

変換するわけですね。

この変換作業を手でやっていては時間がいくらあっても足りません。
このドキュメントを書くに先立ってソースコードをHTML形式に変換するちいさなプログラムを作ることにしました。

要するに上記の変換規則に従って文字を置き換えればいいわけです。

アルゴリズムはこんな感じ:

変換のための辞書を作る
入力がなくなるまで
1. 入力文字を取り出す
2. 入力文字をkeyとして検索する
3. 変換辞書に登録されていたら、対応するvalue(文字列)を出力する。
4. 変換の必要がないなら、入力文字をそのまま出力する。

よし、それではこのアルゴリズムに忠実なコードを示しましょう。もちろんSTLをバキバキに使います^^;

#include <string>
#include <map>

using namespace std;

template
OutputIterator
src2html(InputIterator first, InputIterator last, OutputIterator result) {
  map conv; // [1]
  conv['&'] = "&amp;";
  conv['&quot'] = "&quot;";
  conv['<'] = "&lt;";
  conv['<'] = "&gt;";

  while ( first != last ) { // [2]
    char ch = *first++; // [2.1]
    map::iterator i = conv.find(ch); // [2.2]
    if ( i != conv.end() ) // [2.3]
      result = copy(i->second.begin(), i->second.end(), result);
    else // [2.4]
      *result++ = ch;
  }
  return result;
}

ではこいつを使って標準入力から読み込んだソースをHTML変換して標準出力に吐き出しましょう。

int main() {
  ostreambuf_iterator<char> result(cout);

  string pre  = "<HTML><BODY><PRE>";
  copy(pre.begin(), pre.end(), result);

  istreambuf_iterator<char> input(cin);
  istreambuf_iterator<char> last;
  src2html(input, last, result);

  string post = "</PRE></BODY></HTML>";
  copy(post.begin(), post.end(), result);
  return 0;
}

完全なソースsrc2html.cppを自分自身に食わせでできたHTMLがこれです。

同様のWindowsアプリケーション&src2html.exe&をVisual C++ 6.0で書いてみました。

src2html for windows

このアプリケーションはエクスプローラからのDrag&Dropに対応しています。このページももちろん、src2html.exeを使って書きました。
こいつの全ソースおよび実行形式はここにあります。

Posted in misc | No Comments »

COMからのイベントを捕まえる方法

Thursday, March 30th, 2006

"見てくれ"を持たないCOMからのイベントの受理

Visual C++が提供してくれるATL(Active Template Library)を使うと、COM(Component Object Model)を簡単に作ることができます。

COMに発生した状態の変化をイベントとしてCOM利用者(Client)に通知したいことがあるでしょう。この機能が提供されていないと、COMの状態変化を知りたいClientはCOMに対してメソッドもしくはプロパティを定期的にコール/取得しなければなりません。

Clientに対してイベントを発行する機能を持ったCOMを作るには、dispinterface(ディスパッチ・インタフェース)と呼ばれる接続ポイントを用意します。接続ポイントには、COMが発行できるイベントを定義しておきます。このイベントは、実際にはイベント毎にユニークなIDとして表されます。

一方、COMからのイベントを受理するClientは、COMが用意した接続ポイントを実装し、COMが送出したIDに対応するハンドラを実装します。

COMはイベントの発行時に、ID、そしてイベントに付随するパラメータ(引数)をClientに引き渡すことができますが、このパラメータは型およびパラメータの数に自由度を与えるため、"任意の型"を表現できる型VARIANTの配列としてClientに引き渡されます。
Clientは引き渡されたVARIANT配列の一つ一つの要素をID(イベントの種類)に応じて、COMがイベントの発行時に引き渡した"本来の型"に戻さなくてはなりません。

ActiveXコントロールとしてCOMを作れば Visual BasicやVisual C++などのActiveXコントロール・コンテナを作れる開発環境下でActiveXコントロールをフォームやダイアログに貼り付ければ、COMから発せられるイベントのハンドリング、すなわちイベントIDとパラメータの解釈を自動的に行なってくれます。

ところがActiveXコントロールではないCOM、すなわち"見てくれ"を伴わないCOMの場合、イベントの受理に関するコードはプログラマが書かねばなりません。

NTTデータの中野さんが、ATLが提供するクラスIDispEventImplを使って、COMイベントをエレガントに受理する方法を見つけてくれました。
ビジネスロジックなどのように"見てくれ"を持たないCOMを利用するときのイベントの受理がとても簡単になるテクニックです。

お試しCOMを作る

まず、イベントを発行し、見てくれを持たないCOMをさくさくっと作っておきます。

Visual C++の"ATL COM AppWizard"で"CounterServer"なるDLLを作ります。

COM event figure #1

COM event figure #2

この段階ではまだCOMのいれものができただけです。
ATLオブジェクトを新規作成します。
作るのはCounter。"+1する"/"-1する"/"値を返す"の3つの機能をサポートします。

COM event figure #3

COM event figure #4

COM event figure #5

"オブジェクトウィザードのプロパティ"で"コネクションポイントのサポート"をチェックしておくのをお忘れなく。

ICounterにメソッドincr/decr、そしてプロパティvalueを追加します。

COM event figure #6

COM event figure #7

COM event figure #8

イベントはCounterの保持する値に変化が生じたときに、"changed"を発行させましょう。
_ICounterEventsにメソッドchangedを追加します。

そのとき、CounterのインタフェースICounterのポインタをパラメータとして渡し、Client側でイベントの発生したCOMを取得できるようにします。

COM event #9

インタフェースICounterの実装であるCCounterにイベントの接続ポイント_ICounterEventsをサポートさせます。

COM event figure #10

CCounterにはカウンタ値を保持するメンバ変数long value_を追加します。

COM event figure #11

ここまでの作業によって、すべての準備は整いました。

COM event figure #12

ではCCounterの実装に取り掛かりましょう。といっても実に単純な実装です。コンストラクト時にvalue_を0にし、incr()で+1、decr()で-1、get_value()でvalue_を返すだけです。incr()/decr()中でイベントを発行します。Wizardが作ってくれたFire_changed()を呼び出せばイベントの送出は完了です。

class ATL_NO_VTABLE CCounter :
  public CComObjectRootEx<CComSingleThreadModel>,
  public CComCoClass<CCounter, &CLSID_Counter>,
  public IConnectionPointContainerImpl<CCounter>,
  public IDispatchImpl<ICounter, &IID_ICounter, &LIBID_COUNTERSERVERLib>,
  public CProxy_ICounterEvents< CCounter > {
public:
  CCounter();

DECLARE_REGISTRY_RESOURCEID(IDR_COUNTER)

DECLARE_PROTECT_FINAL_CONSTRUCT()

BEGIN_COM_MAP(CCounter)
  COM_INTERFACE_ENTRY(ICounter)
  COM_INTERFACE_ENTRY(IDispatch)
  COM_INTERFACE_ENTRY(IConnectionPointContainer)
  COM_INTERFACE_ENTRY_IMPL(IConnectionPointContainer)
END_COM_MAP()
BEGIN_CONNECTION_POINT_MAP(CCounter)
CONNECTION_POINT_ENTRY(DIID__ICounterEvents)
END_CONNECTION_POINT_MAP()

public:
  STDMETHOD(get_value)(/*[out, retval]*/ long *pVal);
  STDMETHOD(decr)();
  STDMETHOD(incr)();
private:
  long value_;
};

// ---------- implementaion ----------

CCounter::CCounter() {
  value_ = 0;
}

STDMETHODIMP CCounter::incr() {
  ++value_;
  Fire_changed(this);
  return S_OK;
}

STDMETHODIMP CCounter::decr() {
  --value_;
  Fire_changed(this);
  return S_OK;
}

STDMETHODIMP CCounter::get_value(long *pVal) {
  *pVal = value_;
  return S_OK;
}

イベントを捕まえる

ここからが本題です。こうやって作られたCOMを動かすのに難しいことは何もありません。
COMの初期化や後始末を取り除けば、クラスIDからインスタンスを生成し、メソッドを呼び出すだけです。

int main() {
  CComPtr<ICounter> counter;
  counter.CoCreateInstance(CLSID_Counter);

  int i;
  for (i = 0; i < 10; i++)
    counter->incr();
  for (i = 0; i < 10; i++)
    counter->decr();

  return 0;
}

counterをince()/decr()するたびにcounterの中ではイベントを発行するのですが、
現時点ではそのイベントの受付窓口を用意していないので、ただ単にカウンタ値が増減しているだけです。

では、このCOM-ClientにCounterからのイベントを受理させましょう。

Counterはイベント発生時に、イベント通知のための接続ポイント_ICounterEventsに宣言されたメソッドを呼び出します。Clientにはインタフェース_ICounterEventsを実装したインスタンスを用意し、Counterに接続、つまり"何か起こったら僕にしらせてね"とお願いしておけばいいのです。が、これがけっこうややこしいんですね。

Counterがイベントを発行するメソッドFire_changed()の実装を見てみましょう:

template <class T>
class CProxy_ICounterEvents
  : public IConnectionPointImpl<T, &DIID__ICounterEvents, CComDynamicUnkArray>
{
public:
  VOID Fire_changed(ICounter * source) {
    T* pT = static_cast<T*>(this);
    int nConnectionIndex;
    CComVariant* pvars = new CComVariant[1];
    int nConnections = m_vec.GetSize();
    for (nConnectionIndex = 0; nConnectionIndex < nConnections; nConnectionIndex++) {
      pT->Lock();
      CComPtr<IUnknown> sp = m_vec.GetAt(nConnectionIndex);
      pT->Unlock();
      IDispatch* pDispatch = reinterpret_cast<IDispatch*>(sp.p);
      if (pDispatch != NULL) {
        pvars[0] = source;
        DISPPARAMS disp = { pvars, NULL, 1, 0 };
        pDispatch->Invoke(0x1, IID_NULL, LOCALE_USER_DEFAULT,
                         DISPATCH_METHOD, &disp, NULL, NULL, NULL);
      }
    }
    delete[] pvars;
  }
};

ようするにFire_changed()は接続されたハンドラそれぞれに対し、関数Invoke()を呼んでいます。
したがってClient側に用意するインスタンスには関数Invoke()をこさえておけば、イベント発生時にはそいつが呼ばれてくれることでしょう。

Client側に用意した関数Invoke()の中ではイベントのIDを識別し、さらにイベントに応じて第5引数(VARIANT型の集合)を解釈しなければならないのです。
ここでATLが提供するIDispEventImplを使えば、イベントの解釈がぐっと楽になるわけです。

イベント受理クラスCounterEventsはCComObjectRootExとIDispEventImplから導出します:

#define SINKID_COUNTEREVENTS 0

class ATL_NO_VTABLE CounterEvents :
  public CComObjectRootEx<CComSingleThreadModel>,
  public IDispEventImpl<SINKID_COUNTEREVENTS, CounterEvents,
                              &DIID__ICounterEvents, &LIBID_COUNTERSERVERLib, 1, 0>
{
public:
  CounterEvents() {}

そして、CounterEventsはインタフェース_ICounterEventsを実装していることを宣言します。

BEGIN_COM_MAP(CounterEvents)
  COM_INTERFACE_ENTRY_IID(DIID__ICounterEvents, CounterEvents)
END_COM_MAP()

次に、こいつに対してイベントID=1なるイベントを受理したら、メソッドhandle_changed()を呼び出してくれるよう仕組みます。

BEGIN_SINK_MAP(CounterEvents)
  SINK_ENTRY_EX(SINKID_COUNTEREVENTS, DIID__ICounterEvents,
                        1, handle_changed)
END_SINK_MAP()

handle_changed()は以下のように実装しました。

  virtual void changed(ICounter* pCounter) =0;

  HRESULT _stdcall handle_changed(ICounter* pCounter) {
    changed(pCounter);
    return S_OK;
  }
};

CcounterEventsの派生クラスでchanged()を再定義します。

class DerivedEvents : public CounterEvents {
  virtual void changed(ICounter* pCounter) {
    long lValue;
    pCounter->get_value(&lValue);
    std::cout << "update to " << lValue << std::endl;
  }
};

最終的に出来上がったClientはこうなります。

#include "stdafx.h"
#include <iostream>
#import "CounterServer/CounterServer.tlb" no_namespace, named_guids

CComModule _Module;

/*  CComInitializer : COM初期化クラス
 */
class CComInitializer {
  bool initialized_;

public:
  CComInitializer() : initialized_(false) { }
  HRESULT init() {
    HRESULT hr;
    hr = ::CoInitialize(NULL);
    if ( initialized_ = SUCCEEDED(hr) )
      _Module.Init(NULL, ::GetModuleHandle(NULL));
    return hr;
  }

  ‾CComInitializer() {
    if ( initialized_ ) {
      _Module.Term();
      ::CoUninitialize();
    }
  }
};

/* com_assert : エラーチェックと例外送出
 */
void com_assert(HRESULT result, const std::string& msg) {
  if ( FAILED(result) )
    throw std::runtime_error(msg);
}

#define SINKID_COUNTEREVENTS 0
#define MY_SINK_ENTRY(id,fn) ¥
  SINK_ENTRY_EX(SINKID_COUNTEREVENTS, DIID__ICounterEvents, id, fn)

/* CounterEvents : シンク(イベント受付窓口)クラス
 */
class ATL_NO_VTABLE CounterEvents :
  public CComObjectRootEx<CComSingleThreadModel>,
  public IDispEventImpl<SINKID_COUNTEREVENTS, CounterEvents,
                        &DIID__ICounterEvents, &LIBID_COUNTERSERVERLib, 1, 0>
{
public:
  CounterEvents() {}

BEGIN_COM_MAP(CounterEvents)
  COM_INTERFACE_ENTRY_IID(DIID__ICounterEvents, CounterEvents)
END_COM_MAP()

BEGIN_SINK_MAP(CounterEvents)
//  MY_SINK_ENTRY(1, handle_changed)
  SINK_ENTRY_EX(SINKID_COUNTEREVENTS, DIID__ICounterEvents, 1, handle_changed)
END_SINK_MAP()

  virtual void changed(ICounter* pCounter) =0;

  HRESULT _stdcall handle_changed(ICounter* pCounter) {
    changed(pCounter);
    return S_OK;
  }
};

#undef MY_SINK_ENTRY

/* DerivedEvents : イベントハンドラ
 */
class DerivedEvents : public CounterEvents {
  void changed(ICounter* pCounter) {
    HRESULT hr;
    long lValue = 0;
    hr = pCounter->get_value(&lValue);
    com_assert(hr,"get_value failed in changed event handler");
    std::cout << "update to " << lValue << std::endl;
  }
};

/* ecom_event_sink : シンクラッパー
 */
template<class Event>
class com_event_sink {
  typedef CComObject<Event> com_object_type;
  com_object_type*  sink_;
  CComPtr<IUnknown> unk_;
public:
  HRESULT create() {
    HRESULT hr = com_object_type::CreateInstance(&sink_);
    if ( SUCCEEDED(hr) )
      sink_->QueryInterface(IID_IUnknown,(void**)&unk_);
    return hr;
  }
  com_object_type* operator->() {
    return sink_;
  }
};

/* main : Let's try!
 */
int main() {
  try {
    HRESULT hr;
    CComInitializer com;
    hr = com.init();
    com_assert(hr, "CoInitialize failed");

    {
          // カウンタの生成
      CComPtr<ICounter> counter;
      hr = counter.CoCreateInstance(CLSID_Counter);
      com_assert(hr, "CCI ControlCounter failed");

      // イベントハンドラの生成
      com_event_sink<DerivedEvents> sink;
      hr = sink.create();
      com_assert(hr,"CCI Event sink failed");

      // 接続
      hr = sink->DispEventAdvise(counter);
      com_assert(hr, "DispEventAdvise failed");

      // メソッド呼び出し
      int i;
      for (i = 0; i < 10; i++) counter->incr();
      for (i = 0; i < 10; i++) counter->decr();

      // 解放
      hr = sink->DispEventUnadvise(counter);
      com_assert(hr, "DispEventUnadvise failed");
    }
  } catch ( std::exception& ex ) {
    std::cout << ex.what() << std::endl;
    return -1;
  }
  return 0;
}

Posted in misc | No Comments »

SMC(State Map Compiler) の拡張

Thursday, March 30th, 2006

はじめに

C Magazine 1999/9 で、SMC(State Map Compiler)を紹介しました。 SMCに状態遷移表を記述したスクリプト(テキストファイル)を食わせると、状態遷移表に書かれた通りに動作するFSM(Finite State Machine:有限状態機械) クラスを生成してくれます。

僕はこのSMCがいたく気に入り、更なる機能拡張を試みました。

スクリプト拡張

まず、SMCに食わすスクリプトの文法を少しばかり拡張しました。

namespace/package指定

SMCが吐くFSMおよびFSMが参照するコンテキストをnamespaceで囲む機能を追加しました。

スクリプトのヘッダ部に、
```
namespace <FSM-名前空間>
package   <FSM-package>
```
と書いておけば、FSMを指定したnamespaceに置くことができます。

package指定は後述する”Javaコード生成”時の package名を指定します。

同様にコンテキストに対しては、
```
contextnamespace <Context-名前空間>
contextpackage   <Context-package>
```
と記述します。
状態が遷移しないイベント
スクリプトの状態遷移部には、
```
状態 {
  イベント 次の状態 { アクション }
...
}
```
という形式で状態遷移を記述します。状態の遷移を伴わない場合、すなわち’次の状態’が’状態’に等しいときは、
```
状態 {
  イベント ----- { アクション }
...
}
```
のように、ひとつ以上の’-'を書くことができます。
遷移/アクションが一致するイベント
複数のイベントに対し、まったく同じ遷移/アクションを行なうとき、たとえば、
```
状態 {
  イベント-1 次の状態 { アクション }
  イベント-2 次の状態 { アクション }
  イベント-3 次の状態 { アクション }
    	...
}
```
のような記述は、
```
状態 {
  イベント-1 次の状態 { アクション }
  イベント-2 = イベント-1
  イベント-3 = イベント-1
...
}
```
と書くことで、イベント-2/イベント-3に対する遷移/アクションはイベント-1と同じであることを表現できます。

Javaコード生成

SMCにJavaコードを生成させたのが今回の拡張の目玉です。

fsmname          GateFSM
package          jp.gr.java_conf.episteme.fsm
namespace        fsm

context          GateContext
contextpackage   jp.gr.java_conf.episteme.ct
contextnamespace ct

initial          Locked

{

  Locked {
    Coin Unlocked Unlock
    Pass Locked   Alarm
  }

  Unlocked {
    Coin Unlocked ThankYou
    Pass Locked   Lock
  }
}

というスクリプトGateFSM.smをSMCに食わせます:

  smc -j GateFSM.sm   ... -j : Javaコード生成

すると、smcは以下のようなJavaソース’GateFSM.java’を生成します。

/* produced by SMC-Deluxe */
package jp.gr.java_conf.episteme.fsm;

class GateFSMState {
  public String name() { return "(GateFSMState)"; }
  public void Pass(GateFSM s) { s.getContext().FSMError("Pass", s.getState().name()); }
  public void Coin(GateFSM s) { s.getContext().FSMError("Coin", s.getState().name()); }
};

class GateFSMUnlockedState extends GateFSMState {
  // 省略...
};

class GateFSMLockedState extends GateFSMState {
  // 省略...
};

public class GateFSM extends jp.gr.java_conf.episteme.ct.GateContext {
  public GateFSM() { itsState = LockedState; }
  public void Pass() {itsState.Pass(this);}
  public void Coin() {itsState.Coin(this);}
  public void setState(GateFSMState theState) {itsState=theState;}
  public GateFSMState getState() {return itsState;};
  public String getStateName() {return itsState.name();};
  // 省略...
}

GateFSMのベースクラスjp.gr.java_conf.episteme.ct.GateContextとテストルーチンは以下のようになります。

/*
 * GateContext.java
 */

package jp.gr.java_conf.episteme.ct;

public class GateContext {

  public void FSMError(String event, String state)
    { System.out.println(state + " 状態で " +
                       event + " が発生するはずないのに!");
    }

  public void Lock()
    { System.out.println("ゲートを閉じます"); }

  public void ThankYou()
    { System.out.println("これはどうも...有り難く頂戴します"); }

  public void Alarm()
    { System.out.println("タダで入っちゃいけませんよ!"); }

  public void Unlock()
    { System.out.println("ゲートを開けます"); }

}

/*
 * gate.java
 */

import jp.gr.java_conf.episteme.fsm.*;

public class gate {

  public static void main(String[] arg) throws Exception {
    GateFSM fsm = new GateFSM();
    for ( boolean cont = true;  cont; ) {
      System.out.println("現在の状態は " + fsm.getStateName());
      System.out.print("Coin or Pass (c/p) ? ");
      int input = System.in.read();
      System.in.skip(System.in.available());
      switch ( input ) {
        case 'c' : fsm.Coin(); break;
        case 'p' : fsm.Pass(); break;
        default  : cont = false;
      }
    }
  }

}

FSMとコンテキストの分離

FSMはコンテキストの派生クラスというオブジェクトモデルではなく、 FSMとコンテキストを独立させるオプション’-s’を追加しました。

  smc -s GateFSM.sm     ... C++
  smc -j -s GateFSM.sm  ... Java

によって生成されたコードGateFSM.hおよびGateFSM.javaは以下のようになります。

/*
 * GateFSM.h
 */

#include "GateContext.h"

namespace fsm {
  ...
class GateFSM {
  ...
private:
  GateFSMState* itsState;
  ct::GateContext* itsContext;
public:
  void setContext(ct::GateContext& context) { itsContext = &context; }
  ct::GateContext& getContext() { return *itsContext; }
  ...
};
}

#endif

/*
 * GateFSM.java
 */
package jp.gr.java_conf.episteme.fsm;
  ...

public class GateFSM {
  ...
  public void setContext(jp.gr.java_conf.episteme.ct.GateContext context)
    { itsContext = context; }
  public jp.gr.java_conf.episteme.ct.GateContext getContext()
    { return itsContext; }
}

このように、FSMにメソッドsetContext()が追加されます。

FSMのコンストラクトの後、setContext()によって、コンテキストを設定してください。

実行途中でsetContext()することで、コンテキストをダイナミックに入れ換えることも可能です。

コンテキスト生成

オプション’-c’で、コンテキストにひな型(C++では”コンテキスト名.h” , Javaでは “コンテキスト名.java”)を生成します。

/*
 * GateContext.h
 */

#ifndef _H_GateContext
#define _H_GateContext

namespace ct {

class GateContext {
public:
  void FSMError(const char*, const char*);
  void Lock();
  void ThankYou();
  void Alarm();
  void Unlock();
};
}
#endif

/*
 * GateContext.java
 */

package jp.gr.java_conf.episteme.ct;

public class GateContext {
  public void FSMError(String event, String state) {
    // code here
  }
  public void Lock() {
    // code here
  }
  public void ThankYou() {
    // code here
  }
  public void Alarm() {
    // code here
  }
  public void Unlock() {
    // code here
  }
}

抽象コンテキスト

‘-a’オプションでコンテキストが抽象クラスとなります。

ただし、このオプションは’-s’と併用しなければなりません。

C++では全メソッドを純粋仮想関数とします。

/*
 * GateContext.h
 * (smc -c -a -s GateFSM.sm)
 */

#ifndef _H_GateContext
#define _H_GateContext

namespace ct {

class GateContext {
public:
  virtual void FSMError(const char*, const char*) =0;
  virtual void Lock() =0;
  virtual void ThankYou() =0;
  virtual void Alarm() =0;
  virtual void Unlock() =0;
};
}
#endif

Javaではinterfaceを定義します。

/*
 * GateContext.java
 * (smc -j -c -a -s GateFSM.sm)
 */

package jp.gr.java_conf.episteme.ct;

public interface GateContext {
  void FSMError(String event, String state);
  void Lock();
  void ThankYou();
  void Alarm();
  void Unlock();
}

抽象コンテキストの場合、C++/Javaそれぞれのテストルーチンは以下のようになります。

/*
 * gate.cpp
 */

#include "GateContext.h"
#include "GateFSM.h"
#include <iostream>

using namespace std;

class TheGateContext : public ct::GateContext {
public:
  virtual void FSMError(const char*, const char*);
  virtual void Lock();
  virtual void ThankYou();
  virtual void Alarm();
  virtual void Unlock();
};

void TheGateContext::Lock()
{ cout << "ゲートを閉じます" << endl; }

void TheGateContext::Unlock()
{ cout << "ゲートを開けます" << endl; }

void TheGateContext::Alarm()
{ cout << "タダで入っちゃいけませんよ!" << endl; }

void TheGateContext::ThankYou()
{ cout << "これはどうも...有り難く頂戴します" << endl; }

void TheGateContext::FSMError(const char* event, const char* state) {
  cout << state << " 状態で "
       << event << " が発生するはずないのに!"
  << endl;
}

int main() {
  TheGateContext context;
  fsm::GateFSM fsm;
  fsm.setContext(context);
  for ( bool cont = true;  cont; ) {
    char input[32];
    cout << "現在の状態は : " << fsm.getState().name() << endl;
    cout << "Coin or Pass (c/p) ? " << flush;
    cin >> input;
    switch ( *input ) {
      case 'c' : fsm.Coin(); break;
      case 'p' : fsm.Pass(); break;
      default  : cont = false;
    }
  }
  return 0;
}

/*
 * gate.java
 */

import jp.gr.java_conf.episteme.fsm.*;
import jp.gr.java_conf.episteme.ct.*;

class TheGateContext implements GateContext {

  public void FSMError(String event, String state) {
    System.out.println(state + " 状態で " +
                       event + " が発生するはずないのに!");
  }

  public void Lock()
  { System.out.println("ゲートを閉じます"); }

  public void ThankYou()
  { System.out.println("これはどうも...有り難く頂戴します"); }

  public void Alarm()
  { System.out.println("タダで入っちゃいけませんよ!"); }

  public void Unlock()
  { System.out.println("ゲートを開けます"); }

}

public class gate {

  public static void main(String[] arg) throws Exception {
    GateFSM fsm = new GateFSM();
    GateContext context = new TheGateContext();
    fsm.setContext(context);
    for ( boolean cont = true;  cont; ) {
      System.out.println("現在の状態は " + fsm.getStateName());
      System.out.print("Coin or Pass (c/p) ? ");
      int input = System.in.read();
      System.in.skip(System.in.available());
      switch ( input ) {
        case 'c' : fsm.Coin(); break;
        case 'p' : fsm.Pass(); break;
        default  : cont = false;
      }
    }
  }

}

Posted in misc | No Comments »

State Map Compiler

Thursday, March 30th, 2006

状態遷移表

FSM(Finite State Machine:有限状態機械)は、アプリケーションの分析･設計において重要なパートのひとつです。非常に多くのアプリケーションが、その動作をFSMによって記述することができます。

FSMは”State Map:状態表”あるいは”State Transition Table:状態遷移表”と呼ばれる表の形で表現されます。

“(門番のいる)ゲート”を例に、FSMを作ってみましょう。以下のようなState Mapを用意しました。

現在の状態	イベント	次の状態	アクション
Locked	Coin	Unlocked	Unlock
Locked	Pass	Locked	Alarm
Unlocked	Coin	Unlocked	ThankYou
Unlocked	Pass	Locked	Lock

このState Mapはゲートの制御モデルを表現しています。ゲートは2つの状態Locked(閉じている)とUnlocked(開いている)をもち、2つのイベントCoinとPassを受け付けます。

Coinイベント: 門番が入場料を受け取った
Passイベント: 誰かがゲートを通過した

また、ゲートには4つのアクションが定義されています。

Unlock: ゲートを開ける
Lock: ゲートを閉じる
Alarm: 警報を鳴らす
ThankYou: 余分なお金をもらったことに礼を言う

このState Mapの読み方は以下のとおりです:

ゲートがLocked状態のとき:
- Coinイベントが発生したら、Unlocked状態に遷移してUnlockアクションを起こす。
- Passイベントが発生したら、閉じているゲートを無理矢理誰かが通過したことに対しAlarmアクションを起こす
ゲートがUnlocked状態のとき:
- Passイベントが発生したら、Locked状態に戻してLockアクションを起こす
- Coinイベントが発生したら、余分なお金を頂いた事に礼を言う(ThankYouアクションを起こす)。

さて、このState Mapに表された動作を行なうプログラムをどのように書きましょうか。

いちばん単純なのは二重のswitch文です。つまり:

  enum { Locked, Unlocked } state;
  enum { Coin, Pass }       event;

  state s = Locked; // 初期状態
  event e;

  while ( true ) { // 無限ループ
    e = 発生したイベント;
    switch ( s ) {
    case Locked :
      switch ( e ) {
      case Coin :
        s = Unlocked;
        Unlock();
        break;
      case Pass :
        s = Locked;
        Alarm();
        break;
      }
      break;
    case Unocked :
      switch ( e ) {
      case Coin :
        s = Unlocked;
        ThankYou();
        break;
      case Pass :
        s = Locked;
        Lock();
        break;
      }
      break;
    }
  }

実に素直なコードです。この例では状態とイベントが2つづつだからまだマシですが、これが状態10コ/イベント10コに増えたとしたら500 行を越える長大なswitch文になってしまいます。書くのも大変読むのも大変デバッグするのはもっと大変、とてもやってられません。

二次元配列を使えばよりエレガントになります:

  enum { Locked, Unlocked } state;
  enum { Coin, Pass }       event;

  state Locked_Coin() {
    Unlock();
    return Unlocked;
  }

  state Locked_Pass() {
    Alarm();
    return Locked;
  }

  state Unlocked_Coin() {
    ThankYou();
    return Unlocked;
  }

  state Unlocked_Pass() {
    Lock();
    return Locked;
  }

  ...

  state s = Locked; // 初期状態
  event e;

  typedef state (*transition)();
  transition table[2][2] = {
    Locked_Coin,   Locked_Pass,
    Unlocked_Coun, Unlocked_Pass
  };

  while ( true ) {
    e = 発生したイベント;
    s = (*table[s][e])();
  }

状態とイベントの組それぞれに対し関数を用意し、その中でアクションの実行と次の状態の設定を行ないます。二重のswitch文よりはずっと奇麗ですが、状態数xイベント数と同数の関数定義が必要です。もっとエレガントなコードは書けないものでしょうか…

State Map Compiler

僕の愛用するクラスライブラリのひとつに Rogue Wave社のTools.h++ Professionalというのがあります。このクラスライブラリはFTP/HTTP/SMTP/POP3のクライアントをいとも簡単に作れるクラス群を提供しています。readmeドキュメントの中に、｢プロトコルの実装にはSMC(State Map Compiler)を使いました。SMCはhttp://www.oma.com/Offerings/catalog.htmlから無料で入手できます。｣とありました。

SMCによるFSMの実装手順を説明しましょう。まず、状態遷移表に現われるアクションを定義するクラス(”Context:コンテキスト”と呼んでいます)を作ります。

// GateContext.h

#ifndef __GATECONTEXT_H__
#define __GATECONTEXT_H__

class GateContext {
public:
  void Lock();
  void Unlock();
  void Alarm();
  void ThankYou();
  void FSMError(const char*, const char*);
};

#endif

// GateContext.cpp

#include "GateContext.h"
#include <iostream>

using namespace std;

void GateContext::Lock() { cout << "ゲートを閉じます" << endl; }
void GateContext::Unlock() { cout << "ゲートを開けます" << endl; }
void GateContext::Alarm() { cout << "タダで入っちゃいけませんよ!" << endl; }
void GateContext::ThankYou() { cout << "これはどうも...有り難く頂戴します" << endl; }

void GateContext::FSMError(const char* event, const char* state) {
  cout << state << " 状態で "
       << event << " が発生するはずないのに!"
       << endl;
}

次に、状態遷移表を表現するStateMapファイルを作ります:

// GateSFM.sm
fsmname GateFSM
context GateContext
header  GateContext.h
initial Locked

{
  Locked {
    Coin Unlocked Unlock
    Pass Locked   Alarm
  }
  Unlocked {
    Coin Unlocked ThankYou
    Pass Locked   Lock
  }
}

このファイルGateFSM.smをSMCに食わせます:

 smc < GateFSM.sm

するとSMCはgateFSM.hとgateFSM.ccを出力します。簡単なテストドライバをこさえましょう:

// gate.cpp
#include "gateFSM.h"
#include 

using namespace std;

int main() {
  GateFSM fsm;
  for ( bool cont = true;  cont; ) {
    char input[32];
    cout << "現在の状態は : " << fsm.GetState().StateName() << endl;
    cout << "Coin or Pass (c/p) ? " << flush;
    cin >> input;
    switch ( *input ) {
      case 'c' : fsm.Coin(); break;
      case 'p' : fsm.Pass(); break;
      default  : cont = false;
    }
  }
  return 0;
}

これで完了です。gate.cpp, gateFSM.cc, GateContext.cppをコンパイル/リンクすれば実行形式ができあがります。実行結果を以下に示します。

現在の状態は : Locked
Coin or Pass (c/p) ? c
ゲートを開けます
現在の状態は : Unlocked
Coin or Pass (c/p) ? p
ゲートを閉じます
現在の状態は : Locked
Coin or Pass (c/p) ? p
タダで入っちゃいけませんよ!
現在の状態は : Locked
Coin or Pass (c/p) ? c
ゲートを開けます
現在の状態は : Unlocked
Coin or Pass (c/p) ? c
これはどうも...有り難く頂戴します
現在の状態は : Unlocked
Coin or Pass (c/p) ? p
ゲートを閉じます
現在の状態は : Locked
Coin or Pass (c/p) ? /

GateFSMは受理できるイベントと同名のメソッドを持っており、発生したイベントに対応するメソッドのコールを繰り返すだけです。アクションを実装し、状態遷移表を書くだけでFSMによるアプリケーションができちゃうです。

FSMのからくり

以下に示した、SMCが吐いたコードを追いかけてからくりをあばいてみましょう。

// gateFSM.h

#ifndef _H_GateFSM
#define _H_GateFSM
#include <stddef.h>
#include "GateContext.h"

class GateFSM;

class GateFSMState {
public:
  virtual const char* StateName() const = 0;
  virtual void Pass(GateFSM& s);
  virtual void Coin(GateFSM& s);
};

class GateFSMUnlockedState : public GateFSMState {
public:
  virtual const char* StateName() const
  {return("Unlocked");};
  virtual void Pass(GateFSM&);
  virtual void Coin(GateFSM&);
};

class GateFSMLockedState : public GateFSMState {
public:
  virtual const char* StateName() const
  {return("Locked");};
  virtual void Pass(GateFSM&);
  virtual void Coin(GateFSM&);
};

class GateFSM : public GateContext {
  public:
  static GateFSMUnlockedState UnlockedState;
  static GateFSMLockedState LockedState;
  GateFSM();// default constructor
  void Pass() {itsState->Pass(*this);}
  void Coin() {itsState->Coin(*this);}
  void SetState(GateFSMState& theState) {itsState=&theState;}
  GateFSMState& GetState() const {return *itsState;};
  private:
    GateFSMState* itsState;
};

#endif

#include "gateFSM.h"

static char _versID[] = "No Version.";

GateFSMUnlockedState GateFSM::UnlockedState;
GateFSMLockedState GateFSM::LockedState;

void GateFSMState::Pass(GateFSM& s)
  {s.FSMError("Pass", s.GetState().StateName());}

void GateFSMState::Coin(GateFSM& s)
  {s.FSMError("Coin", s.GetState().StateName());}

void GateFSMUnlockedState::Pass(GateFSM& s) {
  s.SetState(GateFSM::LockedState);
  s.Lock();
}

void GateFSMUnlockedState::Coin(GateFSM& s) {
  s.SetState(GateFSM::UnlockedState);
  s.ThankYou();
}

void GateFSMLockedState::Pass(GateFSM& s) {
  s.SetState(GateFSM::LockedState);
  s.Alarm();
}

void GateFSMLockedState::Coin(GateFSM& s) {
  s.SetState(GateFSM::UnlockedState);
  s.Unlock();
}

GateFSM::GateFSM() : itsState(&LockedState) {}

GateFSMは全アクションが定義されたコンテキストGateContextから導出されています。このことにより、GateFSMは必要とするアクションをすべて手に入れた(コールできる)ことになります。privateメンバitsStateの型GateFSMStateは仮想関数 Coin()とPass()を持っていて、GateFSMのメソッドCoin()/Pass()はそのままitsStateの同名のメソッドCoin() /Pass()をコールします。

さらにGateFSMは、定義されている状態に対応する2つのクラスGateFSMLockedState,GateFSMUnlockedStateをstaticメンバに持ち、そのいずれもGateFSMStateの派生クラスです。

現在の状態がLockedである、すなわちitsState == &GateFSM::GateFSMLockedStateであるGateFSMのインスタンスに対しイベントCoinを発生させる(GateFSM::Coin()をコールする)と、

 void GateFSM::Coin() {
   itsState->Coin(*this);
 }

と定義されているので、GetFSMLockedState::Coin()がコールされます。GetFSMLockedState::Coin()にはLocked状態でCoinイベントが発生したときの処理が定義されています。

void GateFSMLockedState::Coin(GateFSM& s) {
s.SetState(GateFSM::UnlockedState);
s.Unlock();
}

状態遷移表GateFSM.smに記述したとおり、Unlocked状態に遷移した後にUnlockアクションをコールしています。他の状態/イベントの組み合わせに対しても同様です。

SMCはこれらのクラスおよび各メソッドを状態遷移表から生成してくれるわけです。

SMCの文法

ではもう少し大きなFSMを作りながら、SMCの文法を説明します。C++のソースコードからコメントを除去するアプリケーション”stripper”を作りましょう。

C++でのコメントは、

“//”から始まり、改行コードまで。
“/*”から始まり、”*/”まで

です。ソースコードから1文字づつ読み出し、FSMに食わせることでコメントを除去します。

この状態遷移図と等価な状態遷移表を以下に示します。

現在の状態	イベント	次の状態	アクション
outside	Slash	startingSlash
	Star	outside	PutChar
	EOL	outside	PutChar
	Other	outside	PutChar
]startigSlash	Slash	secondSlash
	Star	starAfterSlash
	EOL	outside	PutSlash PutChar
	Other	outside	PutSlash PutChar
secondSlash	Slash	secondSlash
	Star	secondSlash
	EOL	outside	PutChar
	Other	secondSlash
starAfterSlash	Slash	starAfterSlash
	Star	startingStar
	EOL	starAfterSlash		*
	Other	starAfterSlash		*
startingStar	Slash	outside
	Star	starAfterSlash
	EOL	starAfterSlash		*
	Other	starAfterSlash		*

これを基にSMCに食わすスクリプトファイルStripFSM.smを作ります。

FSMName StripFSM
Context StripperContext
Header  stContext.h
Initial outside
Version stripFSM.sm version 1.0

{
  outside {
    Slash    startingSlash   {}
    Star     outside         PutChar
    EOL      outside         PutChar
    Other    outside         PutChar
  }

  startingSlash {
    Slash    secondSlash     {}
    Star     starAfterSlash  {}
    EOL      outside         { PutSlash PutChar }
    Other    outside         { PutSlash PutChar }
  }

  secondSlash {
    EOL      outside         PutChar
    Other    secondSlash     {}
    Star     secondSlash     {}
    Slash    secondSlash     {}
  }

  (inStarComment) {
    Other    starAfterSlash  {}
    EOL      starAfterSlash  {}
  }

  starAfterSlash : inStarComment {
    Star     startingStar    {}
    Slash    starAfterSlash  {}
  }

  startingStar : inStarComment {
    Slash    outside         {}
    Star     startingStar    {}
  }
}

スクリプトはヘッダ部と状態遷移部に分かれていて、

ヘッダ部
{
  状態遷移部
}

の形式で記述します。

ヘッダ部
- FSMName FSM名
  
  生成するFSMの名前を指定します。ここで与えた名前がクラス名となり、最初の1文字を小文字に置き換え、拡張子”.cc”,”.h”を付けたコードが出力されます。
- Context コンテキスト名
  アクションを定義したコンテキストを指定します。FSMはこのコンテキストから導出されます。
- Header ヘッダ名
  FSMヘッダで#includeするファイル(通常コンテキストが宣言されたヘッダ)を指定します。
- Initial 初期状態
  FSMのコンストラクタで、ここに指定した初期状態をセットします。これを指定しなかったときは、SetStateメソッドで明示的に初期状態を設定しなければなりません。
- Version バージョン
  任意の文字列をバージョンIDとして指定できます。
状態遷移部
状態遷移部は、
```
状態 イベント 次の状態 アクション
```
を並べたものです。ひとつの状態に対しイベント/次の状態/アクションをまとめて記述する、
```
状態 {
  イベント1 次の状態1 アクション1
  イベント2 次の状態2 アクション2
  ...
}
```
の書式が許されています。

状態の遷移のみで、実行すべきアクションがないときは、
```
状態 イベント 次の状態 {}
```
としてください。また、複数のアクションを実行したいときは、
```
状態 イベント 次の状態
 { アクション1 アクション2 }
```
のように{}で囲んでください。

また、いくつかの状態で、イベント/次の状態/アクションが完全に一致するとき、それらを一つにまとめることができます。たとえば上記の状態遷移表での*の付けられた行は一致していますから、共通の状態遷移を()で囲み、
```
(inStarComment) {
  Other    starAfterSlash  {}
  EOL      starAfterSlash  {}
}
```
そしてそれを継承するような形式でそれぞれの差分を記述することができます。
```
starAfterSlash : inStarComment {
  Star     startingStar    {}
  Slash    starAfterSlash  {}
}

startingStar : inStarComment {
  Slash    outside         {}
  Star     startingStar    {}
}
```

コンテキストおよびメインルーチンを以下に示します。

// stContext.h

#ifndef _H_stripperContext
#define _H_stripperContext

#include <iostream.h>

class StripperContext {
private:
  char itsChar;
  istream *itsIStream;
  ostream *itsOStream;
public:
  StripperContext() { }

  void SetStreams(istream& i, ostream& o) {
    itsIStream = &i;
    itsOStream = &o;
  }

  void FSMError(const char* t, const char* s) {
      cerr << "Transition error: " << t
           << " in state " << s << endl;
  }

  int ReadChar() {
    int c;
    c = itsIStream->get();
    itsChar = c;
    return c;
  }

  void PutChar() { *itsOStream << itsChar; }
  void PutSlash() { *itsOStream << '/'; }
};
#endif

// stripper.cpp
#include <iostream.h>
#include <stdlib.h>
#include "stripFSM.h"

void main() {
  StripFSM myStripper;
  myStripper.SetStreams(cin,cout);

  while ( cin )
    switch( myStripper.ReadChar() ) {
      case EOF : exit(0);            break;
      case '/' : myStripper.Slash(); break;
      case '*' : myStripper.Star();  break;
      case '\n': myStripper.EOL();   break;
      default  : myStripper.Other(); break;
    }
}

Posted in misc | No Comments »