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

pub trait Action: Copy + Default + Add<Output = Self> {
    fn is_identity(self) -> bool;

    fn to_reverse(self) -> bool { ... }
}
Expand description

Trait representing actions. this entailes having an identity action (Default), being able to compose actions (Add<Output=Self>), checking whether an action is the identity action, and checking whether this action reverses subsegments. In order for the segment trees to work correctly, all of the operations must play nicely with each other. In particular, it must obey these rules:

Rules

  • composition of actions: action composition must be associative, and the identity action should actually be the identity.
    (action3 + action2) + action1 === action3 + (action2 + action1)
default() + action === action + default() === action

If the action implements Acts<Summary> for some type Summary or Value:

  • 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

  • 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’ a cross version instead:

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

    And it should also satisfy that composing two actions xor’s their Action::to_reverse() results:

    (action2 + action1).to_reverse() === action2.to_reverse() ^ action1.to_reverse()

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

    action.act(value).to_summary() === action.act(value.to_summary())

Required methods

Test whether this action is the identity action.

Provided methods

This function should be implemented if you want to be able to reverse subsegments of your tree. The default implementation always returns false.

This function should return whether this action reverses the segment it is applied to.

Implementors