src/lexicon/pytrie.h

/*
 * 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.
 */

#ifndef _SIM_PYTRIE_H
#define _SIM_PYTRIE_H

#include <stdio.h>

#include "../portability.h"

#include <stdint.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>

#define WORD_ID_WIDTH       18

class CPinyinTrie {
public:
    static const unsigned char SYLLABLE_BREAKER  = '\'';
    friend class CPinyinTrieMaker;

    class TTransUnit {
    public:
#if !defined(WORDS_BIGENDIAN)
        unsigned            m_Char  : 8;
        unsigned            m_Offset: 24;
#else
        unsigned            m_Offset: 24;
        unsigned            m_Char  : 8;
#endif
    };

    class TWordIdInfo {
    public:
#if !defined(WORDS_BIGENDIAN)
        unsigned            m_id       : WORD_ID_WIDTH;
        unsigned            m_bGBK     : 1;
        unsigned            m_bGB18030 : 1;
        unsigned            m_len      : 6;
        unsigned            m_cost     : 5;
        unsigned            m_bSeen    : 1;
#else
        unsigned            m_bSeen    : 1;
        unsigned            m_cost     : 5;
        unsigned            m_len      : 6;
        unsigned            m_bGB18030 : 1;
        unsigned            m_bGBK     : 1;
        unsigned            m_id       : WORD_ID_WIDTH;
#endif

    public:
        TWordIdInfo()
            { memset(this, 0, sizeof(TWordIdInfo)); }

        TWordIdInfo(unsigned id, unsigned len=0, unsigned seen=0, unsigned cost = 0, unsigned gbk = 0, unsigned gb18030 = 0)
            : m_id(id), m_bGBK(gbk), m_bGB18030(gb18030), m_len(len), m_cost(cost), m_bSeen(seen) { }

        operator
        unsigned int() const { return m_id; }
    };

    class TNode {
    public:
#if !defined(WORDS_BIGENDIAN)
        unsigned            m_nWordId    : 16;
        unsigned            m_nTransfer  : 8;
        unsigned            m_bGBK       : 1;
        unsigned            m_bGB18030   : 1;
        unsigned            m_bFullSyllableTransfer: 1;
        unsigned            m_bOther     : 5;

#else
        unsigned            m_bOther     : 5;
        unsigned            m_bFullSyllableTransfer: 1;
        unsigned            m_bGB18030   : 1;
        unsigned            m_bGBK       : 1;
        unsigned            m_nTransfer  : 8;
        unsigned            m_nWordId    : 16;

#endif

    public:
        static unsigned int
        size_for(unsigned int nTransfer, unsigned int nWordId)
            { return sizeof(TNode) + sizeof(TTransUnit)*nTransfer +
                sizeof(TWordIdInfo)*nWordId; }

    public:
        TNode() { *((uint32_t*)this) = 0; }

        bool
        hasPinyinChild(void) const
            { return (m_nTransfer > 1) ||
                (m_nTransfer ==1 && getTrans()->m_Char != SYLLABLE_BREAKER); }

        const TTransUnit*
        getTrans() const
            { return (TTransUnit*)(this+1); }

        const TWordIdInfo*
        getWordIdPtr() const
            { return (TWordIdInfo*)(((char*)(this+1))+sizeof(TTransUnit)*m_nTransfer); }

        unsigned int
        transfer(unsigned char c) const;

        inline unsigned int
        transfer(unsigned c) const
            { return transfer((unsigned char)(c)); }
    };

public:
    CPinyinTrie() : m_Size(0), m_mem(NULL), m_words(NULL) { }

    ~CPinyinTrie() { free(); }

    bool
    load(const char* fileName);

    bool
    isValid(const TNode* pnode, bool allowNonComplete, bool allowGBK=true);

    unsigned int
    getRootOffset() const { return 3 * sizeof(unsigned int); }

    const TNode*
    getRootNode() const { return (TNode*)(m_mem+getRootOffset()); }

    const TNode*
    nodeFromOffset(unsigned int offset) const
        { return (offset < getRootOffset())?NULL:((TNode*)(m_mem+offset)); }

    //@{
    /** transfer on an char or a string from a specific node*/
    //inline const TNode*
    //transfer(const TNode* pnode, char c) const
    //    { return transfer(pnode, (unsigned char)c); }

    inline const TNode*
    transfer(const TNode* pnode, unsigned char c) const
        { return nodeFromOffset(pnode->transfer(c)); }

    inline const TNode*
    transfer(const TNode* pnode, TWCHAR wc) const
        { return nodeFromOffset(pnode->transfer(unsigned(wc))); }

    /*
    inline const TNode*
    transfer(const TNode* pnode, const char* str) const
        { return transfer(pnode, (const unsigned char*)str); }
    */

    const TNode*
    transfer(const TNode* pnode, const unsigned char* str) const;

    const TNode*
    transfer(const TNode* pnode, const TWCHAR* wstr) const;

    /*
    inline const TNode*
    transfer(const TNode* pnode, const char* str, int nlen) const
        { return transfer(pnode, (const unsigned char*)str, nlen); }
    */

    const TNode*
    transfer(const TNode* pnode, const unsigned char* str, int nlen) const;

    const TNode*
    transfer(const TNode* pnode, const TWCHAR* wstr, int nlen) const;
    //@}

    //@{
    /** transfer on an char or a string from root node*/
    /*
    inline const TNode*
    transfer(const char* str) const
        { return transfer(getRootNode(), str); }
    */

    inline const TNode*
    transfer(const unsigned char* str) const
        { return transfer(getRootNode(), str); }

    inline const TNode*
    transfer(const TWCHAR* wstr) const
        { return transfer(getRootNode(), wstr); }

    /*
    inline const TNode*
    transfer(const char* str, int nlen) const
        { return transfer(getRootNode(), str, nlen); }
    */

    inline const TNode*
    transfer(const unsigned char* str, int nlen) const
        { return transfer(getRootNode(), str, nlen); }

    inline const TNode*
    transfer(const TWCHAR* wstr, int nlen) const
        { return transfer(getRootNode(), wstr, nlen); }
    //@}

    unsigned int
    getWordCount(void) const { return *(unsigned int*)m_mem; }

    unsigned int
    getNodeCount(void) const { return *(unsigned int*)(m_mem+sizeof(unsigned int)); }

    unsigned int
    getStringOffset(void) const { return *(unsigned int*)(m_mem+2*sizeof(unsigned int)); }

    unsigned int
    getSimbolId(const TWCHAR* wstr);

    unsigned int
    getSimbolId(const wstring & wstr);

    const TWCHAR*
    operator[](unsigned int idx) const { return m_words[idx]; }

    int
    lengthAt(unsigned int idx) const;

    void
    free(void);

    void
    print(FILE *fp) const;

protected:
    unsigned int           m_Size;
    char                  *m_mem;
    TWCHAR               **m_words;

    std::map<wstring, unsigned>  m_SimbolMap;

protected:
    void
    print(const TNode* pRoot, std::string& prefix, FILE *fp) const;
};

#endif