inverted_index_util/
entity_list.rs

1use std::cmp::Ordering::{Equal, Greater, Less};
2use typenum::uint::Unsigned;
3
4pub fn insert_entity_mut<N>(entity_list: &mut Vec<u8>, entity: &[u8])
5where
6    N: Unsigned,
7{
8    let entity_len = N::to_usize();
9    assert_eq!(entity_len, entity.len());
10
11    let list_len = entity_list.len();
12
13    assert_eq!(list_len.checked_rem(entity_len), Some(0));
14    let mut size = list_len / entity_len;
15
16    if size == 0 {
17        entity_list.splice(0..0, entity.iter().copied());
18        return;
19    }
20
21    let mut base = 0usize;
22    while size > 1 {
23        let half = size / 2;
24        let mid = base + half;
25        let start = mid * entity_len;
26        let end = start + entity_len;
27        let cmp = entity_list[start..end].cmp(entity);
28        base = if cmp == Greater { base } else { mid };
29        size -= half;
30    }
31
32    let start = base * entity_len;
33    let end = start + entity_len;
34    let cmp = entity_list[start..end].cmp(entity);
35
36    let offset = match cmp {
37        Equal => return, // already present
38        Less => (base + 1) * entity_len,
39        Greater => base * entity_len,
40    };
41
42    entity_list.splice(offset..offset, entity.iter().copied());
43}
44
45pub enum ImmutResult {
46    Changed(Vec<u8>),
47    Unchanged,
48}
49pub fn insert_entity_immut<N>(entity_list: &[u8], entity: &[u8]) -> ImmutResult
50where
51    N: Unsigned,
52{
53    let entity_len = N::to_usize();
54    assert_eq!(entity_len, entity.len());
55
56    let list_len = entity_list.len();
57
58    assert_eq!(list_len.checked_rem(entity_len), Some(0));
59    let mut size = list_len / entity_len;
60
61    if size == 0 {
62        let mut entity_list = entity_list.to_vec();
63        entity_list.splice(0..0, entity.iter().copied());
64        return ImmutResult::Changed(entity_list);
65    }
66
67    let mut base = 0usize;
68    while size > 1 {
69        let half = size / 2;
70        let mid = base + half;
71        let start = mid * entity_len;
72        let end = start + entity_len;
73        let cmp = entity_list[start..end].cmp(entity);
74        base = if cmp == Greater { base } else { mid };
75        size -= half;
76    }
77
78    let start = base * entity_len;
79    let end = start + entity_len;
80    let cmp = entity_list[start..end].cmp(entity);
81
82    let offset = match cmp {
83        Equal => return ImmutResult::Unchanged, // already present
84        Less => (base + 1) * entity_len,
85        Greater => base * entity_len,
86    };
87
88    let mut entity_list = entity_list.to_vec();
89    entity_list.splice(offset..offset, entity.iter().copied());
90
91    ImmutResult::Changed(entity_list)
92}
93
94#[cfg(test)]
95mod tests {
96    use super::*;
97    use typenum::consts::{U16, U32};
98
99    #[test]
100    fn insert_document_mut_16() {
101        let mut entity_list: Vec<u8> = Vec::new();
102
103        insert_entity_mut::<U16>(&mut entity_list, b"aaaaaaaaaaaaaaaa");
104        insert_entity_mut::<U16>(&mut entity_list, b"cccccccccccccccc");
105        insert_entity_mut::<U16>(&mut entity_list, b"aaaaaaaaaaaaaaaa");
106        insert_entity_mut::<U16>(&mut entity_list, b"bbbbbbbbbbbbbbbb");
107
108        assert_eq!(&entity_list[..], &b"aaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbcccccccccccccccc"[..]);
109    }
110    #[test]
111    fn insert_document_immut_16() {
112        let mut entity_list = Vec::new();
113
114        match insert_entity_immut::<U16>(&entity_list, b"aaaaaaaaaaaaaaaa") {
115            ImmutResult::Changed(l) => entity_list = l,
116            ImmutResult::Unchanged => {}
117        };
118        match insert_entity_immut::<U16>(&entity_list, b"cccccccccccccccc") {
119            ImmutResult::Changed(l) => entity_list = l,
120            ImmutResult::Unchanged => {}
121        };
122        match insert_entity_immut::<U16>(&entity_list, b"aaaaaaaaaaaaaaaa") {
123            ImmutResult::Changed(l) => entity_list = l,
124            ImmutResult::Unchanged => {}
125        };
126        match insert_entity_immut::<U16>(&entity_list, b"bbbbbbbbbbbbbbbb") {
127            ImmutResult::Changed(l) => entity_list = l,
128            ImmutResult::Unchanged => {}
129        };
130
131        assert_eq!(entity_list, &b"aaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbcccccccccccccccc"[..]);
132    }
133
134    #[test]
135    fn insert_document_mut_32() {
136        let mut entity_list: Vec<u8> = Vec::new();
137
138        insert_entity_mut::<U32>(&mut entity_list, b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
139        insert_entity_mut::<U32>(&mut entity_list, b"cccccccccccccccccccccccccccccccc");
140        insert_entity_mut::<U32>(&mut entity_list, b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
141        insert_entity_mut::<U32>(&mut entity_list, b"bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb");
142
143        assert_eq!(
144            &entity_list[..],
145            &b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccccccccccccc"[..]
146        );
147    }
148    #[test]
149    fn insert_document_immut_32() {
150        let mut entity_list = Vec::new();
151
152        match insert_entity_immut::<U32>(&entity_list, b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") {
153            ImmutResult::Changed(l) => entity_list = l,
154            ImmutResult::Unchanged => {}
155        };
156        match insert_entity_immut::<U32>(&entity_list, b"cccccccccccccccccccccccccccccccc") {
157            ImmutResult::Changed(l) => entity_list = l,
158            ImmutResult::Unchanged => {}
159        };
160        match insert_entity_immut::<U32>(&entity_list, b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") {
161            ImmutResult::Changed(l) => entity_list = l,
162            ImmutResult::Unchanged => {}
163        };
164        match insert_entity_immut::<U32>(&entity_list, b"bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb") {
165            ImmutResult::Changed(l) => entity_list = l,
166            ImmutResult::Unchanged => {}
167        };
168
169        assert_eq!(
170            entity_list,
171            &b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccccccccccccc"[..]
172        );
173    }
174}
inverted_index_util/entity_list.rs

inverted_index_util/
entity_list.rs
