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
58#[cfg(feature = "std")]
59mod arc_mutex;
60
61use core::cmp::Ordering;
62
63#[cfg(feature = "std")]
64pub use arc_mutex::*;
65
66#[doc(hidden)]
67pub trait SortedInsertBasic<T> {
68 #[doc(hidden)]
69 fn insert_element(&mut self, index: usize, element: T);
70}
71
72pub trait SortedInsertBy<T>: SortedInsertBasic<T> {
73 /// 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.
74 #[inline]
75 fn sorted_insert_by<F: FnMut(&T, &T) -> bool>(&mut self, element: T, mut f: F) -> usize {
76 let index = self.get_sorted_insert_index_by(|e| f(e, &element));
77
78 self.insert_element(index, element);
79
80 index
81 }
82
83 #[doc(hidden)]
84 fn get_sorted_insert_index_by<F: FnMut(&T) -> bool>(&self, f: F) -> usize;
85}
86
87pub trait SortedInsertByKey<T>: SortedInsertBy<T> {
88 /// 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.
89 #[inline]
90 fn sorted_insert_asc_by_key<A: Ord, F: FnMut(&T) -> &A>(
91 &mut self,
92 element: T,
93 mut f: F,
94 ) -> usize {
95 self.sorted_insert_by(element, |e, element| f(e) <= f(element))
96 }
97
98 /// 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.
99 #[inline]
100 fn sorted_insert_desc_by_key<A: Ord, F: FnMut(&T) -> &A>(
101 &mut self,
102 element: T,
103 mut f: F,
104 ) -> usize {
105 self.sorted_insert_by(element, |e, element| f(e) >= f(element))
106 }
107}
108
109pub trait SortedInsert<T: Ord>: SortedInsertByKey<T> {
110 /// 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.
111 #[inline]
112 fn sorted_insert_asc(&mut self, element: T) -> usize {
113 self.sorted_insert_asc_by_key(element, |element| element)
114 }
115
116 /// 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.
117 fn sorted_insert_desc(&mut self, element: T) -> usize {
118 self.sorted_insert_desc_by_key(element, |element| element)
119 }
120}
121
122pub trait SortedInsertBinaryBy<T>: SortedInsertBy<T> {
123 /// 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.
124 fn sorted_insert_binary_by<F: FnMut(&T, &T) -> Ordering>(
125 &mut self,
126 element: T,
127 mut f: F,
128 ) -> usize {
129 let index = self.get_sorted_insert_index_binary_by(|e| f(e, &element));
130
131 self.insert_element(index, element);
132
133 index
134 }
135
136 #[doc(hidden)]
137 fn get_sorted_insert_index_binary_by<F: FnMut(&T) -> Ordering>(&mut self, f: F) -> usize;
138}
139
140pub trait SortedInsertBinaryByKey<T>: SortedInsertBinaryBy<T> {
141 /// 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.
142 #[inline]
143 fn sorted_insert_binary_asc_by_key<A: Ord, F: FnMut(&T) -> &A>(
144 &mut self,
145 element: T,
146 mut f: F,
147 ) -> usize {
148 self.sorted_insert_binary_by(element, |e, element| f(e).cmp(f(element)))
149 }
150
151 /// 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.
152 #[inline]
153 fn sorted_insert_binary_desc_by_key<A: Ord, F: FnMut(&T) -> &A>(
154 &mut self,
155 element: T,
156 mut f: F,
157 ) -> usize {
158 self.sorted_insert_binary_by(element, |e, element| f(element).cmp(f(e)))
159 }
160}
161
162pub trait SortedInsertBinary<T: Ord>: SortedInsertBinaryByKey<T> {
163 /// 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.
164 #[inline]
165 fn sorted_insert_asc_binary(&mut self, element: T) -> usize {
166 self.sorted_insert_binary_asc_by_key(element, |element| element)
167 }
168
169 /// 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.
170 #[inline]
171 fn sorted_insert_desc_binary(&mut self, element: T) -> usize {
172 self.sorted_insert_binary_desc_by_key(element, |element| element)
173 }
174}