mdds
Classes | Public Types | Public Member Functions | Friends | List of all members
mdds::flat_segment_tree< _Key, _Value > Class Template Reference

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_treenode
 
typedef node::node_ptr node_ptr
 
typedef __st::nonleaf_node< flat_segment_treenonleaf_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()

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

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

◆ 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
posspecified insertion point
start_keystart value of the segment being inserted. The value is inclusive.
end_keyend value of the segment being inserted. The value is not inclusive.
valvalue 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_keystart value of the segment being inserted. The value is inclusive.
end_keyend value of the segment being inserted. The value is not inclusive.
valvalue 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_keystart value of the segment being inserted. The value is inclusive.
end_keyend value of the segment being inserted. The value is not inclusive.
valvalue 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.

◆ 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
keykey value
valuevalue associated with key specified gets stored upon successful search.
start_keypointer to a variable where the start key value of the segment that contains the key gets stored upon successful search.
end_keypointer 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
posposition from which the search should start. When the position is invalid, it falls back to the normal search.
keykey value
valuevalue associated with key specified gets stored upon successful search.
start_keypointer to a variable where the start key value of the segment that contains the key gets stored upon successful search.
end_keypointer 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
keykey value
valuevalue associated with key specified gets stored upon successful search.
start_keypointer to a variable where the start key value of the segment that contains the key gets stored upon successful search.
end_keypointer 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_keystart position of the segment being removed.
end_keyend 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
posposition where the right-shift occurs.
sizeamount of shift (must be greater than 0)
skip_start_nodeif 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.