satellite_collections/generic/

fixed_set.rs

//! Fixed-capacity set implementation for allocation-free environments.
//!
//! This module provides [`FixedSet`], a set-like collection for storing unique elements
//! with compile-time capacity bounds, and [`FixedCapacitySet`], a trait for generic
//! set operations.

use crate::generic::push_pop::{PushPopCollection, PushPopError};
use std::fmt::Debug;

/// Error type for [`FixedSet`] operations.
#[derive(Debug, PartialEq, Eq)]
pub enum FixedSetError {
    /// The set has reached its maximum capacity.
    Full,
    /// The item already exists in the set.
    Duplicate,
}

impl From<FixedSetError> for u32 {
    fn from(e: FixedSetError) -> Self {
        match e {
            FixedSetError::Full => 1,
            FixedSetError::Duplicate => 2,
        }
    }
}

impl std::fmt::Display for FixedSetError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{:?}", self)
    }
}

/// Generic trait for fixed-capacity set operations.
///
/// This trait provides a common interface for set-like collections with compile-time
/// capacity bounds. It's implemented by both [`FixedSet`] and types generated by
/// the [`declare_fixed_set!`] macro.
///
/// # Examples
///
/// ```rust
/// use satellite_bitcoin::generic::fixed_set::{FixedSet, FixedCapacitySet};
///
/// fn work_with_set<S: FixedCapacitySet<Item = i32>>(set: &mut S) {
///     set.insert(42).unwrap();
///     set.insert(100).unwrap();
///     assert_eq!(set.len(), 2);
///     assert!(set.contains(&42));
/// }
///
/// let mut set = FixedSet::<i32, 10>::new();
/// work_with_set(&mut set);
/// ```
///
/// [`declare_fixed_set!`]: crate::declare_fixed_set
pub trait FixedCapacitySet: Default + Clone + Debug {
    /// The element type stored in the set.
    type Item: Copy + PartialEq + Default;

    /// Maximum number of elements the set can hold.
    fn capacity(&self) -> usize;

    /// Current number of stored elements.
    fn len(&self) -> usize;

    /// Check whether the set currently contains `item`.
    fn contains<Q>(&self, item: &Q) -> bool
    where
        Self::Item: PartialEq<Q>;

    /// Find the first item equal to `item` in the set.
    fn find<Q>(&self, item: &Q) -> Option<&Self::Item>
    where
        Self::Item: PartialEq<Q>;

    /// Find the first item equal to `item` in the set and return it.
    fn find_mut<Q>(&mut self, item: &Q) -> Option<&mut Self::Item>
    where
        Self::Item: PartialEq<Q>;

    /// Attempt to insert `item`.
    /// Returns `Ok(())` on success or an appropriate [`FixedSetError`].
    fn insert(&mut self, item: Self::Item) -> Result<(), FixedSetError>;

    /// Inserts `item` into the set if it is not already present.
    /// If it is present, modifies it using the provided function.
    /// Returns `Ok(())` on success or an appropriate [`FixedSetError`].
    fn insert_or_modify<E, F>(&mut self, item: Self::Item, modify: F) -> Result<(), E>
    where
        F: FnMut(&mut Self::Item) -> Result<(), E>,
        E: From<FixedSetError>;

    /// Remove `item` if present, returning it.
    fn remove<Q>(&mut self, item: &Q) -> Option<Self::Item>
    where
        Self::Item: PartialEq<Q>;

    /// Access the underlying slice of active items.
    fn as_slice(&self) -> &[Self::Item];

    /// Returns the elements of the set as a mutable slice.
    fn as_mut_slice(&mut self) -> &mut [Self::Item];

    /// Iterate over the set.
    fn iter(&self) -> impl Iterator<Item = &Self::Item> {
        self.as_slice().iter()
    }

    /// Iterate over the set mutably.
    fn iter_mut(&mut self) -> impl Iterator<Item = &mut Self::Item> + '_ {
        self.as_mut_slice().iter_mut()
    }
}

/// A fixed-capacity set for storing unique elements.
///
/// `FixedSet` maintains a collection of unique elements with compile-time capacity bounds.
/// It provides efficient insertion, removal, and lookup operations while maintaining
/// element uniqueness.
///
/// # Type Parameters
///
/// * `T` - The element type. Must implement `Default + Copy + PartialEq`.
/// * `SIZE` - The maximum number of elements the set can hold (compile-time constant).
///
/// # Examples
///
/// ```rust
/// use satellite_bitcoin::generic::fixed_set::FixedSet;
///
/// let mut set: FixedSet<u32, 8> = FixedSet::new();
///
/// set.insert(3).unwrap();
/// set.insert(5).unwrap();
/// assert!(set.contains(&3));
/// assert_eq!(set.len(), 2);
///
/// // Duplicate insertion fails
/// assert!(set.insert(3).is_err());
///
/// // Remove elements
/// assert_eq!(set.remove(&3), Some(3));
/// assert_eq!(set.len(), 1);
/// ```
///
/// # Memory Layout
///
/// The set stores elements in a contiguous array followed by a length field.
/// Element order is not preserved across insertions and removals due to the
/// swap-remove optimization used for O(1) removal.
///
/// # Bytemuck Compatibility
///
/// `FixedSet` implements `Pod` and `Zeroable` when `T` implements these traits,
/// making it suitable for zero-copy serialization in on-chain programs.
#[derive(Debug, Clone, Copy)]
#[repr(C)]
pub struct FixedSet<T, const SIZE: usize> {
    items: [T; SIZE],
    len: usize,
    _padding: [u8; 8],
}

impl<T: Default + Copy + PartialEq, const SIZE: usize> Default for FixedSet<T, SIZE> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T: Default + Copy + PartialEq, const SIZE: usize> FixedSet<T, SIZE> {
    /// Creates an empty `FixedSet`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use satellite_bitcoin::generic::fixed_set::FixedSet;
    ///
    /// let set: FixedSet<u32, 10> = FixedSet::new();
    /// assert!(set.is_empty());
    /// assert_eq!(set.len(), 0);
    /// ```
    pub fn new() -> Self {
        Self {
            items: [T::default(); SIZE],
            len: 0,
            _padding: [0; 8],
        }
    }

    /// Returns the number of elements currently stored in the set.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use satellite_bitcoin::generic::fixed_set::FixedSet;
    ///
    /// let mut set: FixedSet<u32, 10> = FixedSet::new();
    /// assert_eq!(set.len(), 0);
    ///
    /// set.insert(42).unwrap();
    /// assert_eq!(set.len(), 1);
    /// ```
    pub fn len(&self) -> usize {
        self.len
    }

    /// Returns `true` if the set contains no elements.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use satellite_bitcoin::generic::fixed_set::FixedSet;
    ///
    /// let mut set: FixedSet<u32, 10> = FixedSet::new();
    /// assert!(set.is_empty());
    ///
    /// set.insert(42).unwrap();
    /// assert!(!set.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Returns an iterator over all items currently in the set.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use satellite_bitcoin::generic::fixed_set::FixedSet;
    ///
    /// let mut set: FixedSet<u32, 10> = FixedSet::new();
    /// set.insert(1).unwrap();
    /// set.insert(2).unwrap();
    ///
    /// let collected: Vec<_> = set.iter().copied().collect();
    /// assert_eq!(collected.len(), 2);
    /// assert!(collected.contains(&1));
    /// assert!(collected.contains(&2));
    /// ```
    pub fn iter(&self) -> impl Iterator<Item = &T> + '_ {
        self.items[..self.len].iter()
    }

    /// Returns a mutable iterator over all items currently in the set.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use satellite_bitcoin::generic::fixed_set::FixedSet;
    ///
    /// let mut set: FixedSet<u32, 10> = FixedSet::new();
    /// set.insert(1).unwrap();
    /// set.insert(2).unwrap();
    ///
    /// for item in set.iter_mut() {
    ///     *item *= 10;
    /// }
    ///
    /// assert!(set.contains(&10));
    /// assert!(set.contains(&20));
    /// ```
    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> + '_ {
        self.items[..self.len].iter_mut()
    }

    /// Inserts `item` into the set if it is not already present.
    /// If it is present, modifies it using the provided function.
    ///
    /// This is useful for implementing "upsert" semantics where you want to
    /// insert a new item or update an existing one.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use satellite_bitcoin::generic::fixed_set::{FixedSet, FixedSetError};
    ///
    /// #[derive(Clone, Copy, Debug, Default)]
    /// struct Counter { id: u32, count: u32 }
    ///
    /// impl PartialEq for Counter {
    ///     fn eq(&self, other: &Self) -> bool {
    ///         self.id == other.id // Only compare by ID
    ///     }
    /// }
    ///
    /// impl Eq for Counter {}
    ///
    /// #[derive(Debug)]
    /// enum MyError {
    ///     SetError(FixedSetError),
    /// }
    ///
    /// impl From<FixedSetError> for MyError {
    ///     fn from(e: FixedSetError) -> Self {
    ///         MyError::SetError(e)
    ///     }
    /// }
    ///
    /// let mut set: FixedSet<Counter, 10> = FixedSet::new();
    ///
    /// // Insert new item
    /// set.insert_or_modify(
    ///     Counter { id: 1, count: 1 },
    ///     |_| Ok::<(), MyError>(())
    /// ).unwrap();
    ///
    /// // Update existing item
    /// set.insert_or_modify(
    ///     Counter { id: 1, count: 0 }, // count doesn't matter for lookup
    ///     |existing| { existing.count += 1; Ok::<(), MyError>(()) }
    /// ).unwrap();
    ///
    /// assert_eq!(set.find(&Counter { id: 1, count: 0 }).unwrap().count, 2);
    /// ```
    pub fn insert_or_modify<E, F>(&mut self, item: T, mut modify: F) -> Result<(), E>
    where
        F: FnMut(&mut T) -> Result<(), E>,
        E: From<FixedSetError>,
    {
        if self.contains(&item) {
            let pos = self.iter().position(|i| *i == item).unwrap();
            modify(&mut self.items[pos])?;
        } else {
            self.insert(item).map_err(E::from)?;
        }

        Ok(())
    }

    /// Returns `true` if the set already contains `item`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use satellite_bitcoin::generic::fixed_set::FixedSet;
    ///
    /// let mut set: FixedSet<u32, 10> = FixedSet::new();
    /// assert!(!set.contains(&42));
    ///
    /// set.insert(42).unwrap();
    /// assert!(set.contains(&42));
    /// ```
    pub fn contains<Q>(&self, item: &Q) -> bool
    where
        T: PartialEq<Q>,
    {
        self.iter().any(|i| i == item)
    }

    /// Returns the first item equal to `item` in the set.
    ///
    /// This is useful when you need to access the actual stored item that matches
    /// your query, especially when using custom equality implementations.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use satellite_bitcoin::generic::fixed_set::FixedSet;
    ///
    /// let mut set: FixedSet<u32, 10> = FixedSet::new();
    /// set.insert(42).unwrap();
    ///
    /// assert_eq!(set.find(&42), Some(&42));
    /// assert_eq!(set.find(&99), None);
    /// ```
    pub fn find<Q>(&self, item: &Q) -> Option<&T>
    where
        T: PartialEq<Q>,
    {
        self.iter().find(|i| *i == item)
    }

    /// Returns the first item equal to `item` in the set (mutable reference).
    ///
    /// # Examples
    ///
    /// ```rust
    /// use satellite_bitcoin::generic::fixed_set::FixedSet;
    ///
    /// let mut set: FixedSet<u32, 10> = FixedSet::new();
    /// set.insert(42).unwrap();
    ///
    /// if let Some(item) = set.find_mut(&42) {
    ///     *item = 100;
    /// }
    ///
    /// assert!(set.contains(&100));
    /// assert!(!set.contains(&42));
    /// ```
    pub fn find_mut<Q>(&mut self, item: &Q) -> Option<&mut T>
    where
        T: PartialEq<Q>,
    {
        self.iter_mut().find(|i| *i == item)
    }

    /// Attempts to insert `item` into the set.
    ///
    /// # Errors
    ///
    /// * Returns `Err(FixedSetError::Duplicate)` if the item already exists in the set.
    /// * Returns `Err(FixedSetError::Full)` if the set is at full capacity.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use satellite_bitcoin::generic::fixed_set::{FixedSet, FixedSetError};
    ///
    /// let mut set: FixedSet<u32, 2> = FixedSet::new();
    /// assert!(set.insert(1).is_ok());
    /// assert!(set.insert(2).is_ok());
    ///
    /// // Duplicate
    /// assert_eq!(set.insert(1), Err(FixedSetError::Duplicate));
    /// // Full
    /// assert_eq!(set.insert(3), Err(FixedSetError::Full));
    /// ```
    pub fn insert(&mut self, item: T) -> Result<(), FixedSetError> {
        if self.contains(&item) {
            return Err(FixedSetError::Duplicate);
        }
        if self.len >= SIZE {
            return Err(FixedSetError::Full);
        }
        self.items[self.len] = item;
        self.len += 1;
        Ok(())
    }

    /// Removes an item equal to `item` from the set and returns it.
    ///
    /// Uses swap-remove for O(1) performance, which means element order is not preserved.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use satellite_bitcoin::generic::fixed_set::FixedSet;
    ///
    /// let mut set: FixedSet<u32, 10> = FixedSet::new();
    /// set.insert(42).unwrap();
    ///
    /// assert_eq!(set.remove(&42), Some(42));
    /// assert_eq!(set.remove(&42), None);
    /// assert_eq!(set.len(), 0);
    /// ```
    pub fn remove<Q>(&mut self, item: &Q) -> Option<T>
    where
        T: PartialEq<Q>,
    {
        // Search for the item index without creating an iterator that borrows `self`.
        let pos_opt = (0..self.len).find(|&i| self.items[i] == *item);
        if let Some(pos) = pos_opt {
            // Swap-remove: replace the removed element with the last one to keep O(1) removal.
            let removed = self.items[pos];
            self.len -= 1;
            if pos != self.len {
                self.items[pos] = self.items[self.len];
            }
            Some(removed)
        } else {
            None
        }
    }

    /// Removes and returns an arbitrary element from the set (the last one).
    pub fn pop(&mut self) -> Option<T> {
        if self.len > 0 {
            self.len -= 1;
            Some(self.items[self.len])
        } else {
            None
        }
    }

    /// Returns the elements of the set as a slice.
    pub fn as_slice(&self) -> &[T] {
        &self.items[..self.len]
    }

    /// Returns the elements of the set as a mutable slice.
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        &mut self.items[..self.len]
    }

    /// Creates a [`FixedSet`] from any iterator, returning an error if the
    /// number of unique elements exceeds the set's capacity.
    ///
    /// Duplicate elements yielded by the iterator are ignored (because a set
    /// cannot contain the same value twice). However, if inserting additional
    /// *unique* elements would exceed the compile-time capacity `SIZE`, the
    /// construction fails with [`FixedSetError::Full`].
    pub fn try_from_iter<I>(iter: I) -> Result<Self, FixedSetError>
    where
        I: IntoIterator<Item = T>,
    {
        let mut set = Self::new();
        for item in iter {
            match set.insert(item) {
                Ok(()) | Err(FixedSetError::Duplicate) => {}
                Err(FixedSetError::Full) => return Err(FixedSetError::Full),
            }
        }
        Ok(set)
    }

    /// Returns a reference to the **first** element in the set (if any).
    ///
    /// This is a convenience helper useful when the set is known to hold at
    /// most one element (e.g. single‐rune outputs). It avoids having to call
    /// `as_slice().first()` at every call-site.
    #[inline]
    pub fn get(&self) -> Option<&T> {
        self.as_slice().first()
    }
}

impl<T: Default + Copy + PartialEq, const SIZE: usize> PushPopCollection<T> for FixedSet<T, SIZE> {
    fn push(&mut self, item: T) -> Result<(), PushPopError> {
        match self.insert(item) {
            Ok(()) => Ok(()),
            Err(FixedSetError::Full) => Err(PushPopError::Full),
            // Treat duplicate insertions as a no-op success for the generic API.
            Err(FixedSetError::Duplicate) => Ok(()),
        }
    }

    fn pop(&mut self) -> Option<T> {
        self.pop()
    }

    fn as_slice(&self) -> &[T] {
        self.as_slice()
    }

    fn len(&self) -> usize {
        self.len()
    }

    fn max_size(&self) -> usize {
        SIZE
    }
}

impl<T: Default + Copy + PartialEq + Debug, const SIZE: usize> FixedCapacitySet
    for FixedSet<T, SIZE>
{
    type Item = T;

    fn capacity(&self) -> usize {
        SIZE
    }

    fn len(&self) -> usize {
        self.len()
    }

    fn contains<Q>(&self, item: &Q) -> bool
    where
        Self::Item: PartialEq<Q>,
    {
        self.contains(item)
    }

    fn find<Q>(&self, item: &Q) -> Option<&Self::Item>
    where
        Self::Item: PartialEq<Q>,
    {
        self.find(item)
    }

    fn find_mut<Q>(&mut self, item: &Q) -> Option<&mut Self::Item>
    where
        Self::Item: PartialEq<Q>,
    {
        self.find_mut(item)
    }

    fn insert(&mut self, item: Self::Item) -> Result<(), FixedSetError> {
        self.insert(item)
    }

    fn insert_or_modify<E, F>(&mut self, item: Self::Item, modify: F) -> Result<(), E>
    where
        F: FnMut(&mut Self::Item) -> Result<(), E>,
        E: From<FixedSetError>,
    {
        self.insert_or_modify(item, modify)
    }

    fn remove<Q>(&mut self, item: &Q) -> Option<Self::Item>
    where
        Self::Item: PartialEq<Q>,
    {
        self.remove(item)
    }

    fn as_slice(&self) -> &[Self::Item] {
        self.as_slice()
    }

    fn as_mut_slice(&mut self) -> &mut [Self::Item] {
        self.as_mut_slice()
    }
}

// SAFETY: FixedSet is `Pod` if its items are `Pod` and it is `repr(C)` with
// no padding between fields that contain invalid bytes. The `items` array is
// `Pod` when `T` is `Pod`. Both `usize` and arrays of `Pod` types are `Pod`,
// so the struct as a whole is `Pod`.
unsafe impl<T: bytemuck::Pod, const SIZE: usize> bytemuck::Pod for FixedSet<T, SIZE> {}

// SAFETY: A `Zeroable` type must have all-bits-zero represent a valid value.
// Because `FixedSet::default()` sets `len` to 0 and the `items` array to all
// `T::default()`, zeroing the entire struct is sound when `T` itself is
// `Zeroable` (all-bits-zero is a valid representation for `T`).
unsafe impl<T: bytemuck::Zeroable, const SIZE: usize> bytemuck::Zeroable for FixedSet<T, SIZE> {}

// Conversions to/from FixedList
impl<T: Default + Copy + PartialEq, const SIZE: usize>
    From<crate::generic::fixed_list::FixedList<T, SIZE>> for FixedSet<T, SIZE>
{
    fn from(list: crate::generic::fixed_list::FixedList<T, SIZE>) -> Self {
        let mut set = Self::new();
        for item in list.as_slice().iter().copied() {
            let _ = set.insert(item);
        }
        set
    }
}

// Try to build a FixedSet from a slice. Deduplicates; errors on overflow of unique elements.
impl<T: Default + Copy + PartialEq, const SIZE: usize> core::convert::TryFrom<&[T]>
    for FixedSet<T, SIZE>
{
    type Error = FixedSetError;

    fn try_from(slice: &[T]) -> Result<Self, Self::Error> {
        let mut set = Self::new();
        for &item in slice.iter() {
            match set.insert(item) {
                Ok(()) | Err(FixedSetError::Duplicate) => {}
                Err(FixedSetError::Full) => return Err(FixedSetError::Full),
            }
        }
        Ok(set)
    }
}

#[cfg(test)]
mod from_slice_tests {
    use super::*;

    #[test]
    fn set_try_from_slice_dedups_and_caps() {
        let data = [1u32, 2, 2, 3, 4];
        let set = <FixedSet<u32, 3>>::try_from(&data[..]).unwrap();
        assert_eq!(set.len(), 3);
        assert!(set.contains(&1) && set.contains(&2) && set.contains(&3));
    }

    #[test]
    fn set_try_from_slice_errors_on_overflow() {
        let data = [1u32, 2, 3, 4];
        let res = <FixedSet<u32, 3>>::try_from(&data[..]);
        assert!(matches!(res, Err(FixedSetError::Full)));
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_default_is_empty() {
        let set = FixedSet::<u32, 4>::default();
        assert_eq!(set.len(), 0);
        assert!(set.is_empty());
    }

    #[test]
    fn test_insert_and_len() {
        let mut set = FixedSet::<u32, 3>::new();
        assert!(set.insert(10).is_ok());
        assert!(set.insert(20).is_ok());
        assert_eq!(set.len(), 2);
        assert!(!set.is_empty());
        assert!(set.contains(&10));
        assert!(set.contains(&20));
    }

    #[test]
    fn test_duplicate_insertion() {
        let mut set = FixedSet::<u32, 2>::new();
        assert!(set.insert(1).is_ok());
        assert_eq!(set.insert(1), Err(FixedSetError::Duplicate));
        assert_eq!(set.len(), 1);
    }

    #[test]
    fn test_insert_past_capacity() {
        let mut set = FixedSet::<u32, 2>::new();
        assert!(set.insert(1).is_ok());
        assert!(set.insert(2).is_ok());
        assert_eq!(set.insert(3), Err(FixedSetError::Full));
        assert_eq!(set.len(), 2);
    }

    #[test]
    fn test_remove() {
        let mut set = FixedSet::<u32, 3>::new();
        set.insert(5).unwrap();
        set.insert(10).unwrap();
        assert_eq!(set.remove(&5), Some(5));
        assert!(!set.contains(&5));
        assert_eq!(set.len(), 1);
    }

    #[test]
    fn test_pop() {
        let mut set = FixedSet::<u32, 2>::new();
        assert_eq!(set.pop(), None);

        set.insert(100).unwrap();
        set.insert(200).unwrap();
        let first = set.pop();
        let second = set.pop();
        assert!(matches!(
            (first, second),
            (Some(200), Some(100)) | (Some(100), Some(200))
        ));
        assert!(set.is_empty());
    }

    #[test]
    fn test_push_pop_collection_trait() {
        let mut set = FixedSet::<u8, 2>::new();
        PushPopCollection::push(&mut set, 1).unwrap();
        PushPopCollection::push(&mut set, 2).unwrap();
        PushPopCollection::push(&mut set, 2).unwrap(); // duplicate ignored
        assert_eq!(PushPopCollection::len(&set), 2);
        let slice = PushPopCollection::as_slice(&set);
        assert!(slice.contains(&1) && slice.contains(&2));
        PushPopCollection::pop(&mut set);
        PushPopCollection::pop(&mut set);
        assert_eq!(PushPopCollection::pop(&mut set), None);
    }

    #[test]
    fn test_try_from_iter() {
        // Successful construction within capacity
        let data = vec![1, 2, 3];
        let set = FixedSet::<u32, 3>::try_from_iter(data).unwrap();
        assert_eq!(set.len(), 3);
        assert!(set.contains(&1) && set.contains(&2) && set.contains(&3));

        // Construction that exceeds capacity should error
        let too_many = vec![1, 2, 3, 4];
        let res = FixedSet::<u32, 3>::try_from_iter(too_many);
        assert!(matches!(res, Err(FixedSetError::Full)));
    }

    #[test]
    fn test_generic_search_methods() {
        // Create a simple type that implements PartialEq with another type
        #[derive(Debug, Clone, Copy, PartialEq, Default)]
        struct SimpleItem {
            id: u32,
            value: u32,
        }

        #[derive(Debug, Clone, Copy, PartialEq)]
        struct SimpleItemId(u32);

        impl PartialEq<SimpleItemId> for SimpleItem {
            fn eq(&self, other: &SimpleItemId) -> bool {
                self.id == other.0
            }
        }

        let mut set = FixedSet::<SimpleItem, 3>::new();
        let item1 = SimpleItem { id: 1, value: 10 };
        let item2 = SimpleItem { id: 2, value: 20 };

        set.insert(item1).unwrap();
        set.insert(item2).unwrap();

        let search_id = SimpleItemId(1);

        // Test contains
        assert!(set.contains(&search_id));
        assert!(!set.contains(&SimpleItemId(999)));

        // Test find
        let found = set.find(&search_id);
        assert_eq!(found, Some(&item1));

        // Test find_mut
        let found_mut = set.find_mut(&search_id);
        assert!(found_mut.is_some());
        if let Some(found_item) = found_mut {
            found_item.value = 999;
        }

        // Verify the modification worked
        let found_again = set.find(&search_id);
        assert_eq!(found_again.unwrap().value, 999);

        // Test remove
        let removed = set.remove(&SimpleItemId(2));
        assert_eq!(removed, Some(item2));
        assert!(!set.contains(&SimpleItemId(2)));
        assert_eq!(set.len(), 1);
    }
}