btree-indexmap 1.2.0

use btree_indexmap::BTreeIndexMultiSet;

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

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

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

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

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

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

	set.clear();

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

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

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

// ── Push operations ───────────────────────────────────────────────────────────

#[test]
fn push_back() {
	let mut set = BTreeIndexMultiSet::new();
	let (i, unique) = set.push_back("a");
	assert_eq!(i, 0);
	assert!(unique);
	assert_eq!(set.len(), 1);
}

#[test]
fn push_back_duplicate() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("a");
	let (i, unique) = set.push_back("a");
	assert_eq!(i, 1);
	assert!(!unique);
	assert_eq!(set.len(), 2);
}

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

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

#[test]
fn push_front_same_value() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("a");
	set.push_front("a");
	let items: Vec<_> = set.iter().copied().collect();
	assert_eq!(items, ["a", "a"]);
	assert_eq!(set.count("a"), 2);
}

// ── Insert (always adds a new occurrence) ─────────────────────────────────────

#[test]
fn insert() {
	let mut set: BTreeIndexMultiSet<&str> = BTreeIndexMultiSet::new();
	let (i, unique) = set.insert("a");
	assert_eq!((i, unique), (0, true));
	assert_eq!(set.len(), 1);
}

#[test]
fn insert_existing_adds_new_occurrence() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("a");
	set.push_back("b");

	// Unlike a map, inserting an existing value keeps both occurrences.
	let (i, unique) = set.insert("a");
	assert_eq!(i, 2);
	assert!(!unique);
	assert_eq!(set.count("a"), 2);
	assert_eq!(set.len(), 3);
}

// ── Queries ───────────────────────────────────────────────────────────────────

#[test]
fn contains() {
	let mut set = BTreeIndexMultiSet::new();
	assert!(!set.contains("a"));
	set.push_back("a");
	assert!(set.contains("a"));
	assert!(!set.contains("b"));
}

#[test]
fn first_and_last_on_empty_set() {
	let set: BTreeIndexMultiSet<&str> = BTreeIndexMultiSet::new();
	assert_eq!(set.first(), None);
	assert_eq!(set.last(), None);
}

#[test]
fn first_and_last() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("b");
	set.push_back("a");
	assert_eq!(set.first(), Some(&"b"));
	assert_eq!(set.last(), Some(&"a"));
}

#[test]
fn count() {
	let mut set = BTreeIndexMultiSet::new();
	assert_eq!(set.count("a"), 0);
	set.push_back("a");
	assert_eq!(set.count("a"), 1);
	set.push_back("a");
	assert_eq!(set.count("a"), 2);
}

#[test]
fn indexes_of() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("b"); // index 0
	set.push_back("a"); // index 1
	set.push_back("a"); // index 2

	let idxs: Vec<_> = set.indexes_of("a").collect();
	assert_eq!(idxs, [1, 2]);

	let idxs: Vec<_> = set.indexes_of("missing").collect();
	assert!(idxs.is_empty());
}

#[test]
fn index_of() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("b"); // index 0
	set.push_back("a"); // index 1
	set.push_back("a"); // index 2

	assert_eq!(set.index_of("a"), Some(1));
	assert_eq!(set.index_of("missing"), None);
}

// ── Get ───────────────────────────────────────────────────────────────────────

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

#[test]
fn get() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("a");
	set.push_back("a");
	set.push_back("b");

	let vals: Vec<_> = set.get("a").copied().collect();
	assert_eq!(vals, ["a", "a"]);
	assert!(set.get("missing").next().is_none());
}

#[test]
fn get_indexed() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("x"); // index 0
	set.push_back("x"); // index 1

	let result: Vec<_> = set.get_indexed("x").map(|(i, &v)| (i, v)).collect();
	assert_eq!(result, [(0, "x"), (1, "x")]);
}

// ── Removal: position-based ───────────────────────────────────────────────────

#[test]
fn shift_remove_at() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("a"); // index 0
	set.push_back("a"); // index 1

	let removed = set.shift_remove_at(0);
	assert_eq!(removed, Some("a"));
	assert_eq!(set.len(), 1);
	assert_eq!(set.count("a"), 1);
	// Remaining "a" shifts to index 0.
	assert_eq!(set.index_of("a"), Some(0));
}

#[test]
fn shift_remove_at_shift() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("a"); // index 0
	set.push_back("b"); // index 1
	set.push_back("a"); // index 2

	// Remove the first "a" at index 0; "b" and the second "a" shift down.
	let removed = set.shift_remove_at(0);
	assert_eq!(removed, Some("a"));
	assert_eq!(set.index_of("b"), Some(0));
	assert_eq!(set.index_of("a"), Some(1));
}

#[test]
fn shift_remove_at_missing() {
	let mut set: BTreeIndexMultiSet<&str> = BTreeIndexMultiSet::new();
	assert_eq!(set.shift_remove_at(0), None);
}

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

	// Remove "a" at index 0; "c" (last) swaps to index 0.
	let removed = set.swap_remove_at(0);
	assert_eq!(removed, Some("a"));
	assert_eq!(set.len(), 2);
	assert_eq!(set.index_of("c"), Some(0));
	assert_eq!(set.index_of("b"), Some(1));
}

#[test]
fn swap_remove_at_last() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("a"); // index 0
	set.push_back("b"); // index 1

	// Remove "b" (already last): no swap needed.
	let removed = set.swap_remove_at(1);
	assert_eq!(removed, Some("b"));
	assert_eq!(set.len(), 1);
	assert_eq!(set.index_of("a"), Some(0));
}

// ── Removal: value-based ──────────────────────────────────────────────────────

#[test]
fn shift_remove() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("a");
	set.push_back("b");
	set.push_back("a");

	let removed: Vec<_> = set.shift_remove("a").collect();
	assert_eq!(removed, ["a", "a"]);
	assert!(!set.contains("a"));
	assert!(set.contains("b"));
	assert_eq!(set.len(), 1);
}

#[test]
fn shift_remove_missing() {
	let mut set: BTreeIndexMultiSet<&str> = BTreeIndexMultiSet::new();
	let removed: Vec<_> = set.shift_remove("missing").collect();
	assert!(removed.is_empty());
}

#[test]
fn shift_remove_drop() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("a");
	set.push_back("a");
	// Dropping without collecting is enough to remove all occurrences.
	drop(set.shift_remove("a"));
	assert!(!set.contains("a"));
	assert!(set.is_empty());
}

#[test]
fn swap_remove() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("a");
	set.push_back("b");
	set.push_back("a");

	let removed: Vec<_> = set.swap_remove("a").collect();
	assert_eq!(removed.len(), 2);
	assert!(removed.iter().all(|&v| v == "a"));
	assert!(!set.contains("a"));
	assert!(set.contains("b"));
	assert_eq!(set.len(), 1);
}

// ── Sort ──────────────────────────────────────────────────────────────────────

#[test]
fn sort() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("c");
	set.push_back("a");
	set.push_back("b");

	set.sort();

	let items: Vec<_> = set.iter().copied().collect();
	assert_eq!(items, ["a", "b", "c"]);
}

#[test]
fn sort_stable() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("b");
	set.push_back("a");
	set.push_back("a");

	set.sort();

	let items: Vec<_> = set.iter().copied().collect();
	assert_eq!(items, ["a", "a", "b"]);
}

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

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

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

#[test]
fn iter_sorted() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("c");
	set.push_back("a");
	set.push_back("b");
	set.push_back("a");
	let items: Vec<_> = set.iter_sorted().copied().collect();
	// Sorted by value; within "a", position order is preserved.
	assert_eq!(items, ["a", "a", "b", "c"]);
}

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

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

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

// ── Index operator ────────────────────────────────────────────────────────────

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

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

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

	let mut s2 = BTreeIndexMultiSet::new();
	s2.push_back("a");
	s2.push_back("b");

	assert_eq!(s1, s2);
}

#[test]
fn ne() {
	let mut s1 = BTreeIndexMultiSet::new();
	s1.push_back("a");
	s1.push_back("a");

	let mut s2 = BTreeIndexMultiSet::new();
	s2.push_back("a");

	assert_ne!(s1, s2);
}

#[test]
fn clone() {
	let mut original = BTreeIndexMultiSet::new();
	original.push_back("a");
	original.push_back("a");

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

	cloned.push_back("b");
	assert_ne!(original, cloned);
	assert_eq!(original.len(), 2);
}

#[test]
fn from_iterator() {
	let set: BTreeIndexMultiSet<&str> = ["a", "b", "a"].into_iter().collect();
	// Extend uses push_back: all values are added, including duplicates.
	assert_eq!(set.len(), 3);
	assert_eq!(set.count("a"), 2);
	assert_eq!(set.count("b"), 1);
}

#[test]
fn extend() {
	let mut set = BTreeIndexMultiSet::new();
	set.push_back("a");
	set.extend(["b", "a"]);
	// push_back semantics: "a" now has two occurrences.
	assert_eq!(set.len(), 3);
	assert_eq!(set.count("a"), 2);
	assert_eq!(set.count("b"), 1);
}

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