Trait grove::data::Data [−][src]
pub trait Data {
type Value: ToSummary<Self::Summary>;
type Summary: Copy + Default + Add<Output = Self::Summary>;
type Action: Action + Acts<Self::Value> + Acts<Self::Summary>;
}
Expand description
This trait represents the data that will be stored inside the tree.
Every node in the tree will contain an action to be performed on the node’s subtree,
a summary of the node’s subtree, and a value.
The action will be of type Self::Action
, the summary of type Self::Summary
, and the value will be of type Self::Value
.
-
Self::Value
is the type of values in your tree, which can be anything at all. The tree representes a sequence of values of typeSelf::Value
. -
Self::Summary
can include: indices, sizes, sums, maximums and minimums of subtrees, and more. It is the type of information you can gather about a subsegment of your tree. This is the result of querying for information about a segment. -
Self::Action
is the type of actions that can be performed on subsegments. for example, reverse a subsegment, add a constant to all values in a subsegment, applymax
with a constant on all values in a subsegment, and so on.
All of the trait’s requirements are modeled as separated traits in order to allow for easier mixing and matching of different values, summaries and actions.
For convenience, (Value, Summary Action)
implements the Data
trait by itself
if the types are compatible, so you don’t need to create a new market type if you don’t want to.
Requirements
In order for everything to work, we must know how to:
- Compose actions together:
Action composition is done by an
Add
instance. i.e., applyinga + b
should be equivalent to applyingb
and then applyinga
. Composition is right to left. What chronologically happens first, is on the right.
- Compute the summary of a single value, and add up summaries of two subsegments together:
Summaries of segments are created by converting single values into their singletone. summaries using
to_summary()
, and summaries can be added together to obtain bigger summaries, using anAdd
instance. i.e., if the summary for a listvals_list1
issummary1
, and the summary for a listvals_list2
issummary2
, the summary of the concatenationvals_list1 + vals_list2
should besummary1 + summary2
.
- Apply an action on a single value, and apply an action on a summary of a segment:
Applying actions on values and on summaries is required by the bounds
Self::Action
:
Acts
<
Self::Value
> +
Acts
<
Self::Summary
>
. This means that in order to update a segment summarysummary:
Self::Summary
after actionaction:
Self::Action
has been applied to it, you could executesummary = action.act(summary);
oraction.act_inplace(&mut summary);
, and similarly as well forSelf::Value
.
Additional requirements:
- Decide whether to reverse the subsegment it is acted upon. This is done by implementing the
Action::to_reverse()
function. If you do not want to reverse segments, you can use the default implementation, which always returns false. - Have an identity action and empty summary: These are represented by the bounds
Self::Action
:
Default
,Self::Summary
:
Default
. - Test actions for being the identity. This is represented by
Action::is_identity()
.
Rules
In order for the segment trees to work correctly, all of these operations must play nicely with each other.
Most of the rules are imposed in the documentation of the Action
trait. In addition, any instance must
obey these rules:
- Summary addition must be associative, so that we get the same summary regardless of the tree structure,
and the empty summary must be the identity.
(summary1 + summary2) + summary3 === summary1 + (summary2 + summary3) default() + summary === summary + default() === summary
Associated Types
The summaries of values over segments. When querying a segment,
you get a summary of the segment, represented by a value of type Self::Summary
.
Implementations on Foreign Types
A Data
implementation for a generic triplet of value, summary and action types,
so you don’t have to make an impl
yourself.