OpenGrok

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright (c) 2007 Sun Microsystems, Inc. All Rights Reserved.
 *
 * The contents of this file are subject to the terms of either the GNU Lesser
 * General Public License Version 2.1 only ("LGPL") or the Common Development and
 * Distribution License ("CDDL")(collectively, the "License"). You may not use this
 * file except in compliance with the License. You can obtain a copy of the CDDL at
 * http://www.opensource.org/licenses/cddl1.php and a copy of the LGPLv2.1 at
 * http://www.opensource.org/licenses/lgpl-license.php. See the License for the
 * specific language governing permissions and limitations under the License. When
 * distributing the software, include this License Header Notice in each file and
 * include the full text of the License in the License file as well as the
 * following notice:
 *
 * NOTICE PURSUANT TO SECTION 9 OF THE COMMON DEVELOPMENT AND DISTRIBUTION LICENSE
 * (CDDL)
 * For Covered Software in this distribution, this License shall be governed by the
 * laws of the State of California (excluding conflict-of-law provisions).
 * Any litigation relating to this License shall be subject to the jurisdiction of
 * the Federal Courts of the Northern District of California and the state courts
 * of the State of California, with venue lying in Santa Clara County, California.
 *
 * Contributor(s):
 *
 * If you wish your version of this file to be governed by only the CDDL or only
 * the LGPL Version 2.1, indicate your decision by adding "[Contributor]" elects to
 * include this software in this distribution under the [CDDL or LGPL Version 2.1]
 * license." If you don't indicate a single choice of license, a recipient has the
 * option to distribute your version of this file under either the CDDL or the LGPL
 * Version 2.1, or to extend the choice of license to its licensees as provided
 * above. However, if you add LGPL Version 2.1 code and therefore, elected the LGPL
 * Version 2 license, then the option applies only if the new code is made subject
 * to such option by the copyright holder.
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <algorithm>
#include "imi_context.h"
#include "lattice_states.h"


class TSkelCursor {
public:
    struct TPos {
        CSkeletonIter m_bone;
        int           m_idx;
        TPos(CSkeletonIter bone=CSkeletonIter(), int idx=0)
            : m_bone(bone), m_idx(idx) { }
    };

public:
    TSkelCursor(CSkeletonIter h1, CSkeletonIter t1, CSkeletonIter h2, CSkeletonIter t2, bool asis=false)
            : m_h1(h1), m_t1(t1), m_h2(h2), m_t2(t2), m_bone(h1), m_idx(0), m_iLink(0)
        { if (!asis) ensureCursor(); }

    inline bool
    isPinyin() const
        { return (m_bone != m_t2 && m_bone->isPinyinNode()); }

    inline bool
    isBreakAfter() const
        { return (m_bone == m_t2 || m_bone == m_t1 || m_idx >= m_bone->m_String.size()-1); }

    inline bool
    isBreakAfter(TPos & pos) const
        { return (pos.m_bone == m_t2 || pos.m_bone == m_t1 || pos.m_idx >= pos.m_bone->m_String.size()-1); }

    inline bool
    isUserBreakAfter() const
        { return (m_bone == m_t2 || m_bone == m_t1 ||
                    (m_idx == m_bone->m_String.size()-1 && m_bone->isPinyinNode() &&
                     m_bone->m_BoundaryType == CBone::USER_BOUNDARY)); }

    inline bool
    isUserBreakAfter(TPos & pos) const
        { return (pos.m_bone == m_t2 || pos.m_bone == m_t1 ||
                      (pos.m_idx == pos.m_bone->m_String.size()-1 && pos.m_bone->isPinyinNode() &&
                       pos.m_bone->m_BoundaryType == CBone::USER_BOUNDARY)); }

    inline TWCHAR
    getChar()
        {
            ensureCursor();
            return (m_bone != m_t2)?(m_bone->m_String[m_idx]):0;
        }

    inline TWCHAR
    getChar(TPos& pos) const // the pos should be ensured
        { return (pos.m_bone != m_t2)?(pos.m_bone->m_String[pos.m_idx]):0; }

    void
    next(bool asis=false)
        {
            ensureCursor();
            if (m_bone != m_t2) {
                ++m_idx;
                if (!asis) ensureCursor();
            }
        }

    void
    nextBone()
        {
            ensureCursor();
            if (m_bone != m_t2) {
                ++m_bone;
                m_idx=0;
            }
            ensureCursor();
        }

    inline bool
    hasNext()
        {
            ensureCursor();
            return m_bone != m_t2;
        }

    inline bool
    atFirstLink() const
        { return m_iLink == 0; }

    inline TPos
    getPosition() const
        {
            return TPos(m_bone, m_idx);
        }

    /** The parameters must be retrieved from save object before */
    inline void
    setPosition(const TPos& pos)
        { m_bone = pos.m_bone; m_idx = pos.m_idx; }

    bool
    ensureCursor(TPos& curCompare);

protected:
    CSkeletonIter   m_h1, m_h2, m_t1, m_t2;
    CSkeletonIter   m_bone;
    int             m_iLink, m_idx;

protected:
    void
    ensureCursor();
};

void
TSkelCursor::ensureCursor()
{
    while (m_bone != m_t1 && m_bone != m_t2 && m_idx >= m_bone->m_String.size()){
        m_idx = 0;
        ++m_bone;
    }
    if (m_bone == m_t1) {
        ++m_iLink;
        m_bone = m_h2;
        m_idx = 0;
        while (m_bone != m_t2 && m_idx >= m_bone->m_String.size()){
            m_idx = 0;
            ++m_bone;
        }
    }
}

bool
TSkelCursor::ensureCursor(TPos& curCompare)
{
    bool same = false;
    same = (m_bone == curCompare.m_bone && m_idx == curCompare.m_idx);
    while (m_bone != m_t1 && m_bone != m_t2 && m_idx >= m_bone->m_String.size()){
        m_idx = 0;
        ++m_bone;
        same = same || (m_bone == curCompare.m_bone && m_idx == curCompare.m_idx);
    }
    if (m_bone == m_t1) {
        ++m_iLink;
        m_bone = m_h2;
        m_idx = 0;
        same = same || (m_bone == curCompare.m_bone && m_idx == curCompare.m_idx);
        while (m_bone != m_t2 && m_idx >= m_bone->m_String.size()){
            m_idx = 0;
            ++m_bone;
            same = same || (m_bone == curCompare.m_bone && m_idx == curCompare.m_idx);
        }
    }
    return same;
}

/**
 * Determine whether or not the target iterator's position on list of head
 * is located before the iterator first. More precisely, it return whether
 * or not target in [head, first)
 * @param target is the target iterator whose position to be decided
 * @param head is the head iterator of the container (list or vector)
 * @param first iterator to be compared with target
 * @return whether or not the target iterator's position on list of head
 * is located before the iterator first
 */
template<class forwardIt>
bool
isLocatedBefore(forwardIt target, forwardIt head, forwardIt first)
{
    for (; head != first; ++head) {
        if (target == head) return true;
    }
    return false;
}

CIMIContext::CIMIContext()
    : m_bNonCompleteSyllable(false), m_bStrictLeft2Right(false),
      m_bGBK(true), m_bGB18030(false), m_HistoryPower(3), m_ContextRanking(true),
      m_pModel(NULL), m_pPinyinTrie(NULL), m_Skeleton(),
      m_EffectiveCandiBoneStart(), m_EffectiveCandiBoneEnd()
{
}

void
CIMIContext::setCoreData(CIMIData *pCoreData)
{
    m_pModel = pCoreData->getSlm();
    m_pPinyinTrie = pCoreData->getPinyinTrie();
}

void
CIMIContext::clear()
{
    m_Skeleton.clear();
    m_Skeleton.push_back(CBone());
    m_Skeleton.push_back(CBone());
    m_EffectiveCandiBoneStart = m_EffectiveCandiBoneEnd = getLastBone();

    // allocate bone's inner data when it is inserted into the skeleton
    CSkeletonIter itEnd = m_Skeleton.end();
    for (CSkeletonIter bone = m_Skeleton.begin(); bone != itEnd; ++bone) {
        if (bone->m_pInnerData == NULL)
            bone->m_pInnerData = new CBoneInnerData();
    }

    searchFrom(m_Skeleton.begin());
}

static bool
isYuanYinChar(TWCHAR wc)
{
    return (wc == L'a' || wc == L'o' || wc == L'e' ||
            wc == L'i' || wc == L'u' || wc == L'v');
}

CSkeletonIter
CIMIContext::cancelSelection(CSkeletonIter bone, bool update)
{
    bool found = false;
    CSkeletonIter it = bone;
    for (CSkeletonIter first=m_Skeleton.begin(); it->m_BoneType == CBone::NODE_PINYIN; --it) {
        // BestWrod is conjunctive, so no need to check position if user selection
        // like isLocatedBefore(bone, it, it->m_pInnerData->m_BestWord.m_BoneEnd)) {
        if (it->m_pInnerData->m_BWType == CBoneInnerData::UserSelectedBestWord) {
            it->m_pInnerData->m_BWType = CBoneInnerData::NoBestWordStartHere;
            found = true;
            break;
        } else if (it->m_pInnerData->m_BWType != CBoneInnerData::NoBestWordStartHere) {
            break;
        }
        if (it == first)
            break;
    }
    if (found && update)
        searchFrom(it);
    return (found)?(it):(bone);
}

CSkeletonIter
CIMIContext::cancelSelectionCover(CSkeletonIter bone, bool update)
{
    bool found = false;
    if (bone->m_pInnerData->m_BWType != CBoneInnerData::NoBestWordStartHere) {
        return bone;
    }
    CSkeletonIter it = bone;
    for (CSkeletonIter first=m_Skeleton.begin(); it != first; ) {
        --it;
        if (it->m_pInnerData->m_BWType != CBoneInnerData::NoBestWordStartHere) {
            // BestWord is conjunctive, so no need to check position if user selection
            // like isLocatedBefore(bone, it, it->m_pInnerData->m_BestWord.m_BoneEnd)) {
            if (it->m_pInnerData->m_BWType == CBoneInnerData::UserSelectedBestWord) {
                it->m_pInnerData->m_BWType = CBoneInnerData::NoBestWordStartHere;
                found = true;
            }
            break;
        }
    }
    if (found && update)
        searchFrom(it);
    return (found)?(it):(bone);
}

bool
CIMIContext::makeSelection(const CCandidate& candi)
{
    CSkeletonIter boneLeft = cancelSelection(candi.m_BoneStart, false);

    /*
    candi.m_BoneStart->m_pInnerData->m_BWType = CBoneInnerData::NoBestWordStartHere;

    for (CSkeletonIter bone = candi.m_BoneStart; bone != candi.m_BoneEnd; ++bone)
        bone->m_pInnerData->m_BWType = CBoneInnerData::NoBestWordStartHere;
    */

    candi.m_BoneStart->m_pInnerData->m_BestWord = candi;
    candi.m_BoneStart->m_pInnerData->m_BWType = CBoneInnerData::UserSelectedBestWord;
    searchFrom(boneLeft);

    return true;
}

/**
* it is illegal if boneStart == boneEnd and skel.size() == 0
*/
bool
CIMIContext::modify(CSkeletonIter boneStart,
                    CSkeletonIter boneEnd,
                    CSkeleton& skel,
                    bool doSearch,
                    CSkeletonIter* pItLeftmost)
{
    // No change needed, happen on OneLineView, call out a PINYIN i
    // but return it back withou modification.
    // FIXME, maybe this should be put back to OnreLineView's code, not here
    if ((skel.size() == 1) && (boneEnd == ++CSkeletonIter(boneStart)) &&
            (skel.begin()->m_BoneType == boneStart->m_BoneType) &&
            (skel.begin()->m_String == boneStart->m_String)) {
        if (pItLeftmost) *pItLeftmost = getLastBone();
        boneStart->m_BoundaryType = skel.begin()->m_BoundaryType;
        return false;
    }

    // check whether or not the modification would affect the candidates
    // retrieved by the previous getCandidates() call
    CSkeletonIter first = boneStart;
    if (first->m_pInnerData->m_LexiconStates.size() > 0)
        first = first->m_pInnerData->m_LexiconStates[0].m_BoneStart;
    bool affectCandidates =
        !isLocatedBefore(m_EffectiveCandiBoneEnd, m_Skeleton.begin(), first);

    // We must check the user selection which may cover this node
    // if there is such a user selection, we should do search from there
    // starting bone of such a selection.
    // The check should only be done when boneStart to be removed
    CSkeletonIter lefter = cancelSelectionCover(boneStart, false);
    bool bSearchLefter = (lefter != boneStart);

    // Another case is that previous UserSelection just ending at boneStart,
    // which is the first bone to be deleted. In this case, new search will
    // start with the newly inserted bone, and when searching, the User
    // selection word will be check backward and got a wrong range. So
    // we must make it change the UserSelection's ending Bone to the first
    // bone after insertion.
    bool bLeftUS = false;
    CSkeletonIter leftUserBone = lefter;
    if (skel.size() > 0 && !bSearchLefter && leftUserBone != m_Skeleton.begin()) {
        do {
            --leftUserBone;
            int bwType = leftUserBone->m_pInnerData->m_BWType;
            if (bwType != CBoneInnerData::NoBestWordStartHere) {
                bLeftUS = (bwType ==CBoneInnerData::UserSelectedBestWord &&
                           leftUserBone->m_pInnerData->m_BestWord.m_BoneEnd == boneStart);
                break;
            }
        } while (leftUserBone != m_Skeleton.begin());
    }

    CBoneInnerData *pid = NULL;
    // remove the old range
    if (boneStart != boneEnd) {
        // before remove the bone, get the first's bone's innerData
        // reserve it for the first bone to be inserted. (ie. just
        // attach it to the first bone after deletion/insertion
        pid = boneStart->m_pInnerData;
        boneStart->m_pInnerData = NULL;

        m_Skeleton.erase(boneStart, boneEnd);
    }

    // insert new list before boneEnd
    first = boneEnd;
    CSkeleton::iterator it1 = skel.begin(), h = skel.begin();
    CSkeleton::iterator it2 = skel.end();
    for (; it1 != it2; ++it1) {
        CSkeletonIter tmp = m_Skeleton.insert(boneEnd, *it1);
        if (it1 == h)
            first = tmp;
        else
            tmp->m_pInnerData = new CBoneInnerData();
    }

    if (first->m_pInnerData != NULL) {
        // nothing inserted, must deleted something, ie pid != NULL
        pid->m_BWType = first->m_pInnerData->m_BWType;
        pid->m_BestWord = first->m_pInnerData->m_BestWord;
        delete first->m_pInnerData;
        first->m_pInnerData = pid;
    } else if (pid == NULL) {
        // nothing deleted, just inserting something
        first->m_pInnerData = boneEnd->m_pInnerData;
        boneEnd->m_pInnerData = new CBoneInnerData();
        boneEnd->m_pInnerData->m_BWType = first->m_pInnerData->m_BWType;
        boneEnd->m_pInnerData->m_BestWord = first->m_pInnerData->m_BestWord;
        first->m_pInnerData->m_BWType = CBoneInnerData::NoBestWordStartHere;
    } else {
        //something deleted, something inserted
        first->m_pInnerData = pid;
        pid->m_BWType = CBoneInnerData::NoBestWordStartHere;
    }

    // change the left user selection bone's best word's ending bone to first
    if (bLeftUS)
        leftUserBone->m_pInnerData->m_BestWord.m_BoneEnd = first;

    // rebuild the search lattice from the newly inserted list
    // using the just copied lattice states (innerData)
    if (pItLeftmost)
        *pItLeftmost = (bSearchLefter)?(lefter):(first);
    if (doSearch)
        searchFrom((bSearchLefter)?(lefter):(first));

    return affectCandidates;
}

bool
CIMIContext::isValidSyllable(const TWCHAR* pstr)
{
    const CPinyinTrie::TNode* pyn = m_pPinyinTrie->transfer(pstr);
    return m_pPinyinTrie->isValid(pyn, m_bNonCompleteSyllable, m_bGBK);
}

bool
CIMIContext::segPinyinSimplest(const wstring& pinyin, CSkeleton& result)
{
    #ifdef DEBUG
        printf("SegPinyin:");
        print_wide(pinyin.c_str());
        printf("-->");
    #endif

    //"zhuang" is longest syllable, 16 is enought
    bool  validSyllable[16];
    const CPinyinTrie::TNode* pathNodes[16];
    const TWCHAR* str = pinyin.c_str();
    const CPinyinTrie::TNode* pyn = m_pPinyinTrie->getRootNode();

    result.clear();

    //Find out the longest valid PINYIN prefix, save to lastValid
    int idx, lastValid = - 1;
    for (idx = 0; str[idx] != 0; ++idx) {
        pyn = m_pPinyinTrie->transfer(pyn, (unsigned char)(str[idx]));
        pathNodes[idx] = pyn;
        if (validSyllable[idx] = m_pPinyinTrie->isValid(pyn, m_bNonCompleteSyllable, m_bGBK))
            lastValid = idx;
        if (pyn == NULL)
            break;
    }

    /*********************************************************************
    Note, when NULL pyn arrived, the char should also be the last one.
    Try to split it into two nodes if possible:
        (1) [0..idx-2], [0..idx-1] is both complete syllable
            [idx-1] is FuYin, [idx] is Yuanyin,
            [idx-1...] is non-complete or complete (not NULL)
            ====> split into [0..idx-2] [idx-1, idx]
        (2) lastValid >= 0
            ====> split into [0..lastValid] [lastValid+1..]
                  if [lastValid+1...] is not valid, return false
        (3) lastValid = -1
            ====> give a invalid PINYIN bone [0..]
    **********************************************************************/
    if (pyn == NULL && idx >= 2 &&
        pathNodes[idx-1]->m_bFullSyllableTransfer == 1 &&
        pathNodes[idx-2]->m_bFullSyllableTransfer == 1 &&
        !isYuanYinChar(str[idx-1]) && isYuanYinChar(str[idx]) &&
        (pathNodes[idx] = m_pPinyinTrie->transfer(str+idx-1)) != NULL) {

        result.push_back(CBone(str, idx-1, CBone::AUTO_BOUNDARY, CBone::NODE_PINYIN));

        #ifdef DEBUG
            print_wide(wstring(str, idx-1).c_str());
            printf("'");
        #endif

        int bt = CBone::NODE_INCOMPLETE_PINYIN;
        if (pathNodes[idx]->m_bFullSyllableTransfer == 1)
            bt = CBone::NODE_PINYIN;

        result.push_back( CBone(str+idx-1, CBone::AUTO_BOUNDARY, bt) );

        #ifdef DEBUG
            print_wide(str+idx-1);
            fflush(stdout);
        #endif

        return true;
    }

    if (pyn == NULL && lastValid >= 0) {
        result.push_back(CBone(str, lastValid+1, CBone::AUTO_BOUNDARY, CBone::NODE_PINYIN));

        #ifdef DEBUG
            print_wide(wstring(str, lastValid+1).c_str());
            printf("'");
        #endif

        int bt = CBone::NODE_INCOMPLETE_PINYIN;

        pathNodes[idx] = m_pPinyinTrie->transfer(str+lastValid+1);
        if (pathNodes[idx] == NULL)
            bt = CBone::NODE_INVALID_PINYIN;
        else if (m_pPinyinTrie->isValid(pathNodes[idx], m_bNonCompleteSyllable, m_bGBK))
            bt = CBone::NODE_PINYIN;
        else
            bt = CBone::NODE_INCOMPLETE_PINYIN;
        result.push_back(CBone(str+lastValid+1, CBone::AUTO_BOUNDARY, bt));

        #ifdef DEBUG
            print_wide(str+lastValid+1);
            if (bt == CBone::NODE_INVALID_PINYIN)
                printf("(X)");
            fflush(stdout);
        #endif

        return (bt != CBone::NODE_INVALID_PINYIN);
    }

    if (pyn == NULL) {
        result.push_back(CBone(str, CBone::AUTO_BOUNDARY, CBone::NODE_INVALID_PINYIN));

        #ifdef DEBUG
            print_wide(str);
            printf("(X)");
            fflush(stdout);
        #endif

        return false;
    }

    /********************************************************************
    Now, pyn is not NULL, str[idx] should be 0,
        [0..idx-1] is valid (non-complete or complete)
    *********************************************************************/
    int bt = (validSyllable[idx-1])?(CBone::NODE_PINYIN):(CBone::NODE_INCOMPLETE_PINYIN);
    result.push_back(CBone(str, CBone::AUTO_BOUNDARY, bt));

    #ifdef DEBUG
        print_wide(str);
        fflush(stdout);
    #endif

    return true;
}

TCandiRank::TCandiRank(bool user, bool best, unsigned int len,
                       bool fromLattice, TSentenceScore score)
{
    anony.m_user = (user)?0:1;
    anony.m_best = (best)?0:1;
    anony.m_len = (len > 31)?(0):(31-len);
    anony.m_lattice = (fromLattice)?0:1;

    #ifdef DEBUG
        //assert(fromLattice);
        //assert(TSentenceScore(+0.0) < score);
    #endif

    double ds = -score.log2();

    //make it 24-bit
    if (ds > 32767.0)
        ds = 32767.0;
    else if (ds < -32768.0)
        ds = -32768.0;
    unsigned cost = unsigned((ds+32768.0)*256.0);
    anony.m_cost = cost;
}

TCandiRank::TCandiRank(bool user, bool best, unsigned int len,
                       bool fromLattice, unsigned rank)
{
    anony.m_user = (user)?0:1;
    anony.m_best = (best)?0:1;
    anony.m_len = (len > 31)?(0):(31-len);
    anony.m_lattice = (fromLattice)?0:1;
    anony.m_cost = rank;
}

struct TCandiPair {
    CCandidate                      m_Candi;
    TCandiRank                      m_Rank;

    TCandiPair() : m_Candi(), m_Rank() { }
};

struct TCandiPairPtr {
    TCandiPair*                     m_Ptr;

    TCandiPairPtr(TCandiPair* p=NULL) : m_Ptr(p)
    { }

    bool
    operator< (const TCandiPairPtr& b) const
    { return m_Ptr->m_Rank < b.m_Ptr->m_Rank; }
};

// FIXME, this procedure could be modified largely.
void
CIMIContext::getCandidates(CSkeletonIter bone, CCandidates& result)
{
    TCandiPair cp;
    static std::map<unsigned int, TCandiPair> map;
    std::map<unsigned int, TCandiPair>::iterator it_map;

    map.clear();
    result.clear();
    m_EffectiveCandiBoneStart = m_EffectiveCandiBoneEnd = bone;

    if (bone->isTailNode())
        return;
    if (!bone->isValidPinyinNode()) {
        result.push_back(CCandidate(bone->m_String.c_str(), bone, ++CSkeletonIter(bone)));
        return;
    }

    // if user selection or best word starting at bone
    if (bone->m_pInnerData->m_BWType != CBoneInnerData::NoBestWordStartHere) {
        cp.m_Candi = bone->m_pInnerData->m_BestWord;
        cp.m_Rank =
            TCandiRank(bone->m_pInnerData->m_BWType == CBoneInnerData::UserSelectedBestWord,
                       bone->m_pInnerData->m_BWType == CBoneInnerData::BestWordStartHere,
                       0, false, 0);
        map[cp.m_Candi.m_WordId] = cp;
    }

    //collecting all candidates, from both lattice and lexicon
    int len = 1;
    cp.m_Candi.m_BoneStart = bone;
    CSkeletonIter b = ++CSkeletonIter(bone);
    while (b != (--m_Skeleton.end())) {
        cp.m_Candi.m_BoneEnd = b;

        bool found = false;
        CLexiconStates::iterator itlex = b->m_pInnerData->m_LexiconStates.begin();
        CLexiconStates::iterator itlexe = b->m_pInnerData->m_LexiconStates.end();
        for (; itlex != itlexe; ++itlex) {
            if (itlex->m_BoneStart == bone) {
                found = true;
                if (itlex->m_bPinyin) {
                    if (itlex->m_pPYNode && itlex->m_pPYNode->m_nWordId > 0) {
                        unsigned sz = itlex->m_pPYNode->m_nWordId;
                        const CPinyinTrie::TWordIdInfo* p = itlex->m_pPYNode->getWordIdPtr();
                        for (unsigned int i = 0; i < sz; ++i, ++p) {
                            if (m_bGBK || p->m_bGBK == 0) {
                                cp.m_Candi.m_WordId = p->m_id;
                                cp.m_Candi.m_String = (*m_pPinyinTrie)[cp.m_Candi.m_WordId];

                                //sorting according to the order in PinYinTire
                                cp.m_Rank = TCandiRank(false, false, len, false, i);
                                it_map = map.find(cp.m_Candi.m_WordId);
                                if (it_map == map.end() || cp.m_Rank < it_map->second.m_Rank)
                                    map[cp.m_Candi.m_WordId] = cp;
                            }
                        }
                    }
                } else {
                    cp.m_Candi.m_WordId = itlex->m_WordId;
                    cp.m_Candi.m_String = bone->m_String.c_str();
                    cp.m_Rank = TCandiRank(false, false, len, false, 0);
                    it_map = map.find(cp.m_Candi.m_WordId);
                    if (it_map == map.end() || cp.m_Rank < it_map->second.m_Rank)
                        map[cp.m_Candi.m_WordId] = cp;
                }
            }
        }

        if (!found) break;

        CLatticeStates::iterator its = b->m_pInnerData->m_LatticeNodes.begin();
        CLatticeStates::iterator ite = b->m_pInnerData->m_LatticeNodes.end();
        for (;  its != ite; ++its) {
            if (its->m_pBackTraceNode && its->m_pBackTraceNode->m_BoneAfter == bone) {
                cp.m_Candi.m_WordId = its->m_BackTraceWordId;
                cp.m_Candi.m_String = (*m_pPinyinTrie)[cp.m_Candi.m_WordId];
                if (cp.m_Candi.m_String == NULL)
                    cp.m_Candi.m_String = bone->m_String.c_str();
                #ifdef _USE_RAW_PROBABILITY

                    #ifdef DEBUG
                        //assert(its->m_pBackTraceNode->m_Score < 0.0 && its->m_Score < 0.0);
                    #endif

                    cp.m_Rank = TCandiRank(false, false, len, true, its->m_Score / its->m_pBackTraceNode->m_Score);
                #else
                    cp.m_Rank = TCandiRank(false, false, len, true, its->m_Score - its->m_pBackTraceNode->m_Score);
                #endif
                it_map = map.find(cp.m_Candi.m_WordId);
                if (it_map == map.end() || cp.m_Rank < it_map->second.m_Rank)
                    map[cp.m_Candi.m_WordId] = cp;
            }
        }

        m_EffectiveCandiBoneEnd = b;
        ++b;
        ++len;
    }

    std::vector<TCandiPairPtr> vec;

    vec.reserve(map.size());
    std::map<unsigned int, TCandiPair>::iterator it_mapE = map.end();
    for (it_map = map.begin(); it_map != it_mapE; ++it_map)
        vec.push_back(TCandiPairPtr(&(it_map->second)));
    std::make_heap(vec.begin(), vec.end());
    std::sort_heap(vec.begin(), vec.end());

    for (int i=0, sz=vec.size(); i < sz; ++i)
        result.push_back(vec[i].m_Ptr->m_Candi);
}

int
CIMIContext::getBestSentence(wstring & result, CSkeletonIter boneStart,
                             CSkeletonIter boneEnd, bool original_format)
{
    int nWordConverted = 0;
    result.clear();

    // no need to check begin(), because firstBone must at least has some
    // auto best word or user selection best word starting from, this rule
    // must be followed in this call
    int len, prefix = 0;
    CSkeletonIter realStart = boneStart;
    while (realStart->m_pInnerData->m_BWType == CBoneInnerData::NoBestWordStartHere) {
        ++prefix;
        --realStart;
    }

    while (true) {
        #ifdef DEBUG
            //assert(realStart->m_pInnerData->m_BWType != CBoneInnerData::NoBestWordStartHere);
        #endif

        CSkeletonIter bone = boneStart;
        CSkeletonIter rightBone = realStart->m_pInnerData->m_BestWord.m_BoneEnd;
        if (realStart->m_BoneType != CBone::NODE_PINYIN &&
                  realStart->m_BoneType != CBone::NODE_INCOMPLETE_PINYIN) {
            for (; bone != rightBone && bone != boneEnd; ++bone) {
                 if (!original_format)
                     result.push_back(bone->m_String[0]);
                 else
                     result.push_back((unsigned)bone->m_BoundaryType);
            }
        } else {
            ++nWordConverted;
            // get the length from boneStart to current best word tail or end of range
            for (len=0; bone != rightBone && bone != boneEnd; ++bone)
                 ++len;
            result.append(realStart->m_pInnerData->m_BestWord.m_String+prefix, len);
        }
        if (bone == boneEnd)
            break;
        boneStart = realStart = bone;
        prefix = 0;
    }

    return nWordConverted;
}

/**
 * Search from the bone to the tail. the bone can not beyond first psuedo tail.
 * Before search, all BoneInnerData should be set. The states of the bones
 * who's ahead of the bone would not be affected by this function. Yet, states
 * of the bones beyond this bone will be updated or refreshed.
 *
 * After lattice search, only one best path are backtraced and each best word
 * will be attached to corresponding bone.
 */
void
CIMIContext::searchFrom(CSkeletonIter boneStart)
{
    // iterate every bone from boneStart to the second psuedo tail
    CSkeletonIter itEnd = ++getLastBone();
    CSkeletonIter bone = boneStart;
    CSkeletonIter boneFirst = m_Skeleton.begin();
    for (; bone != itEnd; ) {
        if (bone == boneFirst) {
            // do not clear USER_SELECTION_BEST_WORD !!
            bone->m_pInnerData->m_LexiconStates.clear();
            bone->m_pInnerData->m_LatticeNodes.clear();
            #ifdef _USE_RAW_PROBABILITY
                bone->m_pInnerData->m_LatticeNodes.push_back(TLatticeState(-1.0, bone));
            #else
                bone->m_pInnerData->m_LatticeNodes.push_back(TLatticeState(0.0, bone));
            #endif
        } else {
            buildLatticeStates(bone);
        }
        switch (bone->m_BoneType) {
        case CBone::NODE_TAIL:
            bone = forwardTailBone(bone);
            break;
        case CBone::NODE_PINYIN:
            bone = forwardPinyinBone(bone);
            break;
        case CBone::NODE_INCOMPLETE_PINYIN:
        case CBone::NODE_INVALID_PINYIN:
            bone = forwardInvalidBone(bone);
            break;
        case CBone::NODE_PUNC:
            bone = forwardPuncBone(bone);
            break;
        case CBone::NODE_ASCII:
        case CBone::NODE_SIMBOL:
        case CBone::NODE_DIGITAL:
            bone = forwardNonPinyinBone(bone);
            break;
        };
    }

    //Build the last bone's lattice states
    buildLatticeStates(itEnd);

    #ifdef DEBUG
        //assert(itEnd->m_pInnerData->m_LatticeNodes.size() == 1);
    #endif

    // clear all non-user selection
    for (bone=boneFirst; bone != itEnd; ++bone) {
        if (bone->m_pInnerData->m_BWType != CBoneInnerData::UserSelectedBestWord)
            bone->m_pInnerData->m_BWType = CBoneInnerData::NoBestWordStartHere;
    }

    // back tracing, find the best path
    TLatticeState* bs = &(*(itEnd->m_pInnerData->m_LatticeNodes.begin()));
    while (bs->m_BoneAfter != boneFirst) {
        TLatticeState* fs = bs->m_pBackTraceNode;
        CSkeletonIter  fb = fs->m_BoneAfter;
        if (fb->m_pInnerData->m_BWType != CBoneInnerData::UserSelectedBestWord) {
            fb->m_pInnerData->m_BWType = CBoneInnerData::BestWordStartHere;
        }
        fb->m_pInnerData->m_BestWord.m_BoneStart = fb;
        fb->m_pInnerData->m_BestWord.m_BoneEnd = bs->m_BoneAfter;
        fb->m_pInnerData->m_BestWord.m_WordId = bs->m_BackTraceWordId;
        fb->m_pInnerData->m_BestWord.m_String = (*m_pPinyinTrie)[bs->m_BackTraceWordId];
        if (fb->m_pInnerData->m_BestWord.m_String == NULL)
            fb->m_pInnerData->m_BestWord.m_String = fb->m_String.c_str();
        bs = fs;
    }
}

#ifdef DEBUG
static double min_ts = 1.0;
#endif

static double s_history_distribution[11] = {
    0.0, 0.05, 0.10, 0.15, 0.20, 0.25, 0.30, 0.35, 0.40, 0.45, 0.50
};

void
CIMIContext::transferBetween(CSkeletonIter h, CSkeletonIter t, unsigned int id, double ic)
{
    CLatticeStates& latss1 = h->m_pInnerData->m_LatticeNodes;
    CLatticeStates& latss2 = t->m_pInnerData->m_LatticeNodes;
    CLatticeStates::iterator it1 = latss1.begin();
    CLatticeStates::iterator ite = latss1.end();

    #ifdef _USE_RAW_PROBABILITY
        TLatticeState node(-1.0, t);
        TSentenceScore efic(1.0);
    #else
        TLatticeState node(0.0, t);
        TSentenceScore efic(0.0);
    #endif

    if (h->m_pInnerData->m_BestWord.m_WordId == id &&
            h->m_pInnerData->m_BWType == CBoneInnerData::UserSelectedBestWord) {
        #ifdef _USE_RAW_PROBABILITY
            efic = efic * TSentenceScore(30000, 1.0);
        #else
            efic = ic - 30000.0;
        #endif
    }

    double weight_h = s_history_distribution[m_HistoryPower];
    double weight_s = 1.0 - weight_h;

    for (; it1 != ite; ++it1) {
        node.m_pBackTraceNode = &(*it1);
        node.m_BackTraceWordId = id;
        #ifdef _USE_RAW_PROBABILITY
            // the fact is that we could only use bigram cache
            // and all first level node in the language model are non-empty
            double ts = m_pModel->transfer(it1->m_State, id, node.m_State);
            m_pModel->historify(node.m_State);
            // we do not want to shrink the history state if it could be found in cache
            if (node.m_State.getLevel() == 0 && m_pHistory->seenBefore(id)) {
                node.m_State.setIdx(id);  // an psuedo unigram node state
            }

            #ifdef DEBUG
                assert(it1->m_Score < TSentenceScore(0.0));
            #endif

            double cost = ts;
            if (m_pHistory) {
                unsigned history[2] = {m_pModel->lastWordId(it1->m_State), id};
                double hpr = m_pHistory->pr(history, history+2);
                cost = weight_s * ts + weight_h*hpr;
            }
            node.m_Score = it1->m_Score * efic * TSentenceScore(cost);

            #ifdef DEBUG
                if (!(node.m_Score < TSentenceScore(-0.0))) {
                    static char strangeValue[256];

                    node.m_Score.toString(strangeValue);
                    printf("\n***node.m_Score invalid %s ***\n", strangeValue);

                    it1->m_Score.toString(strangeValue);
                    printf("***it1->m_Score is %s ***\n", strangeValue);

                    efic.toString(strangeValue);
                    printf("***efic=%s, ic=(%lf)***\n", strangeValue, ic);

                    TSentenceScore(cost).toString(strangeValue);
                    printf("***cost=%s(%lf), ts=(%16lf)***\n", strangeValue, cost, ts);

                    fflush(stdout);
                    assert(false);
                }
            #endif

        #else
            double ts = m_pModel->transferNegLog(it1->m_State, id, node.m_State);
            m_pModel->historify(node.m_State);
            node.m_Score = it1->m_Score + ts + ic;
        #endif

        latss2.push_back(node);
    }
}

void
CIMIContext::buildLatticeStates(CSkeletonIter bone)
{
    bool bSingleSyllable, bSingleShort;
    unsigned i, sz;
    CSkeletonIter bonePrev = bone;


    --bonePrev;
    CBoneInnerData & innerData = *(bone->m_pInnerData);
    CLexiconStates::iterator itLexState = innerData.m_LexiconStates.begin();
    CLexiconStates::iterator itLexStateE = innerData.m_LexiconStates.end();
    innerData.m_LatticeNodes.clear();
    for (; itLexState != itLexStateE; ++itLexState) {
        CLexiconState& ls = *itLexState;

        // the user selected word may be cut in first pruning process below,
        // So, just let it go first, when it ends here
        CBoneInnerData* pbid = ls.m_BoneStart->m_pInnerData;
        if (pbid->m_BWType == CBoneInnerData::UserSelectedBestWord &&
                    pbid->m_BestWord.m_BoneEnd == bone) {
            #ifdef _USE_RAW_PROBABILITY
                transferBetween(ls.m_BoneStart, bone, pbid->m_BestWord.m_WordId, 1.0);
            #else
                transferBetween(ls.m_BoneStart, bone, pbid->m_BestWord.m_WordId, 0.0);
            #endif
        }

        if (!ls.m_bPinyin) {
            #ifdef _USE_RAW_PROBABILITY
                transferBetween(ls.m_BoneStart, bone, ls.m_WordId, 1.0);
            #else
                transferBetween(ls.m_BoneStart, bone, ls.m_WordId, 0.0);
            #endif
        } else {
            // Cutting words with little unigram possibilities
            // at least 2, at most 32 of the words would be tried
            // if unseed word starting from some position in the first 32
            // candidates(ranked according to unigram pr in lexicon), do not
            // let them be checked.
            bSingleShort = bSingleSyllable = (ls.m_BoneStart == bonePrev);
            if (bSingleSyllable) {
                register unsigned char uc = ls.m_BoneStart->m_String[0];
                bSingleShort = ((ls.m_BoneStart->m_String.size() == 1 && (uc != 'a' && uc != 'o' && uc !='e')) ||
                                (ls.m_BoneStart->m_String.size() == 2 && (ls.m_BoneStart->m_String[1] == 'h')));
            }
            //bSingleShort = (bSingleSyllable && !(m_pPinyinTrie->isValid(ls.m_pPYNode, false)));

            const CPinyinTrie::TNode* pn = ls.m_pPYNode;
            const CPinyinTrie::TWordIdInfo* pwidinfo = pn->getWordIdPtr();
            sz=pn->m_nWordId;
            if (bSingleShort)
                sz = 12;
            else if (sz > 26)
                sz = 26;

            int count = 0;
            for (i=0; count < sz && i < sz && (pwidinfo[i].m_bSeen == 1 || count < 2); ++i) {
                if (m_bGBK || pwidinfo[i].m_bGBK == 0) {
                    #ifdef _USE_RAW_PROBABILITY
                        transferBetween(ls.m_BoneStart, bone, pwidinfo[i].m_id, 1.0);
                    #else
                        transferBetween(ls.m_BoneStart, bone, pwidinfo[i].m_id, 0.0);
                    #endif
                    ++count;
                }
            }
            #ifdef _USE_RAW_PROBABILITY
                // try cached words
                if (m_pHistory) {
                    for (sz = pn->m_nWordId; i < sz; ++i) {
                        if (m_bGBK || pwidinfo[i].m_bGBK == 0) {
                            if (m_pHistory->seenBefore(pwidinfo[i].m_id)) {
                                transferBetween(ls.m_BoneStart, bone, pwidinfo[i].m_id, 1.0);
                            }
                        }
                    }
                }
            #endif
        }
    }
}


/**
* Fussy Pinyin:
*
*/
CSkeletonIter
CIMIContext::forwardOnePinyinBone(CSkeletonIter bone)
{
    const CPinyinTrie::TNode *pn = NULL;

    //clear next bone's lexicon states
    CSkeletonIter boneNext = ++CSkeletonIter(bone);
    CLexiconStates& lexss2 = boneNext->m_pInnerData->m_LexiconStates;
    lexss2.clear();

    // insert the root PinYin Lexicon node
    CLexiconStates& lexss1 = bone->m_pInnerData->m_LexiconStates;
    CLexiconStates::iterator it1 = lexss1.begin();
    CLexiconStates::iterator ite = lexss1.end();
    for (; it1 != ite; ++it1) {
        if (it1->m_bPinyin) {
            pn = m_pPinyinTrie->transfer(it1->m_pPYNode, bone->m_String.c_str());
            if (pn != NULL && (pn = m_pPinyinTrie->transfer(pn, TWCHAR('\''))) != NULL) {
                lexss2.push_back(CLexiconState(it1->m_BoneStart, pn));
            }
        }
    }

    //try transfer from root state of the lexicon
    pn = m_pPinyinTrie->transfer(bone->m_String.c_str());
    if (pn != NULL && (pn = m_pPinyinTrie->transfer(pn, TWCHAR('\''))) != NULL) {
        lexss2.push_back(CLexiconState(bone, pn));
    }

    return boneNext;
}

CSkeletonIter
CIMIContext::forwardPinyinBone(CSkeletonIter bone)
{
    if (bone->m_pInnerData->m_BWType == CBoneInnerData::UserSelectedBestWord && m_bStrictLeft2Right) {
        CSkeletonIter boneLeft = bone;
        CSkeletonIter boneRight = bone->m_pInnerData->m_BestWord.m_BoneEnd;
        for (; bone != boneRight; ++bone)
            (++CSkeletonIter(bone))->m_pInnerData->clear();
        boneRight->m_pInnerData->m_LexiconStates.push_back(
            CLexiconState(boneLeft, boneLeft->m_pInnerData->m_BestWord.m_WordId)
        );
        return boneRight;
    } else {
        return forwardOnePinyinBone(bone);
    }
}

CSkeletonIter
CIMIContext::forwardInvalidBone(CSkeletonIter bone)
{
    CSkeletonIter boneNext = ++CSkeletonIter(bone);
    CLexiconStates & lss = boneNext->m_pInnerData->m_LexiconStates;
    lss.clear();
    lss.push_back(CLexiconState(bone, (unsigned int)UNKNOWN_WORD_ID));

    return boneNext;
}

CSkeletonIter
CIMIContext::forwardPuncBone(CSkeletonIter bone)
{
    unsigned int wid = m_pPinyinTrie->getSimbolId(bone->m_String);

    CSkeletonIter boneNext = ++CSkeletonIter(bone);
    CLexiconStates & lss = boneNext->m_pInnerData->m_LexiconStates;
    lss.clear();
    lss.push_back(CLexiconState(bone, wid));

    return boneNext;
}

CSkeletonIter
CIMIContext::forwardNonPinyinBone(CSkeletonIter bone)
{
    CSkeletonIter boneNext = ++CSkeletonIter(bone);
    CLexiconStates & lss = boneNext->m_pInnerData->m_LexiconStates;
    lss.clear();
    lss.push_back(CLexiconState(bone, (unsigned int)UNKNOWN_WORD_ID));

    return boneNext;
}


CSkeletonIter
CIMIContext::forwardTailBone(CSkeletonIter bone)
{
    CSkeletonIter boneNext = ++CSkeletonIter(bone);
    CLexiconStates & lss = boneNext->m_pInnerData->m_LexiconStates;
    lss.clear();
    lss.push_back(CLexiconState(bone, OOV_WORD_ID));

    return boneNext;
}

CBone::CBone(const CBone& b)
    : m_BoneType(b.m_BoneType), m_BoundaryType(b.m_BoundaryType),
      m_String(b.m_String), m_pInnerData(NULL)
{
}

CBone::CBone(int boundType, int boneType)
    : m_BoneType(boneType), m_BoundaryType(boundType),
      m_String(), m_pInnerData(NULL)
{
}

CBone::CBone(const TWCHAR* pwc, int boundType, int boneType)
    : m_BoneType(boneType), m_BoundaryType(boundType),
      m_String(pwc), m_pInnerData(NULL)
{
}

CBone::CBone(const TWCHAR* pwc,  size_t len, int boundType, int boneType)
    : m_BoneType(boneType), m_BoundaryType(boundType),
      m_String(pwc, len), m_pInnerData(NULL)
{
}

CBone::~CBone()
{
    delete m_pInnerData;
    m_pInnerData = NULL;
}

bool
CBone::isUserSelectionStart(void)
{
    return (m_pInnerData != NULL &&
              m_pInnerData->m_BWType == CBoneInnerData::UserSelectedBestWord);
}

int
cursorMapping(CSkeletonIter head1, CSkeletonIter tail1,
              CSkeletonIter head2, CSkeletonIter tail2,
              CSkeleton& result,
              CSkeletonIter& cursor, int& cursorIdx, bool stickLeft = false)
{
    TSkelCursor sc(head1, tail1, head2, tail2, true);
    TSkelCursor::TPos cp(cursor, cursorIdx);

    int  len = 0;
    bool found =false;

    while (true) {
        found = sc.ensureCursor(cp);
        if (found) break;
        if (!sc.hasNext()) break;
        sc.next(true);
        ++len;
    }

    if (found) {
        TSkelCursor::TPos nc = sc.getPosition();

        int cmplen = cursorIdx = 0,  nNode = 0;
        for (cursor = result.begin(); cursor != result.end(); ++cmplen) {
            if (cmplen == len) break;
            ++cursorIdx;
            if (cursorIdx >= cursor->m_String.size()) {
                ++cursor;
                ++nNode;
                cursorIdx = 0;
            }
        }
        if (cmplen == len) { // now we found that
            if (stickLeft && cursor != result.begin() && cursorIdx == 0) {
                --cursor;
                --nNode;
                cursorIdx = cursor->m_String.size();
            }
        }
        return nNode;
    }
    return -1;
}

/**
* it is illegal if boneStart == boneEnd and skel.size() == 0
*
* 1. from current position, seeking left for 3 bones without HumanBoundary, or bones
*    of non-pinyin type between it. --> its, also can not beyond m_CandiBone.
* 2. in [its, bonStart) from left to right, find the first bone would cause different
*    segmentation result.  --> itd, other wise itds <-- boneStart
* 3. from [itd, boneEnd), do automatic segment
* 4. after boneEnd, util user boundary or non-pinyin bone
*    or segment result equals to original. --> itd2.
* 5. [itd, itd2) re-segment, all resulting bone goes into a new skeleton --> newskel.
*    while convert old cursor position into new position.
* 6. erase old or seg-affected nodes and splice in the newskel.
*    do search if needed
*
* The key part of this would seeking a solution for finding the automatic sentence
* segmentation result.
*/
bool
CIMIContext::modifyAndReseg(CSkeletonIter boneStart, CSkeletonIter boneEnd, CSkeleton& skel,
                            CSkeletonIter& cursor, int& cursorIdx, CSkeletonIter& candiStart,
                            bool stickLeft, bool doSearch)
{
    CSkeleton newskel;

    // Try to look_left to prevent potential segmentation insufficiency
    CSkeletonIter nit, oit, its = boneStart;
    int look_left = 0;
    for (; look_left < 3 && its != getFirstBone() && its != candiStart; ++look_left) {
        --its;
        if (!its->isPinyinNode() || its->m_BoundaryType == CBone::USER_BOUNDARY) {
            ++its;
            break;
        }
        skel.push_front(*its);
    }

    // do Syllable segment on the virtual new list
    segPinyin(skel.begin(), skel.end(), boneEnd, getLastBone(), newskel);

    // Remapping the new cursor
    int  ncIdx = cursorMapping(skel.begin(), skel.end(), boneEnd, getLastBone(), newskel, cursor, cursorIdx, stickLeft);

    // Skip previous look-left nodes that are same with original
    int first_diff = 0;
    CSkeletonIter dif_oits=skel.begin();
    for (oit=skel.begin(), nit=newskel.begin(); first_diff < look_left; ++first_diff) {
        if (nit->m_String.size() != oit->m_String.size()) {
            dif_oits = oit;
            break;
        }
        if (ncIdx == 0) cursor = its;
        --ncIdx;
        ++its;
        ++nit;
        ++oit;
        newskel.pop_front();
    }

    // prepare to restore the CandiStart
    bool candiStartPositionReset = (its == candiStart);

    // Prepare for cursor reposition to restore after modify
    CSkeletonIter leftIt;
    bool leftItIsHead = (its == getFirstBone());
    if (!leftItIsHead) {
        leftIt = its;
        --leftIt;
    }

    // modify original node list
    bool affectCandidates = modify(its, getLastBone(), newskel, doSearch);

    // Reposition cursor
    if (ncIdx >= 0) {
        cursor = (leftItIsHead)?(getFirstBone()):(++CSkeletonIter(leftIt));
        for (int i=0; i < ncIdx; ++i)
            ++cursor;
    }

    // Reposition candiStart
    if (candiStartPositionReset) {
        candiStart = (leftItIsHead)?(getFirstBone()):(++CSkeletonIter(leftIt));
        affectCandidates = true;
    }

    return affectCandidates;
}

void
CIMIContext::segPinyin(CSkeletonIter head1, CSkeletonIter tail1,
                       CSkeletonIter head2, CSkeletonIter tail2,
                       CSkeleton& result)
{
    #ifdef DEBUG
        printf("SegPinyin:");
    #endif

    const CPinyinTrie::TNode* pathNodes[16];
    TSkelCursor::TPos         positions[16];

    #ifdef  DEBUG
        TWCHAR dbg_msg[2] = {0, 0};
        {
            TSkelCursor dsc(head1, tail1, head2, tail2);
            while (dsc.hasNext()) {
                if (dsc.isPinyin()) {
                    dbg_msg[0] = dsc.getChar();
                    print_wide(dbg_msg);
                    if (dsc.isUserBreakAfter()) {
                        printf("'");
                    }
                } else {
                    printf("_");
                    dbg_msg[0] = dsc.getChar();
                    print_wide(dbg_msg);
                }
                dsc.next();
            }
        }
    #endif

    result.clear();
    TSkelCursor sc(head1, tail1, head2, tail2);
    while (sc.hasNext()) {
        if (sc.isPinyin()) {
            int lastValid = 0;
            pathNodes[0] = m_pPinyinTrie->getRootNode();
            positions[0] = sc.getPosition();
            for (int idx=1; sc.isPinyin() && pathNodes[idx-1] != NULL; ++idx) {
                pathNodes[idx] = m_pPinyinTrie->transfer(pathNodes[idx-1], sc.getChar());
                sc.next();
                positions[idx] = sc.getPosition();
                if (m_pPinyinTrie->isValid(pathNodes[idx], m_bNonCompleteSyllable, m_bGBK))
                    lastValid = idx;
                if (sc.isUserBreakAfter(positions[idx-1]))
                    break;
            }
            bool invalid = false;
            if (lastValid == 0) {
                invalid = true;
                lastValid = 1;
            }
            if (lastValid >= 2 && pathNodes[lastValid]->m_bFullSyllableTransfer && pathNodes[lastValid-1]->m_bFullSyllableTransfer) {
                TWCHAR w1 = sc.getChar(positions[lastValid-1]);
                TWCHAR w2 = sc.getChar(positions[lastValid]);
                if (!isYuanYinChar(w1) && isYuanYinChar(w2)){
                    const CPinyinTrie::TNode* pytmp = NULL;
                    pytmp = m_pPinyinTrie->transfer(m_pPinyinTrie->getRootNode(), w1);
                    if (pytmp) pytmp = m_pPinyinTrie->transfer(pytmp, w2);
                    if (pytmp != NULL) --lastValid;
                }
            }
            CBone bnint(CBone::AUTO_BOUNDARY, (invalid)?(CBone::NODE_INVALID_PINYIN):(CBone::NODE_PINYIN));
            if (sc.isUserBreakAfter(positions[lastValid-1]))
                bnint.m_BoundaryType = CBone::USER_BOUNDARY;
            for (int idx=0; idx < lastValid; ++idx)
                bnint.m_String += sc.getChar(positions[idx]);
            result.push_back(bnint);
            sc.setPosition(positions[lastValid]);
        } else {
            result.push_back(*(sc.getPosition().m_bone));
            sc.nextBone();
        }
    }

    #ifdef  DEBUG
        {
            printf(" ==> ");
            TSkelCursor dsc(result.begin(), result.end(), result.end(), result.end());
            while (dsc.hasNext()) {
                if (dsc.isPinyin()) {
                    dbg_msg[0] = dsc.getChar();
                    print_wide(dbg_msg);
                    if (dsc.isBreakAfter()) {
                        printf("'");
                    }
                } else {
                    printf("_");
                    dbg_msg[0] = dsc.getChar();
                    print_wide(dbg_msg);
                }
                dsc.next();
            }
        }
        fflush(stdout);
    #endif
    return;
}

void
CIMIContext::setHistoryMemory(CICHistory *phm)
{
    m_pHistory = phm;
}

CICHistory *
CIMIContext::getHistoryMemory()
{
    return m_pHistory;
}

void CIMIContext::memorize(void)
{
    if (m_pHistory != NULL) {
        std::vector<unsigned int> result;
        CSkeletonIter boneStart = getFirstBone();
        CSkeletonIter boneEnd = getLastBone();

        while (boneStart != boneEnd) {
            #ifdef DEBUG
                //assert(boneStart->m_pInnerData->m_BWType != CBoneInnerData::NoBestWordStartHere);
            #endif

            CSkeletonIter bone = boneStart;
            CSkeletonIter rightBone = boneStart->m_pInnerData->m_BestWord.m_BoneEnd;
            if (boneStart->m_BoneType != CBone::NODE_PINYIN && boneStart->m_BoneType != CBone::NODE_INCOMPLETE_PINYIN) {
                while (bone != rightBone && bone != boneEnd)
                    ++bone;
                result.push_back(0);
            } else {
                while (bone != rightBone && bone != boneEnd)
                     ++bone;
                result.push_back(boneStart->m_pInnerData->m_BestWord.m_WordId);
            }

            boneStart = bone;
        }
        if (result.size() > 0)
            m_pHistory->memorize(&(result[0]), (&(result[0])) + result.size());
    }
}

void
CIMIContext::print_lattice()
{
    printf("\n");
    std::string prefix;
    CSkeletonIter bone = getFirstBone();
    CSkeletonIter boneEnd = getLastBone();
    for (;bone != boneEnd; ++bone)
        bone->print(prefix);
    boneEnd->print(prefix);
    (++boneEnd)->print(prefix);
    fflush(stdout);
}

void
CBone::print(std::string& prefix)
{
    printf(prefix.c_str());
    printf("{Bone@%X:", this);
    print_wide(m_String.c_str());
    printf("}");
    prefix += "    ";
    if (m_pInnerData)
        m_pInnerData->print(prefix);
    prefix.resize(prefix.size() - 4);
    fflush(stdout);
}

void
CCandidate::print(std::string& prefix)
{
    printf(prefix.c_str());
    printf("<Candidate @%X:", this);
    print_wide(m_String);
    printf("-- %d}", m_WordId);
    fflush(stdout);
}


TLongExpFloat::TLongExpFloat(double d)
{
    if (d != 0.0 && d != -0.0) {
        TDoubleAnatomy da(d);
        m_exp = da.getExp();
        da.clearExp();
        m_base = da.getValue();
    } else {
        m_base = d;
        m_exp = 0;
    }
}

TLongExpFloat
TLongExpFloat::operator* (const TLongExpFloat& b) const
{
    double d = this->m_base * b.m_base;
    TLongExpFloat reda(d);
    reda.m_exp += this->m_exp + b.m_exp;
    return reda;
}

TLongExpFloat
TLongExpFloat::operator/ (const TLongExpFloat& b) const
{
    double d = this->m_base / b.m_base;
    TLongExpFloat reda(d);
    reda.m_exp += (this->m_exp - b.m_exp);
    return reda;
}

bool
TLongExpFloat::operator< (const TLongExpFloat& b) const
{
    if (m_base >= 0.0 && b.m_base >= 0.0) {
        return (m_exp < b.m_exp || (m_exp == b.m_exp && m_base < b.m_base));
    } else if (m_base < 0.0 && b.m_base < 0.0) {
        return (m_exp > b.m_exp || (m_exp == b.m_exp && m_base < b.m_base));
    } else if (m_base < 0.0 && b.m_base >= 0.0)
        return true;
    else
        return false;
}

bool
TLongExpFloat::operator<=(const TLongExpFloat& b) const
{
    if (m_base >= 0.0 && b.m_base >= 0.0) {
        return (m_exp < b.m_exp || (m_exp == b.m_exp && m_base <= b.m_base));
    } else if (m_base < 0.0 && b.m_base < 0.0) {
        return (m_exp > b.m_exp || (m_exp == b.m_exp && m_base <= b.m_base));
    } else if (m_base < 0.0 && b.m_base >= 0.0)
        return true;
    else
        return false;
}

bool
TLongExpFloat::operator==(const TLongExpFloat& b) const
{
    return (m_base == b.m_base && m_exp == b.m_exp);
}

void
TLongExpFloat::toString(std::string& str) const
{
    char buf[256];
    toString(buf);
    str = buf;
}

Indexes created Thu May 17 00:32:10 UTC 2012