Loading...
Searching...
No Matches
mdds::flat_segment_tree< Key, Value > Class Template Reference

## Classes

struct | nonleaf_value_type
struct | leaf_value_type
class | const_iterator
class | const_reverse_iterator
class | const_segment_range_type

## Public Types

typedef Key | key_type
typedef Value | value_type
typedef size_t | size_type
using | node = st::detail::node<key_type, leaf_value_type>
using | node_ptr = typename node::node_ptr
using | nonleaf_node = st::detail::nonleaf_node<key_type, nonleaf_value_type>
using | const_segment_iterator = mdds::fst::detail::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
const_segment_range_type | segment_range () const
| flat_segment_tree (key_type min_val, key_type max_val, value_type init_val)
| flat_segment_tree (const flat_segment_tree &r)
| flat_segment_tree (flat_segment_tree &&other) noexcept(nothrow_move_constructible_v)
flat_segment_tree< Key, Value > & | operator= (const flat_segment_tree &other)
flat_segment_tree< Key, Value > & | operator= (flat_segment_tree &&other) noexcept(nothrow_move_assignable_v)
void | swap (flat_segment_tree &other) noexcept(nothrow_swappable_v)
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_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_iterator pos, key_type key, value_type &value, key_type *start_key=nullptr, key_type *end_key=nullptr) const
const_iterator | search (key_type key) const
const_iterator | search (const_iterator pos, key_type key) 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
const_iterator | search_tree (key_type key) const
void | build_tree ()
bool | valid_tree () const noexcept
bool | is_tree_valid () const noexcept
bool | operator== (const flat_segment_tree &other) const noexcept(nothrow_eq_comparable_v)
bool | operator!= (const flat_segment_tree &other) const noexcept(nothrow_eq_comparable_v)
const key_type & | min_key () const noexcept
const key_type & | max_key () const noexcept
const value_type & | default_value () const noexcept
size_type | leaf_size () const noexcept(noexcept(st::detail::count_leaf_nodes< size_type >(m_left_leaf.get(), m_right_leaf.get())))

## Friends

struct | ::mdds::fst::detail::forward_itr_handler< flat_segment_tree >
struct | ::mdds::fst::detail::reverse_itr_handler< flat_segment_tree >

## Constructor & Destructor Documentation

## flat_segment_tree() [1/3]

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/3]

template<typename Key, typename Value>

mdds::flat_segment_tree< Key, Value >::flat_segment_tree | ( | const flat_segment_tree< Key, Value > & | r | ) |

Copy constructor only copies the leaf nodes.

## flat_segment_tree() [3/3]

template<typename Key, typename Value>

mdds::flat_segment_tree< Key, Value >::flat_segment_tree | ( | flat_segment_tree< Key, Value > && | other | ) | const

noexcept

Move constructor.

Warning
  The source instance will not be usable after the move construction.

## 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 corresponds 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_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 noexcept

Deprecated
  Use valid_tree() instead.

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

inline noexcept

Return the number of leaf nodes.

Returns
  number of leaf nodes.

## operator=() [1/2]

template<typename Key, typename Value>

flat_segment_tree< Key, Value > & mdds::flat_segment_tree< Key, Value >::operator= | ( | const flat_segment_tree< Key, Value > & | other | ) |

Copy assignment operator.

Parameters

  other | Source instance to copy from.

Note
  It only copies the leaf nodes.

## operator=() [2/2]

template<typename Key, typename Value>

flat_segment_tree< Key, Value > & mdds::flat_segment_tree< Key, Value >::operator= | ( | flat_segment_tree< Key, Value > && | other | ) |

noexcept

Move assignment operator.

Parameters

  other | Source instance to move from.

## operator==()

template<typename Key, typename Value>

bool mdds::flat_segment_tree< Key, Value >::operator== | ( | const flat_segment_tree< Key, Value > & | other | ) | const

noexcept

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 corresponds 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/4]

template<typename Key, typename Value>

const_iterator mdds::flat_segment_tree< Key, Value >::search | ( | const_iterator | pos,
|  | key_type | key ) const

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

Parameters

  pos | Position from which the search should start if valid. In case of an invalid position, it falls back to a search starting with the first position.
  key | Key value to perform search for.

Returns
  Iterator position associated with the start position of the segment containing the key, or end iterator position if the search has failed.

## search() [2/4]

template<typename Key, typename Value>

std::pair< const_iterator, bool > mdds::flat_segment_tree< Key, Value >::search | ( | 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 variable 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() [3/4]

template<typename Key, typename Value>

const_iterator mdds::flat_segment_tree< Key, Value >::search | ( | key_type | key | ) | const

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

Parameters

  key | Key value to perform search for.

Returns
  Iterator position associated with the start position of the segment containing the key, or end iterator position upon search failure.

## search() [4/4]

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 variable 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() [1/2]

template<typename Key, typename Value>

const_iterator mdds::flat_segment_tree< Key, Value >::search_tree | ( | key_type | key | ) | const

Perform tree search for a value associated with a key. The tree must be valid before performing the search, else the search will fail.

Parameters

  key | Key value to perform search for.

Returns
  Iterator position associated with the start position of the segment containing the key, or end iterator position if the search has failed.

## search_tree() [2/2]

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 variable 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.

## segment_range()

template<typename Key, typename Value>

const_segment_range_type mdds::flat_segment_tree< Key, Value >::segment_range | ( |  | ) | const

Return a range object that provides a begin iterator and an end sentinel.

## 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, Value > & | other | ) |

noexcept

Swap the content of the tree with another instance.

Parameters

  other | instance of flat_segment_tree to swap content with.

## valid_tree()

template<typename Key, typename Value>

bool mdds::flat_segment_tree< Key, Value >::valid_tree | ( |  | ) | const

inline noexcept

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