vg::BitStringTree< Item > Class Template Reference

#include <stream_index.hpp>

Classes
struct	TreeNode

Public Member Functions
void	insert (const BitString &key, const Item &value)
	Insert the given item under the given key. More...
bool	traverse_up (const BitString &key, const function< bool(const Item &)> &iteratee) const
bool	traverse_in_order (const BitString &low, const BitString &high, const function< bool(const Item &)> &iteratee) const

Protected Attributes
TreeNode	root
	The root node has an empty prefix. More...

Detailed Description

template<typename Item>
class vg::BitStringTree< Item >

Represents a radix tree keyed by/internally using BitStrings. Each item has a BitString as a key, and items are stored in a trie/prefix tree. Each node has at most one item and at most two children. Movable but not copyable. TODO: Implement copy.

Member Function Documentation

insert()

template<typename Item >

void vg::BitStringTree< Item >::insert	(	const BitString &	key,
		const Item &	value
	)

Insert the given item under the given key.

traverse_in_order()

template<typename Item >

bool vg::BitStringTree< Item >::traverse_in_order	(	const BitString &	low,
		const BitString &	high,
		const function< bool(const Item &)> &	iteratee
	)		const

Enumerate items which have the given low and high bit strings as a prefix, or which fall between them, as an in-order traversal of the tree. Returns false if stopped early.

traverse_up()

template<typename Item >

bool vg::BitStringTree< Item >::traverse_up	(	const BitString &	key,
		const function< bool(const Item &)> &	iteratee
	)		const

Enumerate items whose keys match prefixes of the given key, in order from most specific to least specific. Returns false if stopped early.

Member Data Documentation

root

template<typename Item >

TreeNode vg::BitStringTree< Item >::root

protected

The root node has an empty prefix.

---

The documentation for this class was generated from the following file:

• src/stream_index.hpp