trie.hpp

Go to the documentation of this file.

#if !defined(HSDS_TRIE_HPP_)
#define HSDS_TRIE_HPP_

#include <vector>
#include "hsds/vector.hpp"
#include "hsds/bit-vector.hpp"

namespace hsds {

class Trie {
public:
    typedef uint64_t id_t; 
    static const id_t NOT_FOUND = ~(0ULL); 
    static const id_t CAN_NOT_TRAVERSE = ~(0ULL) - 1; 

    typedef struct Result {
        id_t id; 
        uint64_t depth; 

        Result(id_t id_, uint64_t depth_) :
                id(id_), depth(depth_) {
        }
    } Result;

    Trie();

    virtual ~Trie();

    void build(std::vector<std::string>& keyList, bool useTailTrie = false);

    id_t exactMatchSearch(const char* str, size_t len) const;

    void commonPrefixSearch(const char* str, size_t len, std::vector<id_t>& retIDs,
            uint64_t limit = DEFAULT_LIMIT_VALUE) const;

    void commonPrefixSearch(const char* str, size_t len, std::vector<Result>& results, uint64_t limit =
            DEFAULT_LIMIT_VALUE) const;

    void predictiveSearch(const char* str, size_t len, std::vector<id_t>& retIDs,
            uint64_t limit = DEFAULT_LIMIT_VALUE) const;

    id_t traverse(const char* str, size_t len, uint64_t& nodePos, uint64_t& zeros, size_t& keyPos) const;

    void decodeKey(id_t id, std::string& key) const;

    void swap(Trie& x);

    void clear();

    size_t size() const;

    void save(std::ostream& os) const throw (hsds::Exception);

    void load(std::istream& is) throw (hsds::Exception);

    uint64_t map(void* ptr, uint64_t mapSize) throw (hsds::Exception);

private:
    static const uint64_t DEFAULT_LIMIT_VALUE = ~(0ULL); 
    BitVector louds_;
    BitVector terminal_;
    BitVector tail_;

    Vector<Vector<char> > vtails_;
    Vector<uint8_t> edges_;
    size_t numOfKeys_;
    bool isReady_;

    Trie* vtailTrie_;
    BitVector tailIDs_;
    uint64_t tailIDSize_;

    void build(hsds::Vector<Vector<char>  >& keyList);// for build tail trie
    void buildTailTrie();
    bool isLeaf(uint64_t pos) const;
    void getChild(uint8_t c, uint64_t& pos, uint64_t& zeros) const;
    void getParent(uint8_t& c, uint64_t& pos, uint64_t& zeros) const;
    void enumerateAll(uint64_t pos, uint64_t zeros, std::vector<id_t>& retIDs, size_t limit) const;
    bool tailMatch(const char* str, size_t len, size_t depth, uint64_t tailID, size_t& retLen) const;
    Vector<char> getTail(uint64_t i) const;
};

}

#endif