Aleph::SegmentTreePolicy Concept Reference

Policy concept for lazy segment tree. More...

#include <tpl_segment_tree.H>

Concept definition

template<typename P>
concept Aleph::SegmentTreePolicy = 
      std::equality_comparable<typename P::lazy_type> and
      requires(const P& p,
               const typename P::value_type& v1,
               const typename P::value_type& v2,
               const typename P::lazy_type& lz1,
               const typename P::lazy_type& lz2,
               size_t count)
        {
          typename P::value_type;
          typename P::lazy_type;
          { p.combine(v1, v2) } -> std::convertible_to<typename P::value_type>;
          { p.apply(v1, lz1, count) } -> std::convertible_to<typename P::value_type>;
          { p.compose(lz1, lz2) } -> std::convertible_to<typename P::lazy_type>;
          { p.value_identity() } -> std::convertible_to<typename P::value_type>;
          { p.lazy_identity() } -> std::convertible_to<typename P::lazy_type>;
        }

Detailed Description

Policy concept for lazy segment tree.

This concept describes the interface required by Gen_Lazy_Segment_Tree<Policy>.

A policy must provide:

• value_type — the type stored in tree nodes.
• lazy_type — the type of pending lazy tags.
• combine(a, b) -> value_type — merge two node values.
• apply(val, lazy, count) -> value_type — apply a lazy tag to a node value covering count leaves.
• compose(old_lazy, new_lazy) -> lazy_type — compose two lazy tags (new on top of old).
• value_identity() -> value_type — identity for combine.
• lazy_identity() -> lazy_type — identity for compose (no-op tag).

Additionally, lazy_type must be equality-comparable so that push_down can test lazy(node) == pol.lazy_identity() to skip propagation when no tag is pending.

Note

Correctness requires combine to be associative and consistent with apply and compose.

Definition at line 695 of file tpl_segment_tree.H.