pub struct FingerVec<T> { /* private fields */ }Expand description
Persistent vector with cheap operations at both ends.
Implementations§
Source§impl<T: Clone> FingerVec<T>
impl<T: Clone> FingerVec<T>
Sourcepub const fn new() -> Self
pub const fn new() -> Self
An empty vector. Does not allocate.
Examples found in repository?
12fn main() {
13 let n = 100_000usize;
14 let mut sink = 0usize;
15 let mut v = FingerVec::new();
16 time("push_right 100k", || {
17 for i in 0..n {
18 v = v.push_right(i);
19 }
20 });
21 let mut p = FingerVec::new();
22 time("push_left 100k", || {
23 for i in 0..n {
24 p = p.push_left(i);
25 }
26 });
27 let source: Vec<usize> = (0..n).collect();
28 let mut b = FingerVec::new();
29 time("from Vec 100k", || b = FingerVec::from(source.clone()));
30 let mut x = 1u64;
31 let idx: Vec<usize> = (0..n)
32 .map(|_| {
33 x ^= x << 13;
34 x ^= x >> 7;
35 x ^= x << 17;
36 (x as usize) % n
37 })
38 .collect();
39 time("get 100k random", || {
40 for &i in &idx {
41 sink += *b.get(i).unwrap();
42 }
43 });
44 time("iterate 100k", || {
45 for y in v.iter() {
46 sink += *y;
47 }
48 });
49 let mut r = v.clone();
50 time("drop_left until empty 100k", || {
51 while !r.is_empty() {
52 r = r.drop_left();
53 }
54 });
55 let mut u = b.clone();
56 time("assoc 100k random", || {
57 for &i in &idx {
58 u = u.assoc(i, i).unwrap();
59 }
60 });
61 let mut c = FingerVec::new();
62 time("concat acc+[x] 20k", || {
63 for i in 0..20_000 {
64 c = c.concat_with(&FingerVec::from(vec![i]));
65 }
66 });
67 let mut m = b.clone();
68 time("insert middle 20k", || {
69 for i in 0..20_000 {
70 let l = m.len();
71 m = m.insert(l / 2, i, false).unwrap();
72 }
73 });
74 println!("depths: pushed {} concat {} inserted {}", v.depth(), c.depth(), m.depth());
75 println!("sink {sink}");
76}Sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
Examples found in repository?
12fn main() {
13 let n = 100_000usize;
14 let mut sink = 0usize;
15 let mut v = FingerVec::new();
16 time("push_right 100k", || {
17 for i in 0..n {
18 v = v.push_right(i);
19 }
20 });
21 let mut p = FingerVec::new();
22 time("push_left 100k", || {
23 for i in 0..n {
24 p = p.push_left(i);
25 }
26 });
27 let source: Vec<usize> = (0..n).collect();
28 let mut b = FingerVec::new();
29 time("from Vec 100k", || b = FingerVec::from(source.clone()));
30 let mut x = 1u64;
31 let idx: Vec<usize> = (0..n)
32 .map(|_| {
33 x ^= x << 13;
34 x ^= x >> 7;
35 x ^= x << 17;
36 (x as usize) % n
37 })
38 .collect();
39 time("get 100k random", || {
40 for &i in &idx {
41 sink += *b.get(i).unwrap();
42 }
43 });
44 time("iterate 100k", || {
45 for y in v.iter() {
46 sink += *y;
47 }
48 });
49 let mut r = v.clone();
50 time("drop_left until empty 100k", || {
51 while !r.is_empty() {
52 r = r.drop_left();
53 }
54 });
55 let mut u = b.clone();
56 time("assoc 100k random", || {
57 for &i in &idx {
58 u = u.assoc(i, i).unwrap();
59 }
60 });
61 let mut c = FingerVec::new();
62 time("concat acc+[x] 20k", || {
63 for i in 0..20_000 {
64 c = c.concat_with(&FingerVec::from(vec![i]));
65 }
66 });
67 let mut m = b.clone();
68 time("insert middle 20k", || {
69 for i in 0..20_000 {
70 let l = m.len();
71 m = m.insert(l / 2, i, false).unwrap();
72 }
73 });
74 println!("depths: pushed {} concat {} inserted {}", v.depth(), c.depth(), m.depth());
75 println!("sink {sink}");
76}Sourcepub fn is_empty(&self) -> bool
pub fn is_empty(&self) -> bool
Examples found in repository?
12fn main() {
13 let n = 100_000usize;
14 let mut sink = 0usize;
15 let mut v = FingerVec::new();
16 time("push_right 100k", || {
17 for i in 0..n {
18 v = v.push_right(i);
19 }
20 });
21 let mut p = FingerVec::new();
22 time("push_left 100k", || {
23 for i in 0..n {
24 p = p.push_left(i);
25 }
26 });
27 let source: Vec<usize> = (0..n).collect();
28 let mut b = FingerVec::new();
29 time("from Vec 100k", || b = FingerVec::from(source.clone()));
30 let mut x = 1u64;
31 let idx: Vec<usize> = (0..n)
32 .map(|_| {
33 x ^= x << 13;
34 x ^= x >> 7;
35 x ^= x << 17;
36 (x as usize) % n
37 })
38 .collect();
39 time("get 100k random", || {
40 for &i in &idx {
41 sink += *b.get(i).unwrap();
42 }
43 });
44 time("iterate 100k", || {
45 for y in v.iter() {
46 sink += *y;
47 }
48 });
49 let mut r = v.clone();
50 time("drop_left until empty 100k", || {
51 while !r.is_empty() {
52 r = r.drop_left();
53 }
54 });
55 let mut u = b.clone();
56 time("assoc 100k random", || {
57 for &i in &idx {
58 u = u.assoc(i, i).unwrap();
59 }
60 });
61 let mut c = FingerVec::new();
62 time("concat acc+[x] 20k", || {
63 for i in 0..20_000 {
64 c = c.concat_with(&FingerVec::from(vec![i]));
65 }
66 });
67 let mut m = b.clone();
68 time("insert middle 20k", || {
69 for i in 0..20_000 {
70 let l = m.len();
71 m = m.insert(l / 2, i, false).unwrap();
72 }
73 });
74 println!("depths: pushed {} concat {} inserted {}", v.depth(), c.depth(), m.depth());
75 println!("sink {sink}");
76}Sourcepub fn depth(&self) -> usize
pub fn depth(&self) -> usize
Height of the middle tree, 0 when there is no tree. Useful in tests.
Examples found in repository?
12fn main() {
13 let n = 100_000usize;
14 let mut sink = 0usize;
15 let mut v = FingerVec::new();
16 time("push_right 100k", || {
17 for i in 0..n {
18 v = v.push_right(i);
19 }
20 });
21 let mut p = FingerVec::new();
22 time("push_left 100k", || {
23 for i in 0..n {
24 p = p.push_left(i);
25 }
26 });
27 let source: Vec<usize> = (0..n).collect();
28 let mut b = FingerVec::new();
29 time("from Vec 100k", || b = FingerVec::from(source.clone()));
30 let mut x = 1u64;
31 let idx: Vec<usize> = (0..n)
32 .map(|_| {
33 x ^= x << 13;
34 x ^= x >> 7;
35 x ^= x << 17;
36 (x as usize) % n
37 })
38 .collect();
39 time("get 100k random", || {
40 for &i in &idx {
41 sink += *b.get(i).unwrap();
42 }
43 });
44 time("iterate 100k", || {
45 for y in v.iter() {
46 sink += *y;
47 }
48 });
49 let mut r = v.clone();
50 time("drop_left until empty 100k", || {
51 while !r.is_empty() {
52 r = r.drop_left();
53 }
54 });
55 let mut u = b.clone();
56 time("assoc 100k random", || {
57 for &i in &idx {
58 u = u.assoc(i, i).unwrap();
59 }
60 });
61 let mut c = FingerVec::new();
62 time("concat acc+[x] 20k", || {
63 for i in 0..20_000 {
64 c = c.concat_with(&FingerVec::from(vec![i]));
65 }
66 });
67 let mut m = b.clone();
68 time("insert middle 20k", || {
69 for i in 0..20_000 {
70 let l = m.len();
71 m = m.insert(l / 2, i, false).unwrap();
72 }
73 });
74 println!("depths: pushed {} concat {} inserted {}", v.depth(), c.depth(), m.depth());
75 println!("sink {sink}");
76}Sourcepub fn get(&self, idx: usize) -> Option<&T>
pub fn get(&self, idx: usize) -> Option<&T>
Examples found in repository?
12fn main() {
13 let n = 100_000usize;
14 let mut sink = 0usize;
15 let mut v = FingerVec::new();
16 time("push_right 100k", || {
17 for i in 0..n {
18 v = v.push_right(i);
19 }
20 });
21 let mut p = FingerVec::new();
22 time("push_left 100k", || {
23 for i in 0..n {
24 p = p.push_left(i);
25 }
26 });
27 let source: Vec<usize> = (0..n).collect();
28 let mut b = FingerVec::new();
29 time("from Vec 100k", || b = FingerVec::from(source.clone()));
30 let mut x = 1u64;
31 let idx: Vec<usize> = (0..n)
32 .map(|_| {
33 x ^= x << 13;
34 x ^= x >> 7;
35 x ^= x << 17;
36 (x as usize) % n
37 })
38 .collect();
39 time("get 100k random", || {
40 for &i in &idx {
41 sink += *b.get(i).unwrap();
42 }
43 });
44 time("iterate 100k", || {
45 for y in v.iter() {
46 sink += *y;
47 }
48 });
49 let mut r = v.clone();
50 time("drop_left until empty 100k", || {
51 while !r.is_empty() {
52 r = r.drop_left();
53 }
54 });
55 let mut u = b.clone();
56 time("assoc 100k random", || {
57 for &i in &idx {
58 u = u.assoc(i, i).unwrap();
59 }
60 });
61 let mut c = FingerVec::new();
62 time("concat acc+[x] 20k", || {
63 for i in 0..20_000 {
64 c = c.concat_with(&FingerVec::from(vec![i]));
65 }
66 });
67 let mut m = b.clone();
68 time("insert middle 20k", || {
69 for i in 0..20_000 {
70 let l = m.len();
71 m = m.insert(l / 2, i, false).unwrap();
72 }
73 });
74 println!("depths: pushed {} concat {} inserted {}", v.depth(), c.depth(), m.depth());
75 println!("sink {sink}");
76}pub fn first(&self) -> Option<&T>
pub fn last(&self) -> Option<&T>
Sourcepub fn push_back_mut(&mut self, x: T)
pub fn push_back_mut(&mut self, x: T)
Append in place. Cheap when this value is not shared.
Sourcepub fn push_front_mut(&mut self, x: T)
pub fn push_front_mut(&mut self, x: T)
Prepend in place. Cheap when this value is not shared.
Sourcepub fn pop_front_mut(&mut self) -> Option<T>
pub fn pop_front_mut(&mut self) -> Option<T>
Remove the first element in place. No-op on an empty vector.
Sourcepub fn pop_back_mut(&mut self) -> Option<T>
pub fn pop_back_mut(&mut self) -> Option<T>
Remove the last element in place. No-op on an empty vector.
Sourcepub fn push_right(&self, x: T) -> Self
pub fn push_right(&self, x: T) -> Self
Examples found in repository?
12fn main() {
13 let n = 100_000usize;
14 let mut sink = 0usize;
15 let mut v = FingerVec::new();
16 time("push_right 100k", || {
17 for i in 0..n {
18 v = v.push_right(i);
19 }
20 });
21 let mut p = FingerVec::new();
22 time("push_left 100k", || {
23 for i in 0..n {
24 p = p.push_left(i);
25 }
26 });
27 let source: Vec<usize> = (0..n).collect();
28 let mut b = FingerVec::new();
29 time("from Vec 100k", || b = FingerVec::from(source.clone()));
30 let mut x = 1u64;
31 let idx: Vec<usize> = (0..n)
32 .map(|_| {
33 x ^= x << 13;
34 x ^= x >> 7;
35 x ^= x << 17;
36 (x as usize) % n
37 })
38 .collect();
39 time("get 100k random", || {
40 for &i in &idx {
41 sink += *b.get(i).unwrap();
42 }
43 });
44 time("iterate 100k", || {
45 for y in v.iter() {
46 sink += *y;
47 }
48 });
49 let mut r = v.clone();
50 time("drop_left until empty 100k", || {
51 while !r.is_empty() {
52 r = r.drop_left();
53 }
54 });
55 let mut u = b.clone();
56 time("assoc 100k random", || {
57 for &i in &idx {
58 u = u.assoc(i, i).unwrap();
59 }
60 });
61 let mut c = FingerVec::new();
62 time("concat acc+[x] 20k", || {
63 for i in 0..20_000 {
64 c = c.concat_with(&FingerVec::from(vec![i]));
65 }
66 });
67 let mut m = b.clone();
68 time("insert middle 20k", || {
69 for i in 0..20_000 {
70 let l = m.len();
71 m = m.insert(l / 2, i, false).unwrap();
72 }
73 });
74 println!("depths: pushed {} concat {} inserted {}", v.depth(), c.depth(), m.depth());
75 println!("sink {sink}");
76}Sourcepub fn push_left(&self, x: T) -> Self
pub fn push_left(&self, x: T) -> Self
Examples found in repository?
12fn main() {
13 let n = 100_000usize;
14 let mut sink = 0usize;
15 let mut v = FingerVec::new();
16 time("push_right 100k", || {
17 for i in 0..n {
18 v = v.push_right(i);
19 }
20 });
21 let mut p = FingerVec::new();
22 time("push_left 100k", || {
23 for i in 0..n {
24 p = p.push_left(i);
25 }
26 });
27 let source: Vec<usize> = (0..n).collect();
28 let mut b = FingerVec::new();
29 time("from Vec 100k", || b = FingerVec::from(source.clone()));
30 let mut x = 1u64;
31 let idx: Vec<usize> = (0..n)
32 .map(|_| {
33 x ^= x << 13;
34 x ^= x >> 7;
35 x ^= x << 17;
36 (x as usize) % n
37 })
38 .collect();
39 time("get 100k random", || {
40 for &i in &idx {
41 sink += *b.get(i).unwrap();
42 }
43 });
44 time("iterate 100k", || {
45 for y in v.iter() {
46 sink += *y;
47 }
48 });
49 let mut r = v.clone();
50 time("drop_left until empty 100k", || {
51 while !r.is_empty() {
52 r = r.drop_left();
53 }
54 });
55 let mut u = b.clone();
56 time("assoc 100k random", || {
57 for &i in &idx {
58 u = u.assoc(i, i).unwrap();
59 }
60 });
61 let mut c = FingerVec::new();
62 time("concat acc+[x] 20k", || {
63 for i in 0..20_000 {
64 c = c.concat_with(&FingerVec::from(vec![i]));
65 }
66 });
67 let mut m = b.clone();
68 time("insert middle 20k", || {
69 for i in 0..20_000 {
70 let l = m.len();
71 m = m.insert(l / 2, i, false).unwrap();
72 }
73 });
74 println!("depths: pushed {} concat {} inserted {}", v.depth(), c.depth(), m.depth());
75 println!("sink {sink}");
76}Sourcepub fn push(&self, x: T) -> Self
pub fn push(&self, x: T) -> Self
Alias of FingerVec::push_right.
Sourcepub fn append(&self, x: T) -> Self
pub fn append(&self, x: T) -> Self
Alias of FingerVec::push_right.
Sourcepub fn prepend(&self, x: T) -> Self
pub fn prepend(&self, x: T) -> Self
Alias of FingerVec::push_left.
Sourcepub fn unshift(&self, x: T) -> Self
pub fn unshift(&self, x: T) -> Self
Alias of FingerVec::push_left.
Sourcepub fn drop_left(&self) -> Self
pub fn drop_left(&self) -> Self
Without the first element. Empty stays empty.
Examples found in repository?
12fn main() {
13 let n = 100_000usize;
14 let mut sink = 0usize;
15 let mut v = FingerVec::new();
16 time("push_right 100k", || {
17 for i in 0..n {
18 v = v.push_right(i);
19 }
20 });
21 let mut p = FingerVec::new();
22 time("push_left 100k", || {
23 for i in 0..n {
24 p = p.push_left(i);
25 }
26 });
27 let source: Vec<usize> = (0..n).collect();
28 let mut b = FingerVec::new();
29 time("from Vec 100k", || b = FingerVec::from(source.clone()));
30 let mut x = 1u64;
31 let idx: Vec<usize> = (0..n)
32 .map(|_| {
33 x ^= x << 13;
34 x ^= x >> 7;
35 x ^= x << 17;
36 (x as usize) % n
37 })
38 .collect();
39 time("get 100k random", || {
40 for &i in &idx {
41 sink += *b.get(i).unwrap();
42 }
43 });
44 time("iterate 100k", || {
45 for y in v.iter() {
46 sink += *y;
47 }
48 });
49 let mut r = v.clone();
50 time("drop_left until empty 100k", || {
51 while !r.is_empty() {
52 r = r.drop_left();
53 }
54 });
55 let mut u = b.clone();
56 time("assoc 100k random", || {
57 for &i in &idx {
58 u = u.assoc(i, i).unwrap();
59 }
60 });
61 let mut c = FingerVec::new();
62 time("concat acc+[x] 20k", || {
63 for i in 0..20_000 {
64 c = c.concat_with(&FingerVec::from(vec![i]));
65 }
66 });
67 let mut m = b.clone();
68 time("insert middle 20k", || {
69 for i in 0..20_000 {
70 let l = m.len();
71 m = m.insert(l / 2, i, false).unwrap();
72 }
73 });
74 println!("depths: pushed {} concat {} inserted {}", v.depth(), c.depth(), m.depth());
75 println!("sink {sink}");
76}Sourcepub fn drop_right(&self) -> Self
pub fn drop_right(&self) -> Self
Without the last element. Empty stays empty.
pub fn rest(&self) -> Result<Self, String>
pub fn butlast(&self) -> Result<Self, String>
Sourcepub fn assoc(&self, idx: usize, item: T) -> Result<Self, String>
pub fn assoc(&self, idx: usize, item: T) -> Result<Self, String>
Replace the element at idx.
Examples found in repository?
12fn main() {
13 let n = 100_000usize;
14 let mut sink = 0usize;
15 let mut v = FingerVec::new();
16 time("push_right 100k", || {
17 for i in 0..n {
18 v = v.push_right(i);
19 }
20 });
21 let mut p = FingerVec::new();
22 time("push_left 100k", || {
23 for i in 0..n {
24 p = p.push_left(i);
25 }
26 });
27 let source: Vec<usize> = (0..n).collect();
28 let mut b = FingerVec::new();
29 time("from Vec 100k", || b = FingerVec::from(source.clone()));
30 let mut x = 1u64;
31 let idx: Vec<usize> = (0..n)
32 .map(|_| {
33 x ^= x << 13;
34 x ^= x >> 7;
35 x ^= x << 17;
36 (x as usize) % n
37 })
38 .collect();
39 time("get 100k random", || {
40 for &i in &idx {
41 sink += *b.get(i).unwrap();
42 }
43 });
44 time("iterate 100k", || {
45 for y in v.iter() {
46 sink += *y;
47 }
48 });
49 let mut r = v.clone();
50 time("drop_left until empty 100k", || {
51 while !r.is_empty() {
52 r = r.drop_left();
53 }
54 });
55 let mut u = b.clone();
56 time("assoc 100k random", || {
57 for &i in &idx {
58 u = u.assoc(i, i).unwrap();
59 }
60 });
61 let mut c = FingerVec::new();
62 time("concat acc+[x] 20k", || {
63 for i in 0..20_000 {
64 c = c.concat_with(&FingerVec::from(vec![i]));
65 }
66 });
67 let mut m = b.clone();
68 time("insert middle 20k", || {
69 for i in 0..20_000 {
70 let l = m.len();
71 m = m.insert(l / 2, i, false).unwrap();
72 }
73 });
74 println!("depths: pushed {} concat {} inserted {}", v.depth(), c.depth(), m.depth());
75 println!("sink {sink}");
76}Sourcepub fn split(&self, idx: usize) -> (Self, Self)
pub fn split(&self, idx: usize) -> (Self, Self)
Split into [0, idx) and [idx, len). An index past the end returns (self, empty).
Sourcepub fn slice(&self, start: usize, end: usize) -> Result<Self, String>
pub fn slice(&self, start: usize, end: usize) -> Result<Self, String>
Elements in [start, end).
Sourcepub fn concat_with(&self, other: &Self) -> Self
pub fn concat_with(&self, other: &Self) -> Self
Concatenate two vectors.
Examples found in repository?
12fn main() {
13 let n = 100_000usize;
14 let mut sink = 0usize;
15 let mut v = FingerVec::new();
16 time("push_right 100k", || {
17 for i in 0..n {
18 v = v.push_right(i);
19 }
20 });
21 let mut p = FingerVec::new();
22 time("push_left 100k", || {
23 for i in 0..n {
24 p = p.push_left(i);
25 }
26 });
27 let source: Vec<usize> = (0..n).collect();
28 let mut b = FingerVec::new();
29 time("from Vec 100k", || b = FingerVec::from(source.clone()));
30 let mut x = 1u64;
31 let idx: Vec<usize> = (0..n)
32 .map(|_| {
33 x ^= x << 13;
34 x ^= x >> 7;
35 x ^= x << 17;
36 (x as usize) % n
37 })
38 .collect();
39 time("get 100k random", || {
40 for &i in &idx {
41 sink += *b.get(i).unwrap();
42 }
43 });
44 time("iterate 100k", || {
45 for y in v.iter() {
46 sink += *y;
47 }
48 });
49 let mut r = v.clone();
50 time("drop_left until empty 100k", || {
51 while !r.is_empty() {
52 r = r.drop_left();
53 }
54 });
55 let mut u = b.clone();
56 time("assoc 100k random", || {
57 for &i in &idx {
58 u = u.assoc(i, i).unwrap();
59 }
60 });
61 let mut c = FingerVec::new();
62 time("concat acc+[x] 20k", || {
63 for i in 0..20_000 {
64 c = c.concat_with(&FingerVec::from(vec![i]));
65 }
66 });
67 let mut m = b.clone();
68 time("insert middle 20k", || {
69 for i in 0..20_000 {
70 let l = m.len();
71 m = m.insert(l / 2, i, false).unwrap();
72 }
73 });
74 println!("depths: pushed {} concat {} inserted {}", v.depth(), c.depth(), m.depth());
75 println!("sink {sink}");
76}Sourcepub fn insert(&self, idx: usize, item: T, after: bool) -> Result<Self, String>
pub fn insert(&self, idx: usize, item: T, after: bool) -> Result<Self, String>
Insert item so it ends up at idx (after == false) or idx + 1 (after == true).
Examples found in repository?
12fn main() {
13 let n = 100_000usize;
14 let mut sink = 0usize;
15 let mut v = FingerVec::new();
16 time("push_right 100k", || {
17 for i in 0..n {
18 v = v.push_right(i);
19 }
20 });
21 let mut p = FingerVec::new();
22 time("push_left 100k", || {
23 for i in 0..n {
24 p = p.push_left(i);
25 }
26 });
27 let source: Vec<usize> = (0..n).collect();
28 let mut b = FingerVec::new();
29 time("from Vec 100k", || b = FingerVec::from(source.clone()));
30 let mut x = 1u64;
31 let idx: Vec<usize> = (0..n)
32 .map(|_| {
33 x ^= x << 13;
34 x ^= x >> 7;
35 x ^= x << 17;
36 (x as usize) % n
37 })
38 .collect();
39 time("get 100k random", || {
40 for &i in &idx {
41 sink += *b.get(i).unwrap();
42 }
43 });
44 time("iterate 100k", || {
45 for y in v.iter() {
46 sink += *y;
47 }
48 });
49 let mut r = v.clone();
50 time("drop_left until empty 100k", || {
51 while !r.is_empty() {
52 r = r.drop_left();
53 }
54 });
55 let mut u = b.clone();
56 time("assoc 100k random", || {
57 for &i in &idx {
58 u = u.assoc(i, i).unwrap();
59 }
60 });
61 let mut c = FingerVec::new();
62 time("concat acc+[x] 20k", || {
63 for i in 0..20_000 {
64 c = c.concat_with(&FingerVec::from(vec![i]));
65 }
66 });
67 let mut m = b.clone();
68 time("insert middle 20k", || {
69 for i in 0..20_000 {
70 let l = m.len();
71 m = m.insert(l / 2, i, false).unwrap();
72 }
73 });
74 println!("depths: pushed {} concat {} inserted {}", v.depth(), c.depth(), m.depth());
75 println!("sink {sink}");
76}pub fn assoc_before(&self, idx: usize, item: T) -> Result<Self, String>
pub fn assoc_after(&self, idx: usize, item: T) -> Result<Self, String>
pub fn reverse(&self) -> Self
pub fn map<V: Clone>(&self, f: impl FnMut(&T) -> V) -> FingerVec<V>
pub fn to_vec(&self) -> Vec<T>
Sourcepub fn traverse_chunks<'a>(&'a self, f: &mut dyn FnMut(&'a [T]))
pub fn traverse_chunks<'a>(&'a self, f: &mut dyn FnMut(&'a [T]))
Visit the elements chunk by chunk.
pub fn traverse(&self, f: &mut dyn FnMut(&T))
Sourcepub fn traverse_result<S>(
&self,
f: &mut dyn FnMut(&T) -> Result<(), S>,
) -> Result<(), S>
pub fn traverse_result<S>( &self, f: &mut dyn FnMut(&T) -> Result<(), S>, ) -> Result<(), S>
Visit elements, returning the first error.
pub fn find_index(&self, f: impl Fn(&T) -> bool) -> Option<usize>
Sourcepub fn iter(&self) -> Iter<'_, T> ⓘ
pub fn iter(&self) -> Iter<'_, T> ⓘ
Examples found in repository?
12fn main() {
13 let n = 100_000usize;
14 let mut sink = 0usize;
15 let mut v = FingerVec::new();
16 time("push_right 100k", || {
17 for i in 0..n {
18 v = v.push_right(i);
19 }
20 });
21 let mut p = FingerVec::new();
22 time("push_left 100k", || {
23 for i in 0..n {
24 p = p.push_left(i);
25 }
26 });
27 let source: Vec<usize> = (0..n).collect();
28 let mut b = FingerVec::new();
29 time("from Vec 100k", || b = FingerVec::from(source.clone()));
30 let mut x = 1u64;
31 let idx: Vec<usize> = (0..n)
32 .map(|_| {
33 x ^= x << 13;
34 x ^= x >> 7;
35 x ^= x << 17;
36 (x as usize) % n
37 })
38 .collect();
39 time("get 100k random", || {
40 for &i in &idx {
41 sink += *b.get(i).unwrap();
42 }
43 });
44 time("iterate 100k", || {
45 for y in v.iter() {
46 sink += *y;
47 }
48 });
49 let mut r = v.clone();
50 time("drop_left until empty 100k", || {
51 while !r.is_empty() {
52 r = r.drop_left();
53 }
54 });
55 let mut u = b.clone();
56 time("assoc 100k random", || {
57 for &i in &idx {
58 u = u.assoc(i, i).unwrap();
59 }
60 });
61 let mut c = FingerVec::new();
62 time("concat acc+[x] 20k", || {
63 for i in 0..20_000 {
64 c = c.concat_with(&FingerVec::from(vec![i]));
65 }
66 });
67 let mut m = b.clone();
68 time("insert middle 20k", || {
69 for i in 0..20_000 {
70 let l = m.len();
71 m = m.insert(l / 2, i, false).unwrap();
72 }
73 });
74 println!("depths: pushed {} concat {} inserted {}", v.depth(), c.depth(), m.depth());
75 println!("sink {sink}");
76}Sourcepub fn check_structure(&self) -> Result<(), String>
pub fn check_structure(&self) -> Result<(), String>
Check internal invariants. Intended for tests.
Trait Implementations§
impl<T: Clone + Eq> Eq for FingerVec<T>
Source§impl<T: Clone> FromIterator<T> for FingerVec<T>
impl<T: Clone> FromIterator<T> for FingerVec<T>
Source§fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self
Source§impl<T: Clone + Hash> Hash for FingerVec<T>
Hashes the length and the elements, the same as [T].
impl<T: Clone + Hash> Hash for FingerVec<T>
Hashes the length and the elements, the same as [T].
Source§impl<'a, T: Clone> IntoIterator for &'a FingerVec<T>
impl<'a, T: Clone> IntoIterator for &'a FingerVec<T>
Source§impl<T: Clone + Ord> Ord for FingerVec<T>
Lexicographic order, the same as Vec<T>.
impl<T: Clone + Ord> Ord for FingerVec<T>
Lexicographic order, the same as Vec<T>.