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
fn is_identity(self) -> bool
fn is_identity(self) -> bool
Test whether this action is the identity action.
Provided methods
fn to_reverse(self) -> bool
fn to_reverse(self) -> bool
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.