プログラミング・演習II

プログラミング・演習II
第１０回
オブジェクトの拡張
BinaryTree
総称
アクセス制御
双方向リストとpriorityQueue
Event
田向
前回までのデータ構造
スタック
First In Last Out (FILO)
キュー
First In First Out (FIFO)
メンバ関数は共通
push(char ch), pop();
メンバ変数は，スタックは現在位置を表す変数
キューは，push, popの位置を表す二つの変数
２進木： binaryTreeNode
class BinaryTreeNode {
BinaryTreeNode *left ，*right;
int value;
public:
BinaryTreeNode(int newValue)
{left = right = 0; value = newValue; }
~BinaryTreeNode() {…} //???
};
２進木：binaryTreeNode使い方
ノードをキー（値）で並べる．
新しいノードをN,
ツリー内の現在のノードをCとする．
１．Cをツリーの根とする．
２．Cが空でないとき
– キー(N) ＜キー(C)ならCを左部分
木に設定．
– キー(N) ＞キー(C)ならCを右部分
木に設定．
– キー(N) ＝キー(C)ならエラー
３．位置CにNを挿入する．
２進木： binaryTreeNode
12
（新値）
8
20
2
1
13
3
9
21
15
12
class BinaryTreeNode {
BinaryTreeNode *left ，*right;
int value;
public:
BinaryTreeNode(int newValue)
{left = right = 0; value = newValue; }
~BinaryTreeNode() {…} //???
};
12
（新値）
8
20
2
1
13
3
9
21
15
12
1.
2.
3.
4.
5.
12< (8)： false: cur->right≠0： move to right
12<(20): true : cur->left≠0 ：move to left
12<(13): true : cur->left≠0 ：move to left
12< (9): false: cur->right = 0 :
set at right of (9)
問題
１．以下に示す10個の数字を，示された
順番で2分木へ格納しなさい
6, 4, 3, 9, 0, 1, 2, 5, 7, 8
２．上記ルールで作成した2分木を使い，
入力したデータを昇順に読み出せること
を確認せよ
binaryTreeNode
Class BinaryTree {
BinaryTreeNode * root;
Public:
BinaryTree ( ){ root = 0; }
~BinaryTree( );
int insert(int value);
int lookup(int value);
};
int BinaryTree::lookup(int value){
BinaryTreeNode * cur = root;
while(cur){
if (cur->value == value) return 1;
else if ( cur->value <value)
cur = cur->left;
else
cur = cur ->right;
}
reuturn 0;
}
binaryTreeNode
Class BinaryTree {
BinaryTreeNode * root;
Public:
BinaryTree ( ){ root = 0; }
~BinaryTree( );
int insert(int value);
int lookup(int value);
};
int BinaryTree::lookup(int value){
BinaryTreeNode * cur = root;
while(cur){
if (cur->value == value) return 1;
else if (value < cur-> value)
cur = cur->left;
else
cur = cur ->right;
}
return 0;
}
２進木::insert
int BinaryTree::insert(int value){
BinaryTreeNode *cur = root;
if(cur==0){ // recursive call の終端処理
root = new BinaryTreeNode(value);
return 1; }
for(;;){
if(cur->value == value) return 0; //既にある．
else if(value < cur->value){
/*辿る先があれば，辿る．*/
if(cur->left){ cur = cur->left;
continue; } //for の最初から再実行
//行き止まりなので，そこにノードを作る．
cur->left=new BinaryTreeNode(value);
return 1; }
else{ if(cur->right){ cur=cur->right;
continue;}
//行き止まりなので，そこにノードを作る．
}
cur->right=new BinaryTreeNode(value);
return 1; }
}
２進木の総称化
• BinararyTreeNode には整数値(int value)しか入
れられない．
• 用途毎にcodeを書き換えなければ，ならない．
• 解決法：クラスを総称クラスに変える．
– オブジェクト自体ではなく，オブジェクトへのポ
インターを保持する．
class BinaryTreeNode {
BinaryTreeNode *left ，*right;
void * value;
public:
BinaryTreeNode(void* newValue)
{left = right = 0; value = newValue; }
~BinaryTreeNode() { }
};
– 未知の型のオブジェクトへのポインター
– ふたつのオブジェクトを比較するすべがない．
比較関数
• ２進木に入れる物の比較を専用に用意する．
• 関数へのポインタを取る．
– 関数にも（先頭）アドレスがあるから．
int (*function)(int , int );
引数が二つで，intの帰り値をとる関数へのポインタ
//typedef で関数ポインタ comparisonFunction を定義．
typedef int (*ComparisonFunction) (void *, void *);
class BinaryTree {
BinaryTreeNode *root;
ComparisonFunction _compare;
public:
BinaryTree(ComparisonFunction compare)
{root = 0; _compare = compare; }
~BinaryTreeNode() { }
virtual void *insert(void *value);
virtual int remove(int value);
void *lookup(void *value);
};
例１
• Btnodeに入れる物：文字列
• 二つの文字列を比較する関数を定義．
// 引数が二つで返り値がintの関数
int CompareString(void* v1, void* v2)
{
char *s1 = (char*) v1, *s2=(char*)v2;
return strcmp(s1，s2);
}
• Btree を作るときに，この比較関数を指定す
る． → そのアドレスを渡す．
main(){
BinaryTree bt(CompareString);
}
※復習：C言語で出たstdlib.hのqsort()の利用
方法と同じ
例２
• 作ったWindow画面をBinaryTree に入れる．
//画面
class myWindow : public window {
coord crdxyZ;
int width, height;
int winID;
…..
}
int CompareWindows( void* w1, void *w2)
{ coord* c1=w1->crdxyZ, c2=w2->crdxyZ;
return c1->z < c2->z;
}
• ｚの値でwindowsの重なり具合を決定するコードが
かける．
• 総称の機能を，もっと，組織的に綺麗に
強力にやりたい．
どうする？
Templateの書式
Complex，coordinateのところを変数Tのようにしたい．
template <class T>
class array {
T *p;
int size;
public:
array(){ p = new T[10]; if(!p) exit(1); size=10; }
array(int sz) { p = new T[sz]; if(!p) exit(1);
size = sz; cout << "「通常の」コンストラクタを使う\n"; }
~array() {delete [] p;}
array(const array &a);
void put(int i, T j) { if(i>=0 && i<size) p[i] = j; }
T get( int i){ return p[i]; }
int getSize(){return size;}
T &operator[](int i){return p[i];}
};
Template Library が作れる．
このarrayの呼び方： array<node>
a；程度が妥当．
汎用かつ強力，極めて重要な機能
けれど，単なる約束，決まり！！
クラスの継承
クラスの継承と合成とは異なる．
基本クラスから，下の記述で書かれる．
class className : public classBase {
//--public:
//--}
//node からANDを派生
class AND : public node{ //nodeと類似なもの
input i1, i2;
output o1;
Public:
…..
};
//AND，ORから halfAdder を合成
class halfAdder{
AND and1;
//部分として組み込まれる
OR or1 ;
Public:
…….
};
基本クラスのアクセス制御
class derived-class-name: access base-class-name {
//……
}
access ：
public：基本クラスの全ての公開メンバ
(public)が派生クラスの公開メンバになる．
private：基本クラスの全ての公開メンバ
(public)が派生クラスの非公開メンバ
(private)になる．
protected：基本クラスの被保護メンバー
(protected)は派生クラスのメンバーからも
アクセスできる．
基本クラスのアクセス制御 public
#include <iostream>
using namespace std;
class base {
int x;
public:
void setx (int n) { x = n; }
void showx() { cout << x << '\n'; }
};
class derived : public base {// publicとして継承する
int y;
public:
void sety(int n) { y = n; }
void showy() { cout << y << '\n'; }
};
int main(){
derived ob;
ob.setx(10); // 基本クラスのメンバにアクセス
ob.sety(20); // 派生クラスのメンバにアクセス
ob.showx(); // 基本クラスのメンバにアクセス
ob.showy(); // 派生クラスのメンバにアクセス
return 0; }
基本クラスのアクセス制御 private
#include <iostream>
using namespace std;
class base {
int x;
public:
void setx(int n) { x = n; }
void showx() { cout << x << '\n'; }
};
class derived : private base {// publicとして継承する
int y;
public:
void sety(int n) { y = n; }
void showy() { cout << y << '\n'; }
};
int main(){
derived ob;
ob.setx(10); // 基本クラスのメンバにアクセス ×
ob.sety(20); // 派生クラスのメンバにアクセス
ob.showx(); // 基本クラスのメンバにアクセス ×
ob.showy(); // 派生クラスのメンバにアクセス
return 0; }
基本クラスのアクセス制御 protected
#include <iostream>
using namespace std;
class samp {
int a; // デフォルトにより非公開
protected: // samp以外には非公開
int b;
public:
int c;
samp(int n, int m) { a = n; b = m; }
int geta() { return a; }
int getb() { return b; }
};
int main(){
samp ob(10, 20);
// ob.b = 99; エラー! bはprotected。したがって非公開
ob.c = 30; // OK。cは公開
cout << ob.geta() << ' ';
cout << ob.getb() << ' ' << ob.c << '\n';
return 0; }
protectedは派生ではアクセス可
#include <iostream>
using namespace std;
class base {
protected: // 基本クラス以外には非公開ながら
int a, b; // 派生クラスからはアクセスできる
public:
void setab(int n, int m) { a = n; b = m; }
};
class derived : public base {
int c;
public:
void setc(int n) { c = n; }
// この関数は、基本クラスのaとbにアクセスできる
void showabc() { cout << a << ' ' << b << ' ' << c << '\n'; }
};
int main(){
derived ob; /* aとbは、ここではアクセスできない。
基本クラスとその派生クラス以外には非公開 */
ob.setab(1, 2);
ob.setc(3);
ob.showabc();
return 0;
}
protectedは派生ではアクセス可
class base {
protected: // 基本クラス以外では非公開ながら
int a, b; // 派生クラスからはアクセスできる
public:
void setab(int n, int m) { a = n; b = m; }
};
class derived : protected base { // protectedとして継承
int c;
public:
void setc(int n) { c = n; }
// この関数は基本クラスのaとbにアクセスできる
void showabc() { cout << a << ' ' << b << ' ' << c << '\n'; }
};
int main(){
derived ob;
// エラー：setab()は基本クラスの被保護メンバ
ob.setab(1, 2); // ここからはsetab()にアクセスできない
ob.setc(3);
ob.showabc();
return 0;}
constructor，destructor の呼び出し順序
#include <iostream>
using namespace std;
class base {
public:
base() { cout << "baseクラスのコンストラクタ呼び出し
\n"; }
~base() { cout << "baseクラスのデストラクタ呼び出し\n"; }
};
class derived : public base {
public:
derived() { cout << "derivedクラスのコンストラクタ呼び出
し\n"; }
~derived() { cout << "derivedクラスのデストラクタ呼び出
し\n"; }
};
int main(){
derived o;
return 0;
}
呼び出し順序
Base → derived → derived → Base
多重継承
class derived-class-name: access base１，
access base2，・・・，access baseN {
//……
}
Derived-const(arg) : base1(arg1), base2(arg2),
･･･,baseN(argN){
//…..
}
いくつもの基本クラスから派生できる．
初期化子
“：” と “｛” の間に置く
仮想基本クラス
class derived-class-name: virtual access base-class-name
{
//……
}
virtual 仮に宣言する．処理は後で
基本クラスが重複した場合，複数のコピーが生じるのを防ぐ．
class base…
class derived1: public base ….
class derived2: public base …..
class derived3: public derived1, public derived2
…..
base のコピーがderived１ derived2 からのが二つあ
る．
必要になったときによく読んで理解する．
今は，あるということだけ知っていれば良い．
問題
１．10-1.cpp をコンパイルしてみよ．問題があ
る場合，なぜなのかを指摘して，正しく動
作するようにmain関数で問題がある部分
をコメントアウトして出力がどうなるか確認
せよ．
２．10-2.cppをコンパイルしてみよ．問題があ
る場合，なぜなのかを指摘して，正しく動
作するようにmain関数内を書き換えよ．
３．10-3.cppをコンパイルしてみよ．問題があ
る場合，なぜなのかを指摘して，正しく動
作するようにderivedクラスを書き換えよ．
４．10-4.cppをコンパイルして動作させよ．ど
のような順番でコンストラクタとデストラクタ
が呼び出されているか確認せよ．さらに，
コンストラクタの引数がどのように伝わって
いるか確認せよ．
離散イベント： event class
Class event( int index, class e)
• 何かの出来事e．離散的，個別的で
– indexで区別をつけることが出来る．
– 順序付けられると整理しやすい．
• 例）
– 信号の変化: (t1,1->0)，(t2,0->1),…
– 命令の順序： (t1, inst1), (t2,inst2),…
– 図の位置： (p1, ◎)，(p2, □),…
• event e1が発生，ｔ１後に処理
– (10, e1) , (5,e2), (12, e3), (2,e4)
– (2,e4), (5,e2), (10,e1), (12,e3) と並べ替
える必要がある．単純にqueueに積め
ない．
event class の実装
class event{ int eCode;
public:
int time;
event( ){time=0; eCode=0;}
event(int t, int e1){ time=t; eCode=e1;}
};
イベントをノードに積む．
class node{
public:
node* left; node* right; int index;
event e;
node( ){left=right=0; index=0;}
node (node* l, node* r, int i){ left=l; right=r;
index=i;};
};
queueの改良
push する時に，indexで入れる位置を探し
て挿入する．
Indexで並べてしまうqueueをpriority queue
という．
push(t,e)
1. t でqueueを調べて入れる場所を探す
2. 入れる場所に空きが無ければqueueの要
素をずらして場所を作る．
3. 出来た場所にeをコピーする
4. tos1,tos2を更新する．
5. queueがいっぱいになったとき困る．エ
ラー処理もいる．
priority queue
insert（）が頻繁に起こる．
いつも要素をずらしているととても遅くなる．
array が配列構造ではうまくいかない．
双方向リストで実現しよう．
class list{ node* root; int size;
public:
list( int s ){ node *pl, *pr;
root = pl = new node( 0, 0, 0); size=s;
for(int I=1; I<s;I++) {
pr=new node(pl,0,I);
pl->right=pr; pl=pr;} }
node& operator[ ](int j)；
};
priority queue-II
node& list ::operator[ ](int j)
{
node* p=root;
for(int i=0; i<size; i++){
if(p->index<j) p = p->right;
else if(p->index==j) return *p;
else
{
if(p->index>j)
{
node* p1 =
new node(p, p->right, j);
(p->right)->left=p1;
p->right = p1;
return *p1;
}
}
}
}
プログラムへの組み込み
class priorityQueue{
list queue;
public:
priorityQueue():queue(10){ }
push(event& e1){ queue[e1.time].e=e1;}
event& pop(int i) { return queue[i].e; }
};
main(){
priorityQueue EVH; //event handler
event e1(0,1);
EVH.push(e1);
event cEvent;
cEvent=EVH.pop(0);
cout << cEvent.time ;
}
binaryTree + priority queue I
List の替わりに binary tree で実現する
class BinaryTreeNode {
BinaryTreeNode *left ，*right;
void * value;
public:
BinaryTreeNode(void* newValue)
{left = right = 0; value = newValue; }
~BinaryTreeNode() { }
};
Class BinaryTree {
BinaryTreeNode * root;
Public:
BinaryTree ( ){ root = 0; }
~BinaryTree( );
int insert(int value);
int lookup(int value);
};
binaryTree + priority queue II
typedef int (*ComparisonFunction) (void *, void *);
class BinaryTree {
BinaryTreeNode *root;
ComparisonFunction _compare;
public:
BinaryTree(ComparisonFunction compare)
{root = 0; _compare = compare; }
~BinaryTreeNode() { }
virtual int insert(void * value);
virtual int remove(int value);
int lookup(void *value);
};
binaryTree + priority queue III
int BinaryTree::lookup(void* value){
BinaryTreeNode * cur = root;
while(cur){
if (cur->value == value) return 1;
else if ( _compare (value , cur-> value) )
cur = cur->left;
else
cur = cur ->right;
}
return 0;
}
binaryTree + priority queue IV
int BinaryTree::insert(void* value){
BinaryTreeNode *cur = root;
if(cur==0){ // recursive call の終端処理
root = new BinaryTreeNode(value);
return 1; }
for(;;){
if(cur->value == value) return 0; //既にある．
else if(_compare (value , cur->value)){
/*辿る先があれば，辿る．*/
if(cur->left){ cur = cur->left;
continue; } //for の最初から再実行
//行き止まりなので，そこにノードを作る．
cur->left=new BinaryTreeNode(value);
return 1; }
else{ if(cur->right){ cur=cur->right;
continue;}
//行き止まりなので，そこにノードを作る．
}
cur->right=new BinaryTreeNode(value);
return 1; }
}
binaryTree + priority queue V
class priorityQueue{
BinaryTree queue;
public:
priorityQueue(ComparisonFunction compare):
queue(compare){ }
push(event& e1){ queue[e1.time].e=e1;}
event& pop(int i) { return queue[i].e; }
};
int Compare0(void* v1, void* v2)
{
int *s1 = (int*) v1, *s2=(int*)v2;
return （ *s1 < *s2 );
}
main(){
priorityQueue EVH(Compare0); //event handler
event e1(0,1);
EVH.push(e1);
event cEvent;
cEvent=EVH.pop(0);
cout << cEvent.time ;
}
現在までの構造
双方向リストで伸び縮みするarrayが出来た．
Arrayに要素が無い場合には，新しく要素を
挿入することが出来る．
問題点：要素の探索が常に０から始めるので
遅くなる．しかし，当面は使える．
BinaryTree を使えばもっと早くなる．
Event：何でも良い，indexとして時間や，位
置を使えば，いろんなものを表現すること
が出来る．
priorityQueueに eventをしまうことが出来る
ようになった．
EventをBASEにして，派生eventを作ればよ
い．
オブジェクト再考
Classで色々なオブジェクトが作れる．
オブジェクト間での値，命令，メッセージなどはeventと
して扱うことが出来る．
座標系（ｘ，ｙ）をBinaryTreeでならべれば，
オブジェクトを配置することも出来る．
• 内部に座標系を作り，その領域をcoutに表示すれ
ばよい．
– ｍｙWindowの領域に書き込んで表示すれば
よい．
• オブジェクトとして， windowの画面（ソフト）以外で
も良い．
– カメラ（cmos センサー），マイク，
– サーボ・モータ：ロボットの手足，
– 動的な変化，事象（イベント），抽象的な物
• イベントとして，画像，音，ロボットへの命令，画面
の表示など，みな同じように扱える．
• FPGA内の回路もオブジェクト，
• 制御信号，データ，命令もイベント
• 画像オブジェクトを作ってライブラリにする．
オブジェクトの利用法
• 派生クラスの仕組み：基本的・共通・単純
なものから特定用途・専用・複雑なものを
作ることが出来る
• Template，総称の仕組み：共通の枠組
みを作り，扱う対象を自由に変えることが
できる．
• ライブラリを作ることが可能になる．
– 共通で基礎的なライブラリから多種多
様な専用化が組織的にできる．
STL(Standard Template Library)
• 半端・冗長である欠点を克服した
• 巨大・複雑なものが作成可能になった
（例）画像で使う部品色々ある
– gadget
– Visual component library
Builder，visual C++
画像ライブラリが用意されてある．
#include <Classes.hpp>，#include <Controls.hpp>
#include <StdCtrls.hpp>，#include <Forms.hpp>
#include <DBGrids.hpp>
#include <Grids.hpp>，#include <DBCtrls.hpp>
#include <Mask.hpp>，#include <ExtCtrls.hpp>
#include <Menus.hpp>
画像部品をFormに貼り付けて画像を設計
これらはすべてclass ,オブジェクトである
プログラム作成画面にコードを記述
クラスとメンバーが自動で
作成される
ハードもソフトもすべてオブジェクト
• オブジェクトにすれば，ｓｗとｈｗの区別が
無くなる．
• それぞれの処理速度，情報が異なるが
ディジタルではすべてバイナリ表現
• 相互のやり取りはイベントとする．
・・・・
image =
cameraObject->getView( );
30 flames/sec
・・・・
wtImage =
waveletObject->Trans();
・・・・
While( value > threhold){
・・・・
Value =
TempletObj>matching( level);
20ms
・・・・
}
Should be
30ms
ソフトでは6秒掛かる
HDL記述で回路もソフト
• プログラムと同様に記述して動かす
• オブジェクトと同じような概念
ソフトと同じようにシミュレーションで検証
• VDECのEDAツールを使用．
• 記述を修正，テストを繰り返す．
回路を合成する
FPGAに書き込む回路情報がファイルとして作られる
回路：bit stream data file
このファイルをclassのデータとする．
回路のオブジェクトを
Class hwObject{…}とする
Classのconstructorでobjectを作るときにこ
の回路をFPGAにロードする．
回路とのやり取りは event として処理．
プログラムの中から直接回路を制御すること
が出来る．
class hwObject{
bitStream bsc;
…
}
回路の動作：値の変化イベントの列

Download Report