Class PatriciaTrie

• Defined in File PatriciaTrie.h

Nested Relationships

Nested Types

• Struct PatriciaTrie::Node

Class Documentation

class PatriciaTrie

a sorted dictionary of strings on a Patricia trie, with the blind search

Public Types

using value_type = std::string

using size_type = std::size_t

using difference_type = std::ptrdiff_t

using reference = const std::string&

using const_reference = const std::string&

using const_iterator = std::vector<std::string>::const_iterator

using iterator = const_iterator

Public Functions

explicit PatriciaTrie(std::vector<std::string> D)

the trie of D

Pre:

D is sorted and its strings distinct (an audit)

std::size_t lexicographicPosition(std::string_view P) const

the number of strings smaller than P, by the blind search

Post:

D[ r - 1 ] < P <= D[ r ]

std::size_t prefixEnd(std::string_view P) const

the number of strings smaller than P#, i.e., smaller than P or prefixed by P

std::pair<std::size_t, std::size_t> prefixRange(std::string_view P) const

the range [ l , r ) of the strings prefixed by P

std::size_t blindLeaf(std::string_view P) const

the leaf l of the first stage of the blind search of P, the only string that the search reads

Pre:

size() >= 1

bool contains(std::string_view P) const

std::size_t size(void) const

std::size_t nodes(void) const

the number of nodes, the root and the leaves included

const std::string &string(std::size_t i) const

the string i

Pre:

i < size()

std::vector<std::pair<std::size_t, int>> shape(void) const

the length of the prefix of each node and its branching character, in preorder (-1 for the end of a string, and for the root)

inline const_iterator begin(void) const

inline const_iterator end(void) const

inline const_iterator cbegin(void) const

inline const_iterator cend(void) const