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