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
128
129
130
131
132
133
134

//! # orx-fixed-vec
//!
//! An efficient fixed capacity vector with pinned elements.
//!
//! ## A. Motivation
//!
//! There might be various situations where pinned elements are helpful.
//!
//! * It is somehow required for async code, following [blog](https://blog.cloudflare.com/pin-and-unpin-in-rust) could be useful for the interested.
//! * It is crucial in representing self-referential types with thin references.
//!
//! This crate focuses more on the latter. Particularly, it aims to make it safe and convenient to build **performant self-referential collections** such as linked lists, trees or graphs. See [`PinnedVec`](https://crates.io/crates/orx-pinned-vec) for complete documentation on the motivation.
//!
//! `FixedVec` is one of the pinned vec implementations which can be wrapped by an [`ImpVec`](https://crates.io/crates/orx-imp-vec) and allow building self referential collections.
//!
//! ## B. Comparison with `SplitVec`
//!
//! [`SplitVec`](https://crates.io/crates/orx-split-vec) is another `PinnedVec` implementation aiming the same goal but with different features. You may see the comparison in the table below.
//!
//! | **`FixedVec`**                                                               | **`SplitVec`**                                                                   |
//! |------------------------------------------------------------------------------|----------------------------------------------------------------------------------|
//! | Implements `PinnedVec` => can be wrapped by an `ImpVec`.                     | Implements `PinnedVec` => can be wrapped by an `ImpVec`.                         |
//! | Requires exact capacity to be known while creating.                          | Can be created with any level of prior information about required capacity.      |
//! | Cannot grow beyond capacity; panics when `push` is called at capacity.       | Can grow dynamically. Further, it provides control on how it must grow. |
//! | It is just a wrapper around `std::vec::Vec`; hence, has equivalent performance. | Performance-optimized built-in growth strategies also have `std::vec::Vec` equivalent performance. |
//!
//! After the performance optimizations on the `SplitVec`, it is now comparable to `std::vec::Vec` in terms of performance. This might make `SplitVec` a dominating choice over `FixedVec`.
//!
//! ## C. Examples
//!
//! ### C.1. Usage similar to `std::vec::Vec`
//!
//! Most common `std::vec::Vec` operations are available in `FixedVec` with the same signature.
//!
//! ```rust
//! use orx_fixed_vec::prelude::*;
//!
//! // capacity is not optional
//! let mut vec = FixedVec::new(4);
//!
//! assert_eq!(4, vec.capacity());
//!
//! vec.push(0);
//! assert!(!vec.is_full());
//! assert_eq!(3, vec.room());
//!
//! vec.extend_from_slice(&[1, 2, 3]);
//! assert_eq!(vec, &[0, 1, 2, 3]);
//! assert!(vec.is_full());
//!
//! // vec.push(42); // push would've panicked when vec.is_full()
//!
//! vec[0] = 10;
//! assert_eq!(10, vec[0]);
//!
//! vec.remove(0);
//! vec.insert(0, 0);
//!
//! assert_eq!(6, vec.iter().sum());
//!
//! assert_eq!(vec.clone(), vec);
//!
//! let stdvec: Vec<_> = vec.into();
//! assert_eq!(&stdvec, &[0, 1, 2, 3]);
//! ```
//!
//!
//! ### C.2. Pinned Elements
//!
//! Unless elements are removed from the vector, the memory location of an element priorly pushed to the `FixedVec` <ins>never</ins> changes. This guarantee is utilized by `ImpVec` in enabling immutable growth to build self referential collections.
//!
//! ```rust
//! use orx_fixed_vec::prelude::*;
//!
//! let mut vec = FixedVec::new(100);
//!
//! // push the first element
//! vec.push(42usize);
//! assert_eq!(vec, &[42]);
//!
//! // let's get a pointer to the first element
//! let addr42 = &vec[0] as *const usize;
//!
//! // let's push 99 new elements
//! for i in 1..100 {
//!     vec.push(i);
//! }
//!
//! for i in 0..100 {
//!     assert_eq!(if i == 0 { 42 } else { i }, vec[i]);
//! }
//!
//! // the memory location of the first element remains intact
//! assert_eq!(addr42, &vec[0] as *const usize);
//!
//! // we can safely dereference it and read the correct value
//! // the method is still unsafe for FixedVec
//! // but the undelrying guarantee will be used by ImpVec
//! assert_eq!(unsafe { *addr42 }, 42);
//!
//! // the next push when `vec.is_full()` panics!
//! // vec.push(0);
//! ```
//!
//! ## E. Benchmarks
//!
//! Recall that the motivation of using a split vector is to get benefit of the pinned elements, rather than to be used in place of the standard vector which is highly efficient. The aim of the benchmarks is to make sure that the performance gap is kept within acceptable and constant limits.
//!
//! Since `FixedVec` is just a wrapper around the `std::vec::Vec` with additional guarantees on pinned elements; it is expected to have equivalent performance. This is verified by the benchmarks which can be found at the at [benches](https://github.com/orxfun/orx-fixed-vec/blob/main/benches) folder.
//!
//!
//! ## License
//!
//! This library is licensed under MIT license. See LICENSE for details.

#![warn(
    missing_docs,
    clippy::unwrap_in_result,
    clippy::unwrap_used,
    clippy::panic,
    clippy::panic_in_result_fn,
    clippy::float_cmp,
    clippy::float_cmp_const,
    clippy::missing_panics_doc,
    clippy::todo
)]

mod common_traits;
mod fixed_vec;
mod pinned_vec;
/// Common relevant traits, structs, enums.
pub mod prelude;

pub use fixed_vec::FixedVec;