sorted_containers 0.1.1

A sorted collections library
Documentation 
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

use sorted_vec::index::PosIndex;

const LOAD_FACTOR: usize = 1000;

#[derive(Debug, Clone)]
pub struct SortedVec<T: Ord> {
    vectors: Vec<Vec<T>>,
    maxes: Vec<T>,
    index: PosIndex,
    len: usize,
    load: usize,
    half: usize,
    dual: usize,
}

impl<T: Ord> SortedVec<T> {
    pub fn new() -> Self {
        SortedVec {
            vectors: Vec::new(),
            maxes: Vec::new(),
            index: PosIndex::new(),
            len: 0,
            load: LOAD_FACTOR,
            half: LOAD_FACTOR >> 1,
            dual: LOAD_FACTOR << 1,
        }
    }

    pub fn with_load_factor(load_factor: usize) -> Self {
        SortedVec {
            vectors: Vec::new(),
            maxes: Vec::new(),
            index: PosIndex::new(),
            len: 0,
            load: load_factor,
            half: load_factor >> 1,
            dual: load_factor << 1,
        }
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn into_vec(mut self) -> Vec<T> {
        let mut vector = Vec::with_capacity(self.len());
        for mut vec in self.vectors.drain(..) {
            vector.extend(vec.drain(..));
        }
        vector
    }
}

impl<T: Ord + Clone> SortedVec<T> {
    pub fn add(&mut self, elem: T) {
        if self.maxes.is_empty() {
            self.vectors.push(vec![elem.clone()]);
            self.maxes.push(elem);
        } else {
            let pos;
            match self.maxes.binary_search(&elem) {
                Ok(i) => {
                    pos = i;
                    self.vectors[i].push(elem);
                }
                Err(i) => {
                    if i == self.maxes.len() {
                        pos = i - 1;
                        self.vectors[pos].push(elem.clone());
                        self.maxes[pos] = elem;
                    } else {
                        pos = i;
                        let j = self.vectors[pos].binary_search(&elem).unwrap_or_else(|e| e);
                        self.vectors[pos].insert(j, elem);
                    }
                }
            }

            self.expand(pos);
        }

        self.len += 1;
    }

    pub fn to_vec(&self) -> Vec<T> {
        let mut vector = Vec::with_capacity(self.len());
        for vec in self.vectors.iter() {
            vector.extend(vec.iter().cloned());
        }
        vector
    }
}

impl<T: Ord + Clone> SortedVec<T> {
    // Splits sublists that are more than double the load level.
    fn expand(&mut self, pos: usize) {
        if self.vectors[pos].len() > self.dual {
            let last_half: Vec<_> = self.vectors[pos].drain(self.load..).collect();

            self.vectors.insert(pos + 1, last_half);
            self.maxes
                .insert(pos, self.vectors[pos][self.load - 1].clone());

        // TODO : update index
        } else {
            // TODO : update index
        }
    }
}