Radix trees in Rcpp

Constructing trees

Trees are constructed using the syntax:

radix_tree<type1, type2> radix;

Where type represents the type of the keys (for example, std::string) and type2 the type of the values.

Radix trees can have any scalar type as keys, although strings are most typical; they can also have any scalar type for values. Once you’ve constructed a tree, new entries can be added in a very R-like way: radix[new_key] = new_value;. Entries can also be removed, with radix.erase(key).

Matching against trees

We then move on to the fun bit: matching! As mentioned, radix trees are really good for matching arbitrary values against keys (well, keys of the same type) and retrieving the associated values.

There are three types of supported matching; longest, prefix, and greedy. Longest does exactly what it says on the tin: it finds the key-value pair where the longest initial part of the key matches the arbitrary value:

radix_tree<std::string, std::string> radix;
radix["turnin"] = "entry the first";
radix["turin"] = "entry the second";

radix_tree<std::string, std::string>::iterator it;

it = radix.longest_match("turing");

if(it = radix.end()){
  printf("No match was found :(");
} else {
  std::string result = "Key of longest match: " + it->first + " , value of longest match: " + it->second;
}

Prefix matching provides all trie entries where the value-to-match is a prefix of the key:

radix_tree<std::string, std::string> radix;
radix["turnin"] = "entry the first";
radix["turin"] = "entry the second";

std::vector<radix_tree<std::string, std::string>::iterator> vec;
std::vector<radix_tree<std::string, std::string>::iterator>::iterator it;

it = radix.prefix_match("tur");

if(it == vec.end()){
  printf("No match was found :(");
} else {
  for (it = vec.begin(); it != vec.end(); ++it) {
    std::string result = "Key of a prefix match: " + it->first + " , value of a prefix match: " + it->second;
  }
}

Greedy matching matches very, very fuzzily (a value of ‘bring’, for example, will match ‘blind’, ‘bind’ and ‘binary’) and, syntactically, looks exactly the same as prefix-matching, albeit with radix.greedy_match() instead of radix.prefix_match().