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 type Self::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, apply max 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., applying a + b should be equivalent to applying b and 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 Add instance. i.e., if the summary for a list vals_list1 is summary1, and the summary for a list vals_list2 is summary2, the summary of the concatenation vals_list1 + vals_list2 should 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 Self::Action: Acts<Self::Value> + Acts<Self::Summary>. This means that in order to update a segment summary summary: Self::Summary after action action: Self::Action has been applied to it, you could execute summary = action.act(summary); or action.act_inplace(&mut summary);, and similarly as well for Self::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 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 Self::Summary.

The actions you can perform on the values

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.

Implementors