toad_array/
lib.rs

1//! This microcrate contains the `Array` trait used by the
2//! [`toad`](https://github.com/toad-lib/toad) CoAP runtime / ecosystem.
3//!
4//! The `Array` trait defines common operations used with heap-allocated
5//! collections like [`Vec`](https://doc.rust-lang.org/std/vec/struct.Vec.html) but
6//! is also implemented for [`tinyvec::ArrayVec`](https://docs.rs/tinyvec/latest) allowing
7//! for applications to be usable on platforms with or without heap allocation.
8
9// docs
10#![doc(html_root_url = "https://docs.rs/toad-array/0.1.0")]
11#![cfg_attr(any(docsrs, feature = "docs"), feature(doc_cfg))]
12// -
13// style
14#![allow(clippy::unused_unit)]
15// -
16// deny
17#![deny(missing_docs)]
18#![deny(missing_debug_implementations)]
19#![deny(missing_copy_implementations)]
20#![cfg_attr(not(test), deny(unsafe_code))]
21// -
22// warnings
23#![cfg_attr(not(test), warn(unreachable_pub))]
24// -
25// features
26#![cfg_attr(not(feature = "std"), no_std)]
27
28#[cfg(feature = "alloc")]
29extern crate alloc as std_alloc;
30
31use core::ops::{Deref, DerefMut};
32
33#[cfg(feature = "alloc")]
34use std_alloc::vec::Vec;
35use toad_len::Len;
36
37/// Operations on ordered indexed collections
38pub trait Indexed<T>
39  where Self: Len + Deref<Target = [T]>
40{
41  /// Insert a new element at `ix`, shifting all other elements to the right.
42  ///
43  /// ```
44  /// use toad_array::Indexed;
45  ///
46  /// fn do_stuff<I: Indexed<u32> + AsRef<Vec<u32>>>(mut i: I) {
47  ///   i.insert(0, 2);
48  ///   assert_eq!(i.as_ref(), &vec![2]);
49  ///
50  ///   i.insert(0, 1);
51  ///   assert_eq!(i.as_ref(), &vec![1, 2]);
52  ///
53  ///   i.insert(2, 3);
54  ///   assert_eq!(i.as_ref(), &vec![1, 2, 3]);
55  /// }
56  ///
57  /// do_stuff(vec![]);
58  /// ```
59  fn insert(&mut self, ix: usize, t: T);
60
61  /// Remove element at `ix`, shifting all other elements to the left.
62  ///
63  /// ```
64  /// use toad_array::Indexed;
65  ///
66  /// fn do_stuff<I: Indexed<u32> + AsRef<Vec<u32>>>(mut i: I) {
67  ///   i.remove(1);
68  ///   assert_eq!(i.as_ref(), &vec![1]);
69  ///
70  ///   i.remove(0);
71  ///   assert_eq!(i.as_ref(), &vec![]);
72  ///
73  ///   i.remove(0);
74  ///   assert_eq!(i.as_ref(), &vec![]);
75  /// }
76  ///
77  /// do_stuff(vec![1, 2]);
78  /// ```
79  fn remove(&mut self, ix: usize) -> Option<T>;
80
81  /// Insert an element at the front of the collection
82  ///
83  /// ```
84  /// use toad_array::Indexed;
85  ///
86  /// fn do_stuff<I: Indexed<u32> + AsRef<Vec<u32>>>(mut i: I) {
87  ///   i.push(3);
88  ///   assert_eq!(i.as_ref(), &vec![3]);
89  ///
90  ///   i.push(2);
91  ///   assert_eq!(i.as_ref(), &vec![2, 3]);
92  ///
93  ///   i.push(1);
94  ///   assert_eq!(i.as_ref(), &vec![1, 2, 3]);
95  /// }
96  ///
97  /// do_stuff(vec![]);
98  /// ```
99  fn push(&mut self, t: T) {
100    self.insert(0, t)
101  }
102
103  /// Insert an element at the end of the collection
104  ///
105  /// ```
106  /// use toad_array::Indexed;
107  ///
108  /// fn do_stuff<I: Indexed<u32> + AsRef<Vec<u32>>>(mut i: I) {
109  ///   i.append(3);
110  ///   assert_eq!(i.as_ref(), &vec![3]);
111  ///
112  ///   i.append(2);
113  ///   assert_eq!(i.as_ref(), &vec![3, 2]);
114  ///
115  ///   i.append(1);
116  ///   assert_eq!(i.as_ref(), &vec![3, 2, 1]);
117  /// }
118  ///
119  /// do_stuff(vec![]);
120  /// ```
121  fn append(&mut self, t: T) {
122    self.insert(self.len(), t)
123  }
124
125  /// Drop `ct` elements from the front of the collection
126  ///
127  /// ```
128  /// use toad_array::Indexed;
129  ///
130  /// let mut v: Vec<u32> = vec![1, 2, 3, 4];
131  ///
132  /// v.drop_front(2);
133  /// assert_eq!(v, vec![3, 4]);
134  ///
135  /// v.drop_front(3);
136  /// assert_eq!(v, vec![]);
137  ///
138  /// v.drop_front(1);
139  /// assert_eq!(v, vec![]);
140  /// ```
141  fn drop_front(&mut self, ct: usize) {
142    if !self.is_empty() && ct > 0 {
143      self.remove(0);
144      self.drop_front(ct - 1);
145    }
146  }
147
148  /// Drop `ct` elements from the back of the collection
149  ///
150  /// ```
151  /// use toad_array::Indexed;
152  ///
153  /// let mut v: Vec<u32> = vec![1, 2, 3, 4];
154  ///
155  /// v.drop_back(2);
156  /// assert_eq!(v, vec![1, 2]);
157  ///
158  /// v.drop_back(2);
159  /// assert_eq!(v, vec![]);
160  ///
161  /// v.drop_back(1);
162  /// assert_eq!(v, vec![]);
163  /// ```
164  fn drop_back(&mut self, ct: usize) {
165    if !self.is_empty() && ct > 0 {
166      self.remove(self.len() - 1);
167      self.drop_back(ct - 1);
168    }
169  }
170
171  /// Drop elements from the front of the collection until
172  /// the collection is emptied or the predicate returns
173  /// false.
174  ///
175  /// ```
176  /// use toad_array::Indexed;
177  ///
178  /// let mut v: Vec<u32> = vec![2, 4, 6, 5];
179  ///
180  /// v.drop_while(|n| n % 2 == 0);
181  /// assert_eq!(v, vec![5]);
182  /// ```
183  fn drop_while<F>(&mut self, f: F)
184    where F: for<'a> Fn(&'a T) -> bool
185  {
186    match self.get(0) {
187      | Some(t) if !f(&t) => return,
188      | None => return,
189      | _ => (),
190    };
191
192    self.remove(0);
193    self.drop_while(f);
194  }
195}
196
197/// Create a data structure and reserve some amount of space for it to grow into
198///
199/// # Examples
200/// - `Vec` is `Reserve`, and invokes `Vec::with_capacity`
201/// - `tinyvec::ArrayVec` is `Reserve` and invokes `Default::default()` because creating an `ArrayVec` automatically allocates the required space on the stack.
202pub trait Reserve
203  where Self: Default
204{
205  /// Create an instance of the collection with a given capacity.
206  ///
207  /// Used to reserve some contiguous space, e.g. [`Vec::with_capacity`]
208  ///
209  /// The default implementation invokes `Default::default`
210  fn reserve(_: usize) -> Self {
211    Default::default()
212  }
213}
214
215/// Truncate this collection to a new length.
216///
217/// If self was shorter than `len`, nothing happens.
218///
219/// If self was longer, drops elements up to `len`
220pub trait Trunc
221  where Self: Sized
222{
223  #[allow(missing_docs)]
224  fn trunc(&mut self, len: usize) -> ();
225
226  /// Erase all elements in the collection
227  fn clear(&mut self) {
228    self.trunc(0);
229  }
230}
231
232#[cfg(feature = "alloc")]
233impl<T> Trunc for Vec<T> {
234  fn trunc(&mut self, len: usize) -> () {
235    self.truncate(len)
236  }
237}
238
239impl<T, const N: usize> Trunc for tinyvec::ArrayVec<[T; N]> where T: Default
240{
241  fn trunc(&mut self, len: usize) -> () {
242    self.truncate(len)
243  }
244}
245
246/// Fill this collection to the end with copies of `t`,
247/// copying array initialization `[0u8; 1000]` to the [`Array`] trait.
248///
249/// If the collection has no end (e.g. [`Vec`]),
250/// this trait's methods will return `None`.
251pub trait Filled<T>: Sized {
252  #[allow(missing_docs)]
253  fn filled(t: T) -> Option<Self>
254    where T: Copy
255  {
256    Self::filled_using(|| t)
257  }
258
259  #[allow(missing_docs)]
260  fn filled_default() -> Option<Self>
261    where T: Default
262  {
263    Self::filled_using(|| Default::default())
264  }
265
266  #[allow(missing_docs)]
267  fn filled_using<F>(f: F) -> Option<Self>
268    where F: Fn() -> T;
269}
270
271#[cfg(feature = "alloc")]
272impl<T> Reserve for Vec<T> {
273  fn reserve(n: usize) -> Self {
274    Self::with_capacity(n)
275  }
276}
277
278#[cfg(feature = "alloc")]
279impl<T> Filled<T> for Vec<T> {
280  fn filled_using<F>(_: F) -> Option<Self>
281    where F: Fn() -> T
282  {
283    None
284  }
285}
286
287impl<A: tinyvec::Array> Reserve for tinyvec::ArrayVec<A> {}
288
289impl<T, const N: usize> Filled<T> for tinyvec::ArrayVec<[T; N]> where T: Default
290{
291  fn filled_using<F>(f: F) -> Option<Self>
292    where F: Fn() -> T
293  {
294    Some(core::iter::repeat(()).take(N).map(|_| f()).collect())
295  }
296
297  fn filled(t: T) -> Option<Self>
298    where T: Copy
299  {
300    Some(Self::from([t; N]))
301  }
302}
303
304/// A generalization of [`std::vec::Vec`]
305///
306/// # Provided implementations
307/// - [`Vec`]
308/// - [`tinyvec::ArrayVec`]
309///
310/// ## Why [`tinyvec::ArrayVec`]?
311/// The performance of `heapless` and `arrayvec`'s Extend implementations
312/// are notably worse than `tinyvec`. (see `toad-msg/benches/collections.rs`)
313/// `tinyvec` also has the added bonus of being 100% unsafe-code-free.
314///
315/// # Definition of an [`Array`]
316/// The Array trait is automatically implemented for ordered indexed collections
317/// with a non-fixed number of elements which are contiguous in memory.
318///
319/// This translates to the trait requirements:
320/// - Must have an empty ([`Default`]) value
321/// - Must allow populating every element with a value ([`Filled`])
322/// - Must allow dropping every element after a given index ([`Trunc`])
323/// - Must allow mutably appending one or more elements ([`Extend`])
324/// - Must be creatable from an iterator ([`FromIterator`])
325/// - Must allow iterating over owned elements ([`IntoIterator`])
326/// - Must be dereferenceable to readonly and mutable slices ([`Deref`], [`DerefMut`])
327/// - Must allow getting the runtime length ([`Len`])
328/// - May have a hard limit on number of elements ([`Len`])
329/// - May allow creating an instance with maximum length and a given filler value ([`Filled`])
330/// - May allow pre-allocating space for a specific number of elements ([`Reserve`])
331pub trait Array:
332  Default
333  + Len
334  + Reserve
335  + Filled<<Self as Array>::Item>
336  + Trunc
337  + Indexed<<Self as Array>::Item>
338  + Extend<<Self as Array>::Item>
339  + FromIterator<<Self as Array>::Item>
340  + IntoIterator<Item = <Self as Array>::Item>
341  + Deref<Target = [<Self as Array>::Item]>
342  + DerefMut
343{
344  /// The type of item contained in the collection
345  type Item;
346}
347
348/// Collections that support extending themselves mutably from copyable slices
349pub trait AppendCopy<T>
350  where T: Copy
351{
352  /// Extend self mutably, copying from a slice.
353  ///
354  /// Worst-case implementations copy 1 element at a time (time O(n))
355  ///
356  /// Best-case implementations copy as much of the origin slice
357  /// at once as possible (system word size), e.g. [`Vec::append`].
358  /// (still linear time, but on 64-bit systems this is 64 times faster than a 1-by-1 copy.)
359  fn append_copy(&mut self, i: &[T]);
360}
361
362#[cfg(feature = "alloc")]
363impl<T> AppendCopy<T> for Vec<T> where T: Copy
364{
365  fn append_copy(&mut self, i: &[T]) {
366    self.extend(i);
367  }
368}
369
370impl<T, A> AppendCopy<T> for tinyvec::ArrayVec<A>
371  where T: Copy,
372        A: tinyvec::Array<Item = T>
373{
374  fn append_copy(&mut self, i: &[T]) {
375    self.extend_from_slice(i);
376  }
377}
378
379#[cfg(feature = "alloc")]
380impl<T> Array for Vec<T> {
381  type Item = T;
382}
383
384#[cfg(feature = "alloc")]
385impl<T> Indexed<T> for Vec<T> {
386  fn insert(&mut self, index: usize, value: T) {
387    self.insert(index, value);
388  }
389
390  fn remove(&mut self, index: usize) -> Option<T> {
391    if index < self.len() {
392      Some(Vec::remove(self, index))
393    } else {
394      None
395    }
396  }
397}
398
399impl<A, T> Array for tinyvec::ArrayVec<A>
400  where Self: Filled<T> + Trunc,
401        A: tinyvec::Array<Item = T>
402{
403  type Item = T;
404}
405
406impl<A> Indexed<A::Item> for tinyvec::ArrayVec<A>
407  where Self: Filled<A::Item> + Trunc,
408        A: tinyvec::Array
409{
410  fn insert(&mut self, ix: usize, t: A::Item) {
411    tinyvec::ArrayVec::insert(self, ix, t)
412  }
413
414  fn remove(&mut self, ix: usize) -> Option<A::Item> {
415    if ix < self.len() {
416      Some(tinyvec::ArrayVec::remove(self, ix))
417    } else {
418      None
419    }
420  }
421}
toad_array/lib.rs

toad_array/
lib.rs
