대칭 코드 조각을 결합 할 수 있습니까?

Question

학교 프로젝트를위한 avl 트리를 구현하면서 대칭 상황에서 거의 동일한 코드를 두 번 쓰는 것을 발견했습니다. 예를 들어,이 함수는 두 노드의 회전을 수행하여 트리의 균형을 조정합니다. 절은 낮은 노드가 높은 하나의 왼쪽 자식 인 경우를 처리하고 다른 절 반대 처리하는 경우 :

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

    } 
} 

을 당신이 볼 수 있듯이, 다른 절은 'L로하면 절에 정확하게 유사하다 '와'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

모든 문제는 너무 많은 indirections의 문제에 대한 과정을 제외하고, 간접 다른 수준에 의해 해결 될 수 있습니다.
(데이비드 윌러)

당신은이 같은 (철저하게 검증되지 않은) 수행 할 수 있습니다. (최종 조건문이 두 경우 모두 동일합니다)

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

저는 마이크의 템플릿 접근 방식을 좋아합니다. 그러나 기록을 위해, 나는 또 다른 대안을 제안한다.

먼저 각 노드에 두 개의 하위 노드가 있다고 가정합니다. "왼쪽"과 "오른쪽"이라고 부르는 것은 마음의 관점 일뿐입니다. 배열에 넣을 수도 있습니다 :

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

그런 다음 측면 종속 코드를 제외 할 수 있습니다. 그래서 여기에 첫 번째 제안이다, 람다처럼 :

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