対称コードを組み合わせることは可能ですか？

Question

私は学校のプロジェクト用にavlツリーを実装していて、自分自身が対称的な状況のためにほぼ同じコードを2回書いていることがわかりました。たとえば、この関数はツリーのバランスをとるために2つのノードのローテーションを実行します。句は、下位ノードが1以上の左の子であり、かつelse節が反対を処理する場合に処理した場合：

void avl<T>::rotate(node<T> *x, node<T> *y) 
{ 
    if (x == y->l) 
    { 
    x->p = y->p; 
    if (y->p != nullptr) 
     if(y->p->l == y) 
     y->p->l = x; 
     else 
     y->p->r = x; 
    else 
     this->setHead(x); 
    y->p = x; 
    y->l = x->r; 
    if(x->r != nullptr) 
     x->r->p = y; 
    x->r = y; 
    y->dl = y->calcd('l'); 
    x->dr = x->calcd('r'); 
    if(x->p != nullptr) 
     if(x->p->l == x) 
     x->p->dl = x->p->calcd('l'); 
     else 
     x->p->dr = x->p->calcd('r'); 
    } 
    else 
    { 
    x->p = y->p; 
    if (y->p != nullptr) 
     if(y->p->r == y) 
     y->p->r = x; 
     else 
     y->p->l = x; 
    else 
     this->setHead(x); 
    y->p = x; 
    y->r = x->l; 
    if(x->l != nullptr) 
     x->l->p = y; 
    x->l = y; 
    y->dl = y->calcd('l'); 
    x->dr = x->calcd('r'); 
    if(x->p != nullptr) 
     if(x->p->r == x) 
     x->p->dr = x->p->calcd('r'); 
     else 
     x->p->dl = x->p->calcd('l'); 

    } 
} 

をあなたが見ることができるように、else節はl」とif節とまったく同じです'と' r 'が入れ替えられました。それらを組み合わせる方法はありますか？それを改善するために私は何ができますか？私のコードにデザインミスがありますか？

Answer 1

使用ポインタを書くことができます。それが出てそれを抽象化する簡単な方法ですので、二つの枝の間の唯一の違いは、どのあなたがアクセスしているメンバーである：

using Child = node<T> node<T>::*; 

void rotate_impl(node<T>* x, node<T>* y, Child* left, Child* right) 
{ 
    x->p = y->p; 
    if (y->p != nullptr) { 
     if(y->p->*left == y) { 
     y->p->*left = x; 
     } 
     else { 
     y->p->*right = x; 
     } 
    } 
    else { 
     this->setHead(x); 
    } 

    y->p = x; 
    y->*left = x->*right; 

    if(x->*right != nullptr) { 
     (x->*right)->p = y; 
    } 

    x->*right = y; 
    y->dl = y->calcd('l'); 
    x->dr = x->calcd('r'); 
    if(x->p != nullptr) { 
     if(x->p->*left == x) { 
     x->p->dl = x->p->calcd('l'); 
     } 
     else { 
     x->p->dr = x->p->calcd('r'); 
     } 
    } 
} 

void avl<T>::rotate(node<T> *x, node<T> *y) 
{ 
    if (x == y->l) { 
    rotate_impl(x, y, &node<T>::l, &node<T>::r); 
    } 
    else { 
    rotate_impl(x, y, &node<T>::r, &node<T>::l); 
    } 
} 

私はまた、あなたのコードにブレースを追加するの自由を取りました。あなたは後で私に感謝することができます。

Answer 2

コンピュータサイエンスのすべての問題は、あまりにも多くの 間接の問題のためのコースの以外、 間接の別のレベルで解決することができます。
（デビッド・ウィーラー）

あなたはこの（徹底的にテストされていない）のような何かを行うことができます。これは持っているかどうか

node<T>** y_sibling_1 = x == y->l ? &y->p->l : &y->p->r; 
node<T>** y_sibling_2 = x == y->l ? &y->p->r : &y->p->l; 
node<T>** x_child = x == y->l ? &x->r : &x->l; 
node<T>** y_child = x == y->l ? &y->l : &y->r; 

x->p = y->p; 
if (y->p != nullptr) 
    if(*y_sibling_1 == y) 
     *y_sibling_1 = x; 
    else 
     *y_sibling_2 = x; 
else 
    this->setHead(x); 
y->p = x; 
*y_child = *x_child; 
if(*x_child != nullptr) 
    (*x_child)->p = y; 
*x_child = y; 
y->dl = y->calcd('l'); 
x->dr = x->calcd('r'); 
if(x->p != nullptr) 
    if(x->p->l == x) 
     x->p->dl = x->p->calcd('l'); 
    else 
     x->p->dr = x->p->calcd('r'); 

（最終的な条件文はどちらの場合も同等であることに注意してください。）

をあまりに多くの迂回は、個人的な意見の問題です。

Answer 3

ここではテンプレートがほしいと思うので、calcd<true>()とcalcd<false>()が必要です。代わりにその変更に伴い

、あなたはメンバーに

template<bool xChildy> 
void avl<T>::rotateImpl(node<T> *x, node<T> *y); 

void avl<T>::rotate(node<T> *x, node<T> *y) 
{ 
    if (x == y->l) { 
    rotateImpl<true>(x,y); 
    } 
    else { 
    rotateImpl<false>(x,y); 
    } 
} 

Answer 4

マイクのテンプレートアプローチが好きです。しかし、記録のために、私はここに別の選択肢を提案する。

まず、各ノードに2つの子があるとします。それらを「左」と「右」と呼ぶことは、心の視点に過ぎません。

template <class T> 
class node { 
public: 
    ... 
    enum side{ left,right,last}; // just to make clear my intent here 
    node *p, *c[last], *d[last]; // no more l and r !!   
    node* calcd(enum side x) {} // lets use our index here instead of char 
    ... 
}; 

次に、サイド依存コードを除外することができます。 - `テストそこに隠れ`場合（引数== 'L'）があります、私は推測してみましょう

template <class T> 
void avl<T>::rotate(node<T> *x, node<T> *y) 
{ 
    // this lambda works directly with locals of rotate() thanks to [&] 
    // so put in the side dependent code, and put the side as parameter 
    // for easy switch. For simplicity I used l and r to facilitate 
    // transposition, but reafctoring it in a neutral side1 and sinde2 
    // could help readbility 
    auto rt = [&](enum node<T>::side l, enum node<T>::side r)->void { 
     x->p = y->p; 
     if (y->p != nullptr) 
      if(y->p->c[l] == y) // l is a parameter here instead of member name 
       y->p->c[l] = x; 
      else 
       y->p->c[r] = x; 
     else 
      this->setHead(x); 
     y->p = x; 
     y->c[l] = x->c[r]; 
     if (x == y->c[l]) 
     { 
      if(x->c[r] != nullptr) 
       x->c[r]->p = y; 
      x->c[r] = y; 
      y->d[l] = y->calcd(sd[l]); 
      x->d[r] = x->calcd(sd[r]); 
      if(x->p != nullptr) 
       if(x->p->c[l] == x) 
        x->p->d[l] = x->p->calcd(sd[l]); 
       else 
        x->p->d[r] = x->p->calcd(sd[r]); 
     } 
    }; // end of the definition of the lambda 

    // the code of the function is then reduced to this: 
    if (x == y->c[node<T>::left]) 
    rt(node<T>::left,node<T>::right); 
    else 
    rt(node<T>::right, node<T>::left); 
}