lib/binary_tree.h

   1 // preorder、postorder、inorderのそれぞれの探索を利用できる、
   2 // 汎用二分木を提供します。
   3 // 汎用二分木では、以下の処理を行うことができます。
   4 // insert - 特定のNodeに対する値の設定
   5 // set_left - 左の葉に値を追加する。
   6 // set_right - 右の葉に値を追加する。
   7 // inorder_begin/end - 通りがけ順に探索するiteratorの開始・終了点を
   8 //                     指定します。
   9 // preorder_begin/end - 行きがけ順に探索するiteratorの開始・終了点を
  10 //                      返します。
  11 // postorder_begin/end - 帰り掛け順に探索するiteratorの開始・終了点を
  12 //                       返します。
  13 //
  14 // postorder/preorder/inorderは、それぞれテンプレート引数で
  15 // 指定することができます。デフォルトはinorderが指定されたことと同一です。
  16 #ifndef _UTAKATA_LIB_BINARY_TREE_H_
  17 #define _UTAKATA_LIB_BINARY_TREE_H_
  18
  19 namespace akebono {
  20 namespace binary_tree_detail {
  21
  22 // 内部でleafなどとして扱われるnode構造体です。この構造体公開はされますが、
  23 // 実際にアクセスすることはできません。
  24 template <typename T>
  25 struct node {
  26   node() : parent_(0), left_(0), right_(0),
  27            next_sibling_(0), prev_sibling_(0), data_() {}
  28   node(const T& data) : parent_(0), left_(0), right_(0),
  29                         next_sibling_(0), prev_sibling_(0),
  30                         data_(data) {}
  31   node<T>* parent_;
  32   node<T>* left_;
  33   node<T>* right_;
  34   // 同じ親に接続されている前後のnodeを指します。
  35   // ただし、二分木の場合、左ノードの場合はnext_sibling_に右ノードが、
  36   // 右ノードの場合はpref_sibling_に左ノードが設定され、
  37   // それぞれprev/nextは0が設定されます。
  38   node<T>* next_sibling_;
  39   node<T>* prev_sibling_;
  40
  41   T data_;
  42 };
  43
  44
  45 // 渡されたT型のポインタから、次に進むべきデータを判別するための
  46 // traverserです。
  47 // pre_orderは、根・左部分木・右部分木の順にtreeへのアクセスを行います。
  48 // 渡された段階で、すでに根にアクセスされているため、この場合は
  49 // 左、右、親の順にチェックを行います。
  50 // また、一つ前にアクセスしたデータを記憶しており、一つ前にアクセスした
  51 // データが、渡されたデータのどの位置に該当するのかをチェックし、
  52 // 次を観測します。
  53 template <typename T>
  54 struct pre_order {
  55   // 渡されたtargetに対して、次のデータに行くかどうかをチェックします。
  56   // left、rightの両方が存在しない場合、parent_のnext_siblingが存在するか
  57   // どうかを再帰的にチェックします。
  58   bool has_next(const node<T>* target) const {
  59     const node<T>* now_target = target;
  60
  61     if (!now_target) {
  62       return false;
  63     }
  64
  65     if (target->left_ || target->right_) {
  66       return true;
  67     }
  68
  69     while (now_target->next_sibling_ == 0) {
  70       if (!now_target->parent_) {
  71         return false;
  72       }
  73       now_target = now_target->parent_;
  74     }
  75     return true;
  76   }
  77
  78   // 渡されたtargetから、次に進むべきデータを返します。
  79   // has_nextがfalseを返却する場合、0が返却されます。
  80   node<T>* next(node<T>* target) {
  81     if (target->left_) {
  82       return target->left_;
  83     } else if (target->right_) {
  84       return target->right_;
  85     }
  86
  87     node<T>* now_target = target;
  88     while (now_target->next_sibling_ == 0) {
  89       now_target = now_target->parent_;
  90       if (now_target == 0) {
  91         return now_target;
  92       }
  93     }
  94     return now_target->next_sibling_;
  95   }
  96 };
  97
  98 } // end of namespace binary_tree
  99
 100 // 汎用的な二分木テンプレートを提供します。
 101 // テンプレート引数は、第一引数が利用する型、第二引数が、二分木の
 102 // 探索方法を設定します。
 103 // 二分木の探索方法は、in_order、pre_order、post_orderが用意されて
 104 // います。
 105 // デフォルトで用意されている探索方法については、すべてakebono::binary_tree_detail
 106 // に用意されています。
 107 // 内部ノードへのアクセスは可能ですが、get_*、has_*による間接的アクセスが
 108 // 推奨されます。
 109 template <typename T,
 110           template<typename S> class Traverse =
 111           akebono::binary_tree_detail::pre_order>
 112 class binary_tree {
 113  public:
 114
 115   // 内部のnodeを利用し、また渡されたtraverserに基づいて、nodeの探索を行います。
 116   struct iterator {
 117
 118     // コピーコンストラクタ、及びデフォルトコンストラクタです。
 119     iterator() : node_(0), traverser_() {}
 120     iterator(const iterator& it) : node_(it.node_),
 121                                    traverser_(it.traverser_) {}
 122     explicit iterator(binary_tree_detail::node<T>* convert) : node_(convert), traverser_() {}
 123
 124     ~iterator() {}
 125
 126     // 渡されたiteratorとの比較を行います。内部で保持しているnode_が
 127     // 同一位置を指していることが条件となります。
 128     bool operator==(const iterator& it) const {return node_ == it.node_;}
 129     bool operator!=(const iterator& it) const {return !(*this == it);}
 130
 131     // 現在指しているnode内のデータへアクセスします。
 132     // node内部ではTとしてのみ保持しているため、変則的にしています。
 133     const T& operator*() const {return node_->data_;}
 134     const T* operator->() const {return &(node_->data_);}
 135     T& operator*() {return node_->data_;}
 136     T* operator->() {return &(node_->data_);}
 137
 138     // 現在指しているnode_を次の要素を指すように変更します。この際、
 139     // Traverseで指定されたTraverserを利用します。
 140     // Traverse::has_nextは、渡されたnode_のアクセスを行うかどうかを
 141     // 表し、Traverse::nextは、次にアクセスすべきnode_を返します。
 142     iterator& operator++() {
 143       node_ = traverser_.next(node_);
 144       return *this;
 145     }
 146
 147     iterator operator++(int) {
 148       iterator tmp(*this);
 149       node_ = traverser_.next(node_);
 150       return tmp;
 151     }
 152
 153     // 各データを格納しているnodeです。node内では、単純にデータを保持
 154     // しているため、取得したポインタを操作することは許可されません。
 155     binary_tree_detail::node<T>* node_;
 156
 157     // operator++によって、二分木の探索を行うためのtraverserです。
 158     Traverse<T> traverser_;
 159   };
 160
 161   // 番兵として機能するend_を設定します。
 162   binary_tree() : root_(new binary_tree_detail::node<T>()),
 163                   end_(new binary_tree_detail::node<T>()) {
 164     root_->parent_ = 0;
 165     root_->left_   = 0;
 166     root_->right_  = 0;
 167     root_->next_sibling_ = end_;
 168     root_->prev_sibling_ = 0;
 169
 170     end_->parent_ = 0;
 171     end_->left_ = 0;
 172     end_->right_ = 0;
 173     end_->prev_sibling_ = root_;
 174     end_->next_sibling_ = 0;
 175   }
 176
 177   virtual ~binary_tree() {
 178     if (root_) {delete root_;}
 179     if (end_) {delete end_;}
 180   }
 181
 182   // rootを指すiteratorを作成して返します。
 183   iterator begin() {
 184     return iterator(root_);
 185   }
 186
 187   // end_を指すiteratorを返却します。
 188   iterator end() {
 189     return iterator(end_);
 190   }
 191
 192   // 渡されたiteratorの左側に新規に葉を作成し、dataを設定します。
 193   // 正常に終了した場合、新規に作成された葉を指すiteratorが
 194   // 返されます。
 195   // 正常に終了しなかった場合、end()で返されるiteratorと同一のiteratorが返されます。
 196   iterator set_left(const iterator& target,
 197                     const T& data) {
 198     if (target == end()) {
 199       return end();
 200     }
 201
 202     binary_tree_detail::node<T>* target_node = target.node_;
 203     target_node->left_ = new binary_tree_detail::node<T>(data);
 204
 205     target_node->left_->parent_ = target_node;
 206     target_node->left_->next_sibling_ = target_node->right_;
 207
 208     if (target_node->right_) {
 209       target_node->right_->prev_sibling_ = target_node->left_;
 210     }
 211     iterator ret(target_node->left_);
 212     return ret;
 213   }
 214
 215   // 渡されたiteratorの右側に新規に葉を作成し、dataを設定します。
 216   // 正常に終了した場合、新規に作成された葉を指すiteratorが
 217   // 返されます。
 218   iterator set_right(const iterator& target,
 219                      const T& data) {
 220     if (target == end()) {
 221       return end();
 222     }
 223
 224     binary_tree_detail::node<T>* target_node = target.node_;
 225     target_node->right_ = new binary_tree_detail::node<T>(data);
 226
 227     target_node->right_->parent_ = target_node;
 228     target_node->right_->prev_sibling_ = target_node->left_;
 229
 230     if (target_node->left_) {
 231       target_node->left_->next_sibling_ = target_node->right_;
 232     }
 233     iterator ret(target_node->right_);
 234     return ret;
 235   }
 236
 237  private:
 238
 239   // 二分木のルートとして設定されます。デフォルトではend_を指しています。
 240   // root_がend_を指している場合、binary_tree::empty()がtrueを返します。
 241   binary_tree_detail::node<T>* root_;
 242
 243   // 常に二分木の末尾として設定されます。ここでの二分木の末尾とは、
 244   // 探索を行う型によって変動します。
 245   binary_tree_detail::node<T>* end_;
 246 };
 247 } // end of namespace akebono
 248
 249 #endif /* _UTAKATA_LIB_BINARY_TREE_H_ */