stillwater/
nonempty.rs

1//! Non-empty vector type for type-safe collections
2//!
3//! This module provides the `NonEmptyVec<T>` type, which is a vector guaranteed to contain
4//! at least one element. This provides type-level guarantees that prevent runtime errors
5//! when operations assume a non-empty collection.
6//!
7//! # Examples
8//!
9//! ```
10//! use stillwater::NonEmptyVec;
11//!
12//! let nev = NonEmptyVec::new(1, vec![2, 3, 4]);
13//! assert_eq!(nev.head(), &1);
14//! assert_eq!(nev.tail(), &[2, 3, 4]);
15//! assert_eq!(nev.len(), 4);
16//! ```
17//!
18//! # Use Cases
19//!
20//! - Validation errors: When a `Validation` fails, there's always at least one error
21//! - Aggregations: Operations like `head()`, `max()`, `min()` require non-empty data
22//! - Type safety: Prevent `None`/`panic!` in operations that need elements
23
24use crate::Semigroup;
25
26/// A non-empty vector guaranteed to contain at least one element.
27///
28/// This type provides type-level guarantees that operations like `head()`,
29/// `max()`, and `min()` will always succeed without returning `Option`.
30///
31/// # Example
32///
33/// ```
34/// use stillwater::NonEmptyVec;
35///
36/// let nev = NonEmptyVec::new(1, vec![2, 3, 4]);
37/// assert_eq!(nev.head(), &1);
38/// assert_eq!(nev.tail(), &[2, 3, 4]);
39/// assert_eq!(nev.len(), 4);
40/// ```
41#[derive(Debug, Clone, PartialEq, Eq)]
42pub struct NonEmptyVec<T> {
43    head: T,
44    tail: Vec<T>,
45}
46
47impl<T> NonEmptyVec<T> {
48    /// Create a new non-empty vector with a head element and tail.
49    ///
50    /// # Example
51    ///
52    /// ```
53    /// use stillwater::NonEmptyVec;
54    ///
55    /// let nev = NonEmptyVec::new(1, vec![2, 3]);
56    /// assert_eq!(nev.len(), 3);
57    /// ```
58    pub fn new(head: T, tail: Vec<T>) -> Self {
59        Self { head, tail }
60    }
61
62    /// Create a non-empty vector from a single element.
63    ///
64    /// # Example
65    ///
66    /// ```
67    /// use stillwater::NonEmptyVec;
68    ///
69    /// let nev = NonEmptyVec::singleton(42);
70    /// assert_eq!(nev.len(), 1);
71    /// assert_eq!(nev.head(), &42);
72    /// ```
73    pub fn singleton(value: T) -> Self {
74        Self::new(value, Vec::new())
75    }
76
77    /// Try to create a non-empty vector from a `Vec`.
78    ///
79    /// Returns `None` if the vector is empty.
80    ///
81    /// # Example
82    ///
83    /// ```
84    /// use stillwater::NonEmptyVec;
85    ///
86    /// let nev = NonEmptyVec::from_vec(vec![1, 2, 3]).unwrap();
87    /// assert_eq!(nev.len(), 3);
88    ///
89    /// let empty = NonEmptyVec::from_vec(Vec::<i32>::new());
90    /// assert!(empty.is_none());
91    /// ```
92    pub fn from_vec(mut vec: Vec<T>) -> Option<Self> {
93        if vec.is_empty() {
94            None
95        } else {
96            let head = vec.remove(0);
97            Some(Self::new(head, vec))
98        }
99    }
100
101    /// Create a non-empty vector from a `Vec` without checking.
102    ///
103    /// # Panics
104    ///
105    /// Panics if the vector is empty.
106    ///
107    /// # Example
108    ///
109    /// ```
110    /// use stillwater::NonEmptyVec;
111    ///
112    /// let nev = NonEmptyVec::from_vec_unchecked(vec![1, 2, 3]);
113    /// assert_eq!(nev.len(), 3);
114    /// ```
115    ///
116    /// ```should_panic
117    /// use stillwater::NonEmptyVec;
118    ///
119    /// let nev = NonEmptyVec::from_vec_unchecked(Vec::<i32>::new()); // panics
120    /// ```
121    pub fn from_vec_unchecked(vec: Vec<T>) -> Self {
122        Self::from_vec(vec).expect("NonEmptyVec::from_vec_unchecked called on empty Vec")
123    }
124
125    /// Get the first element (always succeeds).
126    ///
127    /// # Example
128    ///
129    /// ```
130    /// use stillwater::NonEmptyVec;
131    ///
132    /// let nev = NonEmptyVec::new(1, vec![2, 3]);
133    /// assert_eq!(nev.head(), &1);
134    /// ```
135    pub fn head(&self) -> &T {
136        &self.head
137    }
138
139    /// Get the tail (all elements except the first).
140    ///
141    /// # Example
142    ///
143    /// ```
144    /// use stillwater::NonEmptyVec;
145    ///
146    /// let nev = NonEmptyVec::new(1, vec![2, 3]);
147    /// assert_eq!(nev.tail(), &[2, 3]);
148    /// ```
149    pub fn tail(&self) -> &[T] {
150        &self.tail
151    }
152
153    /// Get the last element (always succeeds).
154    ///
155    /// # Example
156    ///
157    /// ```
158    /// use stillwater::NonEmptyVec;
159    ///
160    /// let nev = NonEmptyVec::new(1, vec![2, 3]);
161    /// assert_eq!(nev.last(), &3);
162    ///
163    /// let single = NonEmptyVec::singleton(42);
164    /// assert_eq!(single.last(), &42);
165    /// ```
166    pub fn last(&self) -> &T {
167        self.tail.last().unwrap_or(&self.head)
168    }
169
170    /// Get the number of elements.
171    ///
172    /// Always >= 1.
173    ///
174    /// # Example
175    ///
176    /// ```
177    /// use stillwater::NonEmptyVec;
178    ///
179    /// let nev = NonEmptyVec::new(1, vec![2, 3]);
180    /// assert_eq!(nev.len(), 3);
181    /// ```
182    pub fn len(&self) -> usize {
183        1 + self.tail.len()
184    }
185
186    /// Check if the vector is empty.
187    ///
188    /// Always returns `false` since a NonEmptyVec is guaranteed to have at least one element.
189    ///
190    /// This method exists to satisfy clippy's `len_without_is_empty` lint.
191    ///
192    /// # Example
193    ///
194    /// ```
195    /// use stillwater::NonEmptyVec;
196    ///
197    /// let nev = NonEmptyVec::singleton(42);
198    /// assert!(!nev.is_empty());
199    /// ```
200    pub fn is_empty(&self) -> bool {
201        false
202    }
203
204    /// Push an element to the end.
205    ///
206    /// # Example
207    ///
208    /// ```
209    /// use stillwater::NonEmptyVec;
210    ///
211    /// let mut nev = NonEmptyVec::singleton(1);
212    /// nev.push(2);
213    /// nev.push(3);
214    /// assert_eq!(nev.len(), 3);
215    /// ```
216    pub fn push(&mut self, value: T) {
217        self.tail.push(value);
218    }
219
220    /// Pop an element from the end.
221    ///
222    /// Returns `None` if there's only one element (the head).
223    ///
224    /// # Example
225    ///
226    /// ```
227    /// use stillwater::NonEmptyVec;
228    ///
229    /// let mut nev = NonEmptyVec::new(1, vec![2, 3]);
230    /// assert_eq!(nev.pop(), Some(3));
231    /// assert_eq!(nev.pop(), Some(2));
232    /// assert_eq!(nev.pop(), None); // Can't remove head
233    /// ```
234    pub fn pop(&mut self) -> Option<T> {
235        self.tail.pop()
236    }
237
238    /// Map a function over all elements.
239    ///
240    /// # Example
241    ///
242    /// ```
243    /// use stillwater::NonEmptyVec;
244    ///
245    /// let nev = NonEmptyVec::new(1, vec![2, 3]);
246    /// let doubled = nev.map(|x| x * 2);
247    /// assert_eq!(doubled.head(), &2);
248    /// assert_eq!(doubled.tail(), &[4, 6]);
249    /// ```
250    pub fn map<U, F>(self, mut f: F) -> NonEmptyVec<U>
251    where
252        F: FnMut(T) -> U,
253    {
254        let head = f(self.head);
255        let tail = self.tail.into_iter().map(f).collect();
256        NonEmptyVec::new(head, tail)
257    }
258
259    /// Filter elements (may return empty Vec).
260    ///
261    /// Since filtering might remove all elements, this returns `Vec<T>`.
262    ///
263    /// # Example
264    ///
265    /// ```
266    /// use stillwater::NonEmptyVec;
267    ///
268    /// let nev = NonEmptyVec::new(1, vec![2, 3, 4]);
269    /// let evens = nev.filter(|x| x % 2 == 0);
270    /// assert_eq!(evens, vec![2, 4]);
271    ///
272    /// let none = NonEmptyVec::singleton(1).filter(|x| x % 2 == 0);
273    /// assert_eq!(none, vec![]);
274    /// ```
275    pub fn filter<F>(self, mut predicate: F) -> Vec<T>
276    where
277        F: FnMut(&T) -> bool,
278    {
279        let mut result = Vec::new();
280        if predicate(&self.head) {
281            result.push(self.head);
282        }
283        result.extend(self.tail.into_iter().filter(predicate));
284        result
285    }
286
287    /// Convert to a regular `Vec`.
288    ///
289    /// # Example
290    ///
291    /// ```
292    /// use stillwater::NonEmptyVec;
293    ///
294    /// let nev = NonEmptyVec::new(1, vec![2, 3]);
295    /// let vec = nev.into_vec();
296    /// assert_eq!(vec, vec![1, 2, 3]);
297    /// ```
298    pub fn into_vec(self) -> Vec<T> {
299        let mut vec = vec![self.head];
300        vec.extend(self.tail);
301        vec
302    }
303
304    /// Iterate over all elements.
305    ///
306    /// # Example
307    ///
308    /// ```
309    /// use stillwater::NonEmptyVec;
310    ///
311    /// let nev = NonEmptyVec::new(1, vec![2, 3]);
312    /// let sum: i32 = nev.iter().sum();
313    /// assert_eq!(sum, 6);
314    /// ```
315    pub fn iter(&self) -> impl Iterator<Item = &T> {
316        std::iter::once(&self.head).chain(self.tail.iter())
317    }
318}
319
320// Semigroup: concatenation
321impl<T> Semigroup for NonEmptyVec<T> {
322    fn combine(mut self, other: Self) -> Self {
323        self.tail.push(other.head);
324        self.tail.extend(other.tail);
325        self
326    }
327}
328
329// IntoIterator
330impl<T> IntoIterator for NonEmptyVec<T> {
331    type Item = T;
332    type IntoIter = std::iter::Chain<std::iter::Once<T>, std::vec::IntoIter<T>>;
333
334    fn into_iter(self) -> Self::IntoIter {
335        std::iter::once(self.head).chain(self.tail)
336    }
337}
338
339// Note: We cannot implement FromIterator for Option<NonEmptyVec<T>> due to orphan rules.
340// Instead, use NonEmptyVec::from_vec(vec) where vec is collected from an iterator.
341
342// Index
343impl<T> std::ops::Index<usize> for NonEmptyVec<T> {
344    type Output = T;
345
346    fn index(&self, index: usize) -> &Self::Output {
347        if index == 0 {
348            &self.head
349        } else {
350            &self.tail[index - 1]
351        }
352    }
353}
354
355#[cfg(test)]
356mod tests {
357    use super::*;
358
359    #[test]
360    fn test_singleton() {
361        let nev = NonEmptyVec::singleton(42);
362        assert_eq!(nev.head(), &42);
363        assert_eq!(nev.tail(), &[] as &[i32]);
364        assert_eq!(nev.len(), 1);
365    }
366
367    #[test]
368    fn test_new() {
369        let nev = NonEmptyVec::new(1, vec![2, 3]);
370        assert_eq!(nev.head(), &1);
371        assert_eq!(nev.tail(), &[2, 3]);
372        assert_eq!(nev.len(), 3);
373    }
374
375    #[test]
376    fn test_from_vec() {
377        let nev = NonEmptyVec::from_vec(vec![1, 2, 3]).unwrap();
378        assert_eq!(nev.head(), &1);
379        assert_eq!(nev.tail(), &[2, 3]);
380
381        let empty = NonEmptyVec::from_vec(Vec::<i32>::new());
382        assert!(empty.is_none());
383    }
384
385    #[test]
386    fn test_from_vec_unchecked() {
387        let nev = NonEmptyVec::from_vec_unchecked(vec![1, 2, 3]);
388        assert_eq!(nev.head(), &1);
389        assert_eq!(nev.tail(), &[2, 3]);
390    }
391
392    #[test]
393    #[should_panic(expected = "NonEmptyVec::from_vec_unchecked called on empty Vec")]
394    fn test_from_vec_unchecked_panics() {
395        NonEmptyVec::from_vec_unchecked(Vec::<i32>::new());
396    }
397
398    #[test]
399    fn test_last() {
400        let nev = NonEmptyVec::new(1, vec![2, 3]);
401        assert_eq!(nev.last(), &3);
402
403        let single = NonEmptyVec::singleton(42);
404        assert_eq!(single.last(), &42);
405    }
406
407    #[test]
408    fn test_push_pop() {
409        let mut nev = NonEmptyVec::singleton(1);
410        nev.push(2);
411        nev.push(3);
412        assert_eq!(nev.len(), 3);
413
414        assert_eq!(nev.pop(), Some(3));
415        assert_eq!(nev.pop(), Some(2));
416        assert_eq!(nev.pop(), None);
417        assert_eq!(nev.len(), 1);
418    }
419
420    #[test]
421    fn test_map() {
422        let nev = NonEmptyVec::new(1, vec![2, 3]);
423        let doubled = nev.map(|x| x * 2);
424        assert_eq!(doubled.into_vec(), vec![2, 4, 6]);
425    }
426
427    #[test]
428    fn test_filter() {
429        let nev = NonEmptyVec::new(1, vec![2, 3, 4]);
430        let evens = nev.filter(|x| x % 2 == 0);
431        assert_eq!(evens, vec![2, 4]);
432
433        let nev2 = NonEmptyVec::singleton(1);
434        let empty = nev2.filter(|x| x % 2 == 0);
435        assert_eq!(empty, Vec::<i32>::new());
436    }
437
438    #[test]
439    fn test_into_vec() {
440        let nev = NonEmptyVec::new(1, vec![2, 3]);
441        let vec = nev.into_vec();
442        assert_eq!(vec, vec![1, 2, 3]);
443    }
444
445    #[test]
446    fn test_iter() {
447        let nev = NonEmptyVec::new(1, vec![2, 3]);
448        let sum: i32 = nev.iter().sum();
449        assert_eq!(sum, 6);
450
451        let collected: Vec<_> = nev.iter().copied().collect();
452        assert_eq!(collected, vec![1, 2, 3]);
453    }
454
455    #[test]
456    fn test_semigroup() {
457        let nev1 = NonEmptyVec::new(1, vec![2]);
458        let nev2 = NonEmptyVec::new(3, vec![4]);
459        let combined = nev1.combine(nev2);
460        assert_eq!(combined.into_vec(), vec![1, 2, 3, 4]);
461    }
462
463    #[test]
464    fn test_into_iter() {
465        let nev = NonEmptyVec::new(1, vec![2, 3]);
466        let vec: Vec<_> = nev.into_iter().collect();
467        assert_eq!(vec, vec![1, 2, 3]);
468    }
469
470    #[test]
471    fn test_from_vec_with_iterator() {
472        // Since we can't implement FromIterator, test the pattern of collect + from_vec
473        let vec: Vec<i32> = vec![1, 2, 3].into_iter().collect();
474        let nev = NonEmptyVec::from_vec(vec);
475        assert!(nev.is_some());
476        assert_eq!(nev.unwrap().into_vec(), vec![1, 2, 3]);
477
478        let vec_empty: Vec<i32> = vec![].into_iter().collect();
479        let nev_empty = NonEmptyVec::from_vec(vec_empty);
480        assert!(nev_empty.is_none());
481    }
482
483    #[test]
484    fn test_index() {
485        let nev = NonEmptyVec::new(1, vec![2, 3]);
486        assert_eq!(nev[0], 1);
487        assert_eq!(nev[1], 2);
488        assert_eq!(nev[2], 3);
489    }
490
491    #[test]
492    #[should_panic]
493    fn test_index_out_of_bounds() {
494        let nev = NonEmptyVec::singleton(42);
495        let _ = nev[1]; // Should panic
496    }
497}
stillwater/nonempty.rs

stillwater/
nonempty.rs
