是否有可能组合对称的代码片段

Question

我正在为我的学校项目实现avl树，并发现自己为对称情况编写了几乎相同的代码两次。例如，这个函数执行两个节点的旋转来平衡树。If子句处理下节点是上节点的左子节点的情况，而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子句与if子句完全相似，只是交换了"l"one_answers"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

您可能在这里需要模板，因此您将有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 3

计算机科学中的所有问题都可以通过另一个层次的间接的，当然除了太多的问题间接。
(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');

(注意，在这两种情况下，你的最终条件是相同的。)

是否有太多的间接性是个人意见的问题。

Answer 4

我喜欢Mike的模板方法。但为了记录在案，我在这里提出另一种选择。

首先，考虑每个节点有两个子节点。称他们为"左"one_answers"右"只是一种思想观点。你也可以把它们放在一个数组中:

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