Top / Pattern Japanese

jjPattern Ver.1.8
C++ Pattern Library

Last Updated: 2006-02-10

Contents

1. What's New
2. Summary
3. Sample
4. Spec. Summary
5. bgen(1) Part-B Generator
6. jjAggregate Aggregate
7. jjCollect, jjDCollect Collection, Double Collection
8. jjCollect1, jjDCollect1 List, Double List
9. jjHash Hash Table
10. jjGraph Graph
11. My Opinion
12. Reference
13. History

What's New

Add the following new features in Ver.1.8: The past "What's New" is here.

Summary

This package is a 'Pattern Library' for C++.

Feature

  1. Based on [JIRI]'s "Taming C++", jjPattern library provides several container patterns and hash pattern.
  2. It is convenient to build patterns(like one-to-many) between several classes. It is interesting to compare with STL. (See My opinion for more detail).
  3. The step of an application built by Pattern library is much smaller than by NIH class library. (See My opinion for more detail).

The differences between this jjPattern and [JIRI]'s are as follows:

  1. use cpp macro rather than template
  2. add some methods in iterator(e.g. starts from not only first element)
  3. change name prefix from 'ZZ' to 'jj'.
  4. Hash array size is now 1024 byte fixed(I'll enhance in near future).
    (--> fixed at Ver1.5)
  5. Parsistent is not supported, sorry!!
I've already been approved by Jiri Soukup to provide my jjPattern library publically.

SAMPLE

  1. Typical example
  2. Tree pattern
  3. Multiple Part-A files
  4. Graph Pattern: Least Cost Path Algorithm

1. Typical example

First sample is sample01.cpp. This sample builds the 1:n(one to many) relations between Publishers, Authors, and Books by using jjPattern, and then doing search & print.

The example of hash pattern is in this source as well.

How to run:
$ make sample01
    
If no error happens then executable file 'a.out' is generated and executed. If the printed is as follows then the sample completed without any error:
P1
  Object Oriented S/W Construction by Meyer
  Theory of Budo by Tugumasa Nangou
        :
        :
     

Explanation of sample01.cpp:
There are four classes; App, Publisher, Author, and Book. The relations between them (= pattern) are as follows:
Relation(Pattern)Description
App : Publisher = 1:n Several publishers in this sample.
App : Author = 1:n Several authors in this sample.
Publisher : Book = 1:n A publisher deals books.
Author : Book = 1:n An author writes books.
Hash in Book add hash key in Books

jjPattern's unique feature is to define relations(patterns) between classes independently from each class in order to avoid mutual(=cyclic) dependency between classes. For example, sample01.cpp defines the relations as the following source program fragment (Part-A):
jjCollect       (publishers,    App,            Publisher);
jjCollect       (authors,       App,            Author);
jjCollect       (books,         Publisher,      Book);
jjAggregate     (byAuthor,      Author,         Book);
jjHash          (isbn_hash,     App,            Book);
The detail information of this pattern-definition is described later in this document, but here brief explanation is. Both jjCollect and jjAggregate defines 1:n relations between two classes. The only differences is that jjAggregate defines pointer to parent from each child.
jjHash(A,B) consists hash table for B on A. For example, at the 1st line in above source fragment, defines 1:n relation between App and Publisher and names "publishers" on the relation.

It is important that there is no relation between each class definitons (see class definitions of App,Publisher,Auther,Book in the example), but there is one keyword like EXT_className.

Relations are defined at the above Part-A. Bgen(1) generates Part-B, which defines actual C++ source code of relation definition between classes, from the Part-A. This is automatic process by bgen(1) so that human does not have to take care the detail.

The next interesting thing is that the fastest search.
Relations are embedded in each class so that pointer is directly used to select relational data. Please look at while-loop at main() in the sample. This searches all of publishers by iterator, print books for each publisher, then print the author of the book.

Publisher-search is just sequential access, but in the outer-most while-loop, Book search and its Author search are directly accessed through pointer. This is the uniq feature of Pattern Library of [JIRI].

On the other side, when the same search is done by RDBMS, each search(Book search by publisher key, Author search by book key) is done by some index method (B-tree or Hash), not by pointer.

2. Tree pattern

sample02.cpp shows how to implement Tree Pattern. There is no "Tree specific pattern" like jjTree. Rather, any container pattern (like jjAggregate, jjCollect, jjDCollect) can be used as tree by defining "One node is parent and child as well" as follows:
class Node {
    EXT_Node
        :
};

jjCollect(tree, Node, Node);
How to run:
$ make sample02
    

3. Multiple Part-A files

when one application or project consists from multiple source files and header files, there may be several Part-A (pattern definition part) files.

In this case, Part-B is necessary to be generated from these Part-A files. sample03*.cpp, sample03*.h shows this case.

How to run:
$ make sample03
    

4. Least Cost Path

"Least Cost Path" algorithm is shown as an example of Graph Pattern. sample04.cpp is the sample file.

How to run:
$ make sample04
    


Spec. Summary

The following table shows access cost for each method of each pattern. The order of pattern is from simple to complex.

Where, 'n' in the table is number of elements, O(n) is "CPU cost in n order", O(log n) is "CPU cost in log(n) order", and so on.
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 -
NOTE
*1: The Pattern in Graph between Node N and Edge E is equivalent to Aggregate. parent() method in Aggregate corresponds to from() method in Graph.
*2: The two digits "n,m" in the left of pattern class means, n-bytes in container class, m-bytes in each element class, for each.
*3: Holder size is variable. It's initial size is 0(zero).

Description of Method

add(C *, E *); add element E to the last of container C -all except Hash
add element E to container C -Hash
add(C *, E *e1, E *e2);
  -all except Hash
add element e2 after e1 in container C
ins(C *, E *);
  -all except Hash
insert element E at the top of of container C
ins(C *, E *e1, E *e2);
  -only jjDCollect, jjDCollect1
insert(add) element e2 before e1 in container C
if C is empty or e1 is NULL then just add e2
rep(C *, E *e1, E *e2); Replace e1 and e2 in container C
fwd(E *); return next element of E
if E is the last one, then return first one
bwd(E *); return previous element of E
if E is first one then return last one
del(E *); -jjAggregate
del(C *, E *); -Other
Delete element E.
if pattern is jjAggregate or jjCollect, it costs O(n)
first(C *);
first(); -jjCollect1, jjDCollect1
child(C *);
Return first element of container C(jjCollect, jjDCollect, jjAggregate)
return first element of list(jjCollect1, jjDCollect1).
jjCollect1, jjDCollect1 doesn't have container class so that child() is not proper name. That's just the reason why first() exists. (Ver1.8) As well as, first() is introduced to all sequential container patterns as corresponding to last().
parent(E *); return container C of E. This is valid for only jjAggregate.
last(C *); --jjAggregate, jjCollect, jjDCollect, jjGraph
last(); --jjCollect1, jjDCollect1
return last element of container C(jjAggregate, jjCollect , jjDCollect, jjGraph).
return last element of list(jjDCollect1).
sel(C *, E *key); search in C by key, and return matched element. This is valid for only jjHash.
num(C *); return the number of elements in C

Iterator Methods

start(C *); reset Iterator.
when scan all of elements
start(C *, E *start);
reset Iterator.
when starts from E.
start2(E *start);
--for jjAssoc
reset Iterator.
when starts from E.
(Aug.30,2002) Changed start() -> start2() in order to support Tree pattern (e.g. At jjAggregate(pattern,Node,Node), pattern.start(Node) starts from parent and pattern.start2(Node) starts from the child.
start(E *start, E *end);
reset Iterator.
when scan from 'start' to 'end'.
operator++ return next element.
return NULL after reached last element
operator-- return previous element.
return NULL after reached first element

bgen(1)

NAME
bgen(1) - B Part Generator
SYNOPSIS
bgen [-l libFile] sourcefile ...
DESCRIPTION
bgen reads sourcefile(s) which includes jjPattern definitions, and generates Part-B(embedded pattern in class) to stdout. The generated Part-B will be included in sourcefile. The flow of compilation is:
        sourcefile
            |
            V
           bgen -> sourcefile.b
                        |
        sourcefile <-+(include)
            |
            V
          C++ Compiler
            |
            V
         Executable file

-l libFile

specify jjPattern library file when use non standard one
FILES
inst_root/share/lib.bg - jjPattern Definition File
SEE ALSO
(not yet)
BUGS
(not yet)

Before the explanation of each Pattern...

Now explanation of each pattern starts in alphabetical order, but I recommend to read in the following order:
  1. jjCollect, jjDCollect
  2. jjAggregate
  3. jjHash
  4. jjGraph
  5. jjCollect1, jjDCollect1 (option)
because jjCollect is typical as 'Pattern library' and the simplest. On the other side, jjCollect1 looks the simplest pattern. However, jjCollect is more suitable than jjCollect1 on an application which more than 2 classes consists some patterns (relations) with each other.

jjAggregate

NAME
jjAggregate -collection with pointers to parent

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


jjAggregate is one of 1:n(one to many) pattern. Each element has pointer to parent.

jjDAggregate(Dual directional Aggregate pattern) is not implemented yet, sorry.


jjCollect, jjDCollect -Collection, Dual Directional Collection

NAME
jjCollect, jjDCollect -Collection, Dual Directional Collection

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


1:n relation pattern.

jjDCollect is for dual directional collection.


jjCollect1, jjDCollect1 -list, dual list

NAME
jjCollect1, jjDCollect1 -list, dual list

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


This is for list of element.

jjHash -Hash pattern

NAME
jjHash -Hash pattern

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


pattern for Key index collection. As described in SYNOPSIS, It is users responsibility to impelemnt 2 methos:
P_class:hash(key) - return integer hash value from key
P_class::cmp(data,key) - return 0 if data == key, !0 if data != key

Where, key, a and b are pointer to Element type

(Sep.9,2002 add) New Spec.: in cmp(), data is in hash, key is search key.

Ready-made hash function for character-string 'jjstr_hash()' is provided so that user can use it for convenience.

P::put_stat() is a utility function to show confilicts of hash.


jjGraph -Graph pattern

NAME
jjGraph -Graph pattern

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 is for directed graph. In Graph-Theory of mathematics, graph is defined as:

G = (N, E)

Where, N is node set, and E is edge set.

The corresponding declaration of Graph Pattern is as follows:
class N { EXT_N ...};
class E { EXT_E ...};
jjGraph(G,N,E);
See sample04.cpp also.

jjGraph doesn't provide any operation for node set N like the following:

for all n in N ...
In such a case, use any container pattern like jjCollect as well.

My Opinion

Let me describe my personal opinion in this chapter. I appreciate to hear your any feedback, comment, and critique.

This package 'jjPattern' is based on [JIRI]. The 'pattern' described in this book is a kind of "MEDIATOR" Pattern written in 'Design Pattern' [GAMMA].
By the way, The [JIRI] book is very unique and interesting for me.

Dr.Jiri points out "Mutual dependency between modules makes project be complex. It makes module-test to be difficult."
He provides the solution; "divides module in two elements, pattern and class. The class doesn't have mutual dependency. The pattern has the responsibility to make pattern(relation) between classes. This relation between pattern and class makes two layer architecture in program, isolates modules, and unit test becomes easier. As the result, reduces the complexity of application."

Pattern Library is derived from his study. The design of his Pattern Library looks against to the traditonal Object-Oriented concept, but his theory is very attractive.

The most interesting part for me in his book is the comparison between Smalltalk, C++ Pattern Library, and C++ NIH Library on the same case study. It should be noticable that the source-code step of C++ Pattern Library version is almost the same as Smalltalk one, on the other side, NIH library version becomes 3 times longer than Pattern Library version.

Another hot topic of [JIRI] is Object Persistence. (Unforunately, jjPattern doesn't provide Object persistence).

I built jjPattern based on [JIRI], and have used for my personal programming. From my short-term experience, I feel Pattern library has its own uniq way.

1. First, Pattern Library can not be used for basic data type like int and double, because it embeds pattern in class/struct by the keyword ZZ_EXT_... If a prgrammer wants to apply Pattern to basic data type, he/she needs to create a wrapper class/struct which includes the basic data type as a member.

2. Second, careless program using Pattern easily falls into run-over. For example, in example 4.4, chapter 4 of [JIRI], when Orange o2 is added to S2L1 without deleting it from S1L1, list becomes infinite pointer loop. (This kind of issue might be out-of-scope of the book, though)

Compare with STL

Dr.Jiri provides his report so that please look at this for the detail.

I'll write my own understanding here.

1. STL doesn't embed 'relation' in class so that object search is always done by any kind of index(hash,etc.), just like RDBMS. On the other side, [JIRI]'s approach represents 'relation' by embedding pointer so that it is direct to find related object as I show at SAMPLE.

2. STIL can be applied to any data type, but Pattern is for only class or struct.

3. STL doesn't provide object persistence.
Dr.Jiri's company's library provides it.
My jjPattern doesn't.

Pattern Library is not OO?

I don't think Pattern Library is against to OO concept. Rather, Pattern and OO can be combined to complement with each other.

One more comment

Unfortunately, Japanese edition of [JIRI] contains a lot of typo and logical error. I am afraid that this surface miss causes a reader disappoints. I hope this book's primitive importance should not be hidden by such a non-important error. For example, in example 4.2, slist_base<T>::del(), the if-statement of its first line, e==tail should not necessary. I've already confirmed to Dr.Jiri about this logical error.
The important thing is to understand the theory/concept in the book, not findig any surface error. I think the value of this book is very high, that's the reason why I introduce this page for Pattern.

Reference

[JIRI] Jiri Soukup, "Taming C++; Pattern Classes and Persistence for Large Projects", Addison-Wesley Publishing Company, Inc., ISBN 4-8101-8088-3 (Japanese Edition)

[Gamma] Erich Gamma / Richard Helm / Ralph Johnson / John Vlissides, "Design Patterns", Addison-Wesley Publishing Company, ISBN 4-89052-797-4 (Japanese Edition)


History

'99-07-03 Ver.1.0 Initial Version
'99-09-20 Ver.1.0.1 Delete jjpattern.h::_jjCollect_iterator::_jjCollect_iterator
'00-01-15 Ver.1.02.0 Add Tree feature, jjCollect1, jjDCollect1.
Write English version of this document.
'01-04-20 Ver.1.3 support multiple Part-A files
'01-05-02 Ver.1.4 add jjGraph pattern
'03-03-24 Ver.1.5 jjHash size is now dynamic!
'03-09-18 Ver.1.6 num() and ins() are introduced
'06-02-10 Ver.1.8 first() and last() are applied to all sequential container patterns
See Release Note for more detail.