btree-indexmap 1.4.0

use btree_indexmap::{BTreeIndexMap, map::Entry};

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

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

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

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

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

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

	map.clear();

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

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

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

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

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

#[test]
fn insert_existing() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 1);
	assert_eq!(map.insert("a", 2), Some(1));
	assert_eq!(map.len(), 1); // still one entry
	assert_eq!(map.get("a"), Some(&2));
}

#[test]
fn insert_full() {
	let mut map = BTreeIndexMap::new();

	// First key goes to the end of the entries Vec (index 0).
	let (i, prev) = map.insert_full("b", 2);
	assert_eq!((i, prev), (0, None));

	// Second key appended (index 1), regardless of sort order.
	let (i, prev) = map.insert_full("a", 1);
	assert_eq!((i, prev), (1, None));

	// Re-inserting "b" keeps its stable index and returns the old value.
	let (i, prev) = map.insert_full("b", 20);
	assert_eq!((i, prev), (0, Some(2)));
}

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

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

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

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

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

#[test]
fn get_entry() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 1);
	assert_eq!(map.get_entry("a"), Some((&"a", &1)));
	assert_eq!(map.get_entry("missing"), None);
}

#[test]
fn get_mut() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 1);
	*map.get_mut("a").unwrap() = 99;
	assert_eq!(map.get("a"), Some(&99));
}

#[test]
fn get_mut_missing() {
	let mut map: BTreeIndexMap<&str, i32> = BTreeIndexMap::new();
	assert_eq!(map.get_mut("missing"), None);
}

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

#[test]
fn index_operator() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 42);
	assert_eq!(map["a"], 42);
}

#[test]
#[should_panic]
fn index_operator_panics_on_missing_key() {
	let map: BTreeIndexMap<&str, i32> = BTreeIndexMap::new();
	let _ = map["missing"];
}

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

#[test]
fn shift_remove() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 1);
	map.insert("b", 2);
	assert_eq!(map.shift_remove("a"), Some(1));
	assert_eq!(map.len(), 1);
	assert_eq!(map.shift_remove("a"), None); // already gone
}

#[test]
fn shift_remove_missing() {
	let mut map: BTreeIndexMap<&str, i32> = BTreeIndexMap::new();
	assert_eq!(map.shift_remove("missing"), None);
}

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

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

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

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

	// Removing "b" (index 1): "a" unchanged, "c" shifts to index 1.
	map.shift_remove_full("b");
	assert_eq!(map.get_full("a"), Some((0, &"a", &1)));
	assert_eq!(map.get_full("c"), Some((1, &"c", &3)));
}

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

#[test]
fn swap_remove() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 1);
	assert_eq!(map.swap_remove("a"), Some(1));
	assert!(map.is_empty());
	assert_eq!(map.swap_remove("a"), None);
}

#[test]
fn swap_remove_missing() {
	let mut map: BTreeIndexMap<&str, i32> = BTreeIndexMap::new();
	assert_eq!(map.swap_remove("missing"), None);
}

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

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

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

	// Remove "b" (already last): no swap, "a" unchanged.
	let (i, k, v) = map.swap_remove_full("b").unwrap();
	assert_eq!((i, k, v), (1, "b", 2));
	assert_eq!(map.get_full("a"), Some((0, &"a", &1)));
}

#[test]
fn swap_remove_only_element() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 1);
	assert_eq!(map.swap_remove_full("a"), Some((0, "a", 1)));
	assert!(map.is_empty());
}

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

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

#[test]
fn entry_vacant_into_key() {
	let mut map: BTreeIndexMap<&str, i32> = BTreeIndexMap::new();
	match map.entry("hello") {
		Entry::Vacant(e) => assert_eq!(e.into_key(), "hello"),
		Entry::Occupied(_) => panic!("expected vacant"),
	}
}

#[test]
fn entry_occupied_get() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 1);
	match map.entry("a") {
		Entry::Occupied(e) => {
			assert_eq!(*e.key(), "a");
			assert_eq!(*e.get(), 1);
		}
		Entry::Vacant(_) => panic!("expected occupied"),
	}
}

#[test]
fn entry_occupied_get_full() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 10); // index 0
	map.insert("b", 20); // index 1
	match map.entry("b") {
		Entry::Occupied(e) => {
			let (i, k, v) = e.get_full();
			assert_eq!((i, *k, *v), (1, "b", 20));
		}
		Entry::Vacant(_) => panic!("expected occupied"),
	}
}

#[test]
fn entry_occupied_insert() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 1);
	match map.entry("a") {
		Entry::Occupied(mut e) => {
			let old = e.insert(99);
			assert_eq!(old, 1);
		}
		Entry::Vacant(_) => panic!("expected occupied"),
	}
	assert_eq!(map.get("a"), Some(&99));
}

#[test]
fn entry_occupied_get_mut() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 1);
	match map.entry("a") {
		Entry::Occupied(mut e) => *e.get_mut() = 42,
		Entry::Vacant(_) => panic!("expected occupied"),
	}
	assert_eq!(map.get("a"), Some(&42));
}

#[test]
fn entry_occupied_into_mut() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 1);
	match map.entry("a") {
		Entry::Occupied(e) => {
			let v = e.into_mut();
			*v = 55;
		}
		Entry::Vacant(_) => panic!("expected occupied"),
	}
	assert_eq!(map.get("a"), Some(&55));
}

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

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

#[test]
fn iter_next_back() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 1);
	map.insert("b", 2);
	map.insert("c", 3);
	let mut iter = map.iter();
	assert_eq!(iter.next().map(|(&k, &v)| (k, v)), Some(("a", 1)));
	assert_eq!(iter.next_back().map(|(&k, &v)| (k, v)), Some(("c", 3)));
	assert_eq!(iter.next().map(|(&k, &v)| (k, v)), Some(("b", 2)));
	assert_eq!(iter.next(), None);
}

#[test]
fn iter_size_hint() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 1);
	map.insert("b", 2);
	let mut iter = map.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 map = BTreeIndexMap::new();
	map.insert("c", 3);
	map.insert("a", 1);
	map.insert("b", 2);
	let items: Vec<_> = map.iter_sorted().map(|(&k, &v)| (k, v)).collect();
	assert_eq!(items, [("a", 1), ("b", 2), ("c", 3)]);
}

#[test]
fn iter_sorted_next_back() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 1);
	map.insert("b", 2);
	map.insert("c", 3);
	let mut iter = map.iter_sorted();
	assert_eq!(iter.next().map(|(&k, &v)| (k, v)), Some(("a", 1)));
	assert_eq!(iter.next_back().map(|(&k, &v)| (k, v)), Some(("c", 3)));
	assert_eq!(iter.next().map(|(&k, &v)| (k, v)), Some(("b", 2)));
	assert_eq!(iter.next(), None);
}

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

#[test]
fn iter_mut() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 1);
	map.insert("b", 2);
	for (_, v) in map.iter_mut() {
		*v *= 10;
	}
	assert_eq!(map.get("a"), Some(&10));
	assert_eq!(map.get("b"), Some(&20));
}

#[test]
fn iter_mut_order() {
	let mut map = BTreeIndexMap::new();
	map.insert("c", 3);
	map.insert("a", 1);
	let keys: Vec<_> = map.iter_mut().map(|(&k, _)| k).collect();
	assert_eq!(keys, ["c", "a"]);
}

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

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

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

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

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

#[test]
fn values_mut() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 1);
	map.insert("b", 2);
	for v in map.values_mut() {
		*v += 10;
	}
	let vals: Vec<_> = map.values().copied().collect();
	assert_eq!(vals, [11, 12]);
}

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

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

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

	assert_eq!(m1, m2);
}

#[test]
fn ne_different_values() {
	let mut m1 = BTreeIndexMap::new();
	m1.insert("a", 1);
	let mut m2 = BTreeIndexMap::new();
	m2.insert("a", 2);
	assert_ne!(m1, m2);
}

#[test]
fn ne_different_keys() {
	let mut m1 = BTreeIndexMap::new();
	m1.insert("a", 1);
	let mut m2 = BTreeIndexMap::new();
	m2.insert("b", 1);
	assert_ne!(m1, m2);
}

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

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

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

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

#[test]
fn from_iterator() {
	let map: BTreeIndexMap<&str, i32> = [("a", 1), ("b", 2), ("c", 3)].into_iter().collect();
	assert_eq!(map.len(), 3);
	assert_eq!(map.get("a"), Some(&1));
	assert_eq!(map.get("b"), Some(&2));
	assert_eq!(map.get("c"), Some(&3));
}

#[test]
fn from_iterator_duplicate_key() {
	let map: BTreeIndexMap<&str, i32> = [("a", 1), ("a", 2)].into_iter().collect();
	assert_eq!(map.len(), 1);
	assert_eq!(map.get("a"), Some(&2));
}

#[test]
fn extend() {
	let mut map = BTreeIndexMap::new();
	map.insert("a", 1);
	map.extend([("b", 2), ("a", 99)]);
	assert_eq!(map.len(), 2);
	assert_eq!(map.get("a"), Some(&99));
	assert_eq!(map.get("b"), Some(&2));
}

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