/rust/registry/src/index.crates.io-1949cf8c6b5b557f/elsa-1.11.2/src/vec.rs

Source
use std::cell::UnsafeCell;
use std::cmp::Ordering;
use std::iter::FromIterator;
use std::ops::Index;

use stable_deref_trait::StableDeref;

/// Append-only version of `std::vec::Vec` where
/// insertion does not require mutable access
pub struct FrozenVec<T> {
    vec: UnsafeCell<Vec<T>>,
    // XXXManishearth do we need a reentrancy guard here as well?
    // StableDeref may not guarantee that there are no side effects
}

// safety: UnsafeCell implies !Sync

impl<T> FrozenVec<T> {
    /// Constructs a new, empty vector.
    pub const fn new() -> Self {
        Self {
            vec: UnsafeCell::new(Vec::new()),
        }
    }
}

impl<T> FrozenVec<T> {
    // these should never return &T
    // these should never delete any entries

    /// Appends an element to the back of the vector.
    pub fn push(&self, val: T) {
        unsafe {
            let vec = self.vec.get();
            (*vec).push(val)
        }
    }
}

impl<T: StableDeref> FrozenVec<T> {
    /// Push, immediately getting a reference to the element
    pub fn push_get(&self, val: T) -> &T::Target {
        unsafe {
            let vec = self.vec.get();
            (*vec).push(val);
            &*(&**(*vec).get_unchecked((*vec).len() - 1) as *const T::Target)
        }
    }

    /// Returns a reference to an element.
    pub fn get(&self, index: usize) -> Option<&T::Target> {
        unsafe {
            let vec = self.vec.get();
            (*vec).get(index).map(|x| &**x)
        }
    }

    /// Returns a reference to an element, without doing bounds checking.
    ///
    /// ## Safety
    ///
    /// `index` must be in bounds, i.e. it must be less than `self.len()`
    pub unsafe fn get_unchecked(&self, index: usize) -> &T::Target {
        let vec = self.vec.get();
        (*vec).get_unchecked(index)
    }
}

impl<T: Copy> FrozenVec<T> {
    /// Returns a copy of an element.
    pub fn get_copy(&self, index: usize) -> Option<T> {
        unsafe {
            let vec = self.vec.get();
            (*vec).get(index).copied()
        }
    }
}

impl<T> FrozenVec<T> {
    /// Returns the number of elements in the vector.
    pub fn len(&self) -> usize {
        unsafe {
            let vec = self.vec.get();
            (*vec).len()
        }
    }

    /// Returns `true` if the vector contains no elements.
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
}

impl<T: StableDeref> FrozenVec<T> {
    /// Returns the first element of the vector, or `None` if empty.
    pub fn first(&self) -> Option<&T::Target> {
        unsafe {
            let vec = self.vec.get();
            (*vec).first().map(|x| &**x)
        }
    }

    /// Returns the last element of the vector, or `None` if empty.
    pub fn last(&self) -> Option<&T::Target> {
        unsafe {
            let vec = self.vec.get();
            (*vec).last().map(|x| &**x)
        }
    }
    /// Returns an iterator over the vector.
    pub fn iter(&self) -> Iter<T> {
        self.into_iter()
    }
}

impl<T: StableDeref> FrozenVec<T> {
    /// Converts the frozen vector into a plain vector.
    pub fn into_vec(self) -> Vec<T> {
        self.vec.into_inner()
    }
}

impl<T: StableDeref> FrozenVec<T> {
    // binary search functions: they need to be reimplemented here to be safe (instead of calling
    // their equivalents directly on the underlying Vec), as they run user callbacks that could
    // reentrantly call other functions on this vector

    /// Binary searches this sorted vector for a given element, analogous to [slice::binary_search].
    pub fn binary_search(&self, x: &T::Target) -> Result<usize, usize>
    where
        T::Target: Ord,
    {
        self.binary_search_by(|p| p.cmp(x))
    }

    /// Binary searches this sorted vector with a comparator function, analogous to
    /// [slice::binary_search_by].
    pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
    where
        F: FnMut(&'a T::Target) -> Ordering,
    {
        let mut size = self.len();
        let mut left = 0;
        let mut right = size;
        while left < right {
            let mid = left + size / 2;

            // safety: like the core algorithm, mid is always within original vector len; in
            // pathlogical cases, user could push to the vector in the meantime, but this can only
            // increase the length, keeping this safe
            let cmp = f(unsafe { self.get_unchecked(mid) });

            if cmp == Ordering::Less {
                left = mid + 1;
            } else if cmp == Ordering::Greater {
                right = mid;
            } else {
                return Ok(mid);
            }

            size = right - left;
        }
        Err(left)
    }

    /// Binary searches this sorted vector with a key extraction function, analogous to
    /// [slice::binary_search_by_key].
    pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
    where
        F: FnMut(&'a T::Target) -> B,
        B: Ord,
    {
        self.binary_search_by(|k| f(k).cmp(b))
    }

    /// Returns the index of the partition point according to the given predicate
    /// (the index of the first element of the second partition), analogous to
    /// [slice::partition_point].
    pub fn partition_point<P>(&self, mut pred: P) -> usize
    where
        P: FnMut(&T::Target) -> bool,
    {
        let mut left = 0;
        let mut right = self.len();

        while left != right {
            let mid = left + (right - left) / 2;
            // safety: like in binary_search_by
            let value = unsafe { self.get_unchecked(mid) };
            if pred(value) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        left
    }

    // TODO add more
}

impl<T> std::convert::AsMut<Vec<T>> for FrozenVec<T> {
    /// Get mutable access to the underlying vector.
    ///
    /// This is safe, as it requires a `&mut self`, ensuring nothing is using
    /// the 'frozen' contents.
    fn as_mut(&mut self) -> &mut Vec<T> {
        unsafe { &mut *self.vec.get() }
    }
}

impl<T> Default for FrozenVec<T> {
    fn default() -> Self {
        FrozenVec::new()
    }
}

impl<T: Clone> Clone for FrozenVec<T> {
    fn clone(&self) -> Self {
        Self {
            vec: unsafe { self.vec.get().as_ref().unwrap() }.clone().into(),
        }
    }
}

impl<T> From<Vec<T>> for FrozenVec<T> {
    fn from(vec: Vec<T>) -> Self {
        Self {
            vec: UnsafeCell::new(vec),
        }
    }
}

impl<T: StableDeref> Index<usize> for FrozenVec<T> {
    type Output = T::Target;
    fn index(&self, idx: usize) -> &T::Target {
        self.get(idx).unwrap_or_else(|| {
            panic!(
                "index out of bounds: the len is {} but the index is {}",
                self.len(),
                idx
            )
        })
    }
}

impl<A> FromIterator<A> for FrozenVec<A> {
    fn from_iter<T>(iter: T) -> Self
    where
        T: IntoIterator<Item = A>,
    {
        let vec: Vec<_> = iter.into_iter().collect();
        vec.into()
    }
}

/// Iterator over FrozenVec, obtained via `.iter()`
///
/// It is safe to push to the vector during iteration
pub struct Iter<'a, T> {
    vec: &'a FrozenVec<T>,
    idx: usize,
}

impl<'a, T: StableDeref> Iterator for Iter<'a, T> {
    type Item = &'a T::Target;
    fn next(&mut self) -> Option<&'a T::Target> {
        if let Some(ret) = self.vec.get(self.idx) {
            self.idx += 1;
            Some(ret)
        } else {
            None
        }
    }
}

impl<'a, T: StableDeref> IntoIterator for &'a FrozenVec<T> {
    type Item = &'a T::Target;
    type IntoIter = Iter<'a, T>;
    fn into_iter(self) -> Iter<'a, T> {
        Iter { vec: self, idx: 0 }
    }
}

impl<T: StableDeref + PartialEq> PartialEq for FrozenVec<T>
where
    T::Target: PartialEq,
{
    fn eq(&self, other: &Self) -> bool {
        unsafe { self.vec.get().as_ref() == other.vec.get().as_ref() }
    }
}

#[test]
fn test_iteration() {
    let vec = vec!["a", "b", "c", "d"];
    let frozen: FrozenVec<_> = vec.clone().into();

    assert_eq!(vec, frozen.iter().collect::<Vec<_>>());
    for (e1, e2) in vec.iter().zip(frozen.iter()) {
        assert_eq!(*e1, e2);
    }

    assert_eq!(vec.len(), frozen.iter().count())
}

#[test]
fn test_accessors() {
    let vec: FrozenVec<String> = FrozenVec::new();

    assert!(vec.is_empty());
    assert_eq!(vec.len(), 0);
    assert_eq!(vec.first(), None);
    assert_eq!(vec.last(), None);
    assert_eq!(vec.get(1), None);

    vec.push("a".to_string());
    vec.push("b".to_string());
    vec.push("c".to_string());

    assert!(!vec.is_empty());
    assert_eq!(vec.len(), 3);
    assert_eq!(vec.first(), Some("a"));
    assert_eq!(vec.last(), Some("c"));
    assert_eq!(vec.get(1), Some("b"));
}

#[test]
fn test_non_stable_deref() {
    #[derive(Copy, Clone, Debug, PartialEq, Eq)]
    struct Moo(i32);
    let vec: FrozenVec<Moo> = FrozenVec::new();

    assert!(vec.is_empty());
    assert_eq!(vec.len(), 0);
    assert_eq!(vec.get_copy(1), None);

    vec.push(Moo(1));
    vec.push(Moo(2));
    vec.push(Moo(3));

    assert!(!vec.is_empty());
    assert_eq!(vec.len(), 3);
    assert_eq!(vec.get_copy(1), Some(Moo(2)));
}

#[test]
fn test_binary_search() {
    let vec: FrozenVec<_> = vec!["ab", "cde", "fghij"].into();

    assert_eq!(vec.binary_search("cde"), Ok(1));
    assert_eq!(vec.binary_search("cdf"), Err(2));
    assert_eq!(vec.binary_search("a"), Err(0));
    assert_eq!(vec.binary_search("g"), Err(3));

    assert_eq!(vec.binary_search_by_key(&1, |x| x.len()), Err(0));
    assert_eq!(vec.binary_search_by_key(&3, |x| x.len()), Ok(1));
    assert_eq!(vec.binary_search_by_key(&4, |x| x.len()), Err(2));

    assert_eq!(vec.partition_point(|x| x.len() < 4), 2);
    assert_eq!(vec.partition_point(|_| false), 0);
    assert_eq!(vec.partition_point(|_| true), 3);
}

Coverage Report

Created: 2026-01-25 06:45

Line	Count	Source
1		use std::cell::UnsafeCell;
2		use std::cmp::Ordering;
3		use std::iter::FromIterator;
4		use std::ops::Index;
5
6		use stable_deref_trait::StableDeref;
7
8		/// Append-only version of `std::vec::Vec` where
9		/// insertion does not require mutable access
10		pub struct FrozenVec<T> {
11		vec: UnsafeCell<Vec<T>>,
12		// XXXManishearth do we need a reentrancy guard here as well?
13		// StableDeref may not guarantee that there are no side effects
14		}
15
16		// safety: UnsafeCell implies !Sync
17
18		impl<T> FrozenVec<T> {
19		/// Constructs a new, empty vector.
20	0	pub const fn new() -> Self {
21	0	Self {
22	0	vec: UnsafeCell::new(Vec::new()),
23	0	}
24	0	} Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::Typed>>>::new Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::ctxt::StoredImport>>>::new Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::ctxt::StoredImportAlternative>>>::new
25		}
26
27		impl<T> FrozenVec<T> {
28		// these should never return &T
29		// these should never delete any entries
30
31		/// Appends an element to the back of the vector.
32	0	pub fn push(&self, val: T) {
33		unsafe {
34	0	let vec = self.vec.get();
35	0	(*vec).push(val)
36		}
37	0	} Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::Typed>>>::push Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::ctxt::StoredImport>>>::push Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::ctxt::StoredImportAlternative>>>::push
38		}
39
40		impl<T: StableDeref> FrozenVec<T> {
41		/// Push, immediately getting a reference to the element
42		pub fn push_get(&self, val: T) -> &T::Target {
43		unsafe {
44		let vec = self.vec.get();
45		(*vec).push(val);
46		&(&(vec).get_unchecked((vec).len() - 1) as const T::Target)
47		}
48		}
49
50		/// Returns a reference to an element.
51	0	pub fn get(&self, index: usize) -> Option<&T::Target> {
52		unsafe {
53	0	let vec = self.vec.get();
54	0	(vec).get(index).map(\|x\| &*x) Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::Typed>>>::get::{closure#0} Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::ctxt::StoredImport>>>::get::{closure#0} Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::ctxt::StoredImportAlternative>>>::get::{closure#0}
55		}
56	0	} Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::Typed>>>::get Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::ctxt::StoredImport>>>::get Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::ctxt::StoredImportAlternative>>>::get
57
58		/// Returns a reference to an element, without doing bounds checking.
59		///
60		/// ## Safety
61		///
62		/// `index` must be in bounds, i.e. it must be less than `self.len()`
63		pub unsafe fn get_unchecked(&self, index: usize) -> &T::Target {
64		let vec = self.vec.get();
65		(*vec).get_unchecked(index)
66		}
67		}
68
69		impl<T: Copy> FrozenVec<T> {
70		/// Returns a copy of an element.
71		pub fn get_copy(&self, index: usize) -> Option<T> {
72		unsafe {
73		let vec = self.vec.get();
74		(*vec).get(index).copied()
75		}
76		}
77		}
78
79		impl<T> FrozenVec<T> {
80		/// Returns the number of elements in the vector.
81	0	pub fn len(&self) -> usize {
82		unsafe {
83	0	let vec = self.vec.get();
84	0	(*vec).len()
85		}
86	0	} Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::Typed>>>::len Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::ctxt::StoredImport>>>::len Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::ctxt::StoredImportAlternative>>>::len
87
88		/// Returns `true` if the vector contains no elements.
89		pub fn is_empty(&self) -> bool {
90		self.len() == 0
91		}
92		}
93
94		impl<T: StableDeref> FrozenVec<T> {
95		/// Returns the first element of the vector, or `None` if empty.
96		pub fn first(&self) -> Option<&T::Target> {
97		unsafe {
98		let vec = self.vec.get();
99		(vec).first().map(\|x\| &*x)
100		}
101		}
102
103		/// Returns the last element of the vector, or `None` if empty.
104		pub fn last(&self) -> Option<&T::Target> {
105		unsafe {
106		let vec = self.vec.get();
107		(vec).last().map(\|x\| &*x)
108		}
109		}
110		/// Returns an iterator over the vector.
111		pub fn iter(&self) -> Iter<T> {
112		self.into_iter()
113		}
114		}
115
116		impl<T: StableDeref> FrozenVec<T> {
117		/// Converts the frozen vector into a plain vector.
118		pub fn into_vec(self) -> Vec<T> {
119		self.vec.into_inner()
120		}
121		}
122
123		impl<T: StableDeref> FrozenVec<T> {
124		// binary search functions: they need to be reimplemented here to be safe (instead of calling
125		// their equivalents directly on the underlying Vec), as they run user callbacks that could
126		// reentrantly call other functions on this vector
127
128		/// Binary searches this sorted vector for a given element, analogous to [slice::binary_search].
129		pub fn binary_search(&self, x: &T::Target) -> Result<usize, usize>
130		where
131		T::Target: Ord,
132		{
133		self.binary_search_by(\|p\| p.cmp(x))
134		}
135
136		/// Binary searches this sorted vector with a comparator function, analogous to
137		/// [slice::binary_search_by].
138		pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
139		where
140		F: FnMut(&'a T::Target) -> Ordering,
141		{
142		let mut size = self.len();
143		let mut left = 0;
144		let mut right = size;
145		while left < right {
146		let mid = left + size / 2;
147
148		// safety: like the core algorithm, mid is always within original vector len; in
149		// pathlogical cases, user could push to the vector in the meantime, but this can only
150		// increase the length, keeping this safe
151		let cmp = f(unsafe { self.get_unchecked(mid) });
152
153		if cmp == Ordering::Less {
154		left = mid + 1;
155		} else if cmp == Ordering::Greater {
156		right = mid;
157		} else {
158		return Ok(mid);
159		}
160
161		size = right - left;
162		}
163		Err(left)
164		}
165
166		/// Binary searches this sorted vector with a key extraction function, analogous to
167		/// [slice::binary_search_by_key].
168		pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
169		where
170		F: FnMut(&'a T::Target) -> B,
171		B: Ord,
172		{
173		self.binary_search_by(\|k\| f(k).cmp(b))
174		}
175
176		/// Returns the index of the partition point according to the given predicate
177		/// (the index of the first element of the second partition), analogous to
178		/// [slice::partition_point].
179		pub fn partition_point<P>(&self, mut pred: P) -> usize
180		where
181		P: FnMut(&T::Target) -> bool,
182		{
183		let mut left = 0;
184		let mut right = self.len();
185
186		while left != right {
187		let mid = left + (right - left) / 2;
188		// safety: like in binary_search_by
189		let value = unsafe { self.get_unchecked(mid) };
190		if pred(value) {
191		left = mid + 1;
192		} else {
193		right = mid;
194		}
195		}
196
197		left
198		}
199
200		// TODO add more
201		}
202
203		impl<T> std::convert::AsMut<Vec<T>> for FrozenVec<T> {
204		/// Get mutable access to the underlying vector.
205		///
206		/// This is safe, as it requires a `&mut self`, ensuring nothing is using
207		/// the 'frozen' contents.
208		fn as_mut(&mut self) -> &mut Vec<T> {
209		unsafe { &mut *self.vec.get() }
210		}
211		}
212
213		impl<T> Default for FrozenVec<T> {
214	0	fn default() -> Self {
215	0	FrozenVec::new()
216	0	} Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::Typed>> as core::default::Default>::default Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::ctxt::StoredImport>> as core::default::Default>::default Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::ctxt::StoredImportAlternative>> as core::default::Default>::default
217		}
218
219		impl<T: Clone> Clone for FrozenVec<T> {
220		fn clone(&self) -> Self {
221		Self {
222		vec: unsafe { self.vec.get().as_ref().unwrap() }.clone().into(),
223		}
224		}
225		}
226
227		impl<T> From<Vec<T>> for FrozenVec<T> {
228		fn from(vec: Vec<T>) -> Self {
229		Self {
230		vec: UnsafeCell::new(vec),
231		}
232		}
233		}
234
235		impl<T: StableDeref> Index<usize> for FrozenVec<T> {
236		type Output = T::Target;
237	0	fn index(&self, idx: usize) -> &T::Target {
238	0	self.get(idx).unwrap_or_else(\|\| {
239	0	panic!(
240	0	"index out of bounds: the len is {} but the index is {}",
241	0	self.len(), Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::Typed>> as core::ops::index::Index<usize>>::index::{closure#0} Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::ctxt::StoredImport>> as core::ops::index::Index<usize>>::index::{closure#0} Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::ctxt::StoredImportAlternative>> as core::ops::index::Index<usize>>::index::{closure#0}
242		idx
243		)
244		})
245	0	} Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::Typed>> as core::ops::index::Index<usize>>::index Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::ctxt::StoredImport>> as core::ops::index::Index<usize>>::index Unexecuted instantiation: <elsa::vec::FrozenVec<alloc::boxed::Box<dhall::ctxt::StoredImportAlternative>> as core::ops::index::Index<usize>>::index
246		}
247
248		impl<A> FromIterator<A> for FrozenVec<A> {
249		fn from_iter<T>(iter: T) -> Self
250		where
251		T: IntoIterator<Item = A>,
252		{
253		let vec: Vec<_> = iter.into_iter().collect();
254		vec.into()
255		}
256		}
257
258		/// Iterator over FrozenVec, obtained via `.iter()`
259		///
260		/// It is safe to push to the vector during iteration
261		pub struct Iter<'a, T> {
262		vec: &'a FrozenVec<T>,
263		idx: usize,
264		}
265
266		impl<'a, T: StableDeref> Iterator for Iter<'a, T> {
267		type Item = &'a T::Target;
268		fn next(&mut self) -> Option<&'a T::Target> {
269		if let Some(ret) = self.vec.get(self.idx) {
270		self.idx += 1;
271		Some(ret)
272		} else {
273		None
274		}
275		}
276		}
277
278		impl<'a, T: StableDeref> IntoIterator for &'a FrozenVec<T> {
279		type Item = &'a T::Target;
280		type IntoIter = Iter<'a, T>;
281		fn into_iter(self) -> Iter<'a, T> {
282		Iter { vec: self, idx: 0 }
283		}
284		}
285
286		impl<T: StableDeref + PartialEq> PartialEq for FrozenVec<T>
287		where
288		T::Target: PartialEq,
289		{
290		fn eq(&self, other: &Self) -> bool {
291		unsafe { self.vec.get().as_ref() == other.vec.get().as_ref() }
292		}
293		}
294
295		#[test]
296		fn test_iteration() {
297		let vec = vec!["a", "b", "c", "d"];
298		let frozen: FrozenVec<_> = vec.clone().into();
299
300		assert_eq!(vec, frozen.iter().collect::<Vec<_>>());
301		for (e1, e2) in vec.iter().zip(frozen.iter()) {
302		assert_eq!(*e1, e2);
303		}
304
305		assert_eq!(vec.len(), frozen.iter().count())
306		}
307
308		#[test]
309		fn test_accessors() {
310		let vec: FrozenVec<String> = FrozenVec::new();
311
312		assert!(vec.is_empty());
313		assert_eq!(vec.len(), 0);
314		assert_eq!(vec.first(), None);
315		assert_eq!(vec.last(), None);
316		assert_eq!(vec.get(1), None);
317
318		vec.push("a".to_string());
319		vec.push("b".to_string());
320		vec.push("c".to_string());
321
322		assert!(!vec.is_empty());
323		assert_eq!(vec.len(), 3);
324		assert_eq!(vec.first(), Some("a"));
325		assert_eq!(vec.last(), Some("c"));
326		assert_eq!(vec.get(1), Some("b"));
327		}
328
329		#[test]
330		fn test_non_stable_deref() {
331		#[derive(Copy, Clone, Debug, PartialEq, Eq)]
332		struct Moo(i32);
333		let vec: FrozenVec<Moo> = FrozenVec::new();
334
335		assert!(vec.is_empty());
336		assert_eq!(vec.len(), 0);
337		assert_eq!(vec.get_copy(1), None);
338
339		vec.push(Moo(1));
340		vec.push(Moo(2));
341		vec.push(Moo(3));
342
343		assert!(!vec.is_empty());
344		assert_eq!(vec.len(), 3);
345		assert_eq!(vec.get_copy(1), Some(Moo(2)));
346		}
347
348		#[test]
349		fn test_binary_search() {
350		let vec: FrozenVec<_> = vec!["ab", "cde", "fghij"].into();
351
352		assert_eq!(vec.binary_search("cde"), Ok(1));
353		assert_eq!(vec.binary_search("cdf"), Err(2));
354		assert_eq!(vec.binary_search("a"), Err(0));
355		assert_eq!(vec.binary_search("g"), Err(3));
356
357		assert_eq!(vec.binary_search_by_key(&1, \|x\| x.len()), Err(0));
358		assert_eq!(vec.binary_search_by_key(&3, \|x\| x.len()), Ok(1));
359		assert_eq!(vec.binary_search_by_key(&4, \|x\| x.len()), Err(2));
360
361		assert_eq!(vec.partition_point(\|x\| x.len() < 4), 2);
362		assert_eq!(vec.partition_point(\|_\| false), 0);
363		assert_eq!(vec.partition_point(\|_\| true), 3);
364		}