btree-indexmap 1.2.0

use btree_indexmap::{BTreeIndexMultiMap, multi_map::Entry};

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

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

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

#[test]
fn singleton() {
	let map = BTreeIndexMultiMap::singleton("a", 1);
	assert_eq!(map.len(), 1);
	assert_eq!(map.get("a").next(), Some(&1));
}

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

#[test]
fn clear() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("a", 1);
	map.push_back("a", 2);
	map.push_back("b", 3);

	map.clear();

	assert!(map.is_empty());
	assert_eq!(map.len(), 0);
	assert!(!map.contains_key("a"));
}

#[test]
fn clear_then_reinsert() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("a", 1);
	map.clear();

	// The map is fully usable after clearing.
	map.push_back("b", 2);
	assert_eq!(map.len(), 1);
	assert_eq!(map.get("b").next(), Some(&2));
	assert_eq!(map.index_of("b"), Some(0));
}

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

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

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

#[test]
fn push_back_order() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("b", 20);
	map.push_back("a", 10);
	map.push_back("a", 11);
	let entries: Vec<_> = map.as_entries().iter().map(|(k, v)| (*k, *v)).collect();
	assert_eq!(entries, [("b", 20), ("a", 10), ("a", 11)]);
}

#[test]
fn push_front() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("b", 2);
	map.push_front("a", 1);
	let entries: Vec<_> = map.as_entries().iter().map(|(k, v)| (*k, *v)).collect();
	assert_eq!(entries, [("a", 1), ("b", 2)]);
}

#[test]
fn push_front_same_key() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("a", 10);
	map.push_front("a", 99);
	let entries: Vec<_> = map.as_entries().iter().map(|(k, v)| (*k, *v)).collect();
	assert_eq!(entries, [("a", 99), ("a", 10)]);
}

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

#[test]
fn contains_key() {
	let mut map = BTreeIndexMultiMap::new();
	assert!(!map.contains_key("a"));
	map.push_back("a", 1);
	assert!(map.contains_key("a"));
	assert!(!map.contains_key("b"));
}

#[test]
fn first_and_last_on_empty_map() {
	let map: BTreeIndexMultiMap<&str, i32> = BTreeIndexMultiMap::new();
	assert_eq!(map.first(), None);
	assert_eq!(map.last(), None);
}

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

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

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

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

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

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

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

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

#[test]
fn get() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("a", 10);
	map.push_back("a", 20);
	map.push_back("b", 30);

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

#[test]
fn get_entries() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("a", 10);
	map.push_back("a", 20);

	let pairs: Vec<_> = map.get_entries("a").map(|(&k, &v)| (k, v)).collect();
	assert_eq!(pairs, [("a", 10), ("a", 20)]);
}

#[test]
fn get_indexed_entries() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("x", 100); // index 0
	map.push_back("x", 200); // index 1

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

#[test]
fn get_mut() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("a", 1);
	map.push_back("a", 2);

	for v in map.get_mut("a") {
		*v *= 10;
	}

	let vals: Vec<_> = map.get("a").copied().collect();
	assert_eq!(vals, [10, 20]);
}

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

#[test]
fn shift_remove_at() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("a", 1); // index 0
	map.push_back("a", 2); // index 1

	let removed = map.shift_remove_at(0);
	assert_eq!(removed, Some(("a", 1)));
	assert_eq!(map.len(), 1);
	assert_eq!(map.key_occurences("a"), 1);
	// Remaining "a" shifts to index 0.
	assert_eq!(map.index_of("a"), Some(0));
	assert_eq!(map.get("a").next(), Some(&2));
}

#[test]
fn shift_remove_at_non_first() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("a", 1); // index 0
	map.push_back("a", 2); // index 1

	// Remove the second occurrence (index 1, which lives in Indexes::rest).
	let removed = map.shift_remove_at(1);
	assert_eq!(removed, Some(("a", 2)));
	assert_eq!(map.len(), 1);
	assert_eq!(map.key_occurences("a"), 1);
	assert_eq!(map.get("a").next(), Some(&1));
}

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

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

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

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

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

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

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

// ── Removal: key-based ────────────────────────────────────────────────────────

#[test]
fn shift_remove() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("a", 1);
	map.push_back("b", 99);
	map.push_back("a", 2);

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

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

#[test]
fn shift_remove_drop() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("a", 1);
	map.push_back("a", 2);
	// Dropping without collecting is enough to remove all entries.
	drop(map.shift_remove("a"));
	assert!(!map.contains_key("a"));
	assert!(map.is_empty());
}

#[test]
fn swap_remove() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("a", 1);
	map.push_back("b", 99);
	map.push_back("a", 2);

	let removed: Vec<_> = map.swap_remove("a").collect();
	assert_eq!(removed.len(), 2);
	assert!(removed.contains(&1));
	assert!(removed.contains(&2));
	assert!(!map.contains_key("a"));
	assert!(map.contains_key("b"));
	assert_eq!(map.len(), 1);
}

// ── Insert (replace-all) ──────────────────────────────────────────────────────

#[test]
fn insert() {
	let mut map: BTreeIndexMultiMap<&str, i32> = BTreeIndexMultiMap::new();
	let old: Vec<_> = map.insert("a", 1).collect();
	assert!(old.is_empty());
	assert_eq!(map.len(), 1);
	assert_eq!(map.get("a").next(), Some(&1));
}

#[test]
fn insert_existing() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("a", 1);
	map.push_back("b", 99);
	map.push_back("a", 2);

	// insert() = shift_insert_back: removes all "a"s and pushes the new one at end.
	let old_vals: Vec<_> = map.insert("a", 42).collect();
	assert_eq!(old_vals, [1, 2]);
	assert_eq!(map.key_occurences("a"), 1);
	assert_eq!(map.get("a").next(), Some(&42));
	// "b" is unaffected.
	assert_eq!(map.get("b").next(), Some(&99));
}

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

#[test]
fn sort() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("c", 3);
	map.push_back("a", 1);
	map.push_back("b", 2);

	map.sort();

	let entries: Vec<_> = map.as_entries().iter().map(|(k, v)| (*k, *v)).collect();
	assert_eq!(entries, [("a", 1), ("b", 2), ("c", 3)]);
}

#[test]
fn sort_stable() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("b", 20);
	map.push_back("a", 1);
	map.push_back("a", 2);

	map.sort();

	let entries: Vec<_> = map.as_entries().iter().map(|(k, v)| (*k, *v)).collect();
	assert_eq!(entries, [("a", 1), ("a", 2), ("b", 20)]);
}

// ── Entry API ─────────────────────────────────────────────────────────────────

#[test]
fn entry_vacant_insert() {
	let mut map: BTreeIndexMultiMap<&str, i32> = BTreeIndexMultiMap::new();
	match map.entry("a") {
		Entry::Vacant(e) => {
			assert_eq!(*e.key(), "a");
			e.insert(42);
		}
		Entry::Occupied(_) => panic!("expected vacant"),
	}
	assert_eq!(map.get("a").next(), Some(&42));
}

#[test]
fn entry_occupied_get() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("a", 10);
	map.push_back("a", 20);
	match map.entry("a") {
		Entry::Occupied(e) => {
			assert_eq!(*e.key(), "a");
			let vals: Vec<_> = e.get().copied().collect();
			assert_eq!(vals, [10, 20]);
		}
		Entry::Vacant(_) => panic!("expected occupied"),
	}
}

#[test]
fn entry_occupied_insert() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("a", 10);
	map.push_back("a", 20);
	match map.entry("a") {
		Entry::Occupied(mut e) => {
			let old = e.insert(99);
			assert_eq!(old, 10);
		}
		Entry::Vacant(_) => panic!("expected occupied"),
	}
	// First value is replaced; second remains.
	let vals: Vec<_> = map.get("a").copied().collect();
	assert_eq!(vals, [99, 20]);
}

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

#[test]
fn iter() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("c", 3);
	map.push_back("a", 1);
	map.push_back("a", 2);
	let items: Vec<_> = map.iter().map(|(&k, &v)| (k, v)).collect();
	assert_eq!(items, [("c", 3), ("a", 1), ("a", 2)]);
}

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

#[test]
fn iter_sorted() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("c", 3);
	map.push_back("a", 1);
	map.push_back("b", 2);
	map.push_back("a", 4);
	let items: Vec<_> = map.iter_sorted().map(|(&k, &v)| (k, v)).collect();
	// Sorted by key; within "a", position order (1 was inserted before 4).
	assert_eq!(items, [("a", 1), ("a", 4), ("b", 2), ("c", 3)]);
}

#[test]
fn iter_sorted_size_hint() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("a", 1);
	map.push_back("a", 2);
	map.push_back("b", 3);
	// 3 entries across 2 unique keys.
	let mut iter = map.iter_sorted();
	assert_eq!(iter.len(), 3);
	iter.next();
	assert_eq!(iter.len(), 2);
	iter.next();
	assert_eq!(iter.len(), 1);
	iter.next();
	assert_eq!(iter.len(), 0);
}

#[test]
fn keys() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("c", 3);
	map.push_back("a", 1);
	map.push_back("a", 2);
	let keys: Vec<_> = map.keys().copied().collect();
	assert_eq!(keys, ["c", "a", "a"]);
}

#[test]
fn values() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("c", 3);
	map.push_back("a", 1);
	map.push_back("a", 2);
	let vals: Vec<_> = map.values().copied().collect();
	assert_eq!(vals, [3, 1, 2]);
}

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

#[test]
fn eq() {
	let mut m1 = BTreeIndexMultiMap::new();
	m1.push_back("b", 2);
	m1.push_back("a", 1);

	let mut m2 = BTreeIndexMultiMap::new();
	m2.push_back("a", 1);
	m2.push_back("b", 2);

	assert_eq!(m1, m2);
}

#[test]
fn ne() {
	let mut m1 = BTreeIndexMultiMap::new();
	m1.push_back("a", 1);
	m1.push_back("a", 2);

	let mut m2 = BTreeIndexMultiMap::new();
	m2.push_back("a", 2);
	m2.push_back("a", 1);

	// Equality is compared via iter_sorted, which respects position order
	// within the same key group.
	assert_ne!(m1, m2);
}

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

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

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

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

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

#[test]
fn debug() {
	let mut map = BTreeIndexMultiMap::new();
	map.push_back("a", 1);
	map.push_back("a", 2);
	let s = format!("{map:?}");
	assert!(s.contains("\"a\""));
	assert!(s.contains('1'));
	assert!(s.contains('2'));
}