1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

/*!
# Sorted Insert

This crate provides traits to insert elements to a sorted collection and remain the order.

## Examples

```rust
extern crate sorted_insert;

use sorted_insert::SortedInsert;

let mut v = vec![1, 5];

v.sorted_insert_asc(2);

assert_eq!([1, 2, 5], v.as_slice());
```

```rust
extern crate sorted_insert;

use sorted_insert::SortedInsertBinary;

let mut v = vec![5, 1];

v.sorted_insert_desc_binary(2);

assert_eq!([5, 2, 1], v.as_slice());
```

## No Std

Disable the default features to compile this crate without std.

```toml
[dependencies.sorted-insert]
version = "*"
default-features = false
```
*/

#![cfg_attr(not(feature = "std"), no_std)]
#![cfg_attr(feature = "nightly", feature(deque_make_contiguous))]

extern crate alloc;

mod collections;

pub trait SortedInsert<T: Ord> {
    /// 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.
    fn sorted_insert_asc(&mut self, element: T) -> usize;

    /// 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.
    fn sorted_insert_desc(&mut self, element: T) -> usize;
}

pub trait SortedInsertBinary<T: Ord> {
    /// 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.
    fn sorted_insert_asc_binary(&mut self, element: T) -> usize;

    /// 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.
    fn sorted_insert_desc_binary(&mut self, element: T) -> usize;
}