diff options
Diffstat (limited to 'vendor/nonempty')
| -rw-r--r-- | vendor/nonempty/.cargo-checksum.json | 1 | ||||
| -rw-r--r-- | vendor/nonempty/Cargo.toml | 37 | ||||
| -rw-r--r-- | vendor/nonempty/LICENSE | 19 | ||||
| -rw-r--r-- | vendor/nonempty/README.md | 20 | ||||
| -rw-r--r-- | vendor/nonempty/deny.toml | 2 | ||||
| -rw-r--r-- | vendor/nonempty/flake.lock | 121 | ||||
| -rw-r--r-- | vendor/nonempty/flake.nix | 148 | ||||
| -rw-r--r-- | vendor/nonempty/src/lib.rs | 1206 | ||||
| -rw-r--r-- | vendor/nonempty/src/nonzero.rs | 96 |
9 files changed, 1650 insertions, 0 deletions
diff --git a/vendor/nonempty/.cargo-checksum.json b/vendor/nonempty/.cargo-checksum.json new file mode 100644 index 00000000..1c11e352 --- /dev/null +++ b/vendor/nonempty/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.toml":"e7395e0be8efd51c690a0d0b48c3c1588f6b31bb90af1e46f307e64bd44f74a2","LICENSE":"e9a7f23bee03fd95309a52a27f3eb77ad8ba9910ec47871111dd80db4df41648","README.md":"04b9e1aa85725bd19b088595885149e1fc249b6fed9dc9bdc5ed3466b9a0b2ee","deny.toml":"468c8206f07be015dcf4d35e88395f4552708180705446dc3b687086440eb7c0","flake.lock":"16205cfef4a3c69bce077ad2e956a32a24e324a339e7ba37983229923a5d59af","flake.nix":"ed174d59ea9fd7b9f2a676bc35dc8fc513fd81e9b93487d7bf70963ce1ed9576","src/lib.rs":"9c89d6ec56614b68c14d9e7ea8de46d1b01644b937461d375e6fd04774f3ad27","src/nonzero.rs":"7b60a1032aa1e85248bdbee1ab2e23fec22c5cb8178a7d0396a5b15836b25981"},"package":"303e8749c804ccd6ca3b428de7fe0d86cb86bc7606bc15291f100fd487960bb8"}
\ No newline at end of file diff --git a/vendor/nonempty/Cargo.toml b/vendor/nonempty/Cargo.toml new file mode 100644 index 00000000..835fc696 --- /dev/null +++ b/vendor/nonempty/Cargo.toml @@ -0,0 +1,37 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies. +# +# If you are reading this file be aware that the original Cargo.toml +# will likely look very different (and much more reasonable). +# See Cargo.toml.orig for the original contents. + +[package] +edition = "2018" +name = "nonempty" +version = "0.10.0" +authors = ["Alexis Sellier <self@cloudhead.io>"] +description = "Correct by construction non-empty vector" +readme = "README.md" +license = "MIT" +repository = "https://github.com/cloudhead/nonempty" + +[dependencies.arbitrary] +version = "1" +features = ["derive"] +optional = true + +[dependencies.serde] +version = "1" +features = ["serde_derive"] +optional = true + +[dev-dependencies.serde_json] +version = "1" + +[features] +arbitrary = ["dep:arbitrary"] +serialize = ["serde"] diff --git a/vendor/nonempty/LICENSE b/vendor/nonempty/LICENSE new file mode 100644 index 00000000..1aa6bbcc --- /dev/null +++ b/vendor/nonempty/LICENSE @@ -0,0 +1,19 @@ +Copyright (c) 2019 Alexis Sellier + +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies +of the Software, and to permit persons to whom the Software is furnished to do +so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/vendor/nonempty/README.md b/vendor/nonempty/README.md new file mode 100644 index 00000000..0b18b605 --- /dev/null +++ b/vendor/nonempty/README.md @@ -0,0 +1,20 @@ +# Correct by Construction Non-Empty List + +This package exposes a type `NonEmpty<T>` with a data representation +that guarantees non-emptiness statically: + + struct NonEmpty<T>(T, Vec<T>) + +The library is meant to have an interface similar to `std::vec::Vec`: + + use nonempty::NonEmpty; + + let mut l = NonEmpty::new(42); + + assert_eq!(l.first(), &42); + + l.push(36); + l.push(58); + + let v: Vec<i32> = l.into(); + assert_eq!(v, vec![42, 36, 58]); diff --git a/vendor/nonempty/deny.toml b/vendor/nonempty/deny.toml new file mode 100644 index 00000000..db2fc9e4 --- /dev/null +++ b/vendor/nonempty/deny.toml @@ -0,0 +1,2 @@ +[licenses] +allow = ["MIT"]
\ No newline at end of file diff --git a/vendor/nonempty/flake.lock b/vendor/nonempty/flake.lock new file mode 100644 index 00000000..3564b7de --- /dev/null +++ b/vendor/nonempty/flake.lock @@ -0,0 +1,121 @@ +{ + "nodes": { + "advisory-db": { + "flake": false, + "locked": { + "lastModified": 1708645386, + "narHash": "sha256-OdK/fVWOpbMBsl37pSWawPqpk5sePqtu1lx1UM+7c9Q=", + "owner": "rustsec", + "repo": "advisory-db", + "rev": "feb54ac57e980ef6578f66b307cfb844869e5260", + "type": "github" + }, + "original": { + "owner": "rustsec", + "repo": "advisory-db", + "type": "github" + } + }, + "crane": { + "inputs": { + "nixpkgs": [ + "nixpkgs" + ] + }, + "locked": { + "lastModified": 1708794349, + "narHash": "sha256-jX+B1VGHT0ruHHL5RwS8L21R6miBn4B6s9iVyUJsJJY=", + "owner": "ipetkov", + "repo": "crane", + "rev": "2c94ff9a6fbeb9f3ea0107f28688edbe9c81deaa", + "type": "github" + }, + "original": { + "owner": "ipetkov", + "repo": "crane", + "type": "github" + } + }, + "fenix": { + "inputs": { + "nixpkgs": [ + "nixpkgs" + ], + "rust-analyzer-src": [] + }, + "locked": { + "lastModified": 1708928609, + "narHash": "sha256-LcXC2NP/TzHMmJThZGG1e+7rht5HeuZK5WOirIDg+lU=", + "owner": "nix-community", + "repo": "fenix", + "rev": "e928fb6b5179ebd032c19afac5c461ccc0b6de55", + "type": "github" + }, + "original": { + "owner": "nix-community", + "repo": "fenix", + "type": "github" + } + }, + "flake-utils": { + "inputs": { + "systems": "systems" + }, + "locked": { + "lastModified": 1705309234, + "narHash": "sha256-uNRRNRKmJyCRC/8y1RqBkqWBLM034y4qN7EprSdmgyA=", + "owner": "numtide", + "repo": "flake-utils", + "rev": "1ef2e671c3b0c19053962c07dbda38332dcebf26", + "type": "github" + }, + "original": { + "owner": "numtide", + "repo": "flake-utils", + "type": "github" + } + }, + "nixpkgs": { + "locked": { + "lastModified": 1708905176, + "narHash": "sha256-pphkt8iO8CV/TugI7bsPOvFzi5mRSifkEQiwqYBK28s=", + "owner": "NixOS", + "repo": "nixpkgs", + "rev": "227a4c47bef2390a7925693c51489e84169b1957", + "type": "github" + }, + "original": { + "owner": "NixOS", + "ref": "release-23.11", + "repo": "nixpkgs", + "type": "github" + } + }, + "root": { + "inputs": { + "advisory-db": "advisory-db", + "crane": "crane", + "fenix": "fenix", + "flake-utils": "flake-utils", + "nixpkgs": "nixpkgs" + } + }, + "systems": { + "locked": { + "lastModified": 1681028828, + "narHash": "sha256-Vy1rq5AaRuLzOxct8nz4T6wlgyUR7zLU309k9mBC768=", + "owner": "nix-systems", + "repo": "default", + "rev": "da67096a3b9bf56a91d16901293e51ba5b49a27e", + "type": "github" + }, + "original": { + "owner": "nix-systems", + "repo": "default", + "type": "github" + } + } + }, + "root": "root", + "version": 7 +} diff --git a/vendor/nonempty/flake.nix b/vendor/nonempty/flake.nix new file mode 100644 index 00000000..2b7b68f8 --- /dev/null +++ b/vendor/nonempty/flake.nix @@ -0,0 +1,148 @@ +{ + description = "Build a cargo project"; + + inputs = { + nixpkgs.url = "github:NixOS/nixpkgs/release-23.11"; + + crane = { + url = "github:ipetkov/crane"; + inputs.nixpkgs.follows = "nixpkgs"; + }; + + fenix = { + url = "github:nix-community/fenix"; + inputs.nixpkgs.follows = "nixpkgs"; + inputs.rust-analyzer-src.follows = ""; + }; + + flake-utils.url = "github:numtide/flake-utils"; + + advisory-db = { + url = "github:rustsec/advisory-db"; + flake = false; + }; + }; + + outputs = { + self, + nixpkgs, + crane, + fenix, + flake-utils, + advisory-db, + ... + }: + flake-utils.lib.eachDefaultSystem (system: let + pname = "nonempty"; + pkgs = nixpkgs.legacyPackages.${system}; + + inherit (pkgs) lib; + + craneLib = crane.lib.${system}; + src = craneLib.cleanCargoSource (craneLib.path ./.); + + # Common arguments can be set here to avoid repeating them later + commonArgs = { + inherit src; + strictDeps = true; + + buildInputs = + [ + # Add additional build inputs here + ] + ++ lib.optionals pkgs.stdenv.isDarwin [ + # Additional darwin specific inputs can be set here + pkgs.libiconv + ]; + }; + + craneLibLLvmTools = + craneLib.overrideToolchain + (fenix.packages.${system}.complete.withComponents [ + "cargo" + "llvm-tools" + "rustc" + ]); + + # Build *just* the cargo dependencies, so we can reuse + # all of that work (e.g. via cachix) when running in CI + cargoArtifacts = craneLib.buildDepsOnly commonArgs; + + # Build the actual crate itself, reusing the dependency + # artifacts from above. + nonempty = craneLib.buildPackage (commonArgs + // { + inherit cargoArtifacts; + doCheck = false; + }); + in { + # Formatter + formatter = pkgs.alejandra; + + checks = { + # Build the crate as part of `nix flake check` for convenience + inherit nonempty; + + # Run clippy (and deny all warnings) on the crate source, + # again, resuing the dependency artifacts from above. + # + # Note that this is done as a separate derivation so that + # we can block the CI if there are issues here, but not + # prevent downstream consumers from building our crate by itself. + nonempty-clippy = craneLib.cargoClippy (commonArgs + // { + inherit cargoArtifacts; + cargoClippyExtraArgs = "--all-targets -- --deny warnings"; + }); + + nonempty-doc = craneLib.cargoDoc (commonArgs + // { + inherit cargoArtifacts; + }); + + # Check formatting + nonempty-fmt = craneLib.cargoFmt { + inherit src; + }; + + # Audit dependencies + nonempty-audit = craneLib.cargoAudit { + inherit src advisory-db; + }; + + # Audit licenses + nonempty-deny = craneLib.cargoDeny { + inherit src; + }; + + # Run tests with cargo-nextest + nonempty-nextest = craneLib.cargoNextest (commonArgs + // { + inherit cargoArtifacts; + partitions = 1; + partitionType = "count"; + }); + }; + + packages = + { + default = nonempty; + } + // lib.optionalAttrs (!pkgs.stdenv.isDarwin) { + nonempty-llvm-coverage = craneLibLLvmTools.cargoLlvmCov (commonArgs + // { + inherit cargoArtifacts; + }); + }; + + devShells.default = craneLib.devShell { + # Extra inputs can be added here; cargo and rustc are provided by default. + packages = [ + pkgs.cargo-watch + pkgs.cargo-nextest + pkgs.ripgrep + pkgs.rust-analyzer + ]; + }; + }); +} diff --git a/vendor/nonempty/src/lib.rs b/vendor/nonempty/src/lib.rs new file mode 100644 index 00000000..f95197c7 --- /dev/null +++ b/vendor/nonempty/src/lib.rs @@ -0,0 +1,1206 @@ +//! A Non-empty growable vector. +//! +//! Non-emptiness can be a powerful guarantee. If your main use of `Vec` is as +//! an `Iterator`, then you may not need to distinguish on emptiness. But there +//! are indeed times when the `Vec` you receive as as function argument needs to +//! be non-empty or your function can't proceed. Similarly, there are times when +//! the `Vec` you return to a calling user needs to promise it actually contains +//! something. +//! +//! With `NonEmpty`, you're freed from the boilerplate of constantly needing to +//! check `is_empty()` or pattern matching before proceeding, or erroring if you +//! can't. So overall, code, type signatures, and logic become cleaner. +//! +//! Consider that unlike `Vec`, [`NonEmpty::first`] and [`NonEmpty::last`] don't +//! return in `Option`, they always succeed. +//! +//! # Examples +//! +//! The simplest way to construct a [`NonEmpty`] is via the [`nonempty`] macro: +//! +//! ``` +//! use nonempty::{NonEmpty, nonempty}; +//! +//! let l: NonEmpty<u32> = nonempty![1, 2, 3]; +//! assert_eq!(l.head, 1); +//! ``` +//! +//! Unlike the familiar `vec!` macro, `nonempty!` requires at least one element: +//! +//! ``` +//! use nonempty::nonempty; +//! +//! let l = nonempty![1]; +//! +//! // Doesn't compile! +//! // let l = nonempty![]; +//! ``` +//! +//! Like `Vec`, you can also construct a [`NonEmpty`] the old fashioned way with +//! [`NonEmpty::new`] or its constructor: +//! +//! ``` +//! use nonempty::NonEmpty; +//! +//! let mut l = NonEmpty { head: 42, tail: vec![36, 58] }; +//! assert_eq!(l.head, 42); +//! +//! l.push(9001); +//! assert_eq!(l.last(), &9001); +//! ``` +//! +//! And if necessary, you're free to convert to and from `Vec`: +//! +//! ``` +//! use nonempty::{NonEmpty, nonempty}; +//! +//! let l: NonEmpty<u32> = nonempty![42, 36, 58, 9001]; +//! let v: Vec<u32> = l.into(); +//! assert_eq!(v, vec![42, 36, 58, 9001]); +//! +//! let u: Option<NonEmpty<u32>> = NonEmpty::from_vec(v); +//! assert_eq!(Some(nonempty![42, 36, 58, 9001]), u); +//! ``` +//! +//! # Caveats +//! +//! Since `NonEmpty` must have a least one element, it is not possible to +//! implement the `FromInterator` trait for it. We can't know, in general, if +//! any given `Iterator` actually contains something. +//! +//! # Features +//! +//! * `serialize`: `serde` support. +//! * `arbitrary`: `arbitrary` support. +#[cfg(feature = "arbitrary")] +use arbitrary::Arbitrary; +#[cfg(feature = "serialize")] +use serde::{ + ser::{SerializeSeq, Serializer}, + Deserialize, Serialize, +}; +use std::mem; +use std::{cmp::Ordering, num::NonZeroUsize}; +use std::{iter, vec}; + +pub mod nonzero; + +/// Like the `vec!` macro, but enforces at least one argument. A nice short-hand +/// for constructing [`NonEmpty`] values. +/// +/// ``` +/// use nonempty::{NonEmpty, nonempty}; +/// +/// let v = nonempty![1, 2, 3]; +/// assert_eq!(v, NonEmpty { head: 1, tail: vec![2, 3] }); +/// +/// let v = nonempty![1]; +/// assert_eq!(v, NonEmpty { head: 1, tail: Vec::new() }); +/// +/// // Accepts trailing commas +/// let v = nonempty![1,]; +/// assert_eq!(v, NonEmpty { head: 1, tail: Vec::new() }); +/// +/// // Doesn't compile! +/// // let v = nonempty![]; +/// ``` +#[macro_export] +macro_rules! nonempty { + ($h:expr, $( $x:expr ),* $(,)?) => {{ + let tail = vec![$($x),*]; + $crate::NonEmpty { head: $h, tail } + }}; + ($h:expr) => { + $crate::NonEmpty { + head: $h, + tail: Vec::new(), + } + }; +} + +/// Non-empty vector. +#[cfg_attr(feature = "serialize", derive(Deserialize))] +#[cfg_attr(feature = "arbitrary", derive(Arbitrary))] +#[cfg_attr(feature = "serialize", serde(try_from = "Vec<T>"))] +#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)] +pub struct NonEmpty<T> { + pub head: T, + pub tail: Vec<T>, +} + +// Nb. `Serialize` is implemented manually, as serde's `into` container attribute +// requires a `T: Clone` bound which we'd like to avoid. +#[cfg(feature = "serialize")] +impl<T> Serialize for NonEmpty<T> +where + T: Serialize, +{ + fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> + where + S: Serializer, + { + let mut seq = serializer.serialize_seq(Some(self.len()))?; + for e in self { + seq.serialize_element(e)?; + } + seq.end() + } +} + +pub struct Iter<'a, T> { + head: Option<&'a T>, + tail: &'a [T], +} + +impl<'a, T> Iterator for Iter<'a, T> { + type Item = &'a T; + + fn next(&mut self) -> Option<Self::Item> { + if let Some(value) = self.head.take() { + Some(value) + } else if let Some((first, rest)) = self.tail.split_first() { + self.tail = rest; + Some(first) + } else { + None + } + } +} + +impl<'a, T> DoubleEndedIterator for Iter<'a, T> { + fn next_back(&mut self) -> Option<Self::Item> { + if let Some((last, rest)) = self.tail.split_last() { + self.tail = rest; + Some(last) + } else if let Some(first_value) = self.head.take() { + Some(first_value) + } else { + None + } + } +} + +impl<'a, T> ExactSizeIterator for Iter<'a, T> { + fn len(&self) -> usize { + self.tail.len() + self.head.map_or(0, |_| 1) + } +} + +impl<'a, T> core::iter::FusedIterator for Iter<'a, T> {} + +impl<T> NonEmpty<T> { + /// Alias for [`NonEmpty::singleton`]. + pub const fn new(e: T) -> Self { + Self::singleton(e) + } + + /// Attempt to convert an iterator into a `NonEmpty` vector. + /// Returns `None` if the iterator was empty. + pub fn collect<I>(iter: I) -> Option<NonEmpty<T>> + where + I: IntoIterator<Item = T>, + { + let mut iter = iter.into_iter(); + let head = iter.next()?; + Some(Self { + head, + tail: iter.collect(), + }) + } + + /// Create a new non-empty list with an initial element. + pub const fn singleton(head: T) -> Self { + NonEmpty { + head, + tail: Vec::new(), + } + } + + /// Always returns false. + pub const fn is_empty(&self) -> bool { + false + } + + /// Get the first element. Never fails. + pub const fn first(&self) -> &T { + &self.head + } + + /// Get the mutable reference to the first element. Never fails. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut non_empty = NonEmpty::new(42); + /// let head = non_empty.first_mut(); + /// *head += 1; + /// assert_eq!(non_empty.first(), &43); + /// + /// let mut non_empty = NonEmpty::from((1, vec![4, 2, 3])); + /// let head = non_empty.first_mut(); + /// *head *= 42; + /// assert_eq!(non_empty.first(), &42); + /// ``` + pub fn first_mut(&mut self) -> &mut T { + &mut self.head + } + + /// Get the possibly-empty tail of the list. + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::new(42); + /// assert_eq!(non_empty.tail(), &[]); + /// + /// let non_empty = NonEmpty::from((1, vec![4, 2, 3])); + /// assert_eq!(non_empty.tail(), &[4, 2, 3]); + /// ``` + pub fn tail(&self) -> &[T] { + &self.tail + } + + /// Push an element to the end of the list. + pub fn push(&mut self, e: T) { + self.tail.push(e) + } + + /// Pop an element from the end of the list. + pub fn pop(&mut self) -> Option<T> { + self.tail.pop() + } + + /// Inserts an element at position index within the vector, shifting all elements after it to the right. + /// + /// # Panics + /// + /// Panics if index > len. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut non_empty = NonEmpty::from((1, vec![2, 3])); + /// non_empty.insert(1, 4); + /// assert_eq!(non_empty, NonEmpty::from((1, vec![4, 2, 3]))); + /// non_empty.insert(4, 5); + /// assert_eq!(non_empty, NonEmpty::from((1, vec![4, 2, 3, 5]))); + /// non_empty.insert(0, 42); + /// assert_eq!(non_empty, NonEmpty::from((42, vec![1, 4, 2, 3, 5]))); + /// ``` + pub fn insert(&mut self, index: usize, element: T) { + let len = self.len(); + assert!(index <= len); + + if index == 0 { + let head = mem::replace(&mut self.head, element); + self.tail.insert(0, head); + } else { + self.tail.insert(index - 1, element); + } + } + + /// Get the length of the list. + pub fn len(&self) -> usize { + self.tail.len() + 1 + } + + /// Gets the length of the list as a NonZeroUsize. + pub fn len_nonzero(&self) -> NonZeroUsize { + unsafe { NonZeroUsize::new_unchecked(self.tail.len().saturating_add(1)) } + } + + /// Get the capacity of the list. + pub fn capacity(&self) -> usize { + self.tail.capacity() + 1 + } + + /// Get the last element. Never fails. + pub fn last(&self) -> &T { + match self.tail.last() { + None => &self.head, + Some(e) => e, + } + } + + /// Get the last element mutably. + pub fn last_mut(&mut self) -> &mut T { + match self.tail.last_mut() { + None => &mut self.head, + Some(e) => e, + } + } + + /// Check whether an element is contained in the list. + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut l = NonEmpty::from((42, vec![36, 58])); + /// + /// assert!(l.contains(&42)); + /// assert!(!l.contains(&101)); + /// ``` + pub fn contains(&self, x: &T) -> bool + where + T: PartialEq, + { + self.iter().any(|e| e == x) + } + + /// Get an element by index. + pub fn get(&self, index: usize) -> Option<&T> { + if index == 0 { + Some(&self.head) + } else { + self.tail.get(index - 1) + } + } + + /// Get an element by index, mutably. + pub fn get_mut(&mut self, index: usize) -> Option<&mut T> { + if index == 0 { + Some(&mut self.head) + } else { + self.tail.get_mut(index - 1) + } + } + + /// Truncate the list to a certain size. Must be greater than `0`. + pub fn truncate(&mut self, len: usize) { + assert!(len >= 1); + self.tail.truncate(len - 1); + } + + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut l = NonEmpty::from((42, vec![36, 58])); + /// + /// let mut l_iter = l.iter(); + /// + /// assert_eq!(l_iter.len(), 3); + /// assert_eq!(l_iter.next(), Some(&42)); + /// assert_eq!(l_iter.next(), Some(&36)); + /// assert_eq!(l_iter.next(), Some(&58)); + /// assert_eq!(l_iter.next(), None); + /// ``` + pub fn iter(&self) -> Iter<T> { + Iter { + head: Some(&self.head), + tail: &self.tail, + } + } + + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut l = NonEmpty::new(42); + /// l.push(36); + /// l.push(58); + /// + /// for i in l.iter_mut() { + /// *i *= 10; + /// } + /// + /// let mut l_iter = l.iter(); + /// + /// assert_eq!(l_iter.next(), Some(&420)); + /// assert_eq!(l_iter.next(), Some(&360)); + /// assert_eq!(l_iter.next(), Some(&580)); + /// assert_eq!(l_iter.next(), None); + /// ``` + pub fn iter_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut T> + '_ { + iter::once(&mut self.head).chain(self.tail.iter_mut()) + } + + /// Often we have a `Vec` (or slice `&[T]`) but want to ensure that it is `NonEmpty` before + /// proceeding with a computation. Using `from_slice` will give us a proof + /// that we have a `NonEmpty` in the `Some` branch, otherwise it allows + /// the caller to handle the `None` case. + /// + /// # Example Use + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty_vec = NonEmpty::from_slice(&[1, 2, 3, 4, 5]); + /// assert_eq!(non_empty_vec, Some(NonEmpty::from((1, vec![2, 3, 4, 5])))); + /// + /// let empty_vec: Option<NonEmpty<&u32>> = NonEmpty::from_slice(&[]); + /// assert!(empty_vec.is_none()); + /// ``` + pub fn from_slice(slice: &[T]) -> Option<NonEmpty<T>> + where + T: Clone, + { + slice.split_first().map(|(h, t)| NonEmpty { + head: h.clone(), + tail: t.into(), + }) + } + + /// Often we have a `Vec` (or slice `&[T]`) but want to ensure that it is `NonEmpty` before + /// proceeding with a computation. Using `from_vec` will give us a proof + /// that we have a `NonEmpty` in the `Some` branch, otherwise it allows + /// the caller to handle the `None` case. + /// + /// This version will consume the `Vec` you pass in. If you would rather pass the data as a + /// slice then use `NonEmpty::from_slice`. + /// + /// # Example Use + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty_vec = NonEmpty::from_vec(vec![1, 2, 3, 4, 5]); + /// assert_eq!(non_empty_vec, Some(NonEmpty::from((1, vec![2, 3, 4, 5])))); + /// + /// let empty_vec: Option<NonEmpty<&u32>> = NonEmpty::from_vec(vec![]); + /// assert!(empty_vec.is_none()); + /// ``` + pub fn from_vec(mut vec: Vec<T>) -> Option<NonEmpty<T>> { + if vec.is_empty() { + None + } else { + let head = vec.remove(0); + Some(NonEmpty { head, tail: vec }) + } + } + + /// Deconstruct a `NonEmpty` into its head and tail. + /// This operation never fails since we are guranteed + /// to have a head element. + /// + /// # Example Use + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut non_empty = NonEmpty::from((1, vec![2, 3, 4, 5])); + /// + /// // Guaranteed to have the head and we also get the tail. + /// assert_eq!(non_empty.split_first(), (&1, &[2, 3, 4, 5][..])); + /// + /// let non_empty = NonEmpty::new(1); + /// + /// // Guaranteed to have the head element. + /// assert_eq!(non_empty.split_first(), (&1, &[][..])); + /// ``` + pub fn split_first(&self) -> (&T, &[T]) { + (&self.head, &self.tail) + } + + /// Deconstruct a `NonEmpty` into its first, last, and + /// middle elements, in that order. + /// + /// If there is only one element then first == last. + /// + /// # Example Use + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut non_empty = NonEmpty::from((1, vec![2, 3, 4, 5])); + /// + /// // Guaranteed to have the last element and the elements + /// // preceding it. + /// assert_eq!(non_empty.split(), (&1, &[2, 3, 4][..], &5)); + /// + /// let non_empty = NonEmpty::new(1); + /// + /// // Guaranteed to have the last element. + /// assert_eq!(non_empty.split(), (&1, &[][..], &1)); + /// ``` + pub fn split(&self) -> (&T, &[T], &T) { + match self.tail.split_last() { + None => (&self.head, &[], &self.head), + Some((last, middle)) => (&self.head, middle, last), + } + } + + /// Append a `Vec` to the tail of the `NonEmpty`. + /// + /// # Example Use + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut non_empty = NonEmpty::new(1); + /// let mut vec = vec![2, 3, 4, 5]; + /// non_empty.append(&mut vec); + /// + /// let mut expected = NonEmpty::from((1, vec![2, 3, 4, 5])); + /// + /// assert_eq!(non_empty, expected); + /// ``` + pub fn append(&mut self, other: &mut Vec<T>) { + self.tail.append(other) + } + + /// A structure preserving `map`. This is useful for when + /// we wish to keep the `NonEmpty` structure guaranteeing + /// that there is at least one element. Otherwise, we can + /// use `nonempty.iter().map(f)`. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::from((1, vec![2, 3, 4, 5])); + /// + /// let squares = non_empty.map(|i| i * i); + /// + /// let expected = NonEmpty::from((1, vec![4, 9, 16, 25])); + /// + /// assert_eq!(squares, expected); + /// ``` + pub fn map<U, F>(self, mut f: F) -> NonEmpty<U> + where + F: FnMut(T) -> U, + { + NonEmpty { + head: f(self.head), + tail: self.tail.into_iter().map(f).collect(), + } + } + + /// A structure preserving, fallible mapping function. + pub fn try_map<E, U, F>(self, mut f: F) -> Result<NonEmpty<U>, E> + where + F: FnMut(T) -> Result<U, E>, + { + Ok(NonEmpty { + head: f(self.head)?, + tail: self.tail.into_iter().map(f).collect::<Result<_, _>>()?, + }) + } + + /// When we have a function that goes from some `T` to a `NonEmpty<U>`, + /// we may want to apply it to a `NonEmpty<T>` but keep the structure flat. + /// This is where `flat_map` shines. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::from((1, vec![2, 3, 4, 5])); + /// + /// let windows = non_empty.flat_map(|i| { + /// let mut next = NonEmpty::new(i + 5); + /// next.push(i + 6); + /// next + /// }); + /// + /// let expected = NonEmpty::from((6, vec![7, 7, 8, 8, 9, 9, 10, 10, 11])); + /// + /// assert_eq!(windows, expected); + /// ``` + pub fn flat_map<U, F>(self, mut f: F) -> NonEmpty<U> + where + F: FnMut(T) -> NonEmpty<U>, + { + let mut heads = f(self.head); + let mut tails = self + .tail + .into_iter() + .flat_map(|t| f(t).into_iter()) + .collect(); + heads.append(&mut tails); + heads + } + + /// Flatten nested `NonEmpty`s into a single one. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::from(( + /// NonEmpty::from((1, vec![2, 3])), + /// vec![NonEmpty::from((4, vec![5]))], + /// )); + /// + /// let expected = NonEmpty::from((1, vec![2, 3, 4, 5])); + /// + /// assert_eq!(NonEmpty::flatten(non_empty), expected); + /// ``` + pub fn flatten(full: NonEmpty<NonEmpty<T>>) -> Self { + full.flat_map(|n| n) + } + + /// Binary searches this sorted non-empty vector for a given element. + /// + /// If the value is found then Result::Ok is returned, containing the index of the matching element. + /// If there are multiple matches, then any one of the matches could be returned. + /// + /// If the value is not found then Result::Err is returned, containing the index where a + /// matching element could be inserted while maintaining sorted order. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::from((0, vec![1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55])); + /// assert_eq!(non_empty.binary_search(&0), Ok(0)); + /// assert_eq!(non_empty.binary_search(&13), Ok(9)); + /// assert_eq!(non_empty.binary_search(&4), Err(7)); + /// assert_eq!(non_empty.binary_search(&100), Err(13)); + /// let r = non_empty.binary_search(&1); + /// assert!(match r { Ok(1..=4) => true, _ => false, }); + /// ``` + /// + /// If you want to insert an item to a sorted non-empty vector, while maintaining sort order: + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let mut non_empty = NonEmpty::from((0, vec![1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55])); + /// let num = 42; + /// let idx = non_empty.binary_search(&num).unwrap_or_else(|x| x); + /// non_empty.insert(idx, num); + /// assert_eq!(non_empty, NonEmpty::from((0, vec![1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]))); + /// ``` + pub fn binary_search(&self, x: &T) -> Result<usize, usize> + where + T: Ord, + { + self.binary_search_by(|p| p.cmp(x)) + } + + /// Binary searches this sorted non-empty with a comparator function. + /// + /// The comparator function should implement an order consistent with the sort order of the underlying slice, + /// returning an order code that indicates whether its argument is Less, Equal or Greater the desired target. + /// + /// If the value is found then Result::Ok is returned, containing the index of the matching element. + /// If there are multiple matches, then any one of the matches could be returned. + /// If the value is not found then Result::Err is returned, containing the index where a matching element could be + /// inserted while maintaining sorted order. + /// + /// # Examples + /// + /// Looks up a series of four elements. The first is found, with a uniquely determined + /// position; the second and third are not found; the fourth could match any position in [1,4]. + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::from((0, vec![1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55])); + /// let seek = 0; + /// assert_eq!(non_empty.binary_search_by(|probe| probe.cmp(&seek)), Ok(0)); + /// let seek = 13; + /// assert_eq!(non_empty.binary_search_by(|probe| probe.cmp(&seek)), Ok(9)); + /// let seek = 4; + /// assert_eq!(non_empty.binary_search_by(|probe| probe.cmp(&seek)), Err(7)); + /// let seek = 100; + /// assert_eq!(non_empty.binary_search_by(|probe| probe.cmp(&seek)), Err(13)); + /// let seek = 1; + /// let r = non_empty.binary_search_by(|probe| probe.cmp(&seek)); + /// assert!(match r { Ok(1..=4) => true, _ => false, }); + /// ``` + pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize> + where + F: FnMut(&'a T) -> Ordering, + { + match f(&self.head) { + Ordering::Equal => Ok(0), + Ordering::Greater => Err(0), + Ordering::Less => self + .tail + .binary_search_by(f) + .map(|index| index + 1) + .map_err(|index| index + 1), + } + } + + /// Binary searches this sorted non-empty vector with a key extraction function. + /// + /// Assumes that the vector is sorted by the key. + /// + /// If the value is found then Result::Ok is returned, containing the index of the matching element. If there are multiple matches, + /// then any one of the matches could be returned. If the value is not found then Result::Err is returned, + /// containing the index where a matching element could be inserted while maintaining sorted order. + /// + /// # Examples + /// + /// Looks up a series of four elements in a non-empty vector of pairs sorted by their second elements. + /// The first is found, with a uniquely determined position; the second and third are not found; + /// the fourth could match any position in [1, 4]. + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::from(( + /// (0, 0), + /// vec![(2, 1), (4, 1), (5, 1), (3, 1), + /// (1, 2), (2, 3), (4, 5), (5, 8), (3, 13), + /// (1, 21), (2, 34), (4, 55)] + /// )); + /// + /// assert_eq!(non_empty.binary_search_by_key(&0, |&(a,b)| b), Ok(0)); + /// assert_eq!(non_empty.binary_search_by_key(&13, |&(a,b)| b), Ok(9)); + /// assert_eq!(non_empty.binary_search_by_key(&4, |&(a,b)| b), Err(7)); + /// assert_eq!(non_empty.binary_search_by_key(&100, |&(a,b)| b), Err(13)); + /// let r = non_empty.binary_search_by_key(&1, |&(a,b)| b); + /// assert!(match r { Ok(1..=4) => true, _ => false, }); + /// ``` + pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize> + where + B: Ord, + F: FnMut(&'a T) -> B, + { + self.binary_search_by(|k| f(k).cmp(b)) + } + + /// Returns the maximum element in the non-empty vector. + /// + /// This will return the first item in the vector if the tail is empty. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::new(42); + /// assert_eq!(non_empty.maximum(), &42); + /// + /// let non_empty = NonEmpty::from((1, vec![-34, 42, 76, 4, 5])); + /// assert_eq!(non_empty.maximum(), &76); + /// ``` + pub fn maximum(&self) -> &T + where + T: Ord, + { + self.maximum_by(|i, j| i.cmp(j)) + } + + /// Returns the minimum element in the non-empty vector. + /// + /// This will return the first item in the vector if the tail is empty. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::new(42); + /// assert_eq!(non_empty.minimum(), &42); + /// + /// let non_empty = NonEmpty::from((1, vec![-34, 42, 76, 4, 5])); + /// assert_eq!(non_empty.minimum(), &-34); + /// ``` + pub fn minimum(&self) -> &T + where + T: Ord, + { + self.minimum_by(|i, j| i.cmp(j)) + } + + /// Returns the element that gives the maximum value with respect to the specified comparison function. + /// + /// This will return the first item in the vector if the tail is empty. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::new((0, 42)); + /// assert_eq!(non_empty.maximum_by(|(k, _), (l, _)| k.cmp(l)), &(0, 42)); + /// + /// let non_empty = NonEmpty::from(((2, 1), vec![(2, -34), (4, 42), (0, 76), (1, 4), (3, 5)])); + /// assert_eq!(non_empty.maximum_by(|(k, _), (l, _)| k.cmp(l)), &(4, 42)); + /// ``` + pub fn maximum_by<'a, F>(&'a self, mut compare: F) -> &T + where + F: FnMut(&'a T, &'a T) -> Ordering, + { + let mut max = &self.head; + for i in self.tail.iter() { + max = match compare(max, i) { + Ordering::Equal => max, + Ordering::Less => i, + Ordering::Greater => max, + }; + } + max + } + + /// Returns the element that gives the minimum value with respect to the specified comparison function. + /// + /// This will return the first item in the vector if the tail is empty. + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::new((0, 42)); + /// assert_eq!(non_empty.minimum_by(|(k, _), (l, _)| k.cmp(l)), &(0, 42)); + /// + /// let non_empty = NonEmpty::from(((2, 1), vec![(2, -34), (4, 42), (0, 76), (1, 4), (3, 5)])); + /// assert_eq!(non_empty.minimum_by(|(k, _), (l, _)| k.cmp(l)), &(0, 76)); + /// ``` + pub fn minimum_by<'a, F>(&'a self, mut compare: F) -> &T + where + F: FnMut(&'a T, &'a T) -> Ordering, + { + self.maximum_by(|a, b| compare(a, b).reverse()) + } + + /// Returns the element that gives the maximum value with respect to the specified function. + /// + /// This will return the first item in the vector if the tail is empty. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::new((0, 42)); + /// assert_eq!(non_empty.maximum_by_key(|(k, _)| k), &(0, 42)); + /// + /// let non_empty = NonEmpty::from(((2, 1), vec![(2, -34), (4, 42), (0, 76), (1, 4), (3, 5)])); + /// assert_eq!(non_empty.maximum_by_key(|(k, _)| k), &(4, 42)); + /// assert_eq!(non_empty.maximum_by_key(|(k, _)| -k), &(0, 76)); + /// ``` + pub fn maximum_by_key<'a, U, F>(&'a self, mut f: F) -> &T + where + U: Ord, + F: FnMut(&'a T) -> U, + { + self.maximum_by(|i, j| f(i).cmp(&f(j))) + } + + /// Returns the element that gives the minimum value with respect to the specified function. + /// + /// This will return the first item in the vector if the tail is empty. + /// + /// # Examples + /// + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::new((0, 42)); + /// assert_eq!(non_empty.minimum_by_key(|(k, _)| k), &(0, 42)); + /// + /// let non_empty = NonEmpty::from(((2, 1), vec![(2, -34), (4, 42), (0, 76), (1, 4), (3, 5)])); + /// assert_eq!(non_empty.minimum_by_key(|(k, _)| k), &(0, 76)); + /// assert_eq!(non_empty.minimum_by_key(|(k, _)| -k), &(4, 42)); + /// ``` + pub fn minimum_by_key<'a, U, F>(&'a self, mut f: F) -> &T + where + U: Ord, + F: FnMut(&'a T) -> U, + { + self.minimum_by(|i, j| f(i).cmp(&f(j))) + } +} + +impl<T: Default> Default for NonEmpty<T> { + fn default() -> Self { + Self::new(T::default()) + } +} + +impl<T> From<NonEmpty<T>> for Vec<T> { + /// Turns a non-empty list into a Vec. + fn from(nonempty: NonEmpty<T>) -> Vec<T> { + iter::once(nonempty.head).chain(nonempty.tail).collect() + } +} + +impl<T> From<NonEmpty<T>> for (T, Vec<T>) { + /// Turns a non-empty list into a Vec. + fn from(nonempty: NonEmpty<T>) -> (T, Vec<T>) { + (nonempty.head, nonempty.tail) + } +} + +impl<T> From<(T, Vec<T>)> for NonEmpty<T> { + /// Turns a pair of an element and a Vec into + /// a NonEmpty. + fn from((head, tail): (T, Vec<T>)) -> Self { + NonEmpty { head, tail } + } +} + +impl<T> IntoIterator for NonEmpty<T> { + type Item = T; + type IntoIter = iter::Chain<iter::Once<T>, vec::IntoIter<Self::Item>>; + + fn into_iter(self) -> Self::IntoIter { + iter::once(self.head).chain(self.tail) + } +} + +impl<'a, T> IntoIterator for &'a NonEmpty<T> { + type Item = &'a T; + type IntoIter = iter::Chain<iter::Once<&'a T>, std::slice::Iter<'a, T>>; + + fn into_iter(self) -> Self::IntoIter { + iter::once(&self.head).chain(self.tail.iter()) + } +} + +impl<T> std::ops::Index<usize> for NonEmpty<T> { + type Output = T; + + /// ``` + /// use nonempty::NonEmpty; + /// + /// let non_empty = NonEmpty::from((1, vec![2, 3, 4, 5])); + /// + /// assert_eq!(non_empty[0], 1); + /// assert_eq!(non_empty[1], 2); + /// assert_eq!(non_empty[3], 4); + /// ``` + fn index(&self, index: usize) -> &T { + if index > 0 { + &self.tail[index - 1] + } else { + &self.head + } + } +} + +impl<T> std::ops::IndexMut<usize> for NonEmpty<T> { + fn index_mut(&mut self, index: usize) -> &mut T { + if index > 0 { + &mut self.tail[index - 1] + } else { + &mut self.head + } + } +} + +impl<A> Extend<A> for NonEmpty<A> { + fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T) { + self.tail.extend(iter) + } +} + +#[cfg(feature = "serialize")] +pub mod serialize { + use std::{convert::TryFrom, fmt}; + + use super::NonEmpty; + + #[derive(Debug)] + pub enum Error { + Empty, + } + + impl fmt::Display for Error { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + Self::Empty => f.write_str( + "the vector provided was empty, NonEmpty needs at least one element", + ), + } + } + } + + impl<T> TryFrom<Vec<T>> for NonEmpty<T> { + type Error = Error; + + fn try_from(vec: Vec<T>) -> Result<Self, Self::Error> { + NonEmpty::from_vec(vec).ok_or(Error::Empty) + } + } +} + +#[cfg(test)] +mod tests { + use crate::NonEmpty; + + #[test] + fn test_from_conversion() { + let result = NonEmpty::from((1, vec![2, 3, 4, 5])); + let expected = NonEmpty { + head: 1, + tail: vec![2, 3, 4, 5], + }; + assert_eq!(result, expected); + } + + #[test] + fn test_into_iter() { + let nonempty = NonEmpty::from((0, vec![1, 2, 3])); + for (i, n) in nonempty.into_iter().enumerate() { + assert_eq!(i as i32, n); + } + } + + #[test] + fn test_iter_syntax() { + let nonempty = NonEmpty::from((0, vec![1, 2, 3])); + for n in &nonempty { + let _ = *n; // Prove that we're dealing with references. + } + for _ in nonempty {} + } + + #[test] + fn test_iter_both_directions() { + let mut nonempty = NonEmpty::from((0, vec![1, 2, 3])); + assert_eq!(nonempty.iter().cloned().collect::<Vec<_>>(), [0, 1, 2, 3]); + assert_eq!( + nonempty.iter().rev().cloned().collect::<Vec<_>>(), + [3, 2, 1, 0] + ); + assert_eq!( + nonempty.iter_mut().rev().collect::<Vec<_>>(), + [&mut 3, &mut 2, &mut 1, &mut 0] + ); + } + + #[test] + fn test_iter_both_directions_at_once() { + let nonempty = NonEmpty::from((0, vec![1, 2, 3])); + let mut i = nonempty.iter(); + assert_eq!(i.next(), Some(&0)); + assert_eq!(i.next_back(), Some(&3)); + assert_eq!(i.next(), Some(&1)); + assert_eq!(i.next_back(), Some(&2)); + assert_eq!(i.next(), None); + assert_eq!(i.next_back(), None); + } + + #[test] + fn test_mutate_head() { + let mut non_empty = NonEmpty::new(42); + non_empty.head += 1; + assert_eq!(non_empty.head, 43); + + let mut non_empty = NonEmpty::from((1, vec![4, 2, 3])); + non_empty.head *= 42; + assert_eq!(non_empty.head, 42); + } + + #[test] + fn test_to_nonempty() { + use std::iter::{empty, once}; + + assert_eq!(NonEmpty::<()>::collect(empty()), None); + assert_eq!(NonEmpty::<()>::collect(once(())), Some(NonEmpty::new(()))); + assert_eq!( + NonEmpty::<u8>::collect(once(1).chain(once(2))), + Some(nonempty!(1, 2)) + ); + } + + #[test] + fn test_try_map() { + assert_eq!( + nonempty!(1, 2, 3, 4).try_map(Ok::<_, String>), + Ok(nonempty!(1, 2, 3, 4)) + ); + assert_eq!( + nonempty!(1, 2, 3, 4).try_map(|i| if i % 2 == 0 { Ok(i) } else { Err("not even") }), + Err("not even") + ); + } + + #[test] + fn test_nontrivial_minimum_by_key() { + #[derive(Debug, Clone, Copy, PartialEq, Eq)] + struct Position { + x: i32, + y: i32, + } + impl Position { + pub fn distance_squared(&self, other: Position) -> u32 { + let dx = self.x - other.x; + let dy = self.y - other.y; + (dx * dx + dy * dy) as u32 + } + } + let positions = nonempty![ + Position { x: 1, y: 1 }, + Position { x: 0, y: 0 }, + Position { x: 3, y: 4 } + ]; + let target = Position { x: 1, y: 2 }; + let closest = positions.minimum_by_key(|position| position.distance_squared(target)); + assert_eq!(closest, &Position { x: 1, y: 1 }); + } + + #[cfg(feature = "serialize")] + mod serialize { + use crate::NonEmpty; + use serde::{Deserialize, Serialize}; + + #[derive(Debug, Deserialize, Eq, PartialEq, Serialize)] + pub struct SimpleSerializable(pub i32); + + #[test] + fn test_simple_round_trip() -> Result<(), Box<dyn std::error::Error>> { + // Given + let mut non_empty = NonEmpty::new(SimpleSerializable(42)); + non_empty.push(SimpleSerializable(777)); + + // When + let res = serde_json::from_str::<'_, NonEmpty<SimpleSerializable>>( + &serde_json::to_string(&non_empty)?, + )?; + + // Then + assert_eq!(res, non_empty); + + Ok(()) + } + + #[test] + fn test_serialization() -> Result<(), Box<dyn std::error::Error>> { + let ne = nonempty![1, 2, 3, 4, 5]; + let ve = vec![1, 2, 3, 4, 5]; + + assert_eq!(serde_json::to_string(&ne)?, serde_json::to_string(&ve)?); + + Ok(()) + } + } + + #[cfg(feature = "arbitrary")] + mod arbitrary { + use crate::NonEmpty; + use arbitrary::{Arbitrary, Unstructured}; + + #[test] + fn test_arbitrary_empty_tail() -> arbitrary::Result<()> { + let mut u = Unstructured::new(&[1, 2, 3, 4]); + let ne = NonEmpty::<i32>::arbitrary(&mut u)?; + assert!(!ne.is_empty()); + assert_eq!( + ne, + NonEmpty { + head: 67305985, + tail: vec![], + } + ); + Ok(()) + } + + #[test] + fn test_arbitrary_with_tail() -> arbitrary::Result<()> { + let mut u = Unstructured::new(&[1, 2, 3, 4, 5, 6, 7, 8]); + let ne = NonEmpty::<i32>::arbitrary(&mut u)?; + assert!(!ne.is_empty()); + assert_eq!( + ne, + NonEmpty { + head: 67305985, + tail: vec![526086], + } + ); + Ok(()) + } + } +} diff --git a/vendor/nonempty/src/nonzero.rs b/vendor/nonempty/src/nonzero.rs new file mode 100644 index 00000000..4d611022 --- /dev/null +++ b/vendor/nonempty/src/nonzero.rs @@ -0,0 +1,96 @@ +#[cfg(feature = "arbitrary")] +use arbitrary::Arbitrary; +use std::num::NonZeroUsize; + +/// A non-empty list which statically guarantees certain operations +/// cannot return zero, using [`std::num::NonZeroUsize`]. +/// +/// *Experimental* +/// +#[repr(transparent)] +#[cfg_attr(feature = "arbitrary", derive(Arbitrary))] +#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)] +pub struct NonEmpty<T>(super::NonEmpty<T>); + +impl<T> NonEmpty<T> { + /// Get the length of the list. + pub fn len(&self) -> NonZeroUsize { + unsafe { NonZeroUsize::new_unchecked(self.0.tail.len() + 1) } + } + + /// Get the capacity of the list. + pub fn capacity(&self) -> NonZeroUsize { + unsafe { NonZeroUsize::new_unchecked(self.0.tail.capacity() + 1) } + } + + /// Truncate the list to a certain size. + pub fn truncate(&mut self, len: NonZeroUsize) { + self.tail.truncate(usize::from(len) - 1); + } +} + +impl<T> From<super::NonEmpty<T>> for NonEmpty<T> { + fn from(other: super::NonEmpty<T>) -> NonEmpty<T> { + NonEmpty(other) + } +} + +impl<T> std::ops::Deref for NonEmpty<T> { + type Target = super::NonEmpty<T>; + + fn deref(&self) -> &Self::Target { + &self.0 + } +} + +impl<T> std::ops::DerefMut for NonEmpty<T> { + fn deref_mut(&mut self) -> &mut Self::Target { + &mut self.0 + } +} + +#[cfg(test)] +mod tests { + use crate::nonzero; + use crate::NonEmpty; + + use std::convert::TryInto; + + #[test] + fn test_nonzero() { + let nonempty: nonzero::NonEmpty<_> = NonEmpty::from((0, vec![1, 2, 3])).into(); + + assert_eq!(nonempty.len(), 4.try_into().unwrap()); + assert_eq!(nonempty.capacity(), 4.try_into().unwrap()); + } + + #[cfg(feature = "arbitrary")] + mod arbitrary { + use crate::nonzero; + use arbitrary::{Arbitrary, Unstructured}; + + use std::convert::TryInto; + + #[test] + fn test_nonzero_arbitrary_empty_tail() -> arbitrary::Result<()> { + let mut u = Unstructured::new(&[1, 2, 3, 4]); + let nonempty: nonzero::NonEmpty<_> = nonzero::NonEmpty::<i32>::arbitrary(&mut u)?; + + assert_eq!(nonempty.len(), 1.try_into().unwrap()); + assert_eq!(nonempty.capacity(), 1.try_into().unwrap()); + + Ok(()) + } + + #[test] + fn test_nonzero_arbitrary_with_tail() -> arbitrary::Result<()> { + let mut u = Unstructured::new(&[1, 2, 3, 4, 5, 6, 7, 8]); + let nonempty: nonzero::NonEmpty<_> = nonzero::NonEmpty::<i32>::arbitrary(&mut u)?; + + assert_eq!(nonempty.len(), 2.try_into().unwrap()); + assert_eq!(nonempty.capacity(), 5.try_into().unwrap()); + + Ok(()) + } + } +} |