btree-indexmap 1.4.0

use btree_indexmap::BTreeIndexSet;

// ── Creation ────────────────────────────────────────────────────────────────

#[test]
fn new_is_empty() {
	let set: BTreeIndexSet<&str> = BTreeIndexSet::new();
	assert!(set.is_empty());
	assert_eq!(set.len(), 0);
}

#[test]
fn default_is_empty() {
	let set: BTreeIndexSet<&str> = BTreeIndexSet::default();
	assert!(set.is_empty());
	assert_eq!(set.len(), 0);
}

#[test]
fn singleton() {
	let set = BTreeIndexSet::singleton("a");
	assert_eq!(set.len(), 1);
	assert!(set.contains("a"));
}

// ── Clear ────────────────────────────────────────────────────────────────────

#[test]
fn clear() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	set.insert("b");

	set.clear();

	assert!(set.is_empty());
	assert_eq!(set.len(), 0);
	assert!(!set.contains("a"));
}

#[test]
fn clear_then_reinsert() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	set.clear();

	// The set is fully usable after clearing.
	set.insert("b");
	assert_eq!(set.len(), 1);
	assert!(set.contains("b"));
	assert_eq!(set.get_index_of("b"), Some(0));
}

// ── Insert ───────────────────────────────────────────────────────────────────

#[test]
fn insert() {
	let mut set = BTreeIndexSet::new();
	assert!(set.insert("a"));
	assert_eq!(set.len(), 1);
	assert!(!set.is_empty());
}

#[test]
fn insert_existing() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	assert!(!set.insert("a")); // already present
	assert_eq!(set.len(), 1); // still one entry
}

#[test]
fn insert_full() {
	let mut set = BTreeIndexSet::new();

	// First value goes to the end of the entries Vec (index 0).
	let (i, inserted) = set.insert_full("b");
	assert_eq!((i, inserted), (0, true));

	// Second value appended (index 1), regardless of sort order.
	let (i, inserted) = set.insert_full("a");
	assert_eq!((i, inserted), (1, true));

	// Re-inserting "b" keeps its stable index and reports it wasn't new.
	let (i, inserted) = set.insert_full("b");
	assert_eq!((i, inserted), (0, false));
}

// ── Lookup ───────────────────────────────────────────────────────────────────

#[test]
fn get() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	assert_eq!(set.get("a"), Some(&"a"));
}

#[test]
fn as_slice() {
	let mut set = BTreeIndexSet::new();
	set.insert("c");
	set.insert("a");
	set.insert("b");
	assert_eq!(set.as_slice(), ["c", "a", "b"]);
}

#[test]
fn get_missing() {
	let set: BTreeIndexSet<&str> = BTreeIndexSet::new();
	assert_eq!(set.get("missing"), None);
}

#[test]
fn get_full() {
	let mut set = BTreeIndexSet::new();
	set.insert("b"); // index 0
	set.insert("a"); // index 1

	assert_eq!(set.get_full("b"), Some((0, &"b")));
	assert_eq!(set.get_full("a"), Some((1, &"a")));
	assert_eq!(set.get_full("c"), None);
}

#[test]
fn get_index_of() {
	let mut set = BTreeIndexSet::new();
	set.insert("b"); // index 0
	set.insert("a"); // index 1
	assert_eq!(set.get_index_of("a"), Some(1));
	assert_eq!(set.get_index_of("missing"), None);
}

#[test]
fn contains() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	assert!(set.contains("a"));
	assert!(!set.contains("missing"));
}

#[test]
fn index_operator() {
	let mut set = BTreeIndexSet::new();
	set.insert("b"); // index 0
	set.insert("a"); // index 1
	assert_eq!(set[0], "b");
	assert_eq!(set[1], "a");
}

#[test]
#[should_panic]
fn index_operator_panics_on_missing_index() {
	let set: BTreeIndexSet<&str> = BTreeIndexSet::new();
	let _ = set[0];
}

// ── Removal: shift_remove ────────────────────────────────────────────────────

#[test]
fn shift_remove() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	set.insert("b");
	assert!(set.shift_remove("a"));
	assert_eq!(set.len(), 1);
	assert!(!set.shift_remove("a")); // already gone
}

#[test]
fn shift_remove_missing() {
	let mut set: BTreeIndexSet<&str> = BTreeIndexSet::new();
	assert!(!set.shift_remove("missing"));
}

#[test]
fn shift_take() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	assert_eq!(set.shift_take("a"), Some("a"));
	assert_eq!(set.shift_take("a"), None);
}

#[test]
fn shift_remove_full() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	assert_eq!(set.shift_remove_full("a"), Some((0, "a")));
	assert!(set.is_empty());
}

#[test]
fn shift_remove_first_shifts_all_subsequent_indices() {
	let mut set = BTreeIndexSet::new();
	set.insert("a"); // index 0
	set.insert("b"); // index 1
	set.insert("c"); // index 2

	// Removing "a" (index 0) shifts "b" and "c" down by one.
	let (i, v) = set.shift_remove_full("a").unwrap();
	assert_eq!((i, v), (0, "a"));
	assert_eq!(set.get_full("b"), Some((0, &"b")));
	assert_eq!(set.get_full("c"), Some((1, &"c")));
}

// ── Removal: swap_remove ─────────────────────────────────────────────────────

#[test]
fn swap_remove() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	assert!(set.swap_remove("a"));
	assert!(set.is_empty());
	assert!(!set.swap_remove("a"));
}

#[test]
fn swap_remove_missing() {
	let mut set: BTreeIndexSet<&str> = BTreeIndexSet::new();
	assert!(!set.swap_remove("missing"));
}

#[test]
fn swap_take() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	assert_eq!(set.swap_take("a"), Some("a"));
	assert_eq!(set.swap_take("a"), None);
}

#[test]
fn swap_remove_moves_last_entry_to_removed_index() {
	let mut set = BTreeIndexSet::new();
	set.insert("a"); // index 0
	set.insert("b"); // index 1
	set.insert("c"); // index 2

	// Remove "a" (index 0); "c" (last, index 2) swaps to index 0.
	let (i, v) = set.swap_remove_full("a").unwrap();
	assert_eq!((i, v), (0, "a"));
	assert_eq!(set.get_full("c"), Some((0, &"c")));
	assert_eq!(set.get_full("b"), Some((1, &"b")));
}

// ── Iterators ────────────────────────────────────────────────────────────────

#[test]
fn iter() {
	let mut set = BTreeIndexSet::new();
	set.insert("c");
	set.insert("a");
	set.insert("b");
	let items: Vec<_> = set.iter().copied().collect();
	assert_eq!(items, ["c", "a", "b"]);
}

#[test]
fn iter_next_back() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	set.insert("b");
	set.insert("c");
	let mut iter = set.iter();
	assert_eq!(iter.next(), Some(&"a"));
	assert_eq!(iter.next_back(), Some(&"c"));
	assert_eq!(iter.next(), Some(&"b"));
	assert_eq!(iter.next(), None);
}

#[test]
fn iter_size_hint() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	set.insert("b");
	let mut iter = set.iter();
	assert_eq!(iter.len(), 2);
	iter.next();
	assert_eq!(iter.len(), 1);
	iter.next();
	assert_eq!(iter.len(), 0);
}

#[test]
fn iter_sorted() {
	let mut set = BTreeIndexSet::new();
	set.insert("c");
	set.insert("a");
	set.insert("b");
	let items: Vec<_> = set.iter_sorted().copied().collect();
	assert_eq!(items, ["a", "b", "c"]);
}

#[test]
fn iter_sorted_next_back() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	set.insert("b");
	set.insert("c");
	let mut iter = set.iter_sorted();
	assert_eq!(iter.next(), Some(&"a"));
	assert_eq!(iter.next_back(), Some(&"c"));
	assert_eq!(iter.next(), Some(&"b"));
	assert_eq!(iter.next(), None);
}

#[test]
fn iter_sorted_size_hint() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	set.insert("b");
	let mut iter = set.iter_sorted();
	assert_eq!(iter.len(), 2);
	iter.next();
	assert_eq!(iter.len(), 1);
}

#[test]
fn into_iter() {
	let mut set = BTreeIndexSet::new();
	set.insert("c");
	set.insert("a");
	set.insert("b");
	let items: Vec<_> = set.into_iter().collect();
	assert_eq!(items, ["c", "a", "b"]);
}

#[test]
fn into_iter_sorted() {
	let mut set = BTreeIndexSet::new();
	set.insert("c");
	set.insert("a");
	set.insert("b");
	let items: Vec<_> = set.into_iter_sorted().collect();
	assert_eq!(items, ["a", "b", "c"]);
}

#[test]
fn into_iter_sorted_next_back() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	set.insert("b");
	set.insert("c");
	let mut iter = set.into_iter_sorted();
	assert_eq!(iter.next(), Some("a"));
	assert_eq!(iter.next_back(), Some("c"));
	assert_eq!(iter.next(), Some("b"));
	assert_eq!(iter.next(), None);
}

// ── Standard Traits ──────────────────────────────────────────────────────────

#[test]
fn eq() {
	let mut s1 = BTreeIndexSet::new();
	s1.insert("b");
	s1.insert("a");

	let mut s2 = BTreeIndexSet::new();
	s2.insert("a");
	s2.insert("b");

	assert_eq!(s1, s2);
}

#[test]
fn ne_different_values() {
	let mut s1 = BTreeIndexSet::new();
	s1.insert("a");
	let mut s2 = BTreeIndexSet::new();
	s2.insert("b");
	assert_ne!(s1, s2);
}

#[test]
fn cmp() {
	let mut small = BTreeIndexSet::new();
	small.insert("a");
	let mut large = BTreeIndexSet::new();
	large.insert("b");
	assert!(small < large);
	assert!(large > small);
	assert_eq!(small.cmp(&small), std::cmp::Ordering::Equal);
}

#[test]
fn clone() {
	let mut original = BTreeIndexSet::new();
	original.insert("a");
	original.insert("b");

	let mut cloned = original.clone();
	assert_eq!(original, cloned);

	// Modifying the clone does not affect the original.
	cloned.insert("c");
	assert_ne!(original, cloned);
	assert_eq!(original.len(), 2);
}

#[test]
fn from_iterator() {
	let set: BTreeIndexSet<&str> = ["a", "b", "c"].into_iter().collect();
	assert_eq!(set.len(), 3);
	assert!(set.contains("a"));
	assert!(set.contains("b"));
	assert!(set.contains("c"));
}

#[test]
fn from_iterator_duplicate_value() {
	let set: BTreeIndexSet<&str> = ["a", "a"].into_iter().collect();
	assert_eq!(set.len(), 1);
}

#[test]
fn extend() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	set.extend(["b", "a"]);
	assert_eq!(set.len(), 2);
	assert!(set.contains("a"));
	assert!(set.contains("b"));
}

#[test]
fn debug() {
	let mut set = BTreeIndexSet::new();
	set.insert("a");
	set.insert("b");
	let s = format!("{set:?}");
	assert!(s.contains("\"a\""));
	assert!(s.contains("\"b\""));
}