MessageTree.cpp

Go to the documentation of this file.

#include <dcl/Config.h>
 
#include <dcl/Object.h>
 
#include "MessageTree.h"
 
#if __DCL_HAVE_THIS_FILE__
#undef __THIS_FILE__
static const char_t __THIS_FILE__[] = __T("fastpage/MessageTree.cpp");
#endif
 
__DCL_BEGIN_NAMESPACE
 
#ifdef _MSC_VER
#define __I64(c)    c##I64
#else   // __GNUC__
#define __I64(c)    c##LL
#endif
 
static int64_t __POWER(int nBase, int nExponent)
{
    // base ^ exponent
    __DCL_ASSERT(nBase > 0);
 
    int64_t r = __I64(1);
    while(nExponent--)
        r *= nBase;
 
    return r;
}
 
// default nWidth
static const int __aWidth[16] = {
//depth:     2        3      4     5     6    7    8    9
    2147483646, 2097151, 55108, 6208, 1448, 511, 234, 127,
//depth:    10       11     12    13    14   15   16   17
            78,      52,    38,   28,   22,  18,  15,  13
};
 
static const int64_t __aPower[16][18] = {
    {   // base 2147483647
        __I64(1),                  //  0
        __I64(2147483647),         //  1
        __I64(4611686014132420609),    //  2
        __I64(0),                  //  3
    },
    {   // base 2097151
        __I64(1),                  //  0
        __I64(2097151),                //  1
        __I64(4398042316801),      //  2
        __I64(9223358842721533951),    //  3
        __I64(0),                  //  4
    },
    {   // base 55108
        __I64(1),                  //  0
        __I64(55108),              //  1
        __I64(3036891664),         //  2
        __I64(167357025819712),        //  3
        __I64(9222710978872688896),    //  4
        __I64(0),                  //  5
    },
    {   // base 6208
        __I64(1),                  //  0
        __I64(6208),               //  1
        __I64(38539264),           //  2
        __I64(239251750912),       //  3
        __I64(1485274869661696),   //  4
        __I64(9220586390859808768),    //  5
        __I64(0),                  //  6
    },
    {   // base 1448
        __I64(1),                  //  0
        __I64(1448),               //  1
        __I64(2096704),                //  2
        __I64(3036027392),         //  3
        __I64(4396167663616),      //  4
        __I64(6365650776915968),   //  5
        __I64(9217462324974321664),    //  6
        __I64(0),                  //  7
    },
    {   // base 511
        __I64(1),                  //  0
        __I64(511),                    //  1
        __I64(261121),             //  2
        __I64(133432831),          //  3
        __I64(68184176641),            //  4
        __I64(34842114263551),     //  5
        __I64(17804320388674561),  //  6
        __I64(9098007718612700671),    //  7
        __I64(0),                  //  8
    },
    {   // base 234
        __I64(1),                  //  0
        __I64(234),                    //  1
        __I64(54756),              //  2
        __I64(12812904),           //  3
        __I64(2998219536),         //  4
        __I64(701583371424),       //  5
        __I64(164170508913216),        //  6
        __I64(38415899085692544),  //  7
        __I64(8989320386052055296),    //  8
        __I64(0),                  //  9
    },
    {   // base 127
        __I64(1),                  //  0
        __I64(127),                    //  1
        __I64(16129),              //  2
        __I64(2048383),                //  3
        __I64(260144641),          //  4
        __I64(33038369407),            //  5
        __I64(4195872914689),      //  6
        __I64(532875860165503),        //  7
        __I64(67675234241018881),  //  8
        __I64(8594754748609397887),    //  9
        __I64(0),                  // 10
    },
    {   // base 78
        __I64(1),                  //  0
        __I64(78),                 //  1
        __I64(6084),               //  2
        __I64(474552),             //  3
        __I64(37015056),           //  4
        __I64(2887174368),         //  5
        __I64(225199600704),       //  6
        __I64(17565568854912),     //  7
        __I64(1370114370683136),   //  8
        __I64(106868920913284608), //  9
        __I64(8335775831236199424),    // 10
        __I64(0),                  // 11
    },
    {   // base 52
        __I64(1),                  //  0
        __I64(52),                 //  1
        __I64(2704),               //  2
        __I64(140608),             //  3
        __I64(7311616),                //  4
        __I64(380204032),          //  5
        __I64(19770609664),            //  6
        __I64(1028071702528),      //  7
        __I64(53459728531456),     //  8
        __I64(2779905883635712),   //  9
        __I64(144555105949057024), // 10
        __I64(7516865509350965248),    // 11
        __I64(0),                  // 12
    },
    {   // base 38
        __I64(1),                  //  0
        __I64(38),                 //  1
        __I64(1444),               //  2
        __I64(54872),              //  3
        __I64(2085136),                //  4
        __I64(79235168),           //  5
        __I64(3010936384),         //  6
        __I64(114415582592),       //  7
        __I64(4347792138496),      //  8
        __I64(165216101262848),        //  9
        __I64(6278211847988224),   // 10
        __I64(238572050223552512), // 11
        __I64(9065737908494995456),    // 12
        __I64(0),                  // 13
    },
    {   // base 28
 
        __I64(1),                  //  0
        __I64(28),                 //  1
        __I64(784),                    //  2
        __I64(21952),              //  3
        __I64(614656),             //  4
        __I64(17210368),           //  5
        __I64(481890304),          //  6
        __I64(13492928512),            //  7
        __I64(377801998336),       //  8
        __I64(10578455953408),     //  9
        __I64(296196766695424),        // 10
        __I64(8293509467471872),   // 11
        __I64(232218265089212416), // 12
        __I64(6502111422497947648),    // 13
        __I64(0),                  // 14
    },
    {   // base 22
 
        __I64(1),                  //  0
        __I64(22),                 //  1
        __I64(484),                    //  2
        __I64(10648),              //  3
        __I64(234256),             //  4
        __I64(5153632),                //  5
        __I64(113379904),          //  6
        __I64(2494357888),         //  7
        __I64(54875873536),            //  8
        __I64(1207269217792),      //  9
        __I64(26559922791424),     // 10
        __I64(584318301411328),        // 11
        __I64(12855002631049216),  // 12
        __I64(282810057883082752), // 13
        __I64(6221821273427820544),    // 14
        __I64(0),                  // 15
    },
    {   // base 18
 
        __I64(1),                  //  0
        __I64(18),                 //  1
        __I64(324),                    //  2
        __I64(5832),               //  3
        __I64(104976),             //  4
        __I64(1889568),                //  5
        __I64(34012224),           //  6
        __I64(612220032),          //  7
        __I64(11019960576),            //  8
        __I64(198359290368),       //  9
        __I64(3570467226624),      // 10
        __I64(64268410079232),     // 11
        __I64(1156831381426176),   // 12
        __I64(20822964865671168),  // 13
        __I64(374813367582081024), // 14
        __I64(6746640616477458432),    // 15
        __I64(0),                  // 16
    },
    {   // base 15
 
        __I64(1),                  //  0
        __I64(15),                 //  1
        __I64(225),                    //  2
        __I64(3375),               //  3
        __I64(50625),              //  4
        __I64(759375),             //  5
        __I64(11390625),           //  6
        __I64(170859375),          //  7
        __I64(2562890625),         //  8
        __I64(38443359375),            //  9
        __I64(576650390625),       // 10
        __I64(8649755859375),      // 11
        __I64(129746337890625),        // 12
        __I64(1946195068359375),   // 13
        __I64(29192926025390625),  // 14
        __I64(437893890380859375), // 15
        __I64(6568408355712890625),    // 16
        __I64(0)                   // 17
    },
    {   // base 13
 
        __I64(1),                  //  0
        __I64(13),                 //  1
        __I64(169),                    //  2
        __I64(2197),               //  3
        __I64(28561),              //  4
        __I64(371293),             //  5
        __I64(4826809),                //  6
        __I64(62748517),           //  7
        __I64(815730721),          //  8
        __I64(10604499373),            //  9
        __I64(137858491849),       // 10
        __I64(1792160394037),      // 11
        __I64(23298085122481),     // 12
        __I64(302875106592253),        // 13
        __I64(3937376385699289),   // 14
        __I64(51185893014090757),  // 15
        __I64(665416609183179841), // 16
        __I64(8650415919381337933) // 17
    }
};
 
int MessageTree::getDefaultWidth(int nDepth)
{
    __DCL_ASSERT(2 <= nDepth && nDepth <= 17);
 
    return __aWidth[nDepth - 2];
}
 
inline int64_t MessageTree::POWER(int nExponent) const
{
#ifdef __DEBUG_ALGORITHM
    // 알고리즘 검사용
    // 데이터베이스에 4 x 4 인 샘플 데이터를 사용한다.
    if (__nWidth == 4)
        return __POWER(__nWidth, nExponent);
#endif
 
    __DCL_ASSERT(0 <= nExponent && nExponent <= 17);
    int64_t r = __aPower[__nDepth - 2][nExponent];
    __DCL_ASSERT(r != __I64(0));
    return r;
}
 
MessageTree::MessageTree(int nDepth)
{
    __DCL_ASSERT(2 <= nDepth && nDepth <= 17);
 
    __nWidth = __aWidth[nDepth - 2];
    __nDepth = nDepth;
 
    __nMinReplyID = 1;
    __nMaxReplyID = ((POWER(__nDepth) - 1) / (__nWidth - 1));
}
 
MessageTree::MessageTree(int nDepth, int nWidth)
{
    __DCL_ASSERT(nWidth >= 2);
    __DCL_ASSERT(nDepth >= 2);
 
    __nWidth = nWidth;
    __nDepth = nDepth;
 
    __nMinReplyID = 1;
    __nMaxReplyID = ((POWER(__nDepth) - 1) / (__nWidth - 1));
}
 
int64_t MessageTree::minReplyID() const
{
    return __nMinReplyID;
}
 
int64_t MessageTree::maxReplyID() const
{
    return __nMaxReplyID;
}
 
int64_t MessageTree::getSiblingGap(int nDepthIndex) const
{
    __DCL_ASSERT(nDepthIndex >= 0);
 
    // 형제노드간의 간격
    // 전체 노드의 개수 중 nDepthIndex - 1 까지의 개수를 뺀 값에서 
    // nDepthIndex 까지의 개수로 나눈 값
    if (nDepthIndex > 0)
        return (__nMaxReplyID - POWER(nDepthIndex - 1))
            / POWER(nDepthIndex);
    else
        return __nMaxReplyID;
}
 
void MessageTree::getPosition(
    int64_t     nReplyID,
    Position&   rPos
) const
{
    __DCL_ASSERT(__nMinReplyID <= nReplyID);    // 0 < nReplyID
    __DCL_ASSERT(nReplyID <= __nMaxReplyID);
 
    rPos.nParentID = 0;
    rPos.nDepthIndex = 0;
    rPos.nWidthIndex = 0;
 
    int64_t __n = nReplyID - 1;
    if (__n == 0) {
        // 시작글(최상위 노드) ==> (0, 0)
        return;
    }
 
    for(int i = 1; i < __nDepth; i++) {
        // i == 1 ==> 0번째, 즉, 최상위 노드는 건너뛴다.
        --__n;
        int64_t nGap = getSiblingGap(i);
        if (nGap > 1) {
            int64_t nRemainder = __n % nGap;
            if (nRemainder == 0) {
                // nDepthIndex가 결정되었다.
                rPos.nDepthIndex = i;
                rPos.nWidthIndex = (int)(__n / nGap);
                rPos.nParentID = nReplyID - (nGap * rPos.nWidthIndex) - 1;
 
                break;
            }
 
            // tree의 가장 좌측으로 이동한다.
            __n = nRemainder;
        }
        else {
//          __DCL_TRACE2(L"i[%d], __n[%lld]\n", i, __n);
            rPos.nDepthIndex = i;
            rPos.nWidthIndex = (int)__n;
            rPos.nParentID = nReplyID - (nGap * rPos.nWidthIndex) - 1;
            break;
        }
    }
}
 
int64_t MessageTree::getFirstChildID(int64_t nReplyID) const
{
    __DCL_ASSERT(0 <= nReplyID);
    return nReplyID + 1;
}
 
int64_t MessageTree::getLastChildID(int64_t nReplyID) const
{
    __DCL_ASSERT(0 <= nReplyID);
 
    Position rPos;
    getPosition(nReplyID, rPos);
 
    __DCL_ASSERT(rPos.nDepthIndex < (__nDepth - 1));
 
    // nReplyID + 전체 자식노드의 개수 중 직 하위의 (nWidth - 1)/__nWidth
    // POWER(__nDepth - rPos.nDepthIndex) / (__nWidth - 1)
    //      * (__nWidth - 1) / __nWidth
 
    return nReplyID
        + POWER(__nDepth - rPos.nDepthIndex) / __nWidth;
 
    /*
    // FirstChildID + 자식노드의 간격 * (__nWidth - 1)의 개수
    return nReplyID + 1
        + getSiblingGap(rPos.nDepthIndex + 1) * (__nWidth - 1);
    */
}
 
int64_t MessageTree::getChildID(int64_t nReplyID, int nWidthIndex) const
{
    __DCL_ASSERT(0 <= nReplyID);
    __DCL_ASSERT(0 <= nWidthIndex && nWidthIndex < __nWidth);
 
    Position rPos;
    getPosition(nReplyID, rPos);
 
    __DCL_ASSERT(rPos.nDepthIndex < __nDepth);
 
    return nReplyID + 1 + getSiblingGap(rPos.nDepthIndex + 1) * nWidthIndex;
}
 
__DCL_END_NAMESPACE
 
#ifdef _CONSOLE
 
#include <dcl/FileOutputStream.h>
#include <dcl/Numeric.h>
 
__DCL_USING_NAMESPACE
 
int main(int argc, char* argv[])
{
    DCLInitialize(NULL, 2);
 
    FileOutputStream out(1, 0, false);
 
    if (argc < 3) {
        out << L"USAGE: " << argv[0] << L" width depth [id]\n";
        goto __done;
    }
 
    try {
        int nWidth = UInteger::parse(argv[1]);
        int nDepth = UInteger::parse(argv[2]);
 
        MessageTree mt(nDepth, nWidth);
 
        out << L"width : " << nWidth
            << L"\ndepth : " << nDepth
            << L"\nrange : " << mt.minReplyID()
            << L" ~ " << mt.maxReplyID()
            << L"\n";
 
        out << L"\nleft:gap\n";
 
        int nCol = 3;
        int nDepthIndex;
        int64_t nParentID = 1;
        for(nDepthIndex = 1; nDepthIndex < nDepth; nDepthIndex++) {
            int64_t nID = mt.getFirstChildID(nParentID);
            int64_t nGap = mt.getSiblingGap(nDepthIndex);
            out << nDepthIndex << L":" << nGap
                << L" ==> ";
            for(int i = 0; i < nCol; i++)
                out << nID + nGap * i << L" ";
            nCol++;
            nParentID = nID;
            out << L" ... " << nID + nGap * (nWidth - 1) << L"\n";
        }
 
        out << L"\nrifht:gap\n";
        nParentID = 1;
        nCol = 3;
        for(nDepthIndex = 1; nDepthIndex < nDepth; nDepthIndex++) {
            int64_t nID = mt.getLastChildID(nParentID);
            int64_t nGap = mt.getSiblingGap(nDepthIndex);
            out << nDepthIndex << L":" << nGap
                << L" ==> ";
            for(int i = 0; i < nCol; i++)
                out << nID - (nGap * (nCol - i - 1)) << L" ";
//          nCol++;
            nParentID = nID;
            out << L"\n";
        }
 
        if (argc == 4) {
            int64_t nReplyID = Int64::parse(argv[3]);
 
            MessageTree::Position rPos;
            mt.getPosition(nReplyID, rPos);
            out << L"\nID : " << nReplyID
                << L"\nDepthIndex : " << rPos.nDepthIndex
                << L"\nWidthIndex : " << rPos.nWidthIndex
                << L"\nParent : " << rPos.nParentID
                << L"\n";
 
            if (rPos.nDepthIndex < nDepth - 1) {
                out << L"\nFirstChildID: " << mt.getFirstChildID(nReplyID)
                    << L"\nLastChildID: " << mt.getLastChildID(nReplyID)
                    << L"\n";
                for(int i = 0; (i < nWidth && i < 5); i++)
                    out << L"\n" << i << L"-st ChildID: " 
                        << mt.getChildID(nReplyID, i);
                out << L"\n";
            }
        }
    }
    catch (Exception* e) {
        out << e->toStringAll() << L"\n";
        e->destroy();
    }
 
__done :
    DCLCleanup();
 
    return 0;
}
 
#endif