Rollup merge of #110234 - marc0246:btree-insert-after-fix, r=cuviper

Fix btree `CursorMut::insert_after` check

Fixes a check inside `BTreeMap`'s `CursorMut::insert_after`, where it would peek the previous element to check whether the inserted key is below the next one, instead of peeking the next element.

2 files changed, 65 insertions, 1 deletions

diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs
index 61db46314b7..da675379cd5 100644
--- a/library/alloc/src/collections/btree/map.rs
+++ b/library/alloc/src/collections/btree/map.rs
@@ -3183,7 +3183,7 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> {
                 panic!("key must be ordered above the current element");
             }
         }
-        if let Some((next, _)) = self.peek_prev() {
+        if let Some((next, _)) = self.peek_next() {
             if &key >= next {
                 panic!("key must be ordered below the next element");
             }
diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs
index 76c2f27b466..4311f21c925 100644
--- a/library/alloc/src/collections/btree/map/tests.rs
+++ b/library/alloc/src/collections/btree/map/tests.rs
@@ -2385,3 +2385,67 @@ fn test_cursor_mut() {
     assert_eq!(cur.key(), Some(&4));
     assert_eq!(map, BTreeMap::from([(0, '?'), (1, 'a'), (3, 'c'), (4, 'd')]));
 }
+
+#[should_panic(expected = "key must be ordered above the previous element")]
+#[test]
+fn test_cursor_mut_insert_before_1() {
+    let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
+    let mut cur = map.upper_bound_mut(Bound::Included(&2));
+    cur.insert_before(0, 'd');
+}
+
+#[should_panic(expected = "key must be ordered above the previous element")]
+#[test]
+fn test_cursor_mut_insert_before_2() {
+    let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
+    let mut cur = map.upper_bound_mut(Bound::Included(&2));
+    cur.insert_before(1, 'd');
+}
+
+#[should_panic(expected = "key must be ordered below the current element")]
+#[test]
+fn test_cursor_mut_insert_before_3() {
+    let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
+    let mut cur = map.upper_bound_mut(Bound::Included(&2));
+    cur.insert_before(2, 'd');
+}
+
+#[should_panic(expected = "key must be ordered below the current element")]
+#[test]
+fn test_cursor_mut_insert_before_4() {
+    let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
+    let mut cur = map.upper_bound_mut(Bound::Included(&2));
+    cur.insert_before(3, 'd');
+}
+
+#[should_panic(expected = "key must be ordered above the current element")]
+#[test]
+fn test_cursor_mut_insert_after_1() {
+    let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
+    let mut cur = map.upper_bound_mut(Bound::Included(&2));
+    cur.insert_after(1, 'd');
+}
+
+#[should_panic(expected = "key must be ordered above the current element")]
+#[test]
+fn test_cursor_mut_insert_after_2() {
+    let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
+    let mut cur = map.upper_bound_mut(Bound::Included(&2));
+    cur.insert_after(2, 'd');
+}
+
+#[should_panic(expected = "key must be ordered below the next element")]
+#[test]
+fn test_cursor_mut_insert_after_3() {
+    let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
+    let mut cur = map.upper_bound_mut(Bound::Included(&2));
+    cur.insert_after(3, 'd');
+}
+
+#[should_panic(expected = "key must be ordered below the next element")]
+#[test]
+fn test_cursor_mut_insert_after_4() {
+    let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
+    let mut cur = map.upper_bound_mut(Bound::Included(&2));
+    cur.insert_after(4, 'd');
+}