Trait grove::data::Data[−][src]

pub trait Data {
    type Value;
    type Summary: Copy + Default + Add<Output = Self::Summary>;
    type Action: Action + Acts<Self::Value> + Acts<Self::Summary>;
    fn to_summary(val: &Self::Value) -> 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.

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.

  • composition of actions: action composition must be associative, and the identity action should actually be the identity.

    (action3 + action2) + action1 === action3 + (action2 + action1)
default() + summary === action + default() === action

  • Action composition must actually be action composition, and the identity must actually be the identity.

    (action2 + action1).act(value) == action2.act(action1.act(value))
(action2 + action1).act(summary) == action2.act(action1.act(summary))
default().act(value) === value
default().act(summary) === summary

  • 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() + action === summary + default() === summary

  • Adding up summaries and then applying an action must be equal to applying the action separately and then summing the parts:

    action.act(summary1 + summary2) == action.act(summary1) + action.act(summary2)

    This property is used so that the summary values can be updated without updating the whole tree. This means that the action respects the monoid structure of the summaries. If the action reverses segments, (i.e, if D::to_reverse(action) == true), then it has to satisfy a ‘cross’ version instead:

    action.act(summary1 + summary2) == action.act(summary2) + action.act(summary1)

  • The action should respect Self::to_summary():

    D::to_summary(&action.act(value)) === action.act(D::to_summary(&value))

  • If the action can reverse segments, it should also satisfy that composing two actions xor’s their Action::to_reverse() results:

    D::to_reverse(action2 + action1) === D::to_reverse(action2) ^ D::to_reverse(action1)

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

Required methods

Creates the summary of a single value.

Implementors