ordered_vec/
lib.rs

1//! The `OrdVec` trait provides an extension to `Vec` to allow for inserting items in order, both
2//! ascending and descending.
3//!
4//! # Examples
5//!
6//! ```
7//! use ordered_vec::OrdVec;
8//!
9//! let mut values: Vec<i32> = Vec::new();
10//! values.push_ord_ascending(5);
11//! values.push_ord_ascending(3);
12//! values.push_ord_ascending(7);
13//! values.push_ord_ascending(1);
14//!
15//! assert_eq!(values, [1, 3, 5, 7]);
16//! ```
17//! ```
18//! use ordered_vec::OrdVec;
19//!
20//! let mut values: Vec<i32> = Vec::new();
21//! values.push_ord_descending(5);
22//! values.push_ord_descending(3);
23//! values.push_ord_descending(7);
24//! values.push_ord_descending(1);
25//!
26//! assert_eq!(values, [7, 5, 3, 1]);
27//! ```
28
29use std::cmp::Ordering;
30
31/// A trait for adding elements to a vector in sorted order, both ascending and descending.
32pub trait OrdVec<T: PartialOrd> {
33    /// Inserts `item` into `self` in sorted ascending order. Returns the index at which `item` was inserted.
34    /// # Examples
35    ///
36    /// ```
37    ///use ordered_vec::OrdVec;
38    ///let mut values: Vec<f64> = Vec::new();
39    ///assert_eq!(values.push_ord_ascending(5.5), Ok(0));
40    ///assert_eq!(values, [5.5]);
41    ///
42    ///assert_eq!(values.push_ord_ascending(3.14), Ok(0));
43    ///assert_eq!(values, [3.14, 5.5]);
44    ///
45    ///assert_eq!(values.push_ord_ascending(7.77), Ok(2));
46    ///assert_eq!(values, [3.14, 5.5, 7.77]);
47    ///
48    /// ```
49    fn push_ord_ascending(&mut self, item: T) -> Result<usize, OrdVecError>;
50    /// Inserts `item` into `self` in sorted descending order. Returns the index at which `item` was inserted.
51    /// # Examples
52    ///
53    /// ```
54    ///use ordered_vec::OrdVec;
55    ///let mut values: Vec<f64> = Vec::new();
56    ///assert_eq!(values.push_ord_descending(5.5), Ok(0));
57    ///assert_eq!(values, [5.5]);
58    ///
59    ///assert_eq!(values.push_ord_descending(3.14), Ok(1));
60    ///assert_eq!(values, [5.5, 3.14]);
61    ///
62    ///assert_eq!(values.push_ord_descending(7.77), Ok(0));
63    ///assert_eq!(values, [7.77, 5.5, 3.14]);
64    ///
65    /// ```
66    fn push_ord_descending(&mut self, item: T) -> Result<usize, OrdVecError>;
67}
68
69impl<T: PartialOrd> OrdVec<T> for Vec<T> {
70    fn push_ord_ascending(&mut self, item: T) -> Result<usize, OrdVecError> {
71        let idx = binary_search_index_ascending(&item, self);
72        match idx {
73            Some(idx) => {
74                self.insert(idx, item);
75                Ok(idx)
76            }
77            None => Err(OrdVecError),
78        }
79    }
80
81    fn push_ord_descending(&mut self, item: T) -> Result<usize, OrdVecError> {
82        let idx = binary_search_index_descending(&item, self);
83        match idx {
84            Some(idx) => {
85                self.insert(idx, item);
86                Ok(idx)
87            }
88            None => Err(OrdVecError),
89        }
90    }
91}
92
93// Create an OrdVecError struct that implements the error and Display trait
94#[derive(Debug, PartialEq, Eq)]
95pub struct OrdVecError;
96
97impl std::fmt::Display for OrdVecError {
98    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
99        write!(f, "Failed to add item to vector")
100    }
101}
102
103impl std::error::Error for OrdVecError {}
104
105/// Finds the mid_point between two integers
106#[inline]
107fn mid_point(a: usize, b: usize) -> usize {
108    (a + b) / 2
109}
110
111/// Returns the index at which `item` should be inserted into `values` to preserve sorted order.
112#[inline]
113fn binary_search_index_ascending<T: PartialOrd>(item: &T, values: &[T]) -> Option<usize> {
114    if values.is_empty() {
115        return Some(0);
116    }
117    let mut start: usize = 0;
118    let mut end = values.len() - 1;
119    if item <= &values[start] {
120        return Some(start);
121    }
122
123    if item >= &values[end] {
124        return Some(end + 1);
125    }
126    let mut idx: usize = mid_point(start, end);
127    loop {
128        match item.partial_cmp(&values[idx]) {
129            Some(Ordering::Less) => {
130                end = idx;
131                idx = mid_point(start, end);
132                if end - start <= 1 {
133                    idx = end;
134                    break;
135                }
136            }
137            Some(Ordering::Greater) => {
138                start = idx;
139                idx = mid_point(start, end);
140                if end - start <= 1 {
141                    idx = end;
142                    break;
143                }
144            }
145            Some(Ordering::Equal) => {
146                break;
147            }
148            None => {
149                return None;
150            }
151        }
152    }
153    Some(idx)
154}
155
156#[inline]
157fn binary_search_index_descending<T: PartialOrd>(item: &T, values: &[T]) -> Option<usize> {
158    if values.is_empty() {
159        return Some(0);
160    }
161    let mut start: usize = 0;
162    let mut end = values.len() - 1;
163    if item >= &values[start] {
164        return Some(start);
165    }
166
167    if item <= &values[end] {
168        return Some(end + 1);
169    }
170    let mut idx: usize = mid_point(start, end);
171    loop {
172        match item.partial_cmp(&values[idx]) {
173            Some(Ordering::Less) => {
174                start = idx;
175                idx = mid_point(start, end);
176                if end - start <= 1 {
177                    idx = end;
178                    break;
179                }
180            }
181            Some(Ordering::Greater) => {
182                end = idx;
183                idx = mid_point(start, end);
184                if end - start <= 1 {
185                    idx = end;
186                    break;
187                }
188            }
189            Some(Ordering::Equal) => {
190                break;
191            }
192            None => {
193                return None;
194            }
195        }
196    }
197    Some(idx)
198}
199
200#[cfg(test)]
201mod tests {
202    use super::*;
203
204    #[test]
205    fn test_mid_point() {
206        for i in 0..100 {
207            assert_eq!(mid_point(0, i), i / 2);
208        }
209    }
210
211    #[test]
212    fn test_binary_search_index_ascending() {
213        let values_1 = [1, 2, 3, 4, 5];
214        assert_eq!(binary_search_index_ascending(&4, &values_1), Some(3));
215        assert_eq!(binary_search_index_ascending(&6, &values_1), Some(5));
216        assert_eq!(binary_search_index_ascending(&0, &values_1), Some(0));
217
218        let values_2 = ["apple", "banana", "cherry", "date", "elderberry"];
219        assert_eq!(binary_search_index_ascending(&"cherry", &values_2), Some(2));
220        assert_eq!(binary_search_index_ascending(&"fig", &values_2), Some(5));
221        assert_eq!(
222            binary_search_index_ascending(&"apricot", &values_2),
223            Some(1)
224        );
225        assert_eq!(
226            binary_search_index_ascending(&"aardvark", &values_2),
227            Some(0)
228        );
229
230        let values_3 = [1.5, 2.7, 3.1, 4.9, 5.2];
231        assert_eq!(binary_search_index_ascending(&2.7, &values_3), Some(1));
232        assert_eq!(binary_search_index_ascending(&3.15, &values_3), Some(3));
233        assert_eq!(binary_search_index_ascending(&1.0, &values_3), Some(0));
234
235        let values_4 = [1, 2, 3, 4];
236        assert_eq!(binary_search_index_ascending(&5, &values_4), Some(4));
237        assert_eq!(binary_search_index_ascending(&0, &values_4), Some(0));
238    }
239
240    #[test]
241    fn test_binary_search_index_descending() {
242        let values = [4, 3, 2, 1];
243        assert_eq!(binary_search_index_descending(&1, &values), Some(4));
244        assert_eq!(binary_search_index_descending(&2, &values), Some(2));
245        assert_eq!(binary_search_index_descending(&3, &values), Some(1));
246        assert_eq!(binary_search_index_descending(&4, &values), Some(0));
247        assert_eq!(binary_search_index_descending(&5, &values), Some(0));
248        assert_eq!(binary_search_index_descending(&0, &values), Some(4));
249        let values = [4., 3., 2., 1.];
250        assert_eq!(binary_search_index_descending(&2.5, &values), Some(2));
251
252        let values = [1];
253        assert_eq!(binary_search_index_descending(&1, &values), Some(0));
254        assert_eq!(binary_search_index_descending(&0, &values), Some(1));
255        assert_eq!(binary_search_index_descending(&2, &values), Some(0));
256
257        let values = [];
258        assert_eq!(binary_search_index_descending(&1, &values), Some(0));
259        assert_eq!(binary_search_index_descending(&0, &values), Some(0));
260        assert_eq!(binary_search_index_descending(&2, &values), Some(0));
261
262        let values = ["elderberry", "date", "cherry", "banana", "apple"];
263        assert_eq!(binary_search_index_descending(&"cherry", &values), Some(2));
264        assert_eq!(binary_search_index_descending(&"fig", &values), Some(0));
265        assert_eq!(binary_search_index_descending(&"apricot", &values), Some(4));
266        assert_eq!(
267            binary_search_index_descending(&"aardvark", &values),
268            Some(5)
269        );
270        assert_eq!(
271            binary_search_index_descending(&"elderberry", &values),
272            Some(0)
273        );
274        assert_eq!(binary_search_index_descending(&"apple", &values), Some(5));
275
276        let values_2 = [5.2, 4.9, 3.1, 2.7, 1.5];
277        assert_eq!(binary_search_index_descending(&2.7, &values_2), Some(3));
278        assert_eq!(binary_search_index_descending(&3.15, &values_2), Some(2));
279        assert_eq!(binary_search_index_descending(&1.0, &values_2), Some(5));
280    }
281
282    #[test]
283    fn test_ord_vec_ascending() {
284        let mut values: Vec<i32> = Vec::new();
285
286        assert_eq!(values.push_ord_ascending(5), Ok(0));
287        assert_eq!(values, [5]);
288
289        assert_eq!(values.push_ord_ascending(3), Ok(0));
290        assert_eq!(values, [3, 5]);
291
292        assert_eq!(values.push_ord_ascending(7), Ok(2));
293        assert_eq!(values, [3, 5, 7]);
294
295        assert_eq!(values.push_ord_ascending(1), Ok(0));
296        assert_eq!(values, [1, 3, 5, 7]);
297
298        assert_eq!(values.push_ord_ascending(9), Ok(4));
299        assert_eq!(values, [1, 3, 5, 7, 9]);
300
301        assert_eq!(values.push_ord_ascending(8), Ok(4));
302        assert_eq!(values, [1, 3, 5, 7, 8, 9]);
303
304        assert_eq!(values.push_ord_ascending(100), Ok(6));
305        assert_eq!(values, [1, 3, 5, 7, 8, 9, 100]);
306
307        assert_eq!(values.push_ord_ascending(3), Ok(1));
308        assert_eq!(values, [1, 3, 3, 5, 7, 8, 9, 100]);
309
310        assert_eq!(values.push_ord_ascending(2), Ok(1));
311        assert_eq!(values, [1, 2, 3, 3, 5, 7, 8, 9, 100]);
312
313        assert_eq!(values.push_ord_ascending(0), Ok(0));
314        assert_eq!(values, [0, 1, 2, 3, 3, 5, 7, 8, 9, 100]);
315    }
316
317    #[test]
318    fn test_ord_vec_descending() {
319        let mut values: Vec<i32> = Vec::new();
320
321        assert_eq!(values.push_ord_descending(5), Ok(0));
322        assert_eq!(values, [5]);
323
324        assert_eq!(values.push_ord_descending(3), Ok(1));
325        assert_eq!(values, [5, 3]);
326
327        assert_eq!(values.push_ord_descending(7), Ok(0));
328        assert_eq!(values, [7, 5, 3]);
329
330        assert_eq!(values.push_ord_descending(1), Ok(3));
331        assert_eq!(values, [7, 5, 3, 1]);
332
333        assert_eq!(values.push_ord_descending(9), Ok(0));
334        assert_eq!(values, [9, 7, 5, 3, 1]);
335
336        assert_eq!(values.push_ord_descending(8), Ok(1));
337        assert_eq!(values, [9, 8, 7, 5, 3, 1]);
338
339        assert_eq!(values.push_ord_descending(100), Ok(0));
340        assert_eq!(values, [100, 9, 8, 7, 5, 3, 1]);
341
342        assert_eq!(values.push_ord_descending(3), Ok(5));
343        assert_eq!(values, [100, 9, 8, 7, 5, 3, 3, 1]);
344
345        assert_eq!(values.push_ord_descending(2), Ok(7));
346        assert_eq!(values, [100, 9, 8, 7, 5, 3, 3, 2, 1]);
347
348        assert_eq!(values.push_ord_descending(0), Ok(9));
349        assert_eq!(values, [100, 9, 8, 7, 5, 3, 3, 2, 1, 0]);
350    }
351}
ordered_vec/lib.rs

ordered_vec/
lib.rs
