是否可以組合對稱代碼段？

Question

我正在爲我的學校項目實施avl樹，發現自己爲對稱情況編寫兩次幾乎相同的代碼。例如，此功能執行兩個節點的旋轉來平衡樹。如果條款處理中下級節點是更高一個的左子的情況下，和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

在計算機科學中的所有問題都可以通過 間接的另一個層面來解決，當然除了太多 間接性的問題。
（David Wheeler的）

你可以做這樣的事情（徹底未經測試）：（請注意，您的最終條件語句在兩種情況下當量）

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'); 

這是否有太多的indirections是個人意見的問題。

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

我喜歡Mike的模板方法。但是爲了記錄，我在這裏提出另一種選擇。

首先，考慮每個節點有兩個孩子。稱他們爲「左」與「右」只是一種心智觀點。你可以把它們放在一個數組中：

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 
    ... 
}; 

然後你可以計算出側面相關的代碼。我喜歡lambda表達式，所以這裏的第一個建議：

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); 
}