# ternary-tree

A Rust implementation of Ternary Search Trees, with no unsafe block and a simplified [Wasm binding](
https://crates.io/crates/ternary-tree-wasm).

[![Build Status]( http://travis-ci.com/julien-montmartin/ternary-tree.svg?branch=master)](
	http://travis-ci.com/julien-montmartin/ternary-tree)
[![Code coverage]( http://codecov.io/gh/julien-montmartin/ternary-tree/branch/master/graph/badge.svg)](
	http://codecov.io/gh/julien-montmartin/ternary-tree)
[![Latest version]( http://img.shields.io/crates/v/ternary-tree.svg)](
	http://crates.io/crates/ternary-tree)
[![API](https://docs.rs/ternary-tree/badge.svg)](
	https://docs.rs/ternary-tree/)

A Ternary Search Tree (TST) is a data structure which stores key/value pairs in a tree. The key is a string, and
its characters are placed in the tree nodes. Each node may have three children (hence the name): a _left_ child, a
_middle_ child and a _right_ child.

A search in a TST compares the current character in the key with the character of the current node:

* If both matches, the search traverses the middle child, and proceed to the next character in the key
* If the key character is less than the node one, the search simply goes through the left child, and keep looking
  for the same key character
* Respectively, if the key character is greater than the node one, the search simply goes through the right child

The data structure and its algorithm are explained very well in [Dr.Dobb's Ternary Search Trees](
http://www.drdobbs.com/database/ternary-search-trees/184410528) article.

The following tree is the TST we get after inserting the following keys in order: "aba", "ab", "bc", "ac", "abc",
"a", "b", "aca", "caa", "cbc", "bac", "c", "cca", "aab", "abb", "aa" (see `tst.dot` produced by code below)

<p align="center"><img alt="An example of a Ternary Search Tree"
src="http://files.jmontmartin.net/tree.svg"></p>

A checked box "☑" denotes a node which stores a value (it corresponds to the last character of a key). An empty box
"☐" means that the node has no value.

A TST can be used as a map, but it allows more flexible ways to retrieve values associated with keys. This crate
provides four ways to iterate over the values of a TST:

* get all values (same as a regular map), with `visit_values` or `iter`
* get all values whose keys begin with some prefix (i.e. _complete_ some prefix), with `visit_complete_values` or
  `iter_complete`
* get all values whose keys are _close_ to some string ([Hamming distance](
  http://en.wikipedia.org/wiki/Hamming_distance)), with `visit_neighbor_values` or `iter_neighbor`
* get all values whose keys match a string with some joker (e.g. "a?c"), with `visit_crossword_values` or
  `iter_crossword`

Visit methods are recursive and apply a closure to found values. They exist in immutable and mutable version
(i.e. `visit_neighbor_values_mut`). But once a value is found (based on its key), they offer no way to know what
the actual key is.

Iterators, on the other hand, save their context in a `Vec` and only work on immutable trees. However they are
double-ended, and support `next` and `next_back` methods to walk the tree from both ends. Moreover, once a value is
found, they offer the `current_key` and `current_key_back` methods to retrieve the associated key.

The following lines may give you a foretaste of this crate and TSTs

```rust
extern crate ternary_tree;

use ternary_tree::Tst;
use std::fs::File;
use std::error::Error;

const SOME_KEYS : [&str; 16] = ["aba", "ab", "bc", "ac",
"abc", "a", "b", "aca", "caa", "cbc", "bac", "c", "cca",
"aab", "abb", "aa"];

let mut map = Tst::new();

for key in &SOME_KEYS {

    // Say the value is the same as the key,
    // it makes the example easier !
    let some_value = *key;

    map.insert(key, some_value);
}

// Use Graphviz to convert tst.dot to tst.png:
// dot -T png -o tst.png tst.dot
let mut file = File::create("tst.dot").unwrap();
map.pretty_print(&mut file);

let mut v = Vec::new();

// Recursively get all values whose keys match "a?a" pattern
map.visit_crossword_values("a?a", '?', |s| v.push(s.clone()));
assert_eq!(v, ["aba", "aca"]);

v.clear();

// Iterate over all values whose keys are close to "abc"
// (At a Hamming distance of 1 from "abc")
{
    let mut it = map.iter_neighbor("abc", 1);

    while let Some(value) = it.next() {

        v.push(*value);
    }
    assert_eq!(v, ["ab", "aba", "abb", "abc", "cbc"]);

    v.clear();
}

// Mutate all values whose keys begin with "c"
map.visit_complete_values_mut("c", |s| *s = "xxx");

assert_eq!(map.get("caa"), Some(&"xxx"));
assert_eq!(map.get("cbc"), Some(&"xxx"));
assert_eq!(map.get("cca"), Some(&"xxx"));
```

License: BSD-3-Clause