sorted_insert/
lib.rs

1/*!
2# Sorted Insert
3
4This crate provides traits to insert elements to a sorted collection and keep the order.
5
6## Examples
7
8```rust
9use sorted_insert::SortedInsert;
10
11let mut v = vec![1, 5];
12
13v.sorted_insert_asc(2);
14
15assert_eq!([1, 2, 5], v.as_slice());
16```
17
18```rust
19use sorted_insert::SortedInsertBinary;
20
21let mut v = vec![5, 1];
22
23v.sorted_insert_desc_binary(2);
24
25assert_eq!([5, 2, 1], v.as_slice());
26```
27
28```rust
29use sorted_insert::SortedInsertByKey;
30
31#[derive(Debug, Copy, Clone, Eq, PartialEq)]
32struct A(i32, i32);
33
34let mut v = vec![A(1, 10), A(2, 20)];
35
36v.sorted_insert_asc_by_key(A(1, 15), |e| &e.1);
37
38assert_eq!([A(1, 10), A(1, 15), A(2, 20)], v.as_slice());
39```
40
41## No Std
42
43Disable the default features to compile this crate without std.
44
45```toml
46[dependencies.sorted-insert]
47version = "*"
48default-features = false
49```
50*/
51
52#![cfg_attr(not(feature = "std"), no_std)]
53
54extern crate alloc;
55
56mod collections;
57
58use core::cmp::Ordering;
59
60#[doc(hidden)]
61pub trait SortedInsertBasic<T> {
62    #[doc(hidden)]
63    fn insert_element(&mut self, index: usize, element: T);
64}
65
66pub trait SortedInsertBy<T>: SortedInsertBasic<T> {
67    /// Insert elements to this sorted collection by a specific comparator and return the inserted index. Use linear search to find the index where a matching element could be inserted.
68    #[inline]
69    fn sorted_insert_by<F: FnMut(&T, &T) -> bool>(&mut self, element: T, mut f: F) -> usize {
70        let index = self.get_sorted_insert_index_by(|e| f(e, &element));
71
72        self.insert_element(index, element);
73
74        index
75    }
76
77    #[doc(hidden)]
78    fn get_sorted_insert_index_by<F: FnMut(&T) -> bool>(&self, f: F) -> usize;
79}
80
81pub trait SortedInsertByKey<T>: SortedInsertBy<T> {
82    /// Insert elements to this sorted collection in ascending order by a specific key and return the inserted index. Use linear search to find the index where a matching element could be inserted.
83    #[inline]
84    fn sorted_insert_asc_by_key<A: Ord, F: FnMut(&T) -> &A>(
85        &mut self,
86        element: T,
87        mut f: F,
88    ) -> usize {
89        self.sorted_insert_by(element, |e, element| f(e) <= f(element))
90    }
91
92    /// Insert elements to this sorted collection in descending order by a specific key and return the inserted index. Use linear search to find the index where a matching element could be inserted.
93    #[inline]
94    fn sorted_insert_desc_by_key<A: Ord, F: FnMut(&T) -> &A>(
95        &mut self,
96        element: T,
97        mut f: F,
98    ) -> usize {
99        self.sorted_insert_by(element, |e, element| f(e) >= f(element))
100    }
101}
102
103pub trait SortedInsert<T: Ord>: SortedInsertByKey<T> {
104    /// Insert elements to this sorted collection in ascending order and return the inserted index. Use linear search to find the index where a matching element could be inserted.
105    #[inline]
106    fn sorted_insert_asc(&mut self, element: T) -> usize {
107        self.sorted_insert_asc_by_key(element, |element| element)
108    }
109
110    /// Insert elements to this sorted collection in descending order and return the inserted index. Use linear search to find the index where a matching element could be inserted.
111    fn sorted_insert_desc(&mut self, element: T) -> usize {
112        self.sorted_insert_desc_by_key(element, |element| element)
113    }
114}
115
116pub trait SortedInsertBinaryBy<T>: SortedInsertBy<T> {
117    /// Insert elements to this sorted collection by a specific comparator and return the inserted index. Use binary search to find the index where a matching element could be inserted.
118    fn sorted_insert_binary_by<F: FnMut(&T, &T) -> Ordering>(
119        &mut self,
120        element: T,
121        mut f: F,
122    ) -> usize {
123        let index = self.get_sorted_insert_index_binary_by(|e| f(e, &element));
124
125        self.insert_element(index, element);
126
127        index
128    }
129
130    #[doc(hidden)]
131    fn get_sorted_insert_index_binary_by<F: FnMut(&T) -> Ordering>(&mut self, f: F) -> usize;
132}
133
134pub trait SortedInsertBinaryByKey<T>: SortedInsertBinaryBy<T> {
135    /// Insert elements to this sorted collection in ascending order by a specific key and return the inserted index. Use binary search to find the index where a matching element could be inserted.
136    #[inline]
137    fn sorted_insert_binary_asc_by_key<A: Ord, F: FnMut(&T) -> &A>(
138        &mut self,
139        element: T,
140        mut f: F,
141    ) -> usize {
142        self.sorted_insert_binary_by(element, |e, element| f(e).cmp(f(element)))
143    }
144
145    /// Insert elements to this sorted collection in descending order by a specific key and return the inserted index. Use binary search to find the index where a matching element could be inserted.
146    #[inline]
147    fn sorted_insert_binary_desc_by_key<A: Ord, F: FnMut(&T) -> &A>(
148        &mut self,
149        element: T,
150        mut f: F,
151    ) -> usize {
152        self.sorted_insert_binary_by(element, |e, element| f(element).cmp(f(e)))
153    }
154}
155
156pub trait SortedInsertBinary<T: Ord>: SortedInsertBinaryByKey<T> {
157    /// Insert elements to this sorted collection in ascending order and return the inserted index. Use binary search to find the index where a matching element could be inserted.
158    #[inline]
159    fn sorted_insert_asc_binary(&mut self, element: T) -> usize {
160        self.sorted_insert_binary_asc_by_key(element, |element| element)
161    }
162
163    /// Insert elements to this sorted collection in descending order and return the inserted index. Use binary search to find the index where a matching element could be inserted.
164    #[inline]
165    fn sorted_insert_desc_binary(&mut self, element: T) -> usize {
166        self.sorted_insert_binary_desc_by_key(element, |element| element)
167    }
168}
sorted_insert/lib.rs

sorted_insert/
lib.rs
