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