planter-core 0.0.7

//! Helpers for keeping a `Vec` of id-carrying items in a caller-controlled order: replace an
//! existing entry by id instead of duplicating it, insert relative to a sibling, remove by id,
//! or move an entry after another. Order lives in the `Vec` itself; identity comes from each
//! item's own id, so there's nothing else to keep in sync with it.

use anyhow::{Context, ensure};
use uuid::Uuid;

/// A type with a stable identity, usable as the key when it's stored in one of these `Vec`s.
pub(crate) trait Identifiable {
    fn id(&self) -> Uuid;
}

/// Returns the item with the given id, if present.
pub(crate) fn find<T: Identifiable>(items: &[T], id: Uuid) -> Option<&T> {
    items.iter().find(|item| item.id() == id)
}

/// Returns a mutable reference to the item with the given id, if present.
pub(crate) fn find_mut<T: Identifiable>(items: &mut [T], id: Uuid) -> Option<&mut T> {
    items.iter_mut().find(|item| item.id() == id)
}

/// Returns whether an item with the given id is present.
pub(crate) fn contains<T: Identifiable>(items: &[T], id: Uuid) -> bool {
    find(items, id).is_some()
}

/// Inserts `item`, replacing any existing entry with the same id in place, or appending it
/// otherwise.
pub(crate) fn upsert<T: Identifiable>(items: &mut Vec<T>, item: T) {
    match find_mut(items, item.id()) {
        Some(slot) => *slot = item,
        None => items.push(item),
    }
}

/// Inserts a new `item` immediately before the entry with id `sibling`. This only ever adds an
/// item, it never moves an existing one.
///
/// # Errors
///
/// Returns an error if `sibling` isn't present, or if `item`'s id is already present.
pub(crate) fn insert_before<T: Identifiable>(
    items: &mut Vec<T>,
    item: T,
    sibling: Uuid,
) -> anyhow::Result<()> {
    ensure!(
        !items.iter().any(|i| i.id() == item.id()),
        "Item id already present"
    );
    let pos = items
        .iter()
        .position(|i| i.id() == sibling)
        .context("Sibling not found")?;
    items.insert(pos, item);
    Ok(())
}

/// As [`insert_before`], but positions `item` immediately after `sibling`.
///
/// # Errors
///
/// Returns an error if `sibling` isn't present, or if `item`'s id is already present.
pub(crate) fn insert_after<T: Identifiable>(
    items: &mut Vec<T>,
    item: T,
    sibling: Uuid,
) -> anyhow::Result<()> {
    ensure!(
        !items.iter().any(|i| i.id() == item.id()),
        "Item id already present"
    );
    let pos = items
        .iter()
        .position(|i| i.id() == sibling)
        .context("Sibling not found")?;
    items.insert(pos + 1, item);
    Ok(())
}

/// Removes the entry with the given id, returning it, or `None` if it wasn't present.
pub(crate) fn remove_by_id<T: Identifiable>(items: &mut Vec<T>, id: Uuid) -> Option<T> {
    let pos = items.iter().position(|i| i.id() == id)?;
    Some(items.remove(pos))
}

/// Moves the entry with id `id` to immediately after the entry with id `after`.
///
/// # Errors
///
/// Returns an error if `id` or `after` isn't present, or if they're the same (there's nothing
/// to move relative to).
pub(crate) fn move_after<T: Identifiable>(
    items: &mut Vec<T>,
    id: Uuid,
    after: Uuid,
) -> anyhow::Result<()> {
    ensure!(id != after, "Cannot move an id after itself");
    let moved_from = items
        .iter()
        .position(|i| i.id() == id)
        .context("Id not found")?;
    let after_before_removal = items
        .iter()
        .position(|i| i.id() == after)
        .context("After id not found")?;

    let moved_item = items.remove(moved_from);
    // Removing `moved_from` shifted everything past it left by one, so if `after` was past the
    // moved item, its position shifted down by one too.
    let after_now = if after_before_removal > moved_from {
        after_before_removal - 1
    } else {
        after_before_removal
    };
    items.insert(after_now + 1, moved_item);
    Ok(())
}

#[cfg(test)]
mod tests {
    use proptest::prelude::*;
    use rand::{RngExt, rng};

    use super::{
        Identifiable, find, find_mut, insert_after, insert_before, move_after, remove_by_id, upsert,
    };

    #[derive(Debug, Clone, PartialEq, Eq)]
    struct Item(u32, &'static str);

    impl Identifiable for Item {
        fn id(&self) -> uuid::Uuid {
            // Tests use plain u32 keys folded into a Uuid for readability.
            uuid::Uuid::from_u128(u128::from(self.0))
        }
    }

    fn id(n: u32) -> uuid::Uuid {
        uuid::Uuid::from_u128(u128::from(n))
    }

    fn labels(items: &[Item]) -> Vec<&'static str> {
        items.iter().map(|i| i.1).collect()
    }

    /// A vec of items with unique, sequential ids (`0..n`), of a random length.
    fn item_vec_strategy() -> impl Strategy<Value = Vec<Item>> {
        (2usize..15).prop_map(|n| (0..n as u32).map(|i| Item(i, "item")).collect())
    }

    #[test]
    fn upsert_appends_new_items_in_order() {
        let mut items = Vec::new();
        upsert(&mut items, Item(1, "a"));
        upsert(&mut items, Item(2, "b"));
        upsert(&mut items, Item(3, "c"));
        assert_eq!(labels(&items), vec!["a", "b", "c"]);
    }

    #[test]
    fn upsert_replaces_an_existing_id_in_place() {
        let mut items = vec![Item(1, "a"), Item(2, "b"), Item(3, "c")];
        upsert(&mut items, Item(2, "B"));
        assert_eq!(labels(&items), vec!["a", "B", "c"]);
    }

    #[test]
    fn find_and_find_mut_locate_by_id() {
        let mut items = vec![Item(1, "a"), Item(2, "b")];
        assert_eq!(find(&items, id(2)), Some(&Item(2, "b")));
        assert_eq!(find(&items, id(99)), None);
        find_mut(&mut items, id(1)).unwrap().1 = "A";
        assert_eq!(labels(&items), vec!["A", "b"]);
    }

    #[test]
    fn remove_by_id_drops_the_entry_and_keeps_the_rest_in_order() {
        let mut items = vec![Item(1, "a"), Item(2, "b"), Item(3, "c")];
        assert_eq!(remove_by_id(&mut items, id(2)), Some(Item(2, "b")));
        assert_eq!(labels(&items), vec!["a", "c"]);
        assert_eq!(remove_by_id(&mut items, id(2)), None);
    }

    #[test]
    fn insert_before_rejects_an_unknown_sibling() {
        let mut items = vec![Item(1, "a"), Item(2, "b")];
        assert!(insert_before(&mut items, Item(3, "c"), id(99)).is_err());
        assert_eq!(labels(&items), vec!["a", "b"]);
    }

    #[test]
    fn insert_after_rejects_an_unknown_sibling() {
        let mut items = vec![Item(1, "a"), Item(2, "b")];
        assert!(insert_after(&mut items, Item(3, "c"), id(99)).is_err());
        assert_eq!(labels(&items), vec!["a", "b"]);
    }

    #[test]
    fn insert_before_rejects_an_id_already_present() {
        let mut items = vec![Item(1, "a"), Item(2, "b")];
        assert!(insert_before(&mut items, Item(2, "B"), id(1)).is_err());
        assert_eq!(labels(&items), vec!["a", "b"]);
    }

    #[test]
    fn insert_after_rejects_an_id_already_present() {
        let mut items = vec![Item(1, "a"), Item(2, "b")];
        assert!(insert_after(&mut items, Item(2, "B"), id(1)).is_err());
        assert_eq!(labels(&items), vec!["a", "b"]);
    }

    #[test]
    fn move_after_rejects_identical_ids() {
        let mut items = vec![Item(1, "a"), Item(2, "b"), Item(3, "c")];
        assert!(move_after(&mut items, id(1), id(1)).is_err());
        assert_eq!(labels(&items), vec!["a", "b", "c"]);
    }

    #[test]
    fn move_after_rejects_an_unknown_id() {
        let mut items = vec![Item(1, "a"), Item(2, "b"), Item(3, "c")];
        assert!(move_after(&mut items, id(99), id(2)).is_err());
        assert_eq!(labels(&items), vec!["a", "b", "c"]);
    }

    #[test]
    fn move_after_rejects_an_unknown_after() {
        let mut items = vec![Item(1, "a"), Item(2, "b"), Item(3, "c")];
        assert!(move_after(&mut items, id(1), id(99)).is_err());
        assert_eq!(labels(&items), vec!["a", "b", "c"]);
    }

    proptest! {
        #[test]
        fn insert_before_positions_the_new_item_immediately_before_the_sibling(
            mut items in item_vec_strategy(),
        ) {
            let n = items.len();
            let sibling = items[rng().random_range(0..n)].id();
            let original_ids: Vec<uuid::Uuid> = items.iter().map(Identifiable::id).collect();

            insert_before(&mut items, Item(n as u32, "new"), sibling).unwrap();

            let new_pos = items.iter().position(|i| i.id() == id(n as u32)).unwrap();
            let sibling_pos = items.iter().position(|i| i.id() == sibling).unwrap();
            assert_eq!(new_pos + 1, sibling_pos);

            let remaining_ids: Vec<uuid::Uuid> = items
                .iter()
                .map(Identifiable::id)
                .filter(|&i| i != id(n as u32))
                .collect();
            assert_eq!(remaining_ids, original_ids);
        }

        #[test]
        fn insert_after_positions_the_new_item_immediately_after_the_sibling(
            mut items in item_vec_strategy(),
        ) {
            let n = items.len();
            let sibling = items[rng().random_range(0..n)].id();
            let original_ids: Vec<uuid::Uuid> = items.iter().map(Identifiable::id).collect();

            insert_after(&mut items, Item(n as u32, "new"), sibling).unwrap();

            let new_pos = items.iter().position(|i| i.id() == id(n as u32)).unwrap();
            let sibling_pos = items.iter().position(|i| i.id() == sibling).unwrap();
            assert_eq!(sibling_pos + 1, new_pos);

            let remaining_ids: Vec<uuid::Uuid> = items
                .iter()
                .map(Identifiable::id)
                .filter(|&i| i != id(n as u32))
                .collect();
            assert_eq!(remaining_ids, original_ids);
        }

        #[test]
        fn move_after_reorders_correctly(mut items in item_vec_strategy()) {
            let n = items.len();
            let mut rand = rng();
            let idx1 = rand.random_range(0..n);
            let mut idx2 = rand.random_range(0..n);
            while idx2 == idx1 {
                idx2 = rand.random_range(0..n);
            }
            let moved = items[idx1].id();
            let target = items[idx2].id();
            let original_ids_without_moved: Vec<uuid::Uuid> = items
                .iter()
                .map(Identifiable::id)
                .filter(|&i| i != moved)
                .collect();

            move_after(&mut items, moved, target).unwrap();

            assert_eq!(items.len(), n);
            let moved_pos = items.iter().position(|i| i.id() == moved).unwrap();
            let target_pos = items.iter().position(|i| i.id() == target).unwrap();
            assert_eq!(moved_pos, target_pos + 1);

            let remaining_ids_without_moved: Vec<uuid::Uuid> = items
                .iter()
                .map(Identifiable::id)
                .filter(|&i| i != moved)
                .collect();
            assert_eq!(remaining_ids_without_moved, original_ids_without_moved);
        }
    }
}