是否可以组合对称代码段？

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