tree.cpp

   1 #include <iostream>
   2
   3 #include <assert.h>
   4 #include <exception>
   5
   6 #include "tree.h"
   7 #include <stack>
   8
   9 #include "utf8_string.h"
  10 #include "literal_data.h"
  11 #include "literal.h"
  12 #include "datum_id.h"
  13
  14 using namespace utakata;
  15 using namespace utakata::literal;
  16 using namespace utakata::utf8_string;
  17 using namespace utakata::syntax;
  18
  19 // 原則としてそれぞれ単純に呼びだされるのみ。
  20
  21 struct Tree::TreeNode
  22 {
  23     TreeNode (node_pair p) : list(), datum (p) {}
  24
  25     std::vector<smart_ptr<TreeNode> > list;
  26
  27     // datumの型と値の両方を保持する。
  28     Tree::node_pair datum;
  29 };
  30
  31 ////////////////////////////
  32 // syntax::Tree::iterator //
  33 ////////////////////////////
  34
  35 syntax::Tree::iterator::iterator () : current_()
  36 {
  37 }
  38
  39 syntax::Tree::iterator::iterator (const Tree::iterator& i)
  40 {
  41     swap (i);
  42 }
  43
  44 syntax::Tree::iterator& syntax::Tree::iterator::operator=(const Tree::iterator& rh)
  45 {
  46     iterator it (rh);
  47     swap (it);
  48     return *this;
  49 }
  50
  51 void syntax::Tree::iterator::swap (const Tree::iterator& t)
  52 {
  53     current_ = t.current_;
  54 }
  55
  56 Tree::iterator& Tree::iterator::operator++ ()
  57 {
  58     // car,cdr をそれぞれ巡回する。 car,cdr それぞれに移動する場合には、
  59     // it を元の tree に渡して取得する。
  60     // 巡回の順序は次の通りとする。
  61     // cons -> cdr に繋がっている cons
  62     // ただし、 cdr に繋がっている cons が literal の場合、以降は進むことが
  63     // 無く、また list として判定されることはない。
  64
  65     ++current_;
  66     return *this;
  67 }
  68
  69 std::pair<DatumID, smart_ptr<literal::Literal> >& Tree::iterator::operator*()
  70 {
  71     // 現在の current_が指す node のリテラルを返す。
  72     return (*current_)->datum;
  73 }
  74
  75 std::pair<DatumID, smart_ptr<literal::Literal> >* Tree::iterator::operator->()
  76 {
  77     // 現在の current_が指す node のリテラルを返す。
  78     return &((*current_)->datum);
  79 }
  80
  81 bool Tree::iterator::operator==(const Tree::iterator& rh)
  82 {
  83     // node_が指す先が同一かどうかを返す。
  84     // 但し、自身か相手のいずれかが nil である場合だけは例外的に、単純に DatumID のみの
  85     // 比較になる。
  86     return current_ == rh.current_;
  87 }
  88
  89 //////////////////
  90 // syntax::Tree //
  91 //////////////////
  92
  93 Tree::Tree () : node_()
  94 {
  95     // 初期値を設定する。
  96     smart_ptr<TreeNode> p(new TreeNode(makeNilList()));
  97     // 最後尾には常にnilがいることにする。
  98     node_.push_back(p);
  99 }
 100
 101 Tree::iterator Tree::begin ()
 102 {
 103     // 開始点を示すデータを返す。
 104     iterator it;
 105     it.current_ = node_.begin();
 106     return it;
 107 }
 108
 109 Tree::iterator Tree::end ()
 110 {
 111     // 終了地点を示す部分を返す。
 112     iterator it;
 113     it.current_ = node_.end();
 114     return it;
 115 }
 116
 117 void Tree::push_back(node_pair datum)
 118 {
 119     // 渡されたdatumを、現在保持しているデータ型に追加する。
 120     // 末尾には常にnilがいるので、その一つ前に設定することにする。
 121     smart_ptr<TreeNode> p(new TreeNode(datum));
 122     node_.insert(--(node_.end()), p);
 123 }
 124
 125 void Tree::push_back(Tree::iterator it, Tree::iterator it2,
 126                      node_pair datum)
 127 {
 128     // itとit2までを、datumで設定されたdatumidであるcompound datum
 129     // に格納して追加する。
 130     smart_ptr<TreeNode> p(new TreeNode(datum));
 131     p->list.insert(p->list.end(), it.current_, it2.current_);
 132     node_.insert(--(node_.end()), p);
 133 }
 134
 135 Tree::iterator Tree::in_compound_begin(Tree::iterator it)
 136 {
 137     // itがcompound datumである場合に、compound datumの内部リストを返す。
 138     if (isCompoundDatum(it))
 139     {
 140         iterator ret;
 141         ret.current_ = (*it.current_)->list.begin();
 142         return ret;
 143     }
 144     else
 145     {
 146         // 違う場合には、endを返すことにする。
 147         return end();
 148     }
 149 }
 150
 151 Tree::iterator Tree::in_compound_end(Tree::iterator it)
 152 {
 153     // itがcompound datumである場合に、compound datumの内部リストを返す。
 154     if (isCompoundDatum(it))
 155     {
 156         iterator ret;
 157         ret.current_ = (*it.current_)->list.end();
 158         return ret;
 159     }
 160     else
 161     {
 162         // 違う場合には、endを返すことにする。
 163         return end();
 164     }
 165 }
 166
 167 //////////////////////
 168 // helper functions //
 169 //////////////////////
 170
 171 bool syntax::isCompoundDatum(Tree::iterator it)
 172 {
 173     if (it->first == syntax::DatumID::list ||
 174         it->first == syntax::DatumID::vector ||
 175         it->first == syntax::DatumID::byteVector)
 176     {
 177         return true;
 178     }
 179     else
 180     {
 181         return false;
 182     }
 183 }
 184
 185 std::pair<DatumID, smart_ptr<literal::Literal> > syntax::makeCompoundDatum (
 186     DatumID id)
 187 {
 188     // datum_id が list である node_pair を返す。
 189     return std::pair<DatumID, smart_ptr<literal::Literal> >(id, smart_ptr<literal::Literal>());
 190 }
 191
 192 std::pair<DatumID, smart_ptr<literal::Literal> > syntax::makeNilList ()
 193 {
 194     // datum_id が nil である node_pair を返す。
 195     return std::pair<DatumID, smart_ptr<literal::Literal> >(
 196         DatumID (DatumID::nil), smart_ptr<literal::Literal>());
 197 }
 198
 199 std::pair<DatumID, smart_ptr<literal::Literal> > syntax::makeLexemeDatum (smart_ptr<literal::Literal> l,
 200     DatumID id)
 201 {
 202     // datum_id が各 lexeme であり、 literal として l を持つ
 203     // datum を返す。
 204     return std::pair<DatumID, smart_ptr<literal::Literal> >(
 205         id, l);
 206 }
 207
 208 std::pair<DatumID, smart_ptr<literal::Literal> > syntax::makeAbbreviation (smart_ptr<literal::Literal> l)
 209 {
 210     // datum_id が literal であり、 literal として l を持つ
 211     // datum を返す。
 212     return std::pair<DatumID, smart_ptr<literal::Literal> >(
 213         DatumID (DatumID::abbreviations), l);
 214 }
 215