TreeMap< K, V, MAP, COW, OPT > Class Template Reference

#include <treemap.h>

Inheritance diagram for TreeMap< K, V, MAP, COW, OPT >:

Detailed Description

template<typename K, typename V, typename MAP = HashMapSelector<>, Bool COW = false, Bool OPT = true>
class maxon::TreeMap< K, V, MAP, COW, OPT >

A TreeMap maps paths of K-typed elements to values of type V by storing the data in a hierarchy of nodes (where each node is a TreeMap itself with TreeMaps as children). This allows to walk through the data in a similar way as for a file system hierarchy.

As an example, consider this TreeMap where the path {1, 2, 3} is mapped to 42.0 and the path {1, 4} to 99.0:

TreeMap<Int, Float> map;
map.Insert(TmpBlock<const Int>{1, 2, 3}, 42.0_f) iferr_return;
map.Insert(TmpBlock<const Int>{1, 4}, 99.0_f) iferr_return;

The code sets up this hierarchy:

/// 1
/// |-- 2
/// |   `-- 3 {value = 42.0}
/// `-- 4 {value = 99.0}
/// 

You can then query for entries with FindValue, iterate over the whole TreeMap with one of the ForEach functions, or recursively walk over the TreeMap nodes yourself using the GetChildren() function at each level.

The example uses true for the OPT template parameter (the default value). This means that each node stores its value in an Opt<V>, then for paths for which no value has been set explicitly (like {1} or {1, 2} in the example) there's no value associated with those paths. With false for OPT the nodes of these paths would have default values, and functions like Contains() or FindValue() would report them.

Template Parameters

K	Type of path elements.
V	Type of values.
MAP	A map selector template to choose the implementation for the children map.
COW	True when the nested trees shall be held by a COW reference. Then they can be shared, but there's no up pointer.
OPT	True when values shall be stored in an Opt<V>. If false, all tree nodes always have a value, so when you insert a node at a nested path, all parent nodes which haven't existed so far are created with a default value.

Public Types
using	KeyType = K
using	ValueType = V
using	Super = TreeMapParent< TreeMap< K, V, MAP, COW, OPT >, COW >
using	Child = typename std::conditional< COW, StrongCOWRef< TreeMap >, TreeMap >::type
using	Ref = typename std::conditional< COW, StrongCOWRef< TreeMap >, void >::type
using	ChildrenMap = typename MAP::template Type< K, Child >
using	OptValueType = typename std::conditional< OPT, Opt< V >, V >::type

Public Member Functions
	TreeMap ()=default
	TreeMap (TreeMap &&src)
	MAXON_OPERATOR_MOVE_ASSIGNMENT (TreeMap)
	MAXON_DISALLOW_COPY_AND_ASSIGN (TreeMap)
template<typename ALLOCATOR >
	TreeMap (ALLOCATOR &&arg)
Result< void >	CopyFrom (const TreeMap &src)
void	Flush ()
void	Reset ()
Result< TreeMap & >	InsertChild (const K &key, Bool withValue=true)
template<typename C >
Result< TreeMap & >	InsertChildCtor (const K &key, C &&constructor)
Result< Child & >	InsertChild (const K &key, Child &&child)
template<typename PATH , typename = typename std::enable_if<!STD_IS_REPLACEMENT(base_of, K, typename std::decay<PATH>::type)>::type>
Result< TreeMap & >	InsertEntry (PATH &&key, Bool withValue=true)
template<typename PATH , typename = typename std::enable_if<!STD_IS_REPLACEMENT(base_of, K, typename std::decay<PATH>::type)>::type>
Result< TreeMap & >	Insert (PATH &&key, const V &value)
template<typename PATH , typename = typename std::enable_if<!STD_IS_REPLACEMENT(base_of, K, typename std::decay<PATH>::type)>::type>
Result< TreeMap & >	Insert (PATH &&key, V &&value)
template<typename PATH >
Result< V & >	InsertKey (PATH &&key, Bool &created)
template<typename PATH >
Result< V & >	InsertKey (PATH &&key)
const TreeMap *	FindChild (const K &key) const
TreeMap *	FindChild (const K &key)
template<typename PATH >
const TreeMap *	FindEntry (PATH &&key) const
template<typename PATH , typename = typename std::enable_if<!COW || AlwaysFalse<PATH>::value>::type>
TreeMap *	FindEntry (PATH &&key)
template<typename PATH >
const TreeMap *	FindFirstEntryWithValue (PATH &&key) const
template<typename PATH >
const TreeMap *	FindClosestEntryWithValue (PATH &&key) const
template<typename PATH >
Opt< const V & >	FindValue (PATH &&key) const
template<typename PATH , typename = typename std::enable_if<!COW || AlwaysFalse<PATH>::value>::type>
Opt< V & >	FindValue (PATH &&key)
template<typename PATH >
Bool	Contains (PATH &&key) const
template<typename PATH >
std::conditional< COW, Result< void >, ResultOk< void > >::type	Erase (PATH &&key, Bool withChildren=false)
String	ToString (const FormatStatement *fs=nullptr) const
const OptValueType &	Get () const
OptValueType &	Get ()
V &	MakeValid ()
void	SetValue (const V &value)
void	SetValue (V &&value)
Bool	IsRoot () const
Bool	IsLeaf () const
const ChildrenMap &	GetChildren () const
ChildrenMap &	GetChildren ()
const K *	GetKey () const
Bool	operator== (const TreeMap &other) const
Bool	operator!= (const TreeMap &other) const
Bool	IsPopulated () const
Bool	IsEmpty () const
Bool	HasSameStructure (const TreeMap &other) const
template<typename OP >
Result< Bool >	ForEachPreOrder (OP &&callback) const
template<typename PATH , typename OP >
Result< Bool >	ForEachPreOrder (OP &&callback, PATH &&path=PATH()) const
template<typename OP >
Result< Bool >	ForEachPreOrder (OP &&callback)
template<typename PATH , typename OP >
Result< Bool >	ForEachPreOrder (OP &&callback, PATH &&path=PATH())
template<typename PATH , typename OP >
Result< void >	ForEachPreOrderX (OP &&callback, PATH &&path=PATH())
template<typename OP >
Result< Bool >	ForEachPostOrder (OP &&callback) const
template<typename PATH , typename OP >
Result< Bool >	ForEachPostOrder (OP &&callback, PATH &&path=PATH()) const
template<typename OP >
Result< Bool >	ForEachPostOrder (OP &&callback)
template<typename PATH , typename OP >
Result< Bool >	ForEachPostOrder (OP &&callback, PATH &&path=PATH())
template<typename PATH >
Result< void >	GetPath (PATH &path) const
Int	GetDepth () const
IndexIterator< const K &, const TreeMap, TreeMap >	GetPath () const
Public Member Functions inherited from TreeMapParent< TreeMap< K, V, HashMapSelector<>, false, true >, false >
const TreeMap< K, V, HashMapSelector<>, false, true > *	GetParent () const
TreeMap< K, V, HashMapSelector<>, false, true > *	GetParent ()

Static Public Member Functions
static ResultRef< TreeMap >	MakeWritable (StrongCOWRef< TreeMap > &ref)
static ResultOk< TreeMap & >	MakeWritable (TreeMap &ref)
static const TreeMap *	GetTreeMap (const TreeMap *child)
static TreeMap *	GetTreeMap (TreeMap *child)
static const TreeMap *	GetTreeMap (const StrongCOWRef< TreeMap > *child)
static const K &	Get (const TreeMap &map, Int index)
static const TreeMap *	GetTreeMap (const V *value)
static TreeMap *	GetTreeMap (V *value)

Private Member Functions
void	ToStringImpl (String &s, BufferedBaseArray< K, 10 > &path, const FormatStatement *fs) const
template<typename IT >
std::conditional< COW, Result< Bool >, ResultOk< Bool > >::type	EraseImpl (IT &beginIt, const IT &endIt, Bool withChildren)

Static Private Member Functions
static const V *	Extract (const V &x)
static const V *	Extract (const Opt< V > &x)

Private Attributes
OptValueType	_value
ChildrenMap	_children

Additional Inherited Members
Protected Member Functions inherited from TreeMapParent< TreeMap< K, V, HashMapSelector<>, false, true >, false >
void	SetParent (TreeMap< K, V, HashMapSelector<>, false, true > *p)
Protected Attributes inherited from TreeMapParent< TreeMap< K, V, HashMapSelector<>, false, true >, false >
Pointer< TreeMap< K, V, HashMapSelector<>, false, true > >	_parent

Member Typedef Documentation

KeyType

using KeyType = K

ValueType

using ValueType = V

Super

using Super = TreeMapParent<TreeMap<K, V, MAP, COW, OPT>, COW>

Child

using Child = typename std::conditional<COW, StrongCOWRef<TreeMap>, TreeMap>::type

Ref

using Ref = typename std::conditional<COW, StrongCOWRef<TreeMap>, void>::type

ChildrenMap

using ChildrenMap = typename MAP::template Type<K, Child>

OptValueType

using OptValueType = typename std::conditional<OPT, Opt<V>, V>::type

Constructor & Destructor Documentation

TreeMap() [1/3]

TreeMap ( )

default

TreeMap() [2/3]

TreeMap

(

TreeMap< K, V, MAP, COW, OPT > &&

src

)

TreeMap() [3/3]

TreeMap ( ALLOCATOR &&  arg )

explicit

Member Function Documentation

MAXON_OPERATOR_MOVE_ASSIGNMENT()

MAXON_OPERATOR_MOVE_ASSIGNMENT

(

TreeMap< K, V, MAP, COW, OPT >

)

MAXON_DISALLOW_COPY_AND_ASSIGN()

MAXON_DISALLOW_COPY_AND_ASSIGN

(

TreeMap< K, V, MAP, COW, OPT >

)

CopyFrom()

Result<void> CopyFrom

(

const TreeMap< K, V, MAP, COW, OPT > &

src

)

Flush()

void Flush

(

)

Reset()

void Reset

(

)

InsertChild() [1/2]

Result<TreeMap&> InsertChild	(	const K &	key,
		Bool	withValue = true
	)

InsertChildCtor()

Result<TreeMap&> InsertChildCtor	(	const K &	key,
		C &&	constructor
	)

InsertChild() [2/2]

Result<Child&> InsertChild	(	const K &	key,
		Child &&	child
	)

MakeWritable() [1/2]

static ResultRef<TreeMap> MakeWritable ( StrongCOWRef< TreeMap< K, V, MAP, COW, OPT > > &  ref )

static

MakeWritable() [2/2]

static ResultOk<TreeMap&> MakeWritable ( TreeMap< K, V, MAP, COW, OPT > &  ref )

static

InsertEntry()

Result<TreeMap&> InsertEntry	(	PATH &&	key,
		Bool	withValue = true
	)

Insert() [1/2]

Result<TreeMap&> Insert	(	PATH &&	key,
		const V &	value
	)

Insert() [2/2]

Result<TreeMap&> Insert	(	PATH &&	key,
		V &&	value
	)

InsertKey() [1/2]

Result<V&> InsertKey	(	PATH &&	key,
		Bool &	created
	)

InsertKey() [2/2]

Result<V&> InsertKey

(

PATH &&

key

)

GetTreeMap() [1/5]

static const TreeMap* GetTreeMap ( const TreeMap< K, V, MAP, COW, OPT > *  child )

static

GetTreeMap() [2/5]

static TreeMap* GetTreeMap ( TreeMap< K, V, MAP, COW, OPT > *  child )

static

GetTreeMap() [3/5]

static const TreeMap* GetTreeMap ( const StrongCOWRef< TreeMap< K, V, MAP, COW, OPT > > *  child )

static

FindChild() [1/2]

const TreeMap* FindChild

(

const K &

key

)

const

FindChild() [2/2]

TreeMap* FindChild

(

const K &

key

)

FindEntry() [1/2]

const TreeMap* FindEntry

(

PATH &&

key

)

const

FindEntry() [2/2]

TreeMap* FindEntry

(

PATH &&

key

)

FindFirstEntryWithValue()

const TreeMap* FindFirstEntryWithValue

(

PATH &&

key

)

const

FindClosestEntryWithValue()

const TreeMap* FindClosestEntryWithValue

(

PATH &&

key

)

const

FindValue() [1/2]

Opt<const V&> FindValue

(

PATH &&

key

)

const

FindValue() [2/2]

Opt<V&> FindValue

(

PATH &&

key

)

Contains()

Bool Contains

(

PATH &&

key

)

const

Erase()

std::conditional<COW, Result<void>, ResultOk<void> >::type Erase	(	PATH &&	key,
		Bool	withChildren = false
	)

ToString()

String ToString

(

const FormatStatement *

fs = nullptr

)

const

Get() [1/3]

const OptValueType& Get

(

)

const

Get() [2/3]

OptValueType& Get

(

)

MakeValid()

V& MakeValid

(

)

SetValue() [1/2]

void SetValue

(

const V &

value

)

SetValue() [2/2]

void SetValue

(

V &&

value

)

IsRoot()

Bool IsRoot

(

)

const

IsLeaf()

Bool IsLeaf

(

)

const

GetChildren() [1/2]

const ChildrenMap& GetChildren

(

)

const

GetChildren() [2/2]

ChildrenMap& GetChildren

(

)

GetKey()

const K* GetKey

(

)

const

operator==()

Bool operator==

(

const TreeMap< K, V, MAP, COW, OPT > &

other

)

const

operator!=()

Bool operator!=

(

const TreeMap< K, V, MAP, COW, OPT > &

other

)

const

IsPopulated()

Bool IsPopulated

(

)

const

IsEmpty()

Bool IsEmpty

(

)

const

HasSameStructure()

Bool HasSameStructure

(

const TreeMap< K, V, MAP, COW, OPT > &

other

)

const

ForEachPreOrder() [1/4]

Result<Bool> ForEachPreOrder

(

OP &&

callback

)

const

ForEachPreOrder() [2/4]

Result<Bool> ForEachPreOrder	(	OP &&	callback,
		PATH &&	path = PATH()
	)		const

ForEachPreOrder() [3/4]

Result<Bool> ForEachPreOrder

(

OP &&

callback

)

ForEachPreOrder() [4/4]

Result<Bool> ForEachPreOrder	(	OP &&	callback,
		PATH &&	path = PATH()
	)

ForEachPreOrderX()

Result<void> ForEachPreOrderX	(	OP &&	callback,
		PATH &&	path = PATH()
	)

ForEachPostOrder() [1/4]

Result<Bool> ForEachPostOrder

(

OP &&

callback

)

const

ForEachPostOrder() [2/4]

Result<Bool> ForEachPostOrder	(	OP &&	callback,
		PATH &&	path = PATH()
	)		const

ForEachPostOrder() [3/4]

Result<Bool> ForEachPostOrder

(

OP &&

callback

)

ForEachPostOrder() [4/4]

Result<Bool> ForEachPostOrder	(	OP &&	callback,
		PATH &&	path = PATH()
	)

GetPath() [1/2]

Result<void> GetPath

(

PATH &

path

)

const

GetDepth()

Int GetDepth

(

)

const

GetPath() [2/2]

IndexIterator<const K&, const TreeMap, TreeMap> GetPath

(

)

const

Get() [3/3]

static const K& Get ( const TreeMap< K, V, MAP, COW, OPT > &  map, Int  index  )

static

GetTreeMap() [4/5]

static const TreeMap* GetTreeMap ( const V *  value )

static

GetTreeMap() [5/5]

static TreeMap* GetTreeMap ( V *  value )

static

Extract() [1/2]

static const V* Extract ( const V &  x )

staticprivate

Extract() [2/2]

static const V* Extract ( const Opt< V > &  x )

staticprivate

ToStringImpl()

void ToStringImpl ( String &  s, BufferedBaseArray< K, 10 > &  path, const FormatStatement *  fs  ) const

private

EraseImpl()

std::conditional<COW, Result<Bool>, ResultOk<Bool> >::type EraseImpl ( IT &  beginIt, const IT &  endIt, Bool  withChildren  )

private

Member Data Documentation

_value

OptValueType _value

private

_children

ChildrenMap _children

private