Contents

ObjectTrie

Overview

An object based trie used for parent-child hierarchies.

This data structure is useful when the parent-child relationships between nodes are semantically important and must not be changed via tree balancing. If this is not the case, a B-tree or red–black tree would most likely be more appropriate.

Each node in the trie contains an object of type T plus a vector of child nodes. A node's children are ordered in the order of appending.

In addition to depth first and breadth first iteration, the object trie contains search and cascade algorithms. The object type T is thus effectively a combination of primary key and value. The type T normally provides a key type field that is compared within the operator == function/method, and one or more value fields that are not part of the equality evaluation.

When using the search algorithms of the object trie, the standard operator == function / method is used for the object type T. Alternative methods are also provided that accept a custom compare function/lambda, allowing value types that do not have a suitable operator == function/method to be used in the object trie search and cascade algorithms.

This trie implementation is not optimised or compressed. Use cases requiring an optimised trie representation would most likely be better using a non-object based trie implementation.

Quick start

#include <Balau/Container/ObjectTrie.hpp>

Construction

An object trie can be constructed either by constructing a trie with a root node containing a default constructed value, or by copying/moving a value into the trie to form the root node.

			// Construct an object trie with a default root value.
			// The int type is used as the value type.
			ObjectTrie<int> trie1;

			// Construct an object trie with a specified root value.
			ObjectTrie<int> trie2(123);

When a class type is used as the object trie type, a suitable operator == function/method should be defined if the object trie's algorithms are to be used.

			// A class used in the object trie.
			// The primary key of the class is the integer.
			struct A {
				int k;
				double v;

				// Implicit construction for key only objects.
				A(int k_) : k(k_) {}

				// Explicit construction for full objects.
				A(int k_, double v_) : v(v_) {}
			};

			inline bool operator == (const A & lhs, const A & rhs) {
				return lhs.k == rhs.k;
			}

			ObjectTrie<A> trie({ 0, 123.45 });

The nodes of the trie are represented by ObjectTrieNode objects. These contain the value T, and a vector of child nodes.

Trie nodes

The root node of the trie may be obtained via the root method.

			ObjectTrieNode<A> & rootNode = trie.root();

To obtain child nodes, the trie has count and get methods that provide the number of children of the root and references to the child nodes. Similarly, the ObjectTrieNode has equivalent count and get methods that provide the number of children of the node and references to the children of the node.

			// Get the second child of the root node.
			ObjectTrieNode<A> & c = trie.get(1);

			// Get the first child of the second child.
			ObjectTrieNode<A> & c = c.get(0);

New child nodes of the root node or child nodes may be added via the add and addAndReturnChild methods. The add method adds the new child node and returns the current node. The addAndReturnChild method adds the new child node and returns the new child.

			// Add a new node to the root of the trie.
			trie.add(2);

			// Add a new node to the first child of the root node.
			c.get(0).add(7);

Searching

The find and findNearest methods perform hierarchical exact and nearest searching.

Find

To use the find methods, call one of the methods with a vector of values to compare. The find method will descend into the trie, comparing each supplied value in turn with the current set of childen. If a match is not found in one of levels, nullptr is returned.

There are two find method overloads. The first overload uses the default operator == function/method for the type T and the second overload allows a custom comparator to be specified.

			// Perform an exact search with the default comparator.
			auto * n = trie.find({ 1 });

By default, the root node is not included in the search, thus the first object in the supplied vector is compared with the child nodes of the root node.

If the root node should be included in the search, true should be passed as the second argument in the method call.

			// Perform an exact search with the default comparator.
			// Include the root node in the search.
			auto * n = trie.find({ 0, 1 }, true);

In order to use a custom comparator, a lambda function can be specified in the call.

			// Perform an exact search with a custom comparator.
			auto * n = trie.find(
				  { 0, 1 }
				, [] (auto & lhs, auto & rhs) { return lhs.k == rhs.k; }
			);

FindNearest

The findNearest methods work in the same way as the find methods, with the exception that if a match is not found in one of levels, the current match is returned. If no matches are found at all, then nullptr is returned.

			// Perform a nearest search with the default comparator.
			auto * n = trie.findNearest({ 1, 2, 3 });

FindNearestLeaf

The findNearestLeaf methods work in the same way as the findNearest methods, with the exception that a match must terminate with a leaf node. If a nearest match is found that is not a leaf node, then nullptr is returned.

			// Perform a nearest leaf search with the default comparator.
			auto * n = trie.findNearestLeaf({ 1, 2, 3 });

Iteration

Standard library compatible iterators are provided in the object trie implementation. There are two types of iterator available:

depth first;
breadth first.

The iterator and const_iterator iterators are typedefs to the DepthIterator and ConstDepthIterator object trie iterators.

Depth first

Depth first iteration is performed in the same way as iteration in any standard library container.

			ObjectTrie<int> trie(0);
			populateUIntTrie(trie);

			// Traditional iteration.
			while (ObjectTrie<int>::iterator i = trie.begin(); i != trie.end(); ++i) {
				auto & object = i->value;

				// ... use the object ...
			}

			// Range-based iteration.
			for (auto & node : trie) {
				auto & object = node.value;

				// ... use the object ...
			}

If the depth first iteration should be explicitly mentioned in code, the depthBegin and depthEnd calls can be specified instead of begin and end.

			while (auto i = trie.depthBegin(); i != trie.depthEnd(); ++i) {
				auto & object = i->value;

				// ... use the object ...
			}

Breadth first

As the range-based loop defaults to depth first iteration, breadth first iteration must be performed via traditional iteration.

			// Perform a breadth first iteration on the same trie.
			while (auto i = trie.breadthBegin(); i != trie.breadthEnd(); ++i) {
				auto & object = i->value;

				// ... use the object ...
			}

Cascading

Object trie cascading involves copying or moving one object trie onto another object trie with the following rules.

Each node in the source trie that matches a node in the destination trie for equality and position is (copy or move) assigned to the node in the source trie.
Each node in the source trie that does not match a node in the destination trie for equality and position is (copy or move) added to the destination trie.

			// Perform an object trie cascade.
			ObjectTrie<int> trie1(0);
			populateUIntTrie1(trie1);

			ObjectTrie<int> trie2(0);
			populateUIntTrie2(trie2);

			trie1.cascade(trie2);

The above code performs copy cascading. This results in the source trie maintaining validity after the cascade operation. If move cascading is required instead, the std::move cast may be used to move the source trie into the cascade call.

			// Perform an object trie cascade via moving.
			trie1.cascade(std::move(trie2));

The third and fourth cascade methods overloads accept a copy or move function in addition to the source trie. This allows the source node's value to be modified during copying / moving. Otherwise, the cascade semantics are identical to the first two method overloads.

Fluent build API

In order to provide a visual representation of an object trie in code, a variadic fluent build API is provided in the object trie implementation. This build API can be most useful in test code, where canned tries need to be constructed.

The ObjectTrieTest::fluentBuild test case provides a usage example of the fluent build API.

			using Trie = ObjectTrie<Value>;
			using Node = ObjectTrieNode<Value>;

			Trie trie;

			trie.add({ 'a', 1 }
				, Node::child({ 'a', 11 })
				, Node::child({ 'b', 12 })
				, Node::child({ 'c', 13 })
				, Node::child({ 'd', 14 })
			).add({ 'b', 2 }
				, Node::child({ 'a', 21 })
				, Node::child({ 'b', 22 }
					, Node::child({ 'a', 221 })
					, Node::child({ 'b', 222 })
					, Node::child({ 'c', 223 })
				)
			).add({ 'c', 3 }
				, Node::child({ 'a', 31 })
				, Node::child({ 'b', 32 })
				, Node::child({ 'c', 33 })
				, Node::child({ 'd', 34 })
				, Node::child({ 'e', 35 })
			);