tree.cpp

   1 #include <iostream>
   2
   3 #include <assert.h>
   4 #include <exception>
   5
   6 #include "tree.h"
   7 #include <stack>
   8 #include <queue>
   9
  10 #include "utf8_string.h"
  11 #include "literal_data.h"
  12 #include "literal.h"
  13 #include "datum_id.h"
  14
  15 using namespace utakata;
  16 using namespace utakata::literal;
  17 using namespace utakata::utf8_string;
  18 using namespace utakata::syntax;
  19
  20 // 原則としてそれぞれ単純に呼びだされるのみ。
  21
  22 struct Tree::TreeNode
  23 {
  24     TreeNode(node_pair p) : datum(p) {}
  25
  26     smart_ptr<TreeNode> parent;
  27     smart_ptr<TreeNode> car;
  28     smart_ptr<TreeNode> cdr;
  29     std::vector<smart_ptr<TreeNode> > child;
  30
  31     Tree::node_pair datum;
  32
  33 };
  34
  35 //syntax::Tree::TreeNode::TreeNode(std::pair<DatumID, smart_ptr<literal::Literal> > p) : datum(p) {}
  36
  37 ////////////////////////////
  38 // syntax::Tree::iterator //
  39 ////////////////////////////
  40
  41 syntax::Tree::iterator::iterator() : node_(), current_()
  42 {
  43 }
  44
  45 syntax::Tree::iterator::iterator(smart_ptr<TreeNode>& node) : node_(node)
  46 {
  47     current_ = node->child.begin();
  48 }
  49
  50 syntax::Tree::iterator::iterator(const Tree::iterator& i)
  51 {
  52     swap(i);
  53 }
  54
  55 syntax::Tree::iterator& syntax::Tree::iterator::operator=(const Tree::iterator& rh)
  56 {
  57     swap(rh);
  58     return *this;
  59 }
  60
  61 void syntax::Tree::iterator::swap(const Tree::iterator& t)
  62 {
  63     node_ = t.node_;
  64     current_ = t.current_;
  65 }
  66
  67 Tree::iterator& Tree::iterator::operator++()
  68 {
  69     // 内部イテレータを巡回し、深さ優先探索と同様の流れになるようにす
  70     // る。
  71     // 巡回順は次のようにして決定する。
  72     // 1. current_が指すnodeに子がいる場合、current_の子のbeginを指定
  73     // する。
  74     // 2. current_が差すnodeに子がおらず、current_が現在のノードの子の
  75     // 末尾ではない場合、current_++する。
  76     // 3. current_がnode_->childの末尾である場合、parentに戻る。
  77     // parentに戻った際、parent->parentが空では無い場合に限り、
  78     // parent->parentの子から、node_->parentではないノードに戻る。
  79
  80     if (!current_->child.empty())
  81     {
  82         node_ = *current_;
  83         current_ = node_->child.begin();
  84     }
  85     else if (node_->child.end() != current_)
  86     {
  87         ++current_;
  88     }
  89     else
  90     {
  91         // 親を遡り、最も近い子を検索する。
  92         node_ = node_->parent;
  93
  94         while (!node_->parent.isNull())
  95         {
  96             std::vector<smart_ptr<Tree::TreeNode> >::iterator tmp = node_->parent->child.find(node_);
  97             if (tmp != node_->parent->child.end())
  98             {
  99                 current_ = ++tmp;
 100                 break;
 101             }
 102             node_ = node_->parent;
 103         }
 104     }
 105
 106     return *this;
 107 }
 108
 109 std::pair<DatumID, smart_ptr<literal::Literal> >& Tree::iterator::operator*()
 110 {
 111     // 現在のcurrent_が指すnodeのリテラルを返す。
 112     return *(*current_)->datum;
 113 }
 114
 115 std::pair<DatumID, smart_ptr<literal::Literal> >* Tree::iterator::operator->()
 116 {
 117     // 現在のcurrent_が指すnodeのリテラルを返す。
 118     return &*((*current_)->datum);
 119 }
 120
 121
 122 //////////////////
 123 // syntax::Tree //
 124 //////////////////
 125
 126 Tree::Tree() : MAX_CONS_SIZE(2), node_()
 127 {
 128     // 初期値を設定する。
 129     node_.add(new TreeNode(node_pair(yntax::DatumID(syntax::DatumID::nil),
 130                                      smart_ptr<literal::Literal>())));
 131 }
 132
 133 Tree::iterator Tree::begin()
 134 {
 135     // 開始点を示すデータを返す。
 136     return iterator(node_);
 137 }
 138
 139 Tree::iterator Tree::end()
 140 {
 141     // 終了地点を示す部分を返す。
 142
 143     smart_ptr<TreeNode> n(new TreeNode(node_pair(
 144                                            syntax::DatumID(syntax::DatumID::nil),
 145                                            smart_ptr<literal::Literal>())));
 146     return iterator(n);
 147 }
 148
 149 Tree::iterator Tree::appendChild(iterator it, Tree::node_pair p)
 150 {
 151     // itが指すnodeのcar,もしくはcdrに追加する。
 152     // すでにcdrも追加されている場合には、例外を発生させる。
 153
 154     if (it.node_->child.size() == Tree::MAX_CONS_SIZE)
 155     {
 156         // 例外を発生させる。
 157         throw std::exception();
 158     }
 159
 160     // 追加して、結果を返す。
 161     smart_ptr<TreeNode> n(new TreeNode(p));
 162
 163     // 親を再度設定する。
 164     n->parent = it.node_;
 165     it.node_->child.push_back(n);
 166     return iterator(n);
 167 }
 168
 169 Tree::iterator Tree::appendChild(iterator it1, iterator it2)
 170 {
 171     // it1にit2のnode_を追加する。
 172
 173     if (it.node_->child.size() == Tree::MAX_CONS_SIZE)
 174     {
 175         // 例外を発生させる。
 176         throw std::exception();
 177     }
 178
 179     // 追加して、結果を返す。
 180     it2.node_->parent = it.node_;
 181     it.node_->child.push_back(it2.node_);
 182     return it2;
 183 }
 184
 185 Tree::iterator Tree::insert(Tree::iterator it, node_pair pair)
 186 {
 187     // itが指す位置に、pairを設定する。
 188     // 作法としては、
 189     // 1. pairを持つTreeNodeを生成
 190     // 2. 生成したTreeNodeを、itのcurrent_が指す位置にinsert
 191     // 3. insert結果、MAX_CONS_SIZEを超えていたら、再び新規に
 192     //    TreeNodeを生成し、末尾の二つを配下に設定して、insertする。
 193
 194     // pairを持つnodeを作成し、親をitが現在指しているデータの親と同一にする。
 195     smart_ptr<TreeNode> n(new TreeNode(pair));
 196     n->parent = it.current_->parent;
 197
 198     // 現在位置に挿入する。この時、itのイテレータを更新する。
 199     it.current_ = it.node_->child.insert(it.current_, n);
 200
 201     if (it.node_->child.size() > Tree::MAX_CONS_SIZE)
 202     {
 203         // 最大サイズを超えていた場合には、後ろの二つを新しいTreeNode
 204         // にして格納しなおす。
 205         smart_ptr<TreeNode> n2(new TreeNode(makeListDatum()));
 206         n2->child.insert(n2->child.begin(), ++(it.node_->child.begin()),
 207                          it.node_->child.end());
 208         it.node_->child.erase(++(it.node_->child.begin()), it.node_->child.end());
 209         it.node_->child.push_back(n2);
 210         it.current_ = it.node_->child.begin();
 211     }
 212
 213     return it;
 214 }
 215
 216 Tree::iterator Tree::insert(Tree::iterator it1, iterator it2)
 217 {
 218     // it1が指す位置に、it2が指すオブジェクトを挿入する。
 219     // 挿入する位置は、末尾になることはありえない。末尾に挿入する必要
 220     // がある場合には、appendChildが利用されること。
 221     // 作法としては、以下のようになる。
 222     // 1. it2が指すTreeNodeをit1のcurrentの位置に挿入する。
 223     // 2. insert時点でMAX_CONS_SIZEだった場合、現在の末尾を
 224     //    it2が指すTreeNodeから辿った末尾=子が無いか、子が一つしかないTreeNode
 225     //    に追加する。
 226     // it2の末尾を取得するためには、it2をルートとする木を一度作成して、
 227     // その木の末尾まで移動することで
 228
 229 }