2012/07/04

String chain using Typelist

久々ですがまたまたまた C++ Typelistネタ。

最近本当につくづく思うのですが、プログラミングにおいて Compositeパターンだとか、再帰的な 構造というのが、物事をシンプルにするのにすごく役立つということを感じます。

教科書的な Compositeパターンとしては、Compositeクラスなるものが あるインターフェースを継承した オブジェクトをコンテナに保有していて、そのアクションをコンテナオブジェクトに委譲するというものだったり しますが、このアイデアを「型」すなわちクラスまで持っていくと、より強力な構築概念になるのではないかと思います。

TypelistはこのCompositeパターンを構成するのに非常に役立つ道具と言えると思います。ここで文字列チェーンクラスを考えてみましょう。
template <typename T, typename TL>
struct StringChain;

// Chain starter implementation

template <NullType, NullType>
struct StringChain
{
    template <typename T>
    StringChain< T, Typelist<NullType, NullType> > operator()(const T& obj) const
    {
        return StringChain<T, Typelist<NullType, NullType> >(obj, *this);
    }

    ...
};
いきなり特殊化されたクラスを書き始めましたが、まずこの StringChainクラスはテンプレートの第一引数にある型、第二引数には、Typelistでエンコードされた型を取ります。そしてこの特殊化されたクラスは、Chainスタータと言って、文字列チェーンを作成開始するための特別なクラスとなります。 operator() 関数を使って、このクラスを成長させて行く訳です。

template <typename T, typename TL>
struct StringChain
{
    StringChain(const T& t, const StringChain& tl)
    : head(t), tail(tl)
    {
    }

    template < typename X >
    StringChain< X, Typelist< T, TL > > operator()(const T& obj)
    {
        return StringChain< X, Typelist< T, TL > > (obj, *this);
    }

    std::string str() const
    {
        std::string ret_str;
        ret_str.resize(getSize());
        size_t offset = 0;
        tail_.appendString(&ret_str[0], offset);
        appendString(&ret_str[offset], offset);
        return ret_str;
    }

    size_t getSize() const
    {
        return tail.getSize() + doGetSize(head);
    }

    void appendString(char* str_ptr,  size_t& offset) const
    {
        tail.appendString(str_ptr, offset);
        offset += doAppendString(str_ptr + offset, head);
        return;
    }
};

ここで doAppendString, doGetSize は StringChainの head要素に格納されているオブジェクトに対して 文字列を書き込む関数と文字列長を返却する関数です。 StringChainクラスにて扱う型に対してあらかじめ これらの関数を準備しておきます。
下記にサンプル実装をポストしました。
http://ideone.com/Ubmtd


It's quite long time since I posted C++ programming matter last time. This is again and again C++ Typelist.

Recently, I often come to think that so-called Composite pattern or some sort of recursive pattern / structure should be the key to simplify the structure in the programming.

According to some authoritative book or textbook kind of stuffs, what is explained as Composite pattern will be typically as follows. So-called Composite class which accommodates inherited class objects in its container or something like that, and then it delegates the very action to those objects. I would rather say that if we could successfully take this idea on to the level of type i.e. user-defined type (class), we can get more powerful construct.

And also I can say that Typelist can help to construct this pattern when it comes to applying Composite pattern into the type. As an example, let's consider the String chain class below.
template <typename T, typename TL>
struct StringChain;

// Chain starter implementation

template <NullType, NullType>
struct StringChain
{
    template <typename T>
    StringChain< T, Typelist<NullType, NullType> > operator()(const T& obj) const
    {
        return StringChain<T, Typelist<NullType, NullType> >(obj, *this);
    }

    ...
};
Although this is the very specialized class template implementation, StringChain class here will take 2 template paramters which takes first argument as conventional type and second argument as typelist encoded type. And this specialized class template is called as 'Chain starter', which will trigger the string chain object creation. By making use of operator() function, we are going to make the string chain grow.

template <typename T, typename TL>
struct StringChain
{
    StringChain(const T& t, const StringChain& tl)
    : head(t), tail(tl)
    {
    }

    template < typename X >
    StringChain< X, Typelist< T, TL > > operator()(const T& obj)
    {
        return StringChain< X, Typelist< T, TL > > (obj, *this);
    }

    std::string str() const
    {
        std::string ret_str;
        ret_str.resize(getSize());
        size_t offset = 0;
        tail_.appendString(&ret_str[0], offset);
        appendString(&ret_str[offset], offset);
        return ret_str;
    }

    size_t getSize() const
    {
        return tail.getSize() + doGetSize(head);
    }

    void appendString(char* str_ptr,  size_t& offset) const
    {
        tail.appendString(str_ptr, offset);
        offset += doAppendString(str_ptr + offset, head);
        return;
    }
};

Here, doAppendString and doGestSize function is the function to write head element to string buffer and size retrieval. We are supposed to prepare for appropriate overload functions towards types we are going to use with StringChain class in advance.
As for some sort of concrete code snippet, please take a look at the following. http://ideone.com/Ubmtd


Reference
Advanced C++ Metaprogramming - by Davide Di Gennaro

2012/06/21

Come back on court - Kei Nishikori

錦織選手がようやく怪我から復帰したようです。とにかく怪我には気をつけて今シーズンを 頑張ってほしいです。

早速 ウインブルドンやロンドンオリンピックが控えています。ウインブルドンは第19シード ですね。頑張れ!



It was reported that Japanese professional tennis player Kei Nishikori came back on court. Hope he continues to play this season without any further injuries.

Great thing that we may be able to see is that he should be shortly joining the exciting tournaments such as Wimbledon , London Olympic games etc.. As for the Wimbledon Championship, he is No.19 seeded. Anyway I believe that he can make it!

2012/03/14

Observer pattern using template and Typelist

またまた Typelistの話題。これまでのTypelistの用法を参考にして、Design Patternのうち
有用な Observerパターンを考えてみましょう。

まずは Observerクラスから。これに関しては任意の型のイベントを受け取るといった想定
で、下記のようなシンプルなテンプレートクラスにします。


#ifndef OBSERVER_H_
#define OBSERVER_H_

#include "typelist.h"

template <typename T>
class Observer
{
public:
    virtual void update(const T& event) = 0;
    virtual ~Observer() {}
};

#endif // OBSERVER_H_

このObserverクラスに対する通知を担う Subjectクラスですが、ここでTypelistを使用
してみます。


#ifndef SUBJECT_H_
#define SUBJECT_H_

#include <vector>
#include "typelist.h"
#include "observer.h"

template <typename TL>
class Subject;

template <typename T, typename U>
class Subject< Typelist<T, U> > : public Subject<U>
{
    typedef std::vector<Observer<T>*> Vector;
public:
    Subject() : observers_()
    {
    }

    ~Subject()
    {
    }

    using Subject<U>::notify;
    void notify(const T& event)
    {
        typename Vector::iterator it = observers_.begin(), end_it = observers_.end();
        for (; it != end_it; ++it) {
            (*it)->update(event);
        }
    }

    using Subject<U>::attach;
    void attach(Observer<T>* observer_ptr)
    {
        observers_.push_back(observer_ptr);
    }

    using Subject<U>::detach;
    void detach(Observer<T>* observer_ptr)
    {
        typename Vector::iterator it = observers_.begin(), end_it = observers_.end();

        for (; it != end_it; ++it) {
            if ((*it) == observer_ptr) {
                break;
            }
        }

        if (it != end_it) {
            observers_.erase(it);
        }
    }

private:
    Vector observers_;
};

template <>
class Subject<NullType>
{
public:
    void notify(const NullType& /* no use */)
    {
    }

    void attach(const NullType& /* no use */)
    {
    }

    void detach(const NullType& /* no use */)
    {
    }
};

#endif // SUBJECT_H_

このSubjectクラスはテンプレートパラメータとしてTypelistを受け取り、Typelist要素の型
に対して attach, detach, notify操作を支援します。クライアントコードにおいては、
Subjectクラスオブジェクトをメンバーとして保有して、detach, attachを委譲するような
メソッドを定義してやれば良い感じになります。

EventTypeListという型でイベントの型集合のTypelistがあるとすると、attach, detachの
委譲メソッドは下記のような感じになります。

#ifndef CONCRETE_SUBJECT_H
#define CONCRETE_SUBJECT_H

#include "subject.h"
#include "event_type_list.h"

class ConcreteSubject
{
public:
    ConcreteSubject();

    template <typename T>
    void attach(Observer<T>* observer)
    {
        typedef typename TypelistOf<EventTypeList, T>::Result TL;
        subject_.Subject<TL>::attach(observer);
    }

    template <typename T>
    void detach(Observer<T>* observer)
    {
        typedef typename TypelistOf<EventTypeList, T>::Result TL;
        subject_.Subject<TL>::detach(observer);
    }

    void action1();
    void action2();

private:
    Subject<EventTypeList> subject_;
};

ここで TypelistOfは以前に紹介した Typelistの部分集合を取り出す操作になります。



Again, I would like to take a look at Typelist. Making use of what has been adopted
until now, I would like to come up with Observer pattern which is quite useful among
various Design Patterns.

First, let's take a look at Observer class. Since we would like to handle various event
types, we are supposed to make the Observer class as parameterized class
(template class) as follows.

#ifndef OBSERVER_H_
#define OBSERVER_H_

#include "typelist.h"

template <typename T>
class Observer
{
public:
    virtual void update(const T& event) = 0;
    virtual ~Observer() {}
};

#endif // OBSERVER_H_

Secondly, we are going to build up Subject class by making use of Typelist as
follows.

#ifndef SUBJECT_H_
#define SUBJECT_H_

#include <vector>
#include "typelist.h"
#include "observer.h"

template <typename TL>
class Subject;

template <typename T, typename U>
class Subject< Typelist<T, U> > : public Subject<U>
{
    typedef std::vector<Observer<T>*> Vector;
public:
    Subject() : observers_()
    {
    }

    ~Subject()
    {
    }

    using Subject<U>::notify;
    void notify(const T& event)
    {
        typename Vector::iterator it = observers_.begin(), end_it = observers_.end();
        for (; it != end_it; ++it) {
            (*it)->update(event);
        }
    }

    using Subject<U>::attach;
    void attach(Observer<T>* observer_ptr)
    {
        observers_.push_back(observer_ptr);
    }

    using Subject<U>::detach;
    void detach(Observer<T>* observer_ptr)
    {
        typename Vector::iterator it = observers_.begin(), end_it = observers_.end();

        for (; it != end_it; ++it) {
            if ((*it) == observer_ptr) {
                break;
            }
        }

        if (it != end_it) {
            observers_.erase(it);
        }
    }

private:
    Vector observers_;
};

template <>
class Subject<NullType>
{
public:
    void notify(const NullType& /* no use */)
    {
    }

    void attach(const NullType& /* no use */)
    {
    }

    void detach(const NullType& /* no use */)
    {
    }
};

#endif // SUBJECT_H_

This parameterized Subject class would intake Typelist as template parameter
and then support attach, detach and notify operations towards respective
Typelist element types. In client code, we are supposed to composite the Subject
class object and then write some appropriate attach and detach method as
delegation.

Assuming that EventTypeList is the Typelist for various event types we are going to
support here, delegation methods for attach and detach will be like the following.

#ifndef CONCRETE_SUBJECT_H
#define CONCRETE_SUBJECT_H

#include "subject.h"
#include "event_type_list.h"

class ConcreteSubject
{
public:
    ConcreteSubject();

    template <typename T>
    void attach(Observer<T>* observer)
    {
        typedef typename TypelistOf<EventTypeList, T>::Result TL;
        subject_.Subject<TL>::attach(observer);
    }

    template <typename T>
    void detach(Observer<T>* observer)
    {
        typedef typename TypelistOf<EventTypeList, T>::Result TL;
        subject_.Subject<TL>::detach(observer);
    }

    void action1();
    void action2();

private:
    Subject<EventTypeList> subject_;
};

Here, TypelistOf operation is what was introduced the other day.

2012/03/13

Biz trip to NY

業務上でしたが、先週初めてNew Yorkに行ってきました。

当然仕事なので、New York観光という訳にはなかなか行きませんでしたが、少しは観光する
ことが出来ました。

一つはスポーツや音楽のイベントの聖地とも言える「ザ・ガーデン」こと Madison Square
Gardenにてカレッジバスケットボールの観戦と、ブロードウェイ(正確にはオフ・ブロード
ウェイ)のミュージカルを見ることが出来ました。

カレッジバスケットボールでは Big East Conferenceと呼ばれるカンファレンスから
Louisville vs Setonhallと University of South Florida vs Villanova の試合を観戦。

個人的には 1試合目の Louisvilleの内容が良かった。効果的なゾーンディフェンスで相手の
切り込みを封じていたように見えたし、PGの選手のシュート、パスそれから身体能力の
高さに驚かされました。この選手、ちょっと調べてみたところそれなりに注目されている
選手のようで、下記のような記事もあったり、YouTube映像なども投稿されていました。
ぜひとも将来はNBA入りして頑張ってもらいたいですね。

Draft NBA Express - Peyton Siva

もう一つのブロードウェイは、英語があまり判らないだろうということで、台詞が理解でき
なくても楽しめそうなものとして Million Dollar Quartet というのを鑑賞しました。これは
1950年代のある日に収録されたジャムセッションを再現するような形で綴られた、古き良き
ロックンロールのミュージカルです。Surf, Garage, Rockabilly好きの私としては
たまらない内容でとても良かったです。

Official site - Million Dollar Quartet



I had a chance to travel to New York for the first time last week, although it was a biz
trip.

Although the purpose of the trip was, of course, business, I could have spent some
time for some sightseeing, visiting NYC.

Firstly, I visited so-called "The Garden" Madison Square Garden - holy place for
sports and music where I could watch college basketball. And also I watched a(n)
(Off-)Broadway musical.

In college basketball games, I watched the following 2 games from Big East
Conference - Louisville vs Setonhall and University of South Florida vs Villanova.

I enjoyed the first game (Louisville vs Setonhall) very much. Louisville's zone
defense seemed to me quite effective towards the opponent and then effectively
prevent them from penetrate into the inner area. And also the PG's was quite good
for shots, passes and his physical performance. According to google, it seems that
he is rather famous among basketball fans.


Draft NBA Express - Peyton Siva

I hope that he can turn pro - NBA in future and can even succeed in his career.

As for the musical in the broadway, since it was quite possible that I could not
understand the exact dialog in the play, I chose Million Dollar Quartet where I
expected that I could enjoy even if I could not understand the story. The motif
of this musical came from a certain famous rock & roll jam session in 1950s,
which should have definitely attracted me, since I'm a big fan of such kind of
music like Surf, Garage and Rockabilly etc..



2012/02/29

Don't leave any broken window unattended

タイトルは「割れ窓」を放っておくな です。

これに関して、自分自身を振り返ってみるとなかなか実践できません。物事は放っておくと
エントロピー増大の法則で無秩序が拡大していくことを、改めて肝に銘じて置かないとと、
最近感じました。

社会学の世界では「割れ窓理論」は必ずしも認められていないようですが、このメタファー
はいろんなレベルで当てはまることが多いのではないでしょうか?




When it comes to the situation around me on the subjected matter, I must admit
that it's quite difficult for me to behave like this. We have to keep in our mind that
any kind of things will follow the second law of thermodynamics (law of entropy
increase). And we should continue to strive not to have any broken window.

It seems that so-called broken windows theory is not always appreciated in the
world of sociology. However, I think that this should be applicable in various
situations.



Reference : Extract from the book - Pragmatic Programmer
                   Broken Windows Theory (Wikipedia)

2012/02/24

Typelist exercise - TypelistOf, TypelistAt operation

またまたC++ネタ、しかもまたTypelistです。

Typelistから Typelistの部分集合を得る操作をやってみましょう。ネーミングが適切
かどうか判りませんが、 先頭に配置したい要素を指定する TypelistOfオペレーションと
N回下る操作の TypelistAtを考えてみます。


template <typename TL, typename V>
struct TypelistOf;

template <typename T, typename U, typename V>
struct TypelistOf< Typelist<T, U> >
{
    typedef typename TypelistOf<U, V>::Result Result;
};

template <typename T, typename V>
struct TypelistOf< Typelist<V, T>, V >
{
    typedef Typelist<V, T> Result;
};



次は N番目のTypelistを得る TypelistAt操作です。
template <typename TL, int N>
struct TypelistAt;

template <typename T, typename U>
struct TypelistAt<Typelist<T, U>, 0>
{
    typedef Typelist<T, U> Result;
};

template <typename T, typename U, int N>
struct TypelistAt<Typelist<T, U>, N>
{
    typedef typename Typelist<U, N - 1>::Result Result;
};



こういったTypelist操作を持っていると単一継承階層を作るのに非常に便利だと思います。
例えばTypelistAt操作を使って 下記のような感じでTupleを構成できます。

template <typename TL>
struct Tuple;

template <typename T, typename U>
struct Tuple< Typelist<T, U> > : public Tuple<U>
{
    T value;

    typedef Typelist<T, U> ThisType;

    template <int N>
    typename TypeAt<ThisType, N>::Result& getValue()
    {
        typedef Tuple<typename TypelistAt<ThisType, N>::Result> ThatType;
        return this->ThatType::value;
    }
};


Modern C++ Designで紹介されている Tupleよりずっとシンプルだと思います。
またこのアイデアは Advanced C++ Metaprogrammingで紹介されている pop_front操作をより
汎化させたものとも言えます。同様の実装が本書では Agglomerate objectとして紹介されています。





Again, I'm going to take a look at another C++ matter and also it is regarding Typelist.

Let's try to manipulate Typelist to derive 'partial' Typelist. Although I'm not really sure
the naming adopted here is appropriate, TypelistOf is the operation to derive the partial Typelist
whose first element type is the requested type. Another one, TypelistAt is the simple operation
to derive N-th Typlist.

The TypelistOf operation will be something like the following.

template <typename TL, typename V>
struct TypelistOf;

template <typename T, typename U, typename V>
struct TypelistOf< Typelist<T, U> >
{
    typedef typename TypelistOf<U, V>::Result Result;
};

template <typename T, typename V>
struct TypelistOf< Typelist<V, T>, V >
{
    typedef Typelist<V, T> Result;
};



On the other hand, TypelistAt operation should be something like this.

template <typename TL, int N>
struct TypelistAt;

template <typename T, typename U>
struct TypelistAt<Typelist<T, U>, 0>
{
    typedef Typelist<T, U> Result;
};

template <typename T, typename U, int N>
struct TypelistAt<Typelist<T, U>, N>
{
    typedef typename Typelist<U, N - 1>::Result Result;
};



I think this type of Typelist operation will be useful when you want to construct single inheritance
hierarchy. For example, when you use TyplistAt operation, you will be able to easily realize so-called 'Tuple'
as follows.

template <typename TL>
struct Tuple;

template <typename T, typename U>
struct Tuple< Typelist<T, U> > : public Tuple<U>
{
    T value;

    typedef Typelist<T, U> ThisType;

    template <int N>
    typename TypeAt<ThisType, N>::Result& getValue()
    {
        typedef Tuple<typename TypelistAt<ThisType, N>::Result> ThatType;
        return this->ThatType::value;
    }
};


I wonder the above implementation should be much simpler and easy to understand than what is
introduced in Modern C++ Design.

And also, this idea will be some more generic version of 'pop_front' operation which is explained in Advanced
C++ Metaprogramming. A similar implementation is also introduced in this book as 'agglomerate object'.

2012/02/23

Very very small tips on STL std::pair

STL std::pair< >についての小ネタ

ちょっと備忘録的なものですが、std::pairって 下記のように算術演算子が overloadされているんですね。知らなかった。

#include <utility>
class TestClass
{
    // ... some implementation here
};

TestClass test1, test2;

std::pair<TestClass, int> obj1(test1, 2), obj2(test2, 3);

bool ret = (obj1 == obj2);  // TestClassに bool operator==(const TestClass& rhs) const などが定義されていれば可能

ret = (obj1 < obj2);  // TestClassに bool operator<(const TestClass& rhs) constなどが定義されていれば可能


テンプレートのインスタンス化は利用される時まで遅らせるという仕組みがうまく利用されている実装ですね。




This is very very small tips in terms of std::pair< > .

I didn't know that std::pair< > implementation also overloads arithmetic operators until now.

#include <utility>
class TestClass
{
    // ... some implementation here
};

TestClass test1, test2;

std::pair<TestClass, int> obj1(test1, 2), obj2(test2, 3);

bool ret = (obj1 == obj2);  // possible if TestClass define e.g. bool operator==(const TestClass& rhs) const

ret = (obj1 < obj2);  // possible if TestClass defines e.g. bool operator<(const TestClass& rhs) const


Now we can see that lazy evaluation of the template instantiation surely makes for.



Reference: C++ Reference - pair