LOUDSでTrieを作る

LOUDSを用いたTrieです. 文字列をキーとした連想配列で使用することを想定しています.
Trieと 完備辞書はこのために作成しました.
上２つは公開時から不具合修正と機能追加をしています.

LOUDSは, 木構造をビット列で表現します.
節点を幅優先で走査し, 各節点で子の数だけ"1"を並べ, 節点の終端に"0"を置きます.
子のない節点は"0", 子が１つの節点は"10"です.

"add", "and", "ans"からなるトライ木は, LOUDSで表現すると"1011010110000"になります.

ビット列を完備辞書として使用すると,
ビット位置mの子は, $select_{0}(rank_{1}(m))+1$のビット位置から始まります.
また, ビット位置mから始まる節点の節点番号は, $rank_{1}(m)$です.

上図の根は, ビット位置0から始まり, 節点番号は$rank_{1}(0)=0$です.
また, 根は子を１つ持ち, 子は$select_{0}(rank_{1}(0))+1=select_{0}(0)+1=1+1=2$から始まります.

namespace
{
    class LOUDS
    {
    public:
        LOUDS();
        ~LOUDS();

        void build(const core::ByteTrie& trie);

        const Char* find(const Char* key) const;
    private:
        LOUDS(const LOUDS&);
        LOUDS& operator=(const LOUDS&);

        struct TraverseTrie
        {
            TraverseTrie(LOUDS& louds, const core::ByteTrie& trie)
                :louds_(louds)
                ,trie_(trie)
            {}

            bool operator()(s32 index, const core::ByteTrie::node_type& node);

            LOUDS& louds_;
            const core::ByteTrie& trie_;
        };

        friend struct TraverseTrie;

        void clear();

        FullyIndexableDictionary fid_;
        ArrayPOD<Char> labels_;
        ArrayPOD<Char*> values_;
    };

    bool LOUDS::TraverseTrie::operator()(s32 index, const ByteTrie::node_type& node)
    {
        const Char* value = trie_.getValue(node);

        louds_.labels_.push_back(node.getLabel());
        louds_.values_.push_back(NULL);

        if(NULL != value){
            s32 len = strlen(value);
            louds_.values_[index] = (Char*)malloc(sizeof(Char)*(len+1));
            memcpy(louds_.values_[index], value, len+1);
        }

        for(s32 i=0; i<node.getNumChildren(); ++i,++index){
            louds_.fid_.add(true);
        }
        louds_.fid_.add(false);
        return true;
    }

    LOUDS::LOUDS()
    {
    }

    LOUDS::~LOUDS()
    {
        clear();
    }

    void LOUDS::build(const core::ByteTrie& trie)
    {
        clear();
        trie.traverse(TraverseTrie(*this, trie));
        fid_.build();
    }

    const Char* LOUDS::find(const Char* key) const
    {
        assert(NULL != key);
        static const u32 Invalid = -1;
        u32 bit = 0;
        u32 index = 0;

        while('\0' != *key){
            if(fid_.sizeInBits()<=bit){
                return NULL;
            }
            u32 next=Invalid;
            index = fid_.rank_one(bit);
            while(0!=fid_.access(bit)){
                ++index;
                if(labels_[index] == *key){
                    next = bit;
                    break;
                }
                ++bit;
            }
            if(Invalid == next){
                return NULL;
            }
            bit = fid_.select_zero(index-1)+1;
            ++key;
        }
        return values_[index];
    }

    void LOUDS::clear()
    {
        for(s32 i=0; i<values_.size(); ++i){
            free(values_[i]);
        }
        labels_.clear();
        values_.clear();
        fid_.clear();
    }
}