MessageTree.h

Go to the documentation of this file.

#ifndef __DCL_HS_MESSAGE_TREE_H__
#define __DCL_HS_MESSAGE_TREE_H__   20051210
 
#ifndef __DCL_CONFIG_H__
#include <dcl/Config.h>
#endif
 
#define __DEBUG_ALGORITHM   0
 
__DCL_BEGIN_NAMESPACE
 
/*
 이 알고리즘은 트리의 각 노드에 64bit 정수값을 사용하여 절대주소를 할당한다.
 width와 depth가 적용된 모든 트리는 완전트리의 구조를 가지며 
 width, depth는 다음의 값을 가질때 가장 넓은 범위를 갖는다.
 
 width  depth(depth index) : 수치의 범위
 -----------------------------------------
 2147483647 2(0 ~  1) : 1 ~         2147483648(INT32_MAX + 1)
  2097151   3(0 ~  2) : 1 ~      4398044413953
   55108    4(0 ~  3) : 1 ~    167360062766485
    6208    5(0 ~  4) : 1 ~   1485514159958081
    1448    6(0 ~  5) : 1 ~   6370049982705129
     511    7(0 ~  6) : 1 ~  17839230820809217
     234    8(0 ~  7) : 1 ~  38580774189064615
     127    9(0 ~  8) : 1 ~  68212339274677761
      78   10(0 ~  9) : 1 ~ 108256828977093499
      52   11(0 ~ 10) : 1 ~ 147389519791195397
      38   12(0 ~ 11) : 1 ~ 245019943472837715
      28   13(0 ~ 12) : 1 ~ 240818941573998061
      22   14(0 ~ 13) : 1 ~ 296277203496562883
      18   15(0 ~ 14) : 1 ~ 396861212733968143
      15   16(0 ~ 15) : 1 ~ 469172025408063616
      13   17(0 ~ 16) : 1 ~ 720867993281778161
 
 depth 2(1)의 width는 더 큰값도 가능하지만
 32bit 컴파일러에서 int는 INT32이기 때문에 위와 같이 정한다.
 
 제곱근을 구하기 위해 반복문을 사용한다. depth가 깊을수록 성능이 떨어진다.
*/
class MessageTree
{
private:
    int __nDepth;   // 트리의최대 깊이, 최상위 노드에서 시작, 1 ~
    int __nWidth;   // 1 이상의 각 깊이에서 최대 형제노드의 개수
 
    int64_t __nMinReplyID;      // == 1
    int64_t __nMaxReplyID;      // width가 홀수이고 depth가 짝수이면 홀수
 
    int64_t POWER(int nExponent) const; // __nWidth ^ nExponent
 
public:
    static int getDefaultWidth(int nDepth);
 
    MessageTree(int nDepth);
#ifdef __DEBUG_ALGORITHM
    MessageTree(int nDepth, int nWidth);
#endif
 
    int depth() const;
    int width() const;
 
    int64_t minReplyID() const;
    int64_t maxReplyID() const;
 
    // 형제노드간의 간격
    int64_t getSiblingGap(int nDepthIndex) const;
 
    struct Position
    {
        int64_t nParentID;
        int     nDepthIndex; // 0 ~
        int     nWidthIndex; // 같은 nParentID인 형제 노드간의 위치 0 ~
    };
 
    void getPosition(
        int64_t     nReplyID,
        Position&   rPos
    ) const;
 
    // 자식노드 중 첫번째 노드(nWidthIndex == 0)의 값
    int64_t getFirstChildID(int64_t nReplyID) const;
 
    // 자식노드 중 마지막 노드(nWidthIndex == (__nWidth - 1)의 값
    int64_t getLastChildID(int64_t nReplyID) const;
 
    // nReplyID의 nWidthIndex(0 based)번째의 자식노드의 값
    int64_t getChildID(int64_t nReplyID, int nWidthIndex) const;
};
 
inline int MessageTree::depth() const
{
    return __nDepth;
}
 
inline int MessageTree::width() const
{
    return __nWidth;
}
 
__DCL_END_NAMESPACE
 
#endif  // __DCL_HS_MESSAGE_TREE_H__