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::Summarycan 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::Actionis the type of actions that can be performed on subsegments. for example, reverse a subsegment, add a constant to all values in a subsegment, apply
maxwith 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.
(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.
In order for everything to work, we must know how to:
- Compose actions together:
Action composition is done by an
Addinstance. i.e., applying
a + bshould be equivalent to applying
band then applying
a. 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 an
Addinstance. i.e., if the summary for a list
summary1, and the summary for a list
summary2, the summary of the concatenation
vals_list1 + vals_list2should be
summary1 + 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
>. This means that in order to update a segment summary
Self::Actionhas been applied to it, you could execute
summary = action.act(summary);or
action.act_inplace(&mut summary);, and similarly as well for
- 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
- Test actions for being the identity. This is represented by
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
The values that reside in trees.
The summaries of values over segments. When querying a segment,
you get a summary of the segment, represented by a value of type
The actions you can perform on the values
Data implementation for a generic triplet of value, summary and action types,
so you don’t have to make an