Skip to main content

FingerVec

Struct FingerVec 

Source
pub struct FingerVec<T> { /* private fields */ }
Expand description

Persistent vector with cheap operations at both ends.

Implementations§

Source§

impl<T: Clone> FingerVec<T>

Source

pub const fn new() -> Self

An empty vector. Does not allocate.

Examples found in repository?
examples/bench.rs (line 15)
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}
Source

pub fn len(&self) -> usize

Examples found in repository?
examples/bench.rs (line 70)
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}
Source

pub fn is_empty(&self) -> bool

Examples found in repository?
examples/bench.rs (line 51)
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}
Source

pub fn depth(&self) -> usize

Height of the middle tree, 0 when there is no tree. Useful in tests.

Examples found in repository?
examples/bench.rs (line 74)
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}
Source

pub fn get(&self, idx: usize) -> Option<&T>

Examples found in repository?
examples/bench.rs (line 41)
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}
Source

pub fn first(&self) -> Option<&T>

Source

pub fn last(&self) -> Option<&T>

Source

pub fn push_back_mut(&mut self, x: T)

Append in place. Cheap when this value is not shared.

Source

pub fn push_front_mut(&mut self, x: T)

Prepend in place. Cheap when this value is not shared.

Source

pub fn pop_front_mut(&mut self) -> Option<T>

Remove the first element in place. No-op on an empty vector.

Source

pub fn pop_back_mut(&mut self) -> Option<T>

Remove the last element in place. No-op on an empty vector.

Source

pub fn push_right(&self, x: T) -> Self

Examples found in repository?
examples/bench.rs (line 18)
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}
Source

pub fn push_left(&self, x: T) -> Self

Examples found in repository?
examples/bench.rs (line 24)
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}
Source

pub fn push(&self, x: T) -> Self

Source

pub fn append(&self, x: T) -> Self

Source

pub fn prepend(&self, x: T) -> Self

Source

pub fn unshift(&self, x: T) -> Self

Source

pub fn drop_left(&self) -> Self

Without the first element. Empty stays empty.

Examples found in repository?
examples/bench.rs (line 52)
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}
Source

pub fn drop_right(&self) -> Self

Without the last element. Empty stays empty.

Source

pub fn rest(&self) -> Result<Self, String>

Source

pub fn butlast(&self) -> Result<Self, String>

Source

pub fn assoc(&self, idx: usize, item: T) -> Result<Self, String>

Replace the element at idx.

Examples found in repository?
examples/bench.rs (line 58)
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}
Source

pub fn split(&self, idx: usize) -> (Self, Self)

Split into [0, idx) and [idx, len). An index past the end returns (self, empty).

Source

pub fn slice(&self, start: usize, end: usize) -> Result<Self, String>

Elements in [start, end).

Source

pub fn skip(&self, n: usize) -> Result<Self, String>

Without the first n elements.

Source

pub fn take(&self, n: usize) -> Result<Self, String>

The first n elements.

Source

pub fn concat_with(&self, other: &Self) -> Self

Concatenate two vectors.

Examples found in repository?
examples/bench.rs (line 64)
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}
Source

pub fn concat(raw: &[Self]) -> Self

Concatenate many vectors.

Source

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?
examples/bench.rs (line 71)
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}
Source

pub fn assoc_before(&self, idx: usize, item: T) -> Result<Self, String>

Source

pub fn assoc_after(&self, idx: usize, item: T) -> Result<Self, String>

Source

pub fn dissoc(&self, idx: usize) -> Result<Self, String>

Remove the element at idx.

Source

pub fn reverse(&self) -> Self

Source

pub fn map<V: Clone>(&self, f: impl FnMut(&T) -> V) -> FingerVec<V>

Source

pub fn to_vec(&self) -> Vec<T>

Source

pub fn traverse_chunks<'a>(&'a self, f: &mut dyn FnMut(&'a [T]))

Visit the elements chunk by chunk.

Source

pub fn traverse(&self, f: &mut dyn FnMut(&T))

Source

pub fn traverse_result<S>( &self, f: &mut dyn FnMut(&T) -> Result<(), S>, ) -> Result<(), S>

Visit elements, returning the first error.

Source

pub fn find_index(&self, f: impl Fn(&T) -> bool) -> Option<usize>

Source

pub fn iter(&self) -> Iter<'_, T> ⓘ

Examples found in repository?
examples/bench.rs (line 45)
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}
Source

pub fn check_structure(&self) -> Result<(), String>

Check internal invariants. Intended for tests.

Source§

impl<T: Clone + PartialEq> FingerVec<T>

Source

pub fn index_of(&self, item: &T) -> Option<usize>

Source

pub fn last_index_of(&self, item: &T) -> Option<usize>

Source§

impl<T: Clone + Display> FingerVec<T>

Source

pub fn format_inline(&self) -> String

Debug view of the layout: {front} tree {back}.

Trait Implementations§

Source§

impl<T> Clone for FingerVec<T>

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl<T: Debug> Debug for FingerVec<T>

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl<T: Clone> Default for FingerVec<T>

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

impl<T: Clone + Display> Display for FingerVec<T>

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl<T: Clone + Eq> Eq for FingerVec<T>

Source§

impl<T: Clone> From<&Vec<T>> for FingerVec<T>

Source§

fn from(xs: &Vec<T>) -> Self

Converts to this type from the input type.
Source§

impl<T: Clone, const N: usize> From<&[T; N]> for FingerVec<T>

Source§

fn from(xs: &[T; N]) -> Self

Converts to this type from the input type.
Source§

impl<T: Clone> From<&[T]> for FingerVec<T>

Source§

fn from(xs: &[T]) -> Self

Converts to this type from the input type.
Source§

impl<T: Clone> From<Vec<T>> for FingerVec<T>

Source§

fn from(xs: Vec<T>) -> Self

Converts to this type from the input type.
Source§

impl<T: Clone> FromIterator<T> for FingerVec<T>

Source§

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator. Read more
Source§

impl<T: Clone + Hash> Hash for FingerVec<T>

Hashes the length and the elements, the same as [T].

Source§

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher. Read more
1.3.0 · Source§

fn hash_slice<H>(data: &[Self], state: &mut H)
where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher. Read more
Source§

impl<T: Clone> Index<usize> for FingerVec<T>

Source§

type Output = T

The returned type after indexing.
Source§

fn index(&self, idx: usize) -> &T

Performs the indexing (container[index]) operation. Read more
Source§

impl<'a, T: Clone> IntoIterator for &'a FingerVec<T>

Source§

type Item = &'a T

The type of the elements being iterated over.
Source§

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?
Source§

fn into_iter(self) -> Iter<'a, T> ⓘ

Creates an iterator from a value. Read more
Source§

impl<T: Clone + Ord> Ord for FingerVec<T>

Lexicographic order, the same as Vec<T>.

Source§

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other. Read more
1.21.0 (const: unstable) · Source§

fn max(self, other: Self) -> Self
where Self: Sized,

Compares and returns the maximum of two values. Read more
1.21.0 (const: unstable) · Source§

fn min(self, other: Self) -> Self
where Self: Sized,

Compares and returns the minimum of two values. Read more
1.50.0 (const: unstable) · Source§

fn clamp(self, min: Self, max: Self) -> Self
where Self: Sized,

Restrict a value to a certain interval. Read more
Source§

fn clamp_to<R>(self, range: R) -> Self
where Self: Sized, R: ClampBounds<Self>,

🔬This is a nightly-only experimental API. (clamp_to)
Restrict a value to a certain range. Read more
Source§

impl<T: Clone + PartialEq> PartialEq for FingerVec<T>

Source§

fn eq(&self, other: &Self) -> bool

Equality operator ==. Read more
1.0.0 (const: unstable) · Source§

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=. Read more
Source§

impl<T: Clone + PartialOrd> PartialOrd for FingerVec<T>

Source§

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists. Read more
1.0.0 (const: unstable) · Source§

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator. Read more
1.0.0 (const: unstable) · Source§

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator. Read more
1.0.0 (const: unstable) · Source§

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator. Read more
1.0.0 (const: unstable) · Source§

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator. Read more

Auto Trait Implementations§

§

impl<T> Freeze for FingerVec<T>
where Buf<T>: Freeze, Option<Tree<T>>: Freeze,

§

impl<T> RefUnwindSafe for FingerVec<T>
where Buf<T>: RefUnwindSafe, Option<Tree<T>>: RefUnwindSafe,

§

impl<T> Send for FingerVec<T>
where Buf<T>: Send, Option<Tree<T>>: Send,

§

impl<T> Sync for FingerVec<T>
where Buf<T>: Sync, Option<Tree<T>>: Sync,

§

impl<T> Unpin for FingerVec<T>
where Buf<T>: Unpin, Option<Tree<T>>: Unpin,

§

impl<T> UnsafeUnpin for FingerVec<T>
where Buf<T>: UnsafeUnpin, Option<Tree<T>>: UnsafeUnpin,

§

impl<T> UnwindSafe for FingerVec<T>
where Buf<T>: UnwindSafe, Option<Tree<T>>: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T> ToString for T
where T: Display + ?Sized,

Source§

fn to_string(&self) -> String

Converts the given value to a String. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.