目次

What's New

• 順序列コンテナパターン(jjAggregate, jjCollect) およびグラフパターン(jjGraph) に、 要素列の最後の要素を得るメソッド last() を追加しました。
• last() が順序列コンテナの共通メソッドとなったことに対応して、 今まで child() と呼んでいた「要素列の最初の要素を得る メソッド」を first() と呼ぶことにします。 first() ←→ last() のペアで考えると覚えやすいかと。
  従来の child() は互換性のために残してあります。

概要

特徴

1. 「C++操縦法(原題：Taming C++)」に 書かれている内容のうち、コンテナパターンとハッシュを 実装したものです。
2. 複数の class 間のパターン(1:nなど)を定義する際に便利で、 STL にはない特徴があります。
3. NIH ライブラリに比べて非常に短いステップでアプリケーションを 組むことができます。

jjPattern と C++操縦法に書かれているオリジナルものとの違いを挙げます：

1. template を使用せず、マクロを使用した
2. iterator に機能を幾つか追加した(列の途中からスタートできる)。
3. プリフィクスを ZZ から jj とした(深い意味は無い)
4. Hash パターンのサイズが 1024 byte 固定(可変長にする予定)
   (--> Ver1.5 で可変としました)
5. オブジェクト永続性はサポートしていない m(__)m

SAMPLE

1. 典型例
2. 木構造パターン
3. 複数の Part-A ファイルを使用する場合
4. 最小コスト経路

1. 典型例

また、ハッシュの使用例も示しています。

実行方法：

$ make sample01j

エラーが無ければ、実行ファイル a.out を作成し、実行します。実行結果として画面上に以下が表示されれば OK です：

P1 Object Oriented S/W Construction by Meyer Theory of Budo by Tugumasa Nangou : :

ソースの解説：
クラスとして、App, Publisher, Author, Book があり、それぞれ以下のような関係があります：

関係	意味
App : Publisher = 1:n	プログラム内で複数の出版者を扱う
App : Author = 1:n	プログラム内で複数の著者を扱う
Publisher : Book = 1:n	出版者は複数の本を扱う
Author : Book = 1:n	一人の著者は複数の本を書く
Hash in Book	Book にハッシュキーをつける

jjPattern の特徴は、クラス間の関係(パターン)をクラスとは独立に記述することで、クラス相互の依存関係を切り離し、クラス間の独立性を高めることです。具体的に、クラス間の関係はソースコードの以下の部分で記述しています：

jjCollect (publishers, App, Publisher); jjCollect (authors, App, Author); jjCollect (books, Publisher, Book); jjAggregate (byAuthor, Author, Book); jjHash (isbn_hash, App, Book);

各パターンの意味に関しては後述のライブラリの仕様を参照して下さい。 簡単に説明すると、jjCollect, jjAggregate 共に 1:n の関係を定義します。 jjAggregate は、子から親へのポインタを有する点が異なります。 jjHash(A,B) は A 上に B のハッシュ表を作成します。
例えば、上の定義の１行目は、App クラスと Publisher クラスとの間に 1:n の関係を定義し、その関係に "publishers" という名前をつけています。

各クラス(App,Publisher,Author,Book)ではお互いの関係を記述していない点に注目して下さい。これは、bgen(1) というプリプロセッサが、上の関係定義式から必要な情報を読みだし、各クラスに埋め込むということで自動化されています。各クラスの EXT_クラス名 というマクロが埋め込み情報に置き換わります。

jjPattern のもう１つの特徴が、検索の高速さです。
関係がクラス内に自動的に埋め込まれるため、検索の連鎖が高速に行えます。main() の最後の while 文を見て下さい。これは、iterator を使って全出版社を検索し、個々の出版社で扱っている本を表示し、その著者を表示しています。

出版社の検索は全件のシーケンシャルサーチです。従って、これには高速性の特徴はありませんが、その次の本検索と著者検索が、全てポインタによる直接検索である点がこの jjPattern の特徴です。

同様なことを DBMS や Hash ライブラリなどを使用すると、こういった類の検索(出版社→本、本→著者)でもキー検索となりますが、jjPattern は直接ポインタを使用しているため、非常に高速になるのです。

2. 木構造パターン

class Node {
    EXT_Node
        :
};

jjCollect(tree, Node, Node);

$ make sample02j
    

3. 複数の Part-A ファイルを使用する場合

この場合、複数の Part-A ファイルから１つの Part-B を生成する 必要があります。 sample03*.cpp, sample03*.h はその一例です。

実行方法：

$ make sample03

4. 最小コスト経路問題

sample04.cppがそのサンプルです。

実行方法：

$ make sample04

仕様 概要

ここで、n は要素数で、O(n)は「要素数に比例した処理時間かかる」を意味し、 O(log n)は「要素数の log(n)に比例した処理時間がかかる」ことを意味します。

Pattern		Pattern Methods												Iterator Methods
		add	ins	rep	fwd	bwd	del	child (first)	parent (from*1)	last	sel	num		++	--
jjCollect1	-,4*2	1	1	n	1	-	n	1	-	1	-	1		1	-
jjCollect	4,4	1	1	n	1	-	n	1	-	1	-	1		1	-
jjDCollect	4,8	1	1	1	1	1	1	1	-	1	-	1		1	1
jjDCollect1	-,8	1	1	1	1	1	1	1	-	1	-	1		1	1
jjAggregate	4,8	1	1	n	1	-	n	1	1	1	-	1		1	-
jjHash	*,4*3	1	-	-	-	-	1	-	-	-	1	1		1	-
jjGraph	4,12	1	-	-	1	1	n	1	1	1	-	1		1	-

註
*1: Graphパターンは、点N と辺E との間の関係がちょうど Aggregate パターンと同型である。Aggregate の parent() メソッドにあたるものが Graph では 辺E の出どころを示す from() メソッドです。
*2: パターンクラスの欄の右にある数字 n,m は、それぞれコンテナクラスで消費するバイト数、要素クラスで消費するバイト数、です。最新のデータを見るには、

$ make size

Method の解説

Iterator Methods

bgen(1)

bgen(1) - B Part Generator

bgen [-l libFile] sourcefile ...

jjPattern を使用している sourcefile を読み込んで、Part-B (クラスの埋め込み情報)を標準出力に生成するプリプロセッサ。生成された Part-B は sourcefile の中で読み込まれます(include)。 実行ファイルを創るまでのフローは以下のようになります：

        sourcefile
            |
            V
           bgen -> sourcefile.b
                        |
        sourcefile <-+(include)
            |
            V
          C++ Compiler
            |
            V
         Executable file

-l libFile

jjPattern ライブラリファイルを標準以外のものを指定する場合

inst_root/share/lib.bg - jjPattern 定義ファイル

(not yet)

(not yet)

jjAggregate -集約

jjAggregate -集約

SYNOPSIS

#include <jj/pattern.h>

jjAggregate(P, Top, Bot);

void    P_class::add     (Top *, Bot *);
void    P_class::ins     (Top *, Bot *);
Bot*    P_class::first   (Top *);
Bot*    P_class::child   (Top *);
Bot*    P_class::last    (Top *);
void    P_class::del     (Bot *);
Bot*    P_class::fwd     (Bot *);
Top*    P_class::parent  (Bot *);
int     P_class::num     (Top *);

        P_iterator::P_iterator();
        P_iterator::P_iterator(Top *);
void    P_iterator::start(Top *);
void    P_iterator::start2(Bot *);
Bot*    P_iterator::operator++();
    

DESCRIPTION

┌─┐ │ │Top └─┘ ↑　　　　↑　　　　↑ ↓　　　　│　　　　│ ┌─┐　　┌─┐　　┌─┐ │ │─→│ │─→│ │・・・ Bot └─┘　　└─┘　　└─┘

1:多の関係を実現するパターンの１つです。親へのポインタを持つ点が類似の 他のパターンに無い特徴です。

双方向Aggregate である jjDAggregate はまだ実装していません。

jjCollect, jjDCollect -コレクション、双方向コレクション

jjCollect, jjDCollect -コレクション、双方向コレクション

SYNOPSIS

#include <jj/pattern.h>

jjCollect(P, Top, Bot);
jjDCollect(P, Top, Bot);

void    P_class::add     (Top *, Bot *);
void    P_class::add     (Top *, Bot *b, Bot *b2);  --add b2 after b
void    P_class::ins     (Top *, Bot *);            --insert to top
void    P_class::ins     (Top *, Bot *b, Bot *b2);  --insert b2 before b jjDCollect only
Bot*    P_class::first   (Top *);
Bot*    P_class::child   (Top *);
Bot*    P_class::last    (Top *);
void    P_class::del     (Top *, Bot *);
Bot*    P_class::fwd     (Bot *);
Bot*    P_class::bwd     (Bot *);           --jjDCollect only
int     P_class::num     (Top *);

        P_iterator::P_iterator();
        P_iterator::P_iterator(Top *);
void    P_iterator::start(Top *);
void    P_iterator::start(Top *, Bot *); --jjCollect only
void    P_iterator::start2(Top *, Bot *);--jjDCollect only
void    P_iterator::start3(Bot *, Bot *);--jjDCollect only
Bot     *P_iterator::operator++();
Bot     *P_iterator::operator--();       --jjDCollect only
    

DESCRIPTION

┌─┐ │ │Top └─┘ ↓ ┌─┐　　┌─┐　　┌─┐ │ │←→│ │←→│ │・・・ Bot └─┘　　└─┘　　└─┘

1:多の関係を実現するパターンの１つです。
親へ戻るポインタは持っていません。

双方向Collection である jjDCollect は必要に迫られたので作成しました。

jjCollect1, jjDCollect1 -列、双方向列

jjCollect1, jjDCollect1 -列、双方向列

SYNOPSIS

#include <jj/pattern.h>

jjCollect1(P, Bot);
jjDCollect1(P, Bot);

void    P_class::add     (Bot *);
void    P_class::ins     (Bot *);
Bot*    P_class::first   ();
Bot*    P_class::last    ();
void    P_class::del     (Bot *);
Bot*    P_class::fwd     (Bot *);
Bot*    P_class::bwd     (Bot *);
int     P_class::num     ();

        P_iterator::P_iterator();
void    P_iterator::start();
void    Q_iterator::start(Bot *);       --jjDCollect1 only
Bot*    P_iterator::operator++();
Bot*    P_iterator::operator--();       --jjDCollect1 only
    

DESCRIPTION

first() ↓ ┌─┐　　┌─┐　　┌─┐ │ │←→│ │←→│ │・・・ Bot └─┘　　└─┘　　└─┘

列を実現するパターンの１つです。

jjHash -ハッシュ

jjHash -ハッシュ

SYNOPSIS

#include <jj/pattern.h>

jjHash(P, Holder, Element);

void    P_class::add(Holder *, Element *);
void    P_class::del(Holder *, Element *);
Element*P_class::sel(Holder *, Element *key);
int     P_class::num(Holder *);

        P_iterator::P_iterator();
        P_iterator::P_iterator(Holder *);
void    P_iterator::start(Holder *);
Bot*    P_iterator::operator++();

//implement
int     P_class::hash(Element *);
int     P_class::cmp(Element *in_hash, Element *key);

// convenient hash functions
int jjstr_hash(char *);

// utility function
void    P::put_stat(Holder *);
    

DESCRIPTION

Holder Elements ┌─┐ ┌─┐　　┌─┐　　┌─┐ │ │→│ │─→│ │─→│ │・・・ Bot ├─┤ └─┘　　└─┘　　└─┘ │ │→ ・・・ ├─┤ ・ ・ ├─┤ │ │ └─┘

キーインデックスを実現するパターン。 SYNOPSIS にも記述してあるように、２つのメソッド P_class::hash(), P_class::cmp() はハッシュパターンを使用する 側で提供しなければなりません。それぞれの仕様は以下です：

P_class:hash(key) - keyの正数ハッシュ値を返す
P_class::cmp(data,key) - data == key なら 0を, data != key なら !0 を返す

ここで、key, data は Element 型へのポインタ。

(2002/09/08 追加) なお、cmp() において、 data は hash 内の element、key は検索キーという違いがある点を 仕様として明記します。

ユーティリティとして文字列用ハッシュ関数 jjstr_hash() を提供しています。 文字列関係のハッシュパターンを構築したい場合、これを P_class::hash() の実装に使用することができます。

P::put_stat() は、ユーティリティの１つで、 ハッシュの衝突状況を表示するものです。

jjGraph -グラフ

jjGraph -グラフ

SYNOPSIS

#include <jj/pattern.h>

jjGraph(P, N, E);

void    P_class::add     (N *from, E *edge, N *to);
E*      P_class::first   (N *);
E*      P_class::last    (N *);
void    P_class::del     (E *);
E*      P_class::fwd     (E *);
N*      P_class::from    (E *);
N*      P_class::to      (E *);
int     P_class::num     (N *);

        P_iterator::P_iterator();
        P_iterator::P_iterator(N *);
void    P_iterator::start(N *);
E*      P_iterator::operator++();
    

DESCRIPTION

「グラフ」とは、点と線からなるものを指します。 下にグラフの一例を示します:

jjGraph は有向グラフを使用するためのパターンです。 グラフの数学的な定義は：

G = (N, E)

ここで、N = 点集合(node set)、E = 辺集合(edge set)

です。これに対応するグラフパターンの定義は以下のようになります：

class N { EXT_N ...};
class E { EXT_E ...};
jjGraph(G,N,E);

sample04.cppも参考のこと。

点 N の集合それ自体に対する処理、例えば

for all n in N ...

に相当するメソッドは jjGraph 自身では提供していませんが、 必要ならば jjCollect パターンなどを使って 別途宣言することで対応します。

私の考え

本ライブラリ jjPattern の原点である「C++操縦法」 の言うところの「パターン」は、今注目されている「 デザインパターン」の中の MEDIATOR パターンに相当する、C++ ライブラリ に位置付けられます。それはそれとして、「C++操縦法」の内容は非常にユニーク です。

Soukup氏は「プログラムを複雑にしているのは、 モジュール間の相互依存のせいである。 そのために個々のモジュールを独立してテストすることが難しくなっている。」 と指摘し、「モジュールをパターンとデータ構造に分け、 フラットな２階層型のモジュール関係を築くことで、モジュール間の独立性を増し、 単体テストを行いやすくし、ひいてはアプリケーションの複雑さを低減させる」 という方法を提案します。

その中から出てきたのが、著書の中にもでてくる、コンテナクラスを主とする パターンライブラリです。一見、 常識としてのオブジェクト指向に反しているような設計ですが、 氏の文章は非常に説得的で、私は 自分の PC で確認しながら理解してきました。

この書の中で非常に面白かったのは、同じ課題を Smalltalk, C++ Patternライブラリ, C++ NIHライブラリで作成し、比較するところです。 Patternライブラリを使用すると Smalltalk とほぼ同じステップ数で書けるあたり、 興味をひきます。

もう１つ、オブジェクトの永続化に関する議論をしているところも 非常に面白い内容でした。Disk access を主とする OODBMS(Object Oriented Database Management System)と、主記憶上での access を主とする永続データを比較している点です。メインメモリが 1G を超えることも普通になってきた昨今、1G程度の永続データなら全て on memory で高速に処理できることを考えれば、氏のアプローチも有望なものと思われます (今回、私の提供する jjPattern には永続データの機能は残念ながらありません)。

今までこのライブラリを極私的なプログラミングで使ってきた経験から言うのも 一面的かも知れませんが、公正を期すために言えば、パターン・ライブラリは非 常に癖があります。

1. まず、構造体にパターンを埋め込む(ZZ_EXT_...)という方法のため、当然ながら int, double などの基本型にパターンライブラリは直接使用できません。ここが STL と比較して弱いところかも知れません。 基本型にパターンライブラリを使用するためには、その基本型を含む class か struct を面倒でも定義する必要があります。

2. 次に、本の中に書かれているままのロジックでは、簡単に暴走するプログラム が書けてしまう、という問題があります。例えば、「C++操縦法」pp.128〜pp.131 のサンプルプログラムの中で、一旦 S1L1 に add したオレンジ o2 を削除(del) せずに S2L1 に add すると、pointer のループができ、iterator での検索時に 無限ループに陥ってしまいます。もちろん、このレベルの問題はこの書の範囲外 なのかもしれませんが...。

STL との比較

以下に、私なりの理解で簡単に要約します。

1. STL は「関係」をオブジェクトの中に埋め込む、ということをしないため、関連する検索の度に hash などのキー検索を使わざるを得ません。これは RDBMS がそうなのと同じです。一方、「C++操縦法」のアプローチは、SAMPLEにも示したように、ポインタによりダイレクトに「関係」を表現しているため、処理も速く簡単になる、という点が大きく異なります。

2. 先にも書きましたが、STL はどのデータにも適用できますが、jjPattern ではクラス型しか適用できません。

3. それと、jjPattern にはありませんが、 Soukup氏の会社 のちゃんとした市販ライブラリにはオブジェクトの永続化が可能となっていますが、 STL には無いようです。

オブジェクト指向とは矛盾しないか？

「オブジェクト指向でないからだめ」などと言う狭い見方はする必要はないのではないか、 と個人的には思っています。

この章の最後に

Reference

Erich Gamma / Richard Helm / Ralph Johnson / John Vlissides=著、本位田真一 / 吉田和樹=監訳 「デザインパターン(原題：Design Patterns)」、ソフトバンク、ISBN4-89052-797-4

History