2章書きなおし！
リストの内部表現として、STLのlistやC++11のtupleを、
なるべくプリミティブに使って、
STLの機能をできる限り活用しようとしてきたが、
2.3.2節の実装にかかり限界が来たらしい。
柔軟なメソッドやalgorithmが多様に使えるlistや、
静的リスト限定ながら型の自由度が大きいtupleは、
それぞれに魅力的だったのだが、listは型の自由度が小さく、tupleは動的生成に弱い。
で、2.3.2節で構文解析が始まり、多様な型のデータを格納した複雑な木を、
動的に生成しなければならない状況に入って、お手上げ状態に。
2.3.2節だけならまだしも、構文解析はこの本の主要部なだけに、
ここでしっかり実装できなければならない。
う～ん、listやtupleを使うのはここまでか。
特にtupleは散々苦労しただけに、ここでやめるのも惜しいが、
 |
| オブジェクト指向における 再利用のための デザインパターン (GoF) |
苦労した分わかったことも多くて、ここまででも十分財産になった。
内部表現はなんでもいいのだ。
動的な木の生成か～、なんて言ったっけこういうの、
使う必要に迫られたことはなかったから、発想になかったわ。
Flyweightパターンも考慮する必要があるかもだが、
とりあえずこれで行こう。
boost
graph libraryとかまで言い出すと大仰すぎるしな。
関数型プログラミングとSTLにこだわるあまり、
C++のクラスを作る事自体を、拒絶してたところもあった。
つくづく自らの硬直した発想力が嫌になる。
ただCompositeパターンは、複雑な木の生成・破棄に関してのメモリマネジメントが、
メモリリークを防ぐためにとても重要。これは手じゃやりきれんので、
今まであまり使ったことないスマートポインタが必須だなこりゃ。
STLのauto_ptrとかを元に、参照カウントとか実装しないといけないのかなあ、
と一時途方に暮れたが、よく見ればC++11にはshared_ptrがあるわけで、
これは参照カウントあるじゃん。auto_ptrはむしろdeprecatedなのか。
これで一気に楽になった～、shared_ptrすげー！もう普通のポインタに戻れないかもｗ
完全なガベージコレクションとはいかないまでも、
自動ムーブコンストラクションとかも多分効いてるだろうから、
多少のマネジメントミスはかなり吸収してくれてるんじゃないかこれ。
shared_ptrを安全に使いこなせてる自信はまだないが、
悩みがだいぶ減ったのは確かだわ。C++11の表現力すげー、感動。
てか本当にすごいのはboostで、boost使いは前から知ってたんだろうが、
自らの不勉強に恥じ入ることしきり。
で、2章のコードはほとんど全部書きなおし。
リスト成分の内部表現はとりあえずstringで、
値の取り出しには別のテンプレートラッパvalue関数を実装する。
まー効率は度外視。これで行けるところまで行ってみよう。
でも基本機能を抽象の壁のむこうに追いやると、思ったより修正箇所が少ないし、
コードもコンパクトでわかりやすくなった。抽象の壁恐るべし。
もっと早くCompositeパターンに気づくべきだった。
基本機能のコードは以下の通り。これで2.2節までうまく行った（2.2.4節除く）。
これを使って、今までの2章のブログ記事もすべて書き直し。
だってヘタクソコードをいつまでも晒すのは恥ずかしいんだもん。
-----
//-------representation
of list (Composite pattern) ----------
typedef
string LeafItemType;
const
LeafItemType nullLeafItem(LeafItemType(""));
class
ListTree
{
public:
virtual ~ListTree(void){}
const shared_ptr<ListTree>
getParentList(void) const{
return(this->_predecessor);}
virtual const LeafItemType
getItem(void)const{
return(this->item);}
virtual const bool isList(void)const{
return(false);}
virtual void addElement(const
shared_ptr<ListTree>&){
cerr<<"You cannot add a leaf
to a leaf."<<endl;
exit(1);
}
virtual const shared_ptr<ListTree>
carElement() const{
cerr<<"You cannot take the
car of a leaf."<<endl;
exit(1);
}
virtual void removeFirstElement(){
cerr<<"You cannot remove the
first element of a leaf."<<endl;
exit(1);
}
virtual const int length(void)const{
cerr<<"You cannot get the
length of a leaf."<<endl;
exit(1);
}
virtual const bool
isNull(void)const{return(false);}
void changePredecessor(const
shared_ptr<ListTree>& _predecessorNew){
this->_predecessor=_predecessorNew;}
virtual const string getExpression(void)
const{
return(this->getItem());}
virtual const int getInt(void)const{
return(stoi(this->getItem()));}
virtual const double getDouble(void)const{
return(stod(this->getItem()));}
protected:
shared_ptr<ListTree> _me;
ListTree(void)=delete;
ListTree(shared_ptr<ListTree>
_predecessorIn,
const LeafItemType& itemIn=nullLeafItem):
_me(nullptr),
_predecessor(_predecessorIn),
item(itemIn)
{
_me=make_shared<ListTree>(*this);
}
private:
shared_ptr<ListTree> _predecessor;
LeafItemType item;
};
class
CompositeList:public ListTree
{
public:
CompositeList(const
shared_ptr<ListTree>& _predecessorIn=nullptr):
ListTree(_predecessorIn),_listTrees(0){}
virtual ~CompositeList(void){
if(! this->_listTrees.empty()){
for_each(this->_listTrees.begin(),this->_listTrees.end(),
[](shared_ptr<ListTree> _element){
if(_element && _element.unique()){
delete _element.get();
}
});
}
}
virtual const bool
isList(void)const{return(true);}
virtual void addElement(const
shared_ptr<ListTree>& _element)
{
this->_listTrees.push_front(_element);
_element->changePredecessor(this->_me);
}
virtual const shared_ptr<ListTree>
carElement() const{
return(this->_listTrees.front());
}
virtual void
removeFirstElement(){this->_listTrees.pop_front();}
virtual const int
length(void)const{return(this->_listTrees.size());}
virtual const bool
isNull(void)const{return(this->_listTrees.empty());}
virtual const string
getExpression(void)const{
string returnString("(");
for_each(this->_listTrees.begin(),this->_listTrees.end(),
[&returnString](const
shared_ptr<ListTree> _element){
returnString+=_element->getExpression()+" ";
});
if(!this->isNull()){returnString.pop_back();}
returnString.push_back(')');
return(returnString);
}
virtual const int getInt(void)const{
cerr<<"requiring an integer
value for a list."<<endl;
return(numeric_limits<int>::quiet_NaN());}
virtual const double getDouble(void)const{
cerr<<"requiring a double
value for a list."<<endl;
return(numeric_limits<double>::quiet_NaN());}
private:
list<shared_ptr<ListTree>>
_listTrees;
};
class
Leaf:public ListTree
{
public:
Leaf(void)=delete;
Leaf(const LeafItemType&
itemIn):ListTree(nullptr,itemIn){}
virtual ~Leaf(void){}
};
//---------abstraction
barrier---------
typedef
shared_ptr<ListTree> List;
//
print list
const
string listString(const List& _listTree)
{return(_listTree->getExpression());}
//
get value expression
//for
string
template
<typename ReturnType>
const
ReturnType value(const List& _listTree)
{return(_listTree->getItem());}
//for
list
template<>
const
List value<List>(const List& _listTree)
{return(_listTree);}
//for
int
template<>
const
int value<int>(const List& _listTree)
{return(_listTree->getInt());}
//for
double
template<>
const
double value<double>(const List& _listTree)
{return(_listTree->getDouble());}
const
List makeCopyList(const List& _listTree)
{
return(make_shared<CompositeList>
(*dynamic_pointer_cast<CompositeList>(_listTree)));
}
template<typename
ItemType>
const
List makeLeaf(const ItemType& x)
{
ostringstream tmpSStreamX;
tmpSStreamX<<setprecision(16)<<x;
return(make_shared<Leaf>(tmpSStreamX.str()));
}
template
<typename ReturnType,typename ArgType>
const
List leafMap(const function<ReturnType(ArgType)> procedure,
const List _leaf)
{
return(makeLeaf(procedure(value<ArgType>(_leaf))));
}
const
List cons(void){return(make_shared<CompositeList>());}
template
<typename ItemTypeX>
const
List cons(const ItemTypeX& x, const List& _yList)
{
List _yListCopy(makeCopyList(_yList));
_yListCopy->addElement(makeLeaf(x));
return(_yListCopy);
}
template<>
const
List cons<List>(const List& _xList,const List& _yList){
List _xListCopy(_xList);
List _yListCopy(makeCopyList(_yList));
_yListCopy->addElement(_xListCopy);
return(_yListCopy);
}
template
<typename ItemTypeX>
const
List cons(const ItemTypeX& x)
{return(cons(x,cons()));}
template
<typename ItemTypeX,typename ItemTypeY>
const
List cons(const ItemTypeX& x,const ItemTypeY& y)
{return(cons(x,cons(y)));}
const
List car(const List& _listTree)
{
return(_listTree->carElement());
}
const
List cdr(const List& _listTree)
{
if(!_listTree->isList()){return(cons());}
List _cdrListTree(makeCopyList(_listTree));
_cdrListTree->removeFirstElement();
return(_cdrListTree);
}
const
List makeList(void)
{
return(cons());
}
template<typename
ListType1, typename ... ListTypes>
const
List makeList(const ListType1& element1, ListTypes... elements)
{
return(cons(element1,makeList(elements...)));
}
//
size of a list
const
int length(const List& _listTree)
{
return(_listTree->length());
}
//
null?
const
bool isNull(const List& _listTree)
{
return(_listTree->isNull());
}
//
pair?
const
bool isPair(const List& _listTree)
{
return(_listTree->isList());
}
//---------abstraction
barrier---------
const
List cadr(const List& listIn)
{
return(car(cdr(listIn)));
}
const
List caddr(const List& listIn)
{
return(car(cdr(cdr(listIn))));
}
0 件のコメント :
コメントを投稿