. 후방 정렬 간소화

앞 실습에서 봤다시피 편집이 일어난 nPos 오프셋의 전방 쪽은 정렬 시작위치만 제대로 찾는다면 완전히 정렬을 생략하고 이전 정렬정보를 사용해도 전혀 문제될 것이 없었다. 그러나 후방 쪽으로는 좀 다르다. 글자가 삽입, 삭제되었다면 그 뒤쪽의 문서는 항상 변화가 있을 수 밖에 없으므로 정렬을 생략할 수 없다. 그러나 후방의 변화는 항상 일정한 규칙에 따라 일어나기 때문에 규칙만 정확하게 찾으면 후방 정렬도 많이 간소화할 수 있다.

후방 정렬의 변화 규칙을 파악하는 것은 그다지 쉽지 않은데 몇 가지 케이스로 나누어 각 케이스별로 어떤 식으로 이전의 정렬정보를 재활용할 수 있는지 방안을 모색해보도록 하자. 규칙이 나름대로 복잡하기 때문에 글만 읽어서 이해하기는 무척 어렵다. 직접 연습장에 그려 가면서 내가 이 코드를 작성한다면 어떤 식으로 규칙을 발견할 수 있는지 먼저 생각해보도록 하자.

케이스1

가장 단순한 경우로 줄 내에서 삽입, 삭제가 일어나 이전 정렬정보의 동일한 지점에서 유사한 패턴을 찾은 경우이다. 여기서 유사 패턴이라는 용어는 구체적으로 재활용이 가능한 정렬정보를 의미한다. 유사 패턴을 찾기만 하면 정렬을 다시 할 필요없이 기존의 정렬정보를 약간만 변경하면 된다.

첫 줄의 중간쯤에서 1바이트의 문자를 삽입(또는 삭제)했는데 이 편집으로 인해 첫 줄은 길이만 변경되었으며 전체 줄 수에는 변화가 없다고 하자. 삽입 후에 첫 줄부터 정렬을 다시 해 오는데 두 번째 줄을 정렬한 후 이전 정렬 결과와 비교를 해보니 1바이트만큼씩만 차이가 있고 나머지는 변화가 없다. 즉 유사한 패턴을 찾은 것이다. 일단 패턴을 찾았으면 이후 세 번째 줄부터는 일일이 다시 정렬할 필요없이 Start End 1씩 증가시켜 주기만 하면 된다.

아주 구체적인 예를 들어 이 정렬방식에 대해 설명해보도록 하자. 다음 그림의 왼쪽 문서는 모두 다섯 줄로 구성되어 있으며 각 줄은 모두 개행코드로 개행되어 있다고 하자. 이 상태에서 두 번째 줄 중간에 Z문자를 삽입한 후의 정렬 과정을 상상해보자.

전방 정렬 생략 기능에 의해 첫 번째 줄은 재정렬되지 않고 두 번째 줄부터 정렬이 시작된다. 두 번째 줄을 정렬해 본 결과 Start는 그대로인데 삽입된 Z에 의해 End 1 증가하여 10에서 11이 되었다. 세 번째 줄을 정렬해보니 Start 13이 되었고 End 16이 되는데 이 결과는 이전 정렬정보의 같은 줄에서 1만큼 더한 값이다. 즉 세 번째 줄 이후는 Z의 삽입에 의해 오프셋만 뒤로 이동될 뿐 줄의 길이에는 변화가 없으며 네 번째 이후도 마찬가지다. 여기서 세 번째 줄 이후 오프셋의 증가분은 삽입된 문자열의 길이와 같다는 규칙을 발견했다.

이 사실을 확인했다면 네 번째 줄부터는 굳이 GetLine 함수를 호출하여 정렬을 다시 할 필요가 없으며 Start, End 1씩 증가시키면 된다. 좀 더 일반적으로 정리한다면 nCount가 삽입되었을 때(삭제시는 음수값) 이전 정렬정보의 같은 줄과 비교하여 nCount만큼 오프셋이 이동된 줄을 찾으면 그 이후 줄은 같은 방식으로 오프셋만 조정하면 된다는 것이다. 문서가 아무리 길어도 뒤쪽 줄은 모두 오프셋만 일괄 조정하면 된다.

케이스 2

이 경우는 문자의 삽입에 의해 줄 길이가 늘어나 다음 줄로 내려간 경우이다. 이렇게 되면 두 번째 줄 이후가 한 줄씩 뒤로 밀리며 이후의 모든 줄에서 이전 정렬정보의 같은 줄과 유사한 패턴이 발견되지 않을 것이다.

그러나 자세히 보면 이전 정렬정보의 바로 앞 줄과 유사한 패턴이 발견되며 이 정보를 재활용할 수 있다. 그래서 이전 정렬정보의 앞 줄을 참조하여 삽입된 길이만큼 오프셋을 이동시키면 재정렬하지 않아도 된다.

케이스 3

케이스 2의 반대 경우로 한 문자를 삭제했는데 줄 길이가 짧아졌다. 즉 첫 번째 줄과 두 번째 줄이 합쳐짐으로써 세 번째 줄 이후가 모두 앞으로 이동하였다.

이때는 이전 정렬정보의 바로 다음 줄과 유사한 패턴이 발견되는데 이 정보도 역시 참조할 수 있다. 세 가지 케이스 모두 유사한 패턴을 찾아 삽입 삭제된 오프셋만큼 Start End를 조정하면 된다. 어떤 경우도 nPara nLine은 변하지 않는다.

개행코드 편집

삽입, 삭제된 문자열에 개행코드가 있는 경우는 문단이 강제로 나누어지기 때문에 문제가 다르다. 그러나 면밀하게 관찰해보면 개행코드가 삽입, 삭제되었다고 하더라도 여전히 앞의 세 케이스 중 하나에 대응된다는 것을 알 수 있다. 왜냐하면 개행코드 하나를 삽입, 삭제할 때 한꺼번에 두 줄 이상이 늘어나거나 줄어들지는 않기 때문이다. 다음 그림을 보자.

케이스를 나누는 기준은 편집 후 유사한 패턴이 이전 정렬정보의 어디쯤에서 발견되었는가 하는 점이다. 개행코드가 편집된 경우는 문단의 번호에도 변화가 생기므로 nPara도 적절히 조정해야 한다. 조정하는 방법은 각 케이스별로 다르다. nLine은 어떤 경우라도 변경되지 않으므로 그대로 두거나 단순 복사하면 된다.

그럼 이제 앞에서 연구해본 대로 실제 코드로 작성해보자. 케이스를 판별하는 조건이 다소 복잡하고 발견 후 정렬정보를 가공하는 코드가 길기 때문에 보다시피 굉장히 길어졌고 복잡해졌다.

 

void UpdateLineInfo(int nPos/*=-1*/, int nCount/*=-1*/)

{

     int l,s,e;

     int nPara, nLine=0;

     int i;

     int ParaStart;

    int ps=-1,pe=-1,pp=0;

    int dPara;

 

     if (nPos==-1) {

          l=0;

          nPara=0;

     } else {

          ParaStart=FindParaStart(nPos);

          if (ParaStart == 0) {

              l=0;

              nPara=0;

          } else {

              GetRCFromOff(ParaStart-2,l,e);

              nPara=pLine[l].nPara+1;

              l++;

          }

     }

 

     for (;;l++) {

          if (l >= Linelen) {

              Linelen += 1000;

              pLine=(tagLine *)realloc(pLine,sizeof(tagLine)*Linelen);

              if (pLine == NULL) {

              }

              for (i=Linelen-1000;i<Linelen;i++) {

                   pLine[i].Start=-1;

              }

          }

 

          GetLine(l,s,e);

        if (nPos != -1 && e > nPos && pLine[l].Start != -1) {

           if (pLine[l].Start+nCount == s && pLine[l].End+nCount == e) {

               dPara=nPara-pLine[l].nPara;

               for (i=l;;i++) {

                   if (pLine[i].Start==-1)

                       break;

                   pLine[i].Start+=nCount;

                   pLine[i].End+=nCount;

                   pLine[i].nPara+=dPara;

               }

               break;

           }

 

           if (ps+nCount == s && pe+nCount == e) {

               if (TotalLine+1 >= Linelen) {

                   Linelen += 1000;

                   pLine=(tagLine *)realloc(pLine,sizeof(tagLine)*Linelen);

                   if (pLine == NULL) {

                   }

                   for (i=Linelen-1000;i<Linelen;i++) {

                       pLine[i].Start=-1;

                   }

               }

               dPara=nPara-pp;

               pLine[TotalLine+1].Start=-1;

               for (i=TotalLine;i>=l;i--) {

                   pLine[i].Start=pLine[i-1].Start+nCount;

                   pLine[i].End=pLine[i-1].End+nCount;

                   pLine[i].nPara=pLine[i-1].nPara+dPara;

                   pLine[i].nLine=pLine[i-1].nLine;

               }

               pLine[l].Start=s;

               pLine[l].End=e;

               pLine[l].nPara=nPara;

               pLine[l].nLine=nLine;

               TotalLine++;

               break;

           }

          

           if (pLine[l+1].Start+nCount == s && pLine[l+1].End+nCount == e) {

               dPara=nPara-pLine[l+1].nPara;

               for (i=l;;i++) {

                   if (pLine[i+1].Start==-1) {

                       pLine[i].Start=-1;

                       break;

                   }

                   pLine[i].Start=pLine[i+1].Start+nCount;

                   pLine[i].End=pLine[i+1].End+nCount;

                   pLine[i].nPara=pLine[i+1].nPara+dPara;

                   pLine[i].nLine=pLine[i+1].nLine;

               }

               TotalLine--;

               break;

           }

        }

 

        ps=pLine[l].Start;

        pe=pLine[l].End;

        pp=pLine[l].nPara;

 

          pLine[l].Start=s;

          pLine[l].End=e;

          pLine[l].nPara=nPara;

          pLine[l].nLine=nLine;

          if (s==-1) {

              TotalLine=l;

              if (MarginWidth != 0) {

                   if (nPara >= 9999 && MarginWidth==25) {

                        MarginWidth=32;

                        SendMessage(hWndMain,WM_SIZE,0,0);

                        Invalidate(-1);

                   }

                   if (nPara < 9999 && MarginWidth==32) {

                        MarginWidth=25;

                        SendMessage(hWndMain,WM_SIZE,0,0);

                        Invalidate(-1);

                   }

              }

              break;

          }

 

          if (buf[e]==‘\r’) {

              nPara++;

              nLine=0;

          } else {

              nLine++;

          }

     }

}

 

몇 가지 변수가 추가되었고 GetLine 호출 후 세 가지 케이스에 해당하는지 점검한 후 정렬 대신 버퍼를 조작하는 코드가 있다. GetLine 바로 다음에 있는 if문은 후방 정렬 간소화를 할 것인가를 판단하는데 일단 nPos -1이면 전체 정렬을 하는 것이므로 조건들을 살펴볼 필요가 없다. 그리고 정렬 시작 줄의 끝이 정렬 시작 오프셋인 nPos보다 클 때만 간소화를 하는데 다음과 같은 경우를 예방하기 위해서이다.

문단의 세 번째 줄이 편집되었는데 이때 정렬 시작위치는 문단의 첫 줄부터가 된다. 첫 줄은 편집이 일어난 위치보다 이전에 있는 줄이므로 이 줄을 정렬할 때는 아직 후방 정렬 간소화를 할 필요가 없다. 최소한 편집이 일어난 줄 이후부터 조건을 점검해 볼 필요가 있는 것이다. 또한 정렬 루프는 GetLine에 의해 조사된 s -1일 때, 즉 모든 줄을 다 정렬할 때까지 반복되는데 끝줄인 경우는 더 이상 조건 점검을 할 필요가 없을 뿐만 아니라 s e가 실제 오프셋이 아닌 -1값을 가지므로 조건문들이 제대로 동작하지 않는 문제가 있다. e>nPos 조건문은 e -1일 때는 조건 점검을 하지 않도록 한다.

후방 정렬 간소화의 마지막 조건인 pLine[l].Start != -1은 새로 할당된 줄에 대해 간소화를 방지하는 역할을 한다. realloc에 의해 새로 할당된 줄은 아직 정렬이 되지 않은 상태이므로 이전 정보와 비교한다는 것이 의미가 없다. 만약 pLine을 재할당할 때 Start -1로 초기화하지 않으면 릴리즈 버전의 경우 Start 0으로 초기화된다. 이 상태에서 긴 텍스트를 붙여넣거나 파일에서 읽어오게 되면 줄 끝에서 케이스1의 조건이 우연히 만족되는데 이때 문서 끝을 찾을 때까지 줄 정보 복사를 시도하게 된다. Start -1로 초기화되지 않은 상태에서는 배열범위를 넘어서게 되고 결국 프로그램이 다운되는 치명적인 문제가 된다.

상기 세 조건이 만족되면 한 줄을 정렬한 결과와 이전 정렬정보를 비교해 본다. 비교하는 방식과 정렬정보를 복사하는 방식은 케이스별로 다르다. 앞에서 설명한 세 가지 케이스가 순서대로 if 블록으로 작성되어 있는데 순서대로 보도록 하자.

이전 정렬의 동일한 줄과 같은 경우

케이스 1의 경우인데 이전 정렬정보의 같은 줄에서 유사한 패턴을 찾았다. 이 조건을 판별하는 if문에서 pLine 배열은 이전 정렬정보이고 새로 조사한 s, e는 새 정렬정보인데 이 두 값이 nCount만큼 차이가 있는지 비교해보았다. 문서의 전체 줄 수는 변화가 없으며 이 줄 이후의 모든 정렬정보는 nCount만큼 오프셋을 이동시켜야 한다. nLine은 변화가 없으며 nPara는 지금 정렬 상태의 nPara와 이전 정렬정보의 nPara의 차인 dPara만큼 더하면 된다. 예를 들어 이전 정렬 상태에서는 5번 문단이었는데 다시 정렬해 본 결과 nPara 6이라면 이후 모든 문단의 번호는 1씩 증가해야 한다.

pLine 배열의 동일한 첨자끼리 오프셋 이동만으로 재정렬을 할 수 있는 가장 단순한 형태이다. 한 줄 내에서만 편집되는 경우이며 발생 빈도도 가장 높고 처리도 단순하여 이 처리만 해도 정렬 속도가 굉장히 빨라진다.

이전 정렬의 앞줄과 같은 경우

케이스 2의 경우이며 이전 정렬정보의 앞 줄에서 유사한 패턴을 찾았다. 그런데 이 조건 비교는 그다지 쉽지가 않다. 왜냐하면 pLine 배열은 하나밖에 없고 새로운 정렬정보를 만드는 중에 앞 줄의 정렬정보가 파괴되어 버렸기 때문이다. 그래서 앞 줄과 비교를 하기 위해 ps, pe, pp 임시 변수가 필요하다. 한 줄을 정렬할 때마다 이 변수에 정렬 상태를 별도로 백업해두면 다음 줄을 정렬할 때 이 변수값이 곧 이전 줄의 정렬정보가 된다. 즉 다음 줄 정렬시 유사 패턴을 찾기 위한 비교 대상이다.

이전 정렬정보의 앞 줄이 현재 줄과 유사 패턴이라는 것은 지금 정렬한 결과 중간에 한 줄이 삽입되었다는 뜻이다. 따라서 이후의 모든 정렬정보는 pLine 배열의 한 칸 아래로 복사되어야 한다. 이때 복사의 방향은 위에서 아래로가 아니라 아래에서 위로여야 한다. 예를 들어 l 10이었다고 하자. 그러면 10줄 정보를 11에 쓰고 11줄 정보를 12에 쓰고 이런 식으로 복사할 수 없다. 10줄 정보를 11에 쓰는 순간 11의 정보는 10줄과 같아지므로 12가 대입받는 정보는 이미 파괴된 것이다.

그래서 문서의 끝에서부터 l까지 정렬정보를 거꾸로 복사해 온다. 마지막으로 l번째 줄은 복사할 필요없이 방금 GetLine 함수가 정렬한 결과를 대입받으면 된다. 중간에 한 줄이 삽입되었으므로 TotalLine 1증가해야 하는데 이 점이 또 문제가 된다. pLine 배열이 이전 정렬 상태에서 문서 크기와 꼭 맞았다면 1증가한 현재는 하나가 모자라게 된다. 그래서 정렬정보 복사를 시작하기 전에 pLine 배열의 크기가 충분한지 점검해보고 모자라면 재할당하여 늘려 주도록 하였다.

이전 정렬의 뒷줄과 같은 경우

케이스 3의 경우이며 이전 정렬정보의 뒷줄에서 유사한 패턴을 찾았다. 이 조건은 점검하기가 비교적 쉽다. 지금 정렬한 결과가 이전 정렬한 결과의 뒷줄과 같다면 중간에 한 줄이 사라진 것이다. 그래서 이후의 모든 정렬정보는 pLine 배열의 한 칸 위로 복사되어야 한다. 뒷줄의 정렬정보는 아직 pLine 배열에 고스란히 남아 있으므로 복사하기도 아주 쉽다. 정렬한 결과 TotalLine 1 감소하는데 줄 수가 줄어드는 것은 문제가 되지 않으므로 pLine 배열의 크기는 관리하지 않아도 된다.

 

이제 아무리 큰 파일을 편집하더라도 재정렬하는 범위가 기껏해야 10줄 미만이기 때문에 정렬에 시간을 거의 뺏기지 않으며 편집속도는 파일 크기에 무관하게 일정할 것이다.