Classes
class	const_iterator

class	const_reverse_iterator

struct	dispose_handler

struct	fill_nonleaf_value_handler

struct	init_handler

struct	leaf_value_type

struct	nonleaf_value_type

Public Types
typedef _Key	key_type

typedef _Value	value_type

typedef size_t	size_type

typedef __st::node< flat_segment_tree >	node

typedef node::node_ptr	node_ptr

typedef __st::nonleaf_node< flat_segment_tree >	nonleaf_node

using	const_segment_iterator = mdds::__fst::const_segment_iterator< flat_segment_tree >

Public Member Functions
const_iterator	begin () const

const_iterator	end () const

const_reverse_iterator	rbegin () const

const_reverse_iterator	rend () const

const_segment_iterator	begin_segment () const

const_segment_iterator	end_segment () const

	flat_segment_tree (key_type min_val, key_type max_val, value_type init_val)

	flat_segment_tree (const flat_segment_tree< key_type, value_type > &r)

flat_segment_tree< key_type, value_type > &	operator= (const flat_segment_tree< key_type, value_type > &other)

void	swap (flat_segment_tree< key_type, value_type > &other)

void	clear ()

std::pair< const_iterator, bool >	insert_front (key_type start_key, key_type end_key, value_type val)

std::pair< const_iterator, bool >	insert_back (key_type start_key, key_type end_key, value_type val)

std::pair< const_iterator, bool >	insert (const const_iterator &pos, key_type start_key, key_type end_key, value_type val)

void	shift_left (key_type start_key, key_type end_key)

void	shift_right (key_type pos, key_type size, bool skip_start_node)

std::pair< const_iterator, bool >	search (key_type key, value_type &value, key_type start_key=nullptr, key_type end_key=nullptr) const

std::pair< const_iterator, bool >	search (const const_iterator &pos, key_type key, value_type &value, key_type start_key=nullptr, key_type end_key=nullptr) const

std::pair< const_iterator, bool >	search_tree (key_type key, value_type &value, key_type start_key=nullptr, key_type end_key=nullptr) const

void	build_tree ()

bool	is_tree_valid () const

bool	operator== (const flat_segment_tree< key_type, value_type > &r) const

bool	operator!= (const flat_segment_tree< key_type, value_type > &r) const

key_type	min_key () const

key_type	max_key () const

value_type	default_value () const

size_type	leaf_size () const

Friends
struct	::mdds::__fst::itr_forward_handler< flat_segment_tree >

struct	::mdds::__fst::itr_reverse_handler< flat_segment_tree >

Constructor & Destructor Documentation

◆ flat_segment_tree() [1/2]

template<typename _Key, typename _Value>

mdds::flat_segment_tree< _Key, _Value >::flat_segment_tree	(	key_type	min_val,
		key_type	max_val,
		value_type	init_val
	)

Constructor that takes minimum and maximum keys and the value to be used for the initial segment.

Parameters

min_val	minimum allowed key value for the entire series of segments.
max_val	maximum allowed key value for the entires series of segments.
init_val	value to be used for the initial segment. This value will also be used for empty segments.

◆ flat_segment_tree() [2/2]

template<typename _Key, typename _Value>

mdds::flat_segment_tree< _Key, _Value >::flat_segment_tree ( const flat_segment_tree< key_type, value_type > & r )

Copy constructor only copies the leaf nodes.

Member Function Documentation

◆ begin()

template<typename _Key, typename _Value>

const_iterator mdds::flat_segment_tree< _Key, _Value >::begin ( ) const

inline

Return an iterator that points to the first leaf node that correspondes with the start position of the first segment.

Returns: immutable iterator that points to the first leaf node that corresponds with the start position of the first segment.

◆ begin_segment()

template<typename _Key, typename _Value>

const_segment_iterator mdds::flat_segment_tree< _Key, _Value >::begin_segment ( ) const

Return an immutable iterator that points to the first segment stored in the tree. It iterates through the segments one segment at a time. Each iterator value consists of start, end, and value members that correspond with the start and end positions of a segment and the value of that segment, respectively.

Returns: immutable iterator that points to the first segment stored in the tree.

◆ build_tree()

template<typename _Key, typename _Value>

void mdds::flat_segment_tree< _Key, _Value >::build_tree ( )

Build a tree of non-leaf nodes based on the values stored in the leaf nodes. The tree must be valid before you can call the search_tree() method.

◆ clear()

template<typename _Key, typename _Value>

void mdds::flat_segment_tree< _Key, _Value >::clear ( )

Remove all stored segments except for the initial segment. The minimum and maximum keys and the default value will be retained after the call returns. This call will also remove the tree.

◆ end()

template<typename _Key, typename _Value>

const_iterator mdds::flat_segment_tree< _Key, _Value >::end ( ) const

inline

Return an iterator that points to the position past the last leaf node that corresponds with the end position of the last segment.

Returns: immutable iterator that points to the position past last leaf node that corresponds with the end position of the last segment.

◆ end_segment()

template<typename _Key, typename _Value>

const_segment_iterator mdds::flat_segment_tree< _Key, _Value >::end_segment ( ) const

Return an immutable iterator that points to the position past the last segment stored in the tree. It iterates through the segments one segment at a time. Each iterator value consists of start, end, and value members that correspond with the start and end positions of a segment and the value of that segment, respectively.

Returns: immutable iterator that points to the position past the last segment stored in the tree.

◆ insert()

template<typename _Key, typename _Value>

std::pair<const_iterator, bool> mdds::flat_segment_tree< _Key, _Value >::insert	(	const const_iterator &	pos,
		key_type	start_key,
		key_type	end_key,
		value_type	val
	)

Insert a new segment into the tree at or after specified point of insertion.

Parameters

pos	specified insertion point
start_key	start value of the segment being inserted. The value is inclusive.
end_key	end value of the segment being inserted. The value is not inclusive.
val	value associated with this segment.

Returns: pair of const_iterator corresponding to the start position of the inserted segment, and a boolean value indicating whether or not the insertion has modified the tree.

◆ insert_back()

template<typename _Key, typename _Value>

std::pair<const_iterator, bool> mdds::flat_segment_tree< _Key, _Value >::insert_back	(	key_type	start_key,
		key_type	end_key,
		value_type	val
	)

inline

Insert a new segment into the tree. Unlike the insert_front() counterpart, this method searches for the point of insertion from the last leaf node toward the first.

Parameters

start_key	start value of the segment being inserted. The value is inclusive.
end_key	end value of the segment being inserted. The value is not inclusive.
val	value associated with this segment.

Returns: pair of const_iterator corresponding to the start position of the inserted segment, and a boolean value indicating whether or not the insertion has modified the tree.

◆ insert_front()

template<typename _Key, typename _Value>

std::pair<const_iterator, bool> mdds::flat_segment_tree< _Key, _Value >::insert_front	(	key_type	start_key,
		key_type	end_key,
		value_type	val
	)

inline

Insert a new segment into the tree. It searches for the point of insertion from the first leaf node.

Parameters

start_key	start value of the segment being inserted. The value is inclusive.
end_key	end value of the segment being inserted. The value is not inclusive.
val	value associated with this segment.

Returns: pair of const_iterator corresponding to the start position of the inserted segment, and a boolean value indicating whether or not the insertion has modified the tree.

◆ is_tree_valid()

template<typename _Key, typename _Value>

bool mdds::flat_segment_tree< _Key, _Value >::is_tree_valid ( ) const

inline

Returns: true if the tree is valid, otherwise false. The tree must be valid before you can call the search_tree() method.

◆ leaf_size()

template<typename _Key, typename _Value>

size_type mdds::flat_segment_tree< _Key, _Value >::leaf_size ( ) const

Return the number of leaf nodes.

Returns: number of leaf nodes.

◆ operator=()

template<typename _Key, typename _Value>

flat_segment_tree<key_type, value_type>& mdds::flat_segment_tree< _Key, _Value >::operator= ( const flat_segment_tree< key_type, value_type > & other )

Assignment only copies the leaf nodes.

◆ operator==()

template<typename _Key, typename _Value>

bool mdds::flat_segment_tree< _Key, _Value >::operator== ( const flat_segment_tree< key_type, value_type > & r ) const

Equality between two flat_segment_tree instances is evaluated by comparing the keys and the values of the leaf nodes only. Neither the non-leaf nodes nor the validity of the tree is evaluated.

◆ rbegin()

template<typename _Key, typename _Value>

const_reverse_iterator mdds::flat_segment_tree< _Key, _Value >::rbegin ( ) const

inline

Return an iterator that points to the last leaf node that correspondes with the end position of the last segment. This iterator moves in the reverse direction of a normal iterator.

Returns: immutable reverse iterator that points to the last leaf node that corresponds with the end position of the last segment.

◆ rend()

template<typename _Key, typename _Value>

const_reverse_iterator mdds::flat_segment_tree< _Key, _Value >::rend ( ) const

inline

Return an iterator that points to the position past the first leaf node that corresponds with the start position of the first segment. This iterator moves in the reverse direction of a normal iterator.

Returns: immutable reverse iterator that points to the position past first leaf node that corresponds with the start position of the first segment.

◆ search() [1/2]

template<typename _Key, typename _Value>

std::pair<const_iterator, bool> mdds::flat_segment_tree< _Key, _Value >::search	(	key_type	key,
		value_type &	value,
		key_type *	start_key = `nullptr`,
		key_type *	end_key = `nullptr`
	)		const

Perform leaf-node search for a value associated with a key.

Parameters

key	key value
value	value associated with key specified gets stored upon successful search.
start_key	pointer to a variable where the start key value of the segment that contains the key gets stored upon successful search.
end_key	pointer to a varaible where the end key value of the segment that contains the key gets stored upon successful search.

Returns: a pair of const_iterator corresponding to the start position of the segment containing the key, and a boolean value indicating whether or not the search has been successful.

◆ search() [2/2]

template<typename _Key, typename _Value>

std::pair<const_iterator, bool> mdds::flat_segment_tree< _Key, _Value >::search	(	const const_iterator &	pos,
		key_type	key,
		value_type &	value,
		key_type *	start_key = `nullptr`,
		key_type *	end_key = `nullptr`
	)		const

Perform leaf-node search for a value associated with a key.

Parameters

pos	position from which the search should start. When the position is invalid, it falls back to the normal search.
key	key value
value	value associated with key specified gets stored upon successful search.
start_key	pointer to a variable where the start key value of the segment that contains the key gets stored upon successful search.
end_key	pointer to a varaible where the end key value of the segment that contains the key gets stored upon successful search.

Returns: a pair of const_iterator corresponding to the start position of the segment containing the key, and a boolean value indicating whether or not the search has been successful.

◆ search_tree()

template<typename _Key, typename _Value>

std::pair<const_iterator, bool> mdds::flat_segment_tree< _Key, _Value >::search_tree	(	key_type	key,
		value_type &	value,
		key_type *	start_key = `nullptr`,
		key_type *	end_key = `nullptr`
	)		const

Perform tree search for a value associated with a key. This method assumes that the tree is valid. Call is_tree_valid() to find out whether the tree is valid, and build_tree() to build a new tree in case it's not.

Parameters

key	key value
value	value associated with key specified gets stored upon successful search.
start_key	pointer to a variable where the start key value of the segment that contains the key gets stored upon successful search.
end_key	pointer to a varaible where the end key value of the segment that contains the key gets stored upon successful search.

Returns: a pair of const_iterator corresponding to the start position of the segment containing the key, and a boolean value indicating whether or not the search has been successful.

◆ shift_left()

template<typename _Key, typename _Value>

void mdds::flat_segment_tree< _Key, _Value >::shift_left	(	key_type	start_key,
		key_type	end_key
	)

Remove a segment specified by the start and end key values, and shift the remaining segments (i.e. those segments that come after the removed segment) to left. Note that the start and end positions of the segment being removed must be within the base segment span.

Parameters

start_key	start position of the segment being removed.
end_key	end position of the segment being removed.

◆ shift_right()

template<typename _Key, typename _Value>

void mdds::flat_segment_tree< _Key, _Value >::shift_right	(	key_type	pos,
		key_type	size,
		bool	skip_start_node
	)

Shift all segments that occur at or after the specified start position to right by the size specified.

Parameters

pos	position where the right-shift occurs.
size	amount of shift (must be greater than 0)
skip_start_node	if true, and the specified position is at an existing node position, that node will not be shifted. This argument has no effect if the position specified does not coincide with any of the existing nodes.

◆ swap()

template<typename _Key, typename _Value>

void mdds::flat_segment_tree< _Key, _Value >::swap ( flat_segment_tree< key_type, value_type > & other )

Swap the content of the tree with another instance.

Parameters

other instance of flat_segment_tree to swap content with.

Classes

Public Types

Public Member Functions

Friends

Constructor & Destructor Documentation

◆ flat_segment_tree() [1/2]

◆ flat_segment_tree() [2/2]

Member Function Documentation

◆ begin()

◆ begin_segment()

◆ build_tree()

◆ clear()

◆ end()

◆ end_segment()

◆ insert()

◆ insert_back()

◆ insert_front()

◆ is_tree_valid()

◆ leaf_size()

◆ operator=()

◆ operator==()

◆ rbegin()

◆ rend()

◆ search() [1/2]

◆ search() [2/2]

◆ search_tree()

◆ shift_left()

◆ shift_right()

◆ swap()