1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
use std::borrow::Borrow;
use canonical::{Canon, Store};
use crate::annotation::{Annotated, Annotation, Cardinality};
use crate::branch::{Branch, Step, Walk};
use crate::branch_mut::{BranchMut, StepMut, WalkMut};
pub enum Child<'a, C, S>
where
C: Compound<S>,
S: Store,
{
Leaf(&'a C::Leaf),
Node(&'a Annotated<C, S>),
EndOfNode,
}
pub enum ChildMut<'a, C, S>
where
C: Compound<S>,
S: Store,
{
Leaf(&'a mut C::Leaf),
Node(&'a mut Annotated<C, S>),
EndOfNode,
}
pub trait Compound<S>
where
Self: Canon<S>,
S: Store,
{
type Leaf;
type Annotation: Canon<S> + Annotation<Self::Leaf> + Clone + Sized;
fn child(&self, ofs: usize) -> Child<Self, S>;
fn child_mut(&mut self, ofs: usize) -> ChildMut<Self, S>;
fn annotation(&self) -> Self::Annotation {
let mut ann = Self::Annotation::identity();
for i in 0.. {
match self.child(i) {
Child::Leaf(l) => ann = ann.op(&Self::Annotation::from_leaf(l)),
Child::Node(c) => ann = ann.op(c.annotation()),
Child::EndOfNode => return ann,
}
}
unreachable!()
}
}
pub trait Nth<'a, S>
where
Self: Compound<S> + Sized,
S: Store,
{
fn nth(&'a self, n: u64) -> Result<Option<Branch<'a, Self, S>>, S::Error>;
fn nth_mut(
&'a mut self,
n: u64,
) -> Result<Option<BranchMut<'a, Self, S>>, S::Error>;
}
impl<'a, C, S> Nth<'a, S> for C
where
C: Compound<S>,
C::Annotation: Borrow<Cardinality>,
S: Store,
{
fn nth(
&'a self,
mut index: u64,
) -> Result<Option<Branch<'a, Self, S>>, S::Error> {
Branch::walk(self, |f| match f {
Walk::Leaf(l) => {
if index == 0 {
Step::Found(l)
} else {
index -= 1;
Step::Next
}
}
Walk::Node(n) => {
let &Cardinality(card) = n.annotation().borrow();
if card <= index {
index -= card;
Step::Next
} else {
Step::Into(n)
}
}
})
}
fn nth_mut(
&'a mut self,
mut index: u64,
) -> Result<Option<BranchMut<'a, Self, S>>, S::Error> {
BranchMut::walk(self, |f| match f {
WalkMut::Leaf(l) => {
if index == 0 {
StepMut::Found(l)
} else {
index -= 1;
StepMut::Next
}
}
WalkMut::Node(n) => {
let &Cardinality(card) = n.annotation().borrow();
if card <= index {
index -= card;
StepMut::Next
} else {
StepMut::Into(n)
}
}
})
}
}