#include <Fw/DataStructures/RedBlackTreeSetOrMapImpl.hpp>

Classes
class	ConstIterator
	Const iterator. More...

class	Node
	Node. More...

Public Types
using	Color = typename Node::Color
	The color type. More...

using	Direction = typename Node::Direction
	The direction type. More...

using	Entry = typename Node::Entry
	The entry type. More...

using	Index = typename Node::Index
	The node index type. More...

using	Nodes = ExternalArray< Node >
	The type of the array for storing the tree nodes. More...

using	FreeNodes = ExternalStack< Index >
	The type of the stack of indices of free nodes. More...

Public Member Functions
	RedBlackTreeSetOrMapImpl ()=default
	Zero-argument constructor. More...

	RedBlackTreeSetOrMapImpl (Node nodes, Index freeNodes, FwSizeType capacity)

	RedBlackTreeSetOrMapImpl (ByteArray data, FwSizeType capacity)

	RedBlackTreeSetOrMapImpl (const RedBlackTreeSetOrMapImpl< KE, VN > &impl)
	Copy constructor. More...

	~RedBlackTreeSetOrMapImpl ()=default
	Destructor. More...

RedBlackTreeSetOrMapImpl< KE, VN > &	operator= (const RedBlackTreeSetOrMapImpl< KE, VN > &impl)
	operator= More...

ConstIterator	begin () const
	Get the begin iterator. More...

void	clear ()
	Clear the set or map. More...

ConstIterator	end () const
	Get the end iterator. More...

Success	find (const KE &keyOrElement, VN &valueOrNil) const

FwSizeType	getCapacity () const

FwSizeType	getSize () const

Success	insert (const KE &keyOrElement, const VN &valueOrNil)

Success	remove (const KE &keyOrElement, VN &valueOrNil)

void	setStorage (Node nodes, Index freeNodes, FwSizeType capacity)

void	setStorage (ByteArray data, FwSizeType capacity)

Static Public Member Functions
static constexpr U8	getByteArrayAlignment ()

static constexpr FwSizeType	getByteArraySize (FwSizeType capacity)

Friends
template<typename KK , typename VV >
class	RedBlackTreeSetOrMapImplTester

Detailed Description

template<typename KE, typename VN>
class Fw::RedBlackTreeSetOrMapImpl< KE, VN >

This class template implements a red-black tree that can be used as a set or map. A red-black tree is a binary search tree (BST) such that each node is colored red or black. A red-black tree is valid if

It satisfies the red child invariant: No red node has a red child.
It satisfies the black height invariant (described below).

The black height invariant of a red-black tree T is checked with respect to the leaf-augmented tree T'. T' is constructed from T by replacing every "missing" node in T (i.e., every place where there could be a child but is not) with a new black node. The black height invariant says that for every node N in T', every path from N to a leaf in T' goes through the same number of black nodes.

A valid red-black tree is balanced, in the sense that the find operation takes O(log n) steps.

Definition at line 39 of file RedBlackTreeSetOrMapImpl.hpp.

Member Typedef Documentation

◆ Color

template<typename KE, typename VN>

using Fw::RedBlackTreeSetOrMapImpl< KE, VN >::Color = typename Node::Color

The color type.

Definition at line 120 of file RedBlackTreeSetOrMapImpl.hpp.

◆ Direction

template<typename KE, typename VN>

using Fw::RedBlackTreeSetOrMapImpl< KE, VN >::Direction = typename Node::Direction

The direction type.

Definition at line 123 of file RedBlackTreeSetOrMapImpl.hpp.

◆ Entry

template<typename KE, typename VN>

using Fw::RedBlackTreeSetOrMapImpl< KE, VN >::Entry = typename Node::Entry

The entry type.

Definition at line 126 of file RedBlackTreeSetOrMapImpl.hpp.

◆ FreeNodes

template<typename KE, typename VN>

using Fw::RedBlackTreeSetOrMapImpl< KE, VN >::FreeNodes = ExternalStack<Index>

The type of the stack of indices of free nodes.

Definition at line 135 of file RedBlackTreeSetOrMapImpl.hpp.

◆ Index

template<typename KE, typename VN>

using Fw::RedBlackTreeSetOrMapImpl< KE, VN >::Index = typename Node::Index

The node index type.

Definition at line 129 of file RedBlackTreeSetOrMapImpl.hpp.

◆ Nodes

template<typename KE, typename VN>

using Fw::RedBlackTreeSetOrMapImpl< KE, VN >::Nodes = ExternalArray<Node>

The type of the array for storing the tree nodes.

Definition at line 132 of file RedBlackTreeSetOrMapImpl.hpp.

Constructor & Destructor Documentation

◆ RedBlackTreeSetOrMapImpl() [1/4]

template<typename KE, typename VN>

Fw::RedBlackTreeSetOrMapImpl< KE, VN >::RedBlackTreeSetOrMapImpl ( )

default

Zero-argument constructor.

◆ RedBlackTreeSetOrMapImpl() [2/4]

template<typename KE, typename VN>

Fw::RedBlackTreeSetOrMapImpl< KE, VN >::RedBlackTreeSetOrMapImpl	(	Node *	nodes,
		Index *	freeNodes,
		FwSizeType	capacity
	)

inline

Constructor providing typed backing storage. nodes must point to at least capacity elements of type Node. freeNodes must point to at least capacity elements of type FwSizeType.

Parameters

nodes	The nodes
freeNodes	The free nodes
capacity	The capacity

Definition at line 248 of file RedBlackTreeSetOrMapImpl.hpp.

◆ RedBlackTreeSetOrMapImpl() [3/4]

template<typename KE, typename VN>

Fw::RedBlackTreeSetOrMapImpl< KE, VN >::RedBlackTreeSetOrMapImpl	(	ByteArray	data,
		FwSizeType	capacity
	)

inline

Constructor providing untyped backing storage. data must be aligned according to getByteArrayAlignment(). data must contain at least getByteArraySize(capacity) bytes.

Parameters

data	The data
capacity	The capacity

Definition at line 258 of file RedBlackTreeSetOrMapImpl.hpp.

◆ RedBlackTreeSetOrMapImpl() [4/4]

template<typename KE, typename VN>

Fw::RedBlackTreeSetOrMapImpl< KE, VN >::RedBlackTreeSetOrMapImpl ( const RedBlackTreeSetOrMapImpl< KE, VN > & impl )

inline

Copy constructor.

Definition at line 265 of file RedBlackTreeSetOrMapImpl.hpp.

◆ ~RedBlackTreeSetOrMapImpl()

template<typename KE, typename VN>

Fw::RedBlackTreeSetOrMapImpl< KE, VN >::~RedBlackTreeSetOrMapImpl ( )

default

Destructor.

Member Function Documentation

◆ begin()

template<typename KE, typename VN>

ConstIterator Fw::RedBlackTreeSetOrMapImpl< KE, VN >::begin ( ) const

inline

Get the begin iterator.

Definition at line 286 of file RedBlackTreeSetOrMapImpl.hpp.

◆ clear()

template<typename KE, typename VN>

void Fw::RedBlackTreeSetOrMapImpl< KE, VN >::clear ( )

inline

Clear the set or map.

Definition at line 289 of file RedBlackTreeSetOrMapImpl.hpp.

◆ end()

template<typename KE, typename VN>

ConstIterator Fw::RedBlackTreeSetOrMapImpl< KE, VN >::end ( ) const

inline

Get the end iterator.

Definition at line 303 of file RedBlackTreeSetOrMapImpl.hpp.

◆ find()

template<typename KE, typename VN>

Success Fw::RedBlackTreeSetOrMapImpl< KE, VN >::find	(	const KE &	keyOrElement,
		VN &	valueOrNil
	)		const

inline

Find a value associated with a key in the map or an element in a set

Returns: SUCCESS if the item was found

Parameters

keyOrElement	The key or element
valueOrNil	The value or Nil

Definition at line 311 of file RedBlackTreeSetOrMapImpl.hpp.

◆ getByteArrayAlignment()

template<typename KE, typename VN>

static constexpr U8 Fw::RedBlackTreeSetOrMapImpl< KE, VN >::getByteArrayAlignment ( )

inlinestatic

Get the alignment of the storage for a RedBlackTreeSetOrMapImpl

Returns: The alignment

Definition at line 423 of file RedBlackTreeSetOrMapImpl.hpp.

◆ getByteArraySize()

template<typename KE, typename VN>

static constexpr FwSizeType Fw::RedBlackTreeSetOrMapImpl< KE, VN >::getByteArraySize ( FwSizeType capacity )

inlinestatic

Get the size of the storage for an ExternalArray of the specified capacity, as a byte array

Returns: The byte array size

Parameters

capacity The capacity

Definition at line 428 of file RedBlackTreeSetOrMapImpl.hpp.

◆ getCapacity()

template<typename KE, typename VN>

FwSizeType Fw::RedBlackTreeSetOrMapImpl< KE, VN >::getCapacity ( ) const

inline

Get the capacity of the set or map (max number of entries)

Returns: The capacity

Definition at line 325 of file RedBlackTreeSetOrMapImpl.hpp.

◆ getSize()

template<typename KE, typename VN>

FwSizeType Fw::RedBlackTreeSetOrMapImpl< KE, VN >::getSize ( ) const

inline

Get the size (number of entries)

Returns: The size

Definition at line 329 of file RedBlackTreeSetOrMapImpl.hpp.

◆ insert()

template<typename KE, typename VN>

Success Fw::RedBlackTreeSetOrMapImpl< KE, VN >::insert	(	const KE &	keyOrElement,
		const VN &	valueOrNil
	)

inline

Insert an element in the set or a (key, value) pair in the map

Returns: SUCCESS if there is room in the set or map

Parameters

keyOrElement	The key or element
valueOrNil	The value or Nil

Definition at line 339 of file RedBlackTreeSetOrMapImpl.hpp.

◆ operator=()

template<typename KE, typename VN>

RedBlackTreeSetOrMapImpl<KE, VN>& Fw::RedBlackTreeSetOrMapImpl< KE, VN >::operator= ( const RedBlackTreeSetOrMapImpl< KE, VN > & impl )

inline

operator=

Definition at line 276 of file RedBlackTreeSetOrMapImpl.hpp.

◆ remove()

template<typename KE, typename VN>

Success Fw::RedBlackTreeSetOrMapImpl< KE, VN >::remove	(	const KE &	keyOrElement,
		VN &	valueOrNil
	)

inline

Remove an element from the set or a (key, value) pair from the map

Returns: SUCCESS if the key or element was there

Parameters

keyOrElement	The key or element
valueOrNil	The value or Nil

Definition at line 364 of file RedBlackTreeSetOrMapImpl.hpp.

◆ setStorage() [1/2]

template<typename KE, typename VN>

void Fw::RedBlackTreeSetOrMapImpl< KE, VN >::setStorage	(	Node *	nodes,
		Index *	freeNodes,
		FwSizeType	capacity
	)

inline

Set the backing storage (typed data) nodes must point to at least capacity elements of type Node. freeNodes must point to at least capacity elements of type FwSizeType.

Parameters

nodes	The nodes
freeNodes	The free nodes
capacity	The capacity

Definition at line 383 of file RedBlackTreeSetOrMapImpl.hpp.

◆ setStorage() [2/2]

template<typename KE, typename VN>

void Fw::RedBlackTreeSetOrMapImpl< KE, VN >::setStorage	(	ByteArray	data,
		FwSizeType	capacity
	)

inline

Set the backing storage (untyped data) data must be aligned according to getByteArrayAlignment(). data must contain at least getByteArraySize(capacity) bytes.

Parameters

data	The data
capacity	The capacity

Definition at line 395 of file RedBlackTreeSetOrMapImpl.hpp.

Friends And Related Function Documentation

◆ RedBlackTreeSetOrMapImplTester

template<typename KE, typename VN>

template<typename KK , typename VV >

friend class RedBlackTreeSetOrMapImplTester

friend

Definition at line 45 of file RedBlackTreeSetOrMapImpl.hpp.

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

Fw/DataStructures/RedBlackTreeSetOrMapImpl.hpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

template<typename KE, typename VN> class Fw::RedBlackTreeSetOrMapImpl< KE, VN >

Member Typedef Documentation

◆ Color

◆ Direction

◆ Entry

◆ FreeNodes

◆ Index

◆ Nodes

Constructor & Destructor Documentation

◆ RedBlackTreeSetOrMapImpl() [1/4]

◆ RedBlackTreeSetOrMapImpl() [2/4]

◆ RedBlackTreeSetOrMapImpl() [3/4]

◆ RedBlackTreeSetOrMapImpl() [4/4]

◆ ~RedBlackTreeSetOrMapImpl()

Member Function Documentation

◆ begin()

◆ clear()

◆ end()

◆ find()

◆ getByteArrayAlignment()

◆ getByteArraySize()

◆ getCapacity()

◆ getSize()

◆ insert()

◆ operator=()

◆ remove()

◆ setStorage() [1/2]

◆ setStorage() [2/2]

Friends And Related Function Documentation

◆ RedBlackTreeSetOrMapImplTester

template<typename KE, typename VN>
class Fw::RedBlackTreeSetOrMapImpl< KE, VN >