1
use crate::{
2
    error::PersyError,
3
    index::{
4
        config::{IndexOrd, IndexType, ValueMode},
5
        tree::PosRef,
6
    },
7
    persy::RecRef,
8
    PRes,
9
};
10
use std::{
11
    cmp::Ordering,
12
    iter::{Peekable, Rev},
13
    ops::Bound,
14
    vec::IntoIter,
15
};
16

17
pub type NodeRef = RecRef;
18 1
#[derive(Clone)]
19
pub enum Node<K, V> {
20 1
    NODE(Nodes<K>),
21 1
    LEAF(Leaf<K, V>),
22
}
23

24
impl<K, V> Node<K, V> {
25 1
    pub fn get_prev(&self) -> &Option<K> {
26 1
        match self {
27 1
            Node::NODE(n) => &n.prev,
28 1
            Node::LEAF(l) => &l.prev,
29
        }
30 1
    }
31 1
    pub fn get_next(&self) -> &Option<K> {
32 1
        match self {
33 1
            Node::NODE(n) => &n.next,
34 1
            Node::LEAF(l) => &l.next,
35
        }
36 1
    }
37 1
    pub fn len(&self) -> usize {
38 1
        match self {
39 1
            Node::NODE(n) => n.len(),
40 1
            Node::LEAF(l) => l.len(),
41
        }
42 1
    }
43
}
44

45
impl<K: IndexOrd + Clone, V> Node<K, V> {
46 1
    pub fn merge_right(&mut self, k: K, node: &mut Node<K, V>) {
47 1
        match self {
48 1
            Node::NODE(n) => match node {
49 0
                Node::NODE(n1) => {
50 0
                    n.merge_right(k, n1);
51
                }
52
                Node::LEAF(_) => {
53 0
                    panic!("impossible merge a leaf to node");
54
                }
55
            },
56 1
            Node::LEAF(l) => match node {
57 1
                Node::NODE(_) => {
58 0
                    panic!("impossible merge a node to leaf");
59
                }
60 1
                Node::LEAF(l1) => {
61 1
                    l.merge_right(l1);
62
                }
63
            },
64
        }
65 1
    }
66

67 1
    pub fn split(&mut self, top_limit: usize) -> Vec<(K, Node<K, V>)> {
68 1
        match self {
69 1
            Node::NODE(n) => n.split(top_limit).into_iter().map(|x| (x.0, Node::NODE(x.1))).collect(),
70 1
            Node::LEAF(l) => l.split(top_limit).into_iter().map(|x| (x.0, Node::LEAF(x.1))).collect(),
71
        }
72 1
    }
73

74 1
    pub fn check_range(&self, k: &K) -> bool {
75 1
        match self {
76 1
            Node::NODE(n) => n.check_range(k),
77 1
            Node::LEAF(l) => l.check_range(k),
78
        }
79 1
    }
80
}
81

82 1
pub(crate) fn compare<T: IndexOrd>(first: &T, second: &T) -> Ordering {
83 1
    first.cmp(second)
84 1
}
85

86 1
#[derive(Clone)]
87
pub struct Nodes<K> {
88 1
    pub keys: Vec<K>,
89 1
    pub pointers: Vec<NodeRef>,
90 1
    pub prev: Option<K>,
91 1
    pub next: Option<K>,
92
}
93

94
impl<K> Nodes<K> {
95 1
    pub fn len(&self) -> usize {
96 1
        self.pointers.len()
97 1
    }
98 1
    pub fn remove(&mut self, pos: usize) -> Option<NodeRef> {
99 1
        if pos < self.pointers.len() {
100 1
            self.keys.remove(pos - 1);
101 1
            Some(self.pointers.remove(pos))
102
        } else {
103 0
            None
104
        }
105 1
    }
106
}
107
impl<K: IndexOrd + Clone> Nodes<K> {
108 1
    pub fn new_from_split(left: NodeRef, values: &[(K, NodeRef)]) -> Nodes<K> {
109 1
        let keys = values.iter().map(|z| z.0.clone()).collect();
110 1
        let mut pointers: Vec<NodeRef> = values.iter().map(|z| z.1.clone()).collect();
111 1
        pointers.insert(0, left);
112 1
        Nodes {
113 1
            keys,
114 1
            pointers,
115 1
            prev: None,
116 1
            next: None,
117
        }
118 1
    }
119

120 1
    pub fn add(&mut self, pos: usize, k: &K, node_ref: NodeRef) {
121 1
        self.keys.insert(pos, k.clone());
122 1
        self.pointers.insert(pos + 1, node_ref);
123 1
    }
124

125 1
    pub fn find(&self, k: &K) -> PosRef<K> {
126 1
        match self.keys.binary_search_by(|x| compare(x, k)) {
127 1
            Ok(index) => {
128 1
                let sibling = Some(self.pointers[index].clone());
129 1
                PosRef::new(k, index + 1, self.pointers[index + 1].clone(), sibling)
130
            }
131 1
            Err(index) => {
132 1
                let sibling = if index > 0 {
133 1
                    Some(self.pointers[index - 1].clone())
134 1
                } else if self.pointers.len() > index + 1 {
135 1
                    Some(self.pointers[index + 1].clone())
136
                } else {
137 0
                    None
138
                };
139 1
                PosRef::new(k, index, self.pointers[index].clone(), sibling)
140
            }
141
        }
142 1
    }
143 1
    pub fn find_write(&self, k: &K) -> Option<PosRef<K>> {
144 1
        let pos = self.find(k);
145 1
        if pos.pos == 0 {
146 1
            if let Some(pk) = &self.prev {
147 1
                if compare(k, pk) == Ordering::Less {
148 0
                    return None;
149
                }
150
            }
151 1
        } else if pos.pos == self.pointers.len() {
152 0
            if let Some(nk) = &self.next {
153 0
                if compare(k, nk) != Ordering::Less {
154 0
                    return None;
155
                }
156
            }
157
        }
158

159 1
        Some(pos)
160 1
    }
161

162 1
    pub fn get_key(&self, pos: usize) -> K {
163 1
        self.keys[pos].clone()
164 1
    }
165

166 1
    pub fn get(&self, pos: usize) -> NodeRef {
167 1
        self.pointers[pos].clone()
168 1
    }
169

170 1
    pub fn insert_after(&mut self, pos: usize, values: &mut Vec<(K, NodeRef)>) {
171 1
        values.reverse();
172 1
        for (key, node) in values.iter() {
173 1
            self.add(pos, &key, node.clone());
174
        }
175 1
    }
176

177 1
    pub fn split(&mut self, max: usize) -> Vec<(K, Nodes<K>)> {
178 1
        let mut split_result: Vec<(K, Nodes<K>)> = Vec::new();
179 1
        let size = self.keys.len();
180 1
        let n_split = size / max;
181 1
        let split_offset = size / (n_split + 1) + 1;
182 1
        let mut others = self.keys.split_off(split_offset - 1);
183 1
        let mut other_pointers = self.pointers.split_off(split_offset);
184

185 1
        let pre_next = self.next.clone();
186 1
        while others.len() > max {
187 1
            let new = others.split_off(split_offset);
188 1
            let new_pointers = other_pointers.split_off(split_offset);
189 1
            let key = others.remove(0);
190 1
            if let Some((_, ref mut x)) = split_result.last_mut() {
191 1
                x.next = Some(key.clone());
192
            } else {
193 1
                self.next = Some(key.clone());
194
            }
195 1
            let leaf = Nodes {
196 1
                keys: others,
197 1
                pointers: other_pointers,
198 1
                prev: Some(key.clone()),
199 1
                next: None,
200 0
            };
201 1
            split_result.push((key, leaf));
202 1
            others = new;
203 1
            other_pointers = new_pointers;
204 1
        }
205

206 1
        let key = others.remove(0);
207 1
        if let Some((_, ref mut x)) = split_result.last_mut() {
208 1
            x.next = Some(key.clone());
209
        } else {
210 1
            self.next = Some(key.clone());
211
        }
212 1
        let leaf = Nodes {
213 1
            keys: others,
214 1
            pointers: other_pointers,
215 1
            prev: Some(key.clone()),
216 1
            next: pre_next,
217 0
        };
218 1
        split_result.push((key, leaf));
219
        split_result
220 1
    }
221

222
    #[allow(dead_code)]
223 1
    pub fn merge_left(&mut self, owner: K, nodes: &mut Nodes<K>) {
224 1
        let mut keys = std::mem::replace(&mut nodes.keys, Vec::new());
225 1
        let mut pointers = std::mem::replace(&mut nodes.pointers, Vec::new());
226 1
        keys.push(owner);
227 1
        keys.append(&mut self.keys);
228 1
        pointers.append(&mut self.pointers);
229 1
        self.keys = keys;
230 1
        self.pointers = pointers;
231 1
    }
232

233 1
    pub fn merge_right(&mut self, owner: K, nodes: &mut Nodes<K>) {
234 1
        self.keys.push(owner);
235 1
        self.keys.append(&mut nodes.keys);
236 1
        self.pointers.append(&mut nodes.pointers);
237 1
        self.next = nodes.next.clone();
238 1
    }
239

240 1
    fn check_range(&self, k: &K) -> bool {
241 1
        if let Some(x) = &self.prev {
242 1
            if compare(x, k) == Ordering::Greater {
243 0
                return false;
244
            }
245
        }
246 1
        if let Some(x) = &self.next {
247 1
            if compare(x, k) == Ordering::Less {
248 0
                return false;
249
            }
250
        }
251 1
        true
252 1
    }
253
}
254

255
/// The associated value to the index key
256 1
#[derive(Clone, PartialEq, Debug)]
257
pub enum Value<V> {
258
    /// A cluster of values
259 1
    CLUSTER(Vec<V>),
260
    /// A single value entry
261 1
    SINGLE(V),
262
}
263

264
impl<V> IntoIterator for Value<V> {
265
    type Item = V;
266
    type IntoIter = IntoIter<V>;
267

268 1
    fn into_iter(self) -> IntoIter<V> {
269 1
        match self {
270 1
            Value::SINGLE(v) => vec![v].into_iter(),
271 0
            Value::CLUSTER(v) => v.into_iter(),
272
        }
273 1
    }
274
}
275

276
pub struct PageIter<K, V> {
277
    pub iter: Peekable<IntoIter<LeafEntry<K, V>>>,
278
}
279

280
pub struct PageIterBack<K, V> {
281
    pub iter: Peekable<Rev<IntoIter<LeafEntry<K, V>>>>,
282
}
283

284 1
#[derive(Clone)]
285
pub struct Leaf<K, V> {
286 1
    pub entries: Vec<LeafEntry<K, V>>,
287 1
    pub prev: Option<K>,
288 1
    pub next: Option<K>,
289
}
290

291 1
#[derive(Clone)]
292
pub struct LeafEntry<K, V> {
293 1
    pub key: K,
294 1
    pub value: Value<V>,
295
}
296

297
impl<K, V> Leaf<K, V> {
298 1
    pub fn new() -> Leaf<K, V> {
299 1
        Leaf {
300 1
            entries: Vec::new(),
301 1
            prev: None,
302 1
            next: None,
303
        }
304 1
    }
305

306 1
    pub fn len(&self) -> usize {
307 1
        self.entries.len()
308 1
    }
309

310
    #[allow(dead_code)]
311 1
    pub fn merge_left(&mut self, leaf: &mut Leaf<K, V>) {
312 1
        let mut entries = std::mem::replace(&mut leaf.entries, Vec::new());
313 1
        entries.append(&mut self.entries);
314 1
        self.entries = entries;
315 1
    }
316
}
317

318
impl<K: IndexOrd + Clone, V> Leaf<K, V> {
319 1
    fn check_range(&self, k: &K) -> bool {
320 1
        if let Some(x) = &self.prev {
321 1
            if compare(x, k) == Ordering::Greater {
322 0
                return false;
323
            }
324
        }
325 1
        if let Some(x) = &self.next {
326 1
            if compare(x, k) == Ordering::Less {
327 0
                return false;
328
            }
329
        }
330 1
        true
331 1
    }
332 1
    pub fn merge_right(&mut self, leaf: &mut Leaf<K, V>) {
333 1
        self.entries.append(&mut leaf.entries);
334 1
        self.next = leaf.next.clone();
335 1
    }
336

337 1
    pub fn split(&mut self, max: usize) -> Vec<(K, Leaf<K, V>)> {
338 1
        let mut split_result: Vec<(K, Leaf<K, V>)> = Vec::new();
339 1
        let size = self.entries.len();
340 1
        let n_split = size / max;
341 1
        let split_offset = size / (n_split + 1) + 1;
342 1
        let mut others = self.entries.split_off(split_offset);
343 1
        let pre_next = self.next.clone();
344 1
        while others.len() > max {
345 1
            let new = others.split_off(split_offset);
346 1
            let key = others[0].key.clone();
347 1
            if let Some((_, ref mut x)) = split_result.last_mut() {
348 1
                x.next = Some(key.clone());
349
            } else {
350 1
                self.next = Some(key.clone());
351
            }
352 1
            let leaf = Leaf {
353 1
                entries: others,
354 1
                prev: Some(key.clone()),
355 1
                next: None,
356 0
            };
357 1
            split_result.push((key, leaf));
358 1
            others = new;
359 1
        }
360

361 1
        let key = others[0].key.clone();
362 1
        if let Some((_, ref mut x)) = split_result.last_mut() {
363 1
            x.next = Some(key.clone());
364
        } else {
365 1
            self.next = Some(key.clone());
366
        }
367 1
        let leaf = Leaf {
368 1
            entries: others,
369 1
            prev: Some(key.clone()),
370 1
            next: pre_next,
371 0
        };
372 1
        split_result.push((key, leaf));
373
        split_result
374 1
    }
375
}
376
impl<K: IndexOrd + Clone, V: Clone> Leaf<K, V> {
377 1
    pub fn find<'a>(&'a self, k: &K) -> Result<(K, Value<V>), usize> {
378 1
        self.entries
379 1
            .binary_search_by(|n| compare(&n.key, k))
380 1
            .map(|index| (self.entries[index].key.clone(), self.entries[index].value.clone()))
381 1
    }
382

383 1
    pub fn add(&mut self, pos: usize, k: &K, v: &V, _value_mode: ValueMode) {
384 1
        self.entries.insert(
385
            pos,
386 1
            LeafEntry {
387 1
                key: k.clone(),
388 1
                value: Value::SINGLE(v.clone()),
389 0
            },
390
        );
391 1
    }
392

393 1
    pub fn iter_from(&self, bound: Bound<&K>) -> IntoIter<LeafEntry<K, V>> {
394 1
        let index = match bound {
395 1
            Bound::Included(k) => match self.entries.binary_search_by(|n| compare(&n.key, k)) {
396 1
                Ok(index) => index,
397 0
                Err(index) => index,
398
            },
399 1
            Bound::Excluded(k) => match self.entries.binary_search_by(|n| compare(&n.key, k)) {
400 1
                Ok(index) => index + 1,
401 1
                Err(index) => index,
402
            },
403 1
            Bound::Unbounded => 0,
404
        };
405 1
        self.entries[index..].to_vec().into_iter()
406 1
    }
407

408 1
    pub fn back_iter_from(&self, bound: Bound<&K>) -> Rev<IntoIter<LeafEntry<K, V>>> {
409 1
        let index = match bound {
410 1
            Bound::Included(k) => match self.entries.binary_search_by(|n| compare(&n.key, k)) {
411 1
                Ok(index) => index + 1,
412 1
                Err(index) => index,
413
            },
414 1
            Bound::Excluded(k) => match self.entries.binary_search_by(|n| compare(&n.key, k)) {
415 1
                Ok(index) => index,
416 1
                Err(index) => index,
417
            },
418 1
            Bound::Unbounded => self.len(),
419
        };
420 1
        self.entries[..index].to_vec().into_iter().rev()
421 1
    }
422
}
423

424
impl<K: IndexType, V: IndexOrd + Clone> Leaf<K, V> {
425 1
    pub fn insert_or_update(&mut self, k: &K, v: &V, value_mode: ValueMode, index_name: &str) -> PRes<()> {
426 1
        match self.entries.binary_search_by(|n| compare(&n.key, k)) {
427 1
            Ok(index) => {
428 1
                let entry = &mut self.entries[index];
429 1
                match value_mode {
430 1
                    ValueMode::REPLACE => {
431 1
                        entry.value = Value::SINGLE(v.clone());
432
                    }
433
                    ValueMode::EXCLUSIVE => match entry.value {
434 1
                        Value::SINGLE(ref ev) => {
435 1
                            if compare(ev, v) != Ordering::Equal {
436 1
                                return Err(PersyError::IndexDuplicateKey(index_name.to_string(), format!("{}", k)));
437
                            }
438
                        }
439 0
                        _ => unreachable!("Exclusive leafs never have cluster values"),
440
                    },
441
                    ValueMode::CLUSTER => {
442 1
                        let mut new_value = None;
443 1
                        match entry.value {
444 1
                            Value::SINGLE(ref ev) => {
445 1
                                if compare(ev, v) != Ordering::Equal {
446 1
                                    new_value = Some(Value::CLUSTER(vec![ev.clone(), v.clone()]));
447
                                }
448
                            }
449 1
                            Value::CLUSTER(ref mut cl) => {
450 1
                                if let Err(index) = cl.binary_search_by(|x| compare(x, v)) {
451 1
                                    cl.insert(index, v.clone());
452
                                }
453
                            }
454
                        }
455 1
                        if let Some(v) = new_value {
456 1
                            entry.value = v;
457
                        }
458 1
                    }
459
                }
460
            }
461 1
            Err(index) => self.add(index, k, v, value_mode),
462
        }
463 1
        Ok(())
464 1
    }
465

466 1
    pub fn remove(&mut self, k: &K, v: &Option<V>) -> bool {
467 1
        match self.entries.binary_search_by(|n| compare(&n.key, k)) {
468 1
            Ok(index) => {
469 1
                if let Some(rv) = v {
470 1
                    let mut removed = false;
471
                    let remove_entry = {
472 1
                        let mut new_value = None;
473 1
                        let entry = &mut self.entries[index];
474 1
                        let remove_entry = match &mut entry.value {
475 1
                            Value::SINGLE(val) => {
476 1
                                if compare(val, rv) == Ordering::Equal {
477 1
                                    removed = true;
478 1
                                    true
479
                                } else {
480 1
                                    false
481
                                }
482
                            }
483 1
                            Value::CLUSTER(ref mut cl) => {
484 1
                                if let Ok(index) = cl.binary_search_by(|x| compare(x, rv)) {
485 1
                                    removed = true;
486 1
                                    cl.remove(index);
487
                                }
488 1
                                if cl.len() == 1 {
489 1
                                    new_value = Some(Value::SINGLE(cl.pop().unwrap()));
490 1
                                    false
491
                                } else {
492 1
                                    cl.is_empty()
493
                                }
494
                            }
495
                        };
496 1
                        if let Some(new) = new_value {
497 1
                            entry.value = new;
498
                        }
499 1
                        remove_entry
500 1
                    };
501 1
                    if remove_entry {
502 1
                        self.entries.remove(index);
503
                    }
504 1
                    removed
505
                } else {
506 1
                    self.entries.remove(index);
507 1
                    true
508
                }
509
            }
510 1
            Err(_) => false,
511
        }
512 1
    }
513
}
514

515
#[cfg(test)]
516
mod tests {
517
    use super::{Leaf, NodeRef, Nodes, PosRef, Value, ValueMode};
518
    use crate::id::RecRef;
519
    use rand::random;
520

521 1
    fn random_pointer() -> NodeRef {
522 1
        RecRef::new(random::<u64>(), random::<u32>())
523 1
    }
524

525
    #[test]
526 1
    fn single_node_add_test() {
527 1
        let val1 = random_pointer();
528 1
        let val2 = random_pointer();
529 1
        let val3 = random_pointer();
530 1
        let val4 = random_pointer();
531 1
        let val5 = random_pointer();
532 1
        let val6 = random_pointer();
533 1
        let mut node = Nodes::new_from_split(val1, &[(0, val2)]);
534 1
        let pos = node.find(&2).pos;
535 1
        node.add(pos, &2, val3.clone());
536 1
        let pos = node.find(&5).pos;
537 1
        node.add(pos, &5, val4.clone());
538 1
        let pos = node.find(&6).pos;
539 1
        node.add(pos, &6, val5);
540 1
        let pos = node.find(&4).pos;
541 1
        node.add(pos, &4, val6.clone());
542

543 1
        let found = node.find(&4);
544 1
        assert_eq!(found.pos, 3);
545
        //If i search for 4 i get the one on the left of 4 so the value of 2 that is val3
546 1
        assert_eq!(found.node_ref, val6);
547

548 1
        let found = node.find(&5);
549 1
        assert_eq!(found.pos, 4);
550
        //If i search for 5 i get the one on the left of 5 so the value of 4 that is val6
551 1
        assert_eq!(found.node_ref, val4);
552

553 1
        let found = node.find(&3);
554
        //If i search for a value that do not exist i get the position of the value at is right
555
        //that is value 4 position 2
556 1
        assert_eq!(found.pos, 2);
557
        //If i search for 3 i get the value at the left of 4 that is val3
558 1
        assert_eq!(found.node_ref, val3);
559 1
    }
560

561
    #[test]
562 1
    fn single_leaf_insert_test() {
563 1
        let mut leaf = Leaf::new();
564 1
        for n in 0..50 {
565 1
            leaf.insert_or_update(&n, &n, ValueMode::REPLACE, "aa")
566
                .expect("insert is ok");
567
        }
568 1
        let res = leaf.find(&10);
569 1
        assert_eq!(Ok((10, Value::SINGLE(10))), res);
570

571 1
        let res = leaf.find(&60);
572 1
        assert_eq!(Err(50), res);
573 1
    }
574

575
    #[test]
576 1
    fn single_leaf_cluster_insert_test() {
577 1
        let mut leaf = Leaf::new();
578 1
        leaf.insert_or_update(&10, &1, ValueMode::CLUSTER, "aa")
579
            .expect("insert is ok");
580 1
        leaf.insert_or_update(&10, &2, ValueMode::CLUSTER, "aa")
581
            .expect("insert is ok");
582 1
        let res = leaf.find(&10);
583 1
        assert_eq!(Ok((10, Value::CLUSTER(vec![1, 2]))), res);
584 1
    }
585

586
    #[test]
587 1
    fn leaf_cluster_remove_test() {
588 1
        let mut leaf = Leaf::new();
589 1
        leaf.insert_or_update(&10, &1, ValueMode::CLUSTER, "aa")
590
            .expect("insert is ok");
591 1
        leaf.insert_or_update(&10, &2, ValueMode::CLUSTER, "aa")
592
            .expect("insert is ok");
593 1
        assert!(leaf.remove(&10, &Some(2)));
594 1
        let res = leaf.find(&10);
595 1
        assert_eq!(Ok((10, Value::SINGLE(1))), res);
596 1
    }
597

598
    #[test]
599 1
    fn leaf_cluster_remove_not_exist_value_test() {
600 1
        let mut leaf = Leaf::new();
601 1
        leaf.insert_or_update(&10, &1, ValueMode::CLUSTER, "aa")
602
            .expect("insert is ok");
603 1
        leaf.insert_or_update(&10, &2, ValueMode::CLUSTER, "aa")
604
            .expect("insert is ok");
605 1
        assert!(!leaf.remove(&10, &Some(10)));
606 1
        let res = leaf.find(&10);
607 1
        assert_eq!(Ok((10, Value::CLUSTER(vec![1, 2]))), res);
608 1
    }
609

610
    #[test]
611 1
    fn leaf_single_delete_not_exist_value_test() {
612 1
        let mut leaf = Leaf::new();
613 1
        leaf.insert_or_update(&10, &1, ValueMode::EXCLUSIVE, "aa")
614
            .expect("insert is ok");
615 1
        assert!(!leaf.remove(&10, &Some(10)));
616 1
        let res = leaf.find(&10);
617 1
        assert_eq!(Ok((10, Value::SINGLE(1))), res);
618 1
    }
619

620
    #[test]
621 1
    fn leaf_duplicate_key_test() {
622 1
        let mut leaf = Leaf::new();
623 1
        leaf.insert_or_update(&10, &1, ValueMode::EXCLUSIVE, "aa")
624
            .expect("insert is ok");
625 1
        let res = leaf.insert_or_update(&10, &2, ValueMode::EXCLUSIVE, "aa");
626 1
        assert!(res.is_err());
627 1
    }
628

629
    #[test]
630 1
    fn test_leaf_split() {
631 1
        let mut leaf = Leaf::new();
632

633 1
        for n in 0..103 {
634 1
            leaf.insert_or_update(&n, &n, ValueMode::REPLACE, "aa")
635
                .expect("insert is ok");
636
        }
637

638 1
        let res = leaf.split(21);
639 1
        assert_eq!(leaf.len(), 21);
640 1
        assert_eq!(res[0].1.len(), 21);
641 1
        assert_eq!(res[1].1.len(), 21);
642 1
        assert_eq!(res[2].1.len(), 21);
643 1
        assert_eq!(res[3].1.len(), 19);
644 1
    }
645

646
    #[test]
647 1
    fn test_node_split() {
648 1
        let mut node = Nodes::new_from_split(random_pointer(), &[(0, random_pointer())]);
649 1
        for n in 1..103 {
650 1
            let pos = node.find(&n).pos;
651 1
            node.add(pos, &n, random_pointer());
652
        }
653

654 1
        let res = node.split(21);
655 1
        assert_eq!(node.len(), 21);
656 1
        assert_eq!(node.pointers.len(), 21);
657 1
        assert_eq!(node.keys.len(), 20);
658 1
        assert_eq!(res[0].1.len(), 21);
659 1
        assert_eq!(res[0].1.pointers.len(), 21);
660 1
        assert_eq!(res[0].1.keys.len(), 20);
661 1
        assert_eq!(res[1].1.len(), 21);
662 1
        assert_eq!(res[1].1.pointers.len(), 21);
663 1
        assert_eq!(res[1].1.keys.len(), 20);
664 1
        assert_eq!(res[2].1.len(), 21);
665 1
        assert_eq!(res[2].1.pointers.len(), 21);
666 1
        assert_eq!(res[2].1.keys.len(), 20);
667 1
        assert_eq!(res[3].1.len(), 20);
668 1
        assert_eq!(res[3].1.pointers.len(), 20);
669 1
        assert_eq!(res[3].1.keys.len(), 19);
670 1
    }
671

672
    #[test]
673 1
    fn test_remove_from_leaf() {
674 1
        let mut leaf = Leaf::new();
675 1
        for n in 0..50 {
676 1
            leaf.insert_or_update(&n, &n, ValueMode::REPLACE, "aa")
677
                .expect("insert is ok");
678
        }
679 1
        assert!(leaf.remove(&10, &Some(10)));
680 1
        assert!(!leaf.remove(&100, &Some(100)));
681 1
        assert_eq!(leaf.len(), 49);
682 1
        let res = leaf.find(&10);
683 1
        assert_eq!(Err(10), res);
684 1
    }
685

686
    #[test]
687 1
    fn test_remove_from_node() {
688
        //TODO: check why the remove of 10 make to point to 9
689 1
        let mut node = Nodes::new_from_split(random_pointer(), &[(0, random_pointer())]);
690 1
        let mut keep_pre = None;
691 1
        let mut keep = None;
692 1
        for n in 1..50 {
693 1
            let pos = node.find(&n).pos;
694 1
            let point = random_pointer();
695 1
            if n == 8 {
696 1
                keep_pre = Some(point.clone());
697
            }
698 1
            if n == 9 {
699 1
                keep = Some(point.clone());
700
            }
701 1
            node.add(pos, &n, point);
702
        }
703 1
        let pos = node.find(&10).pos;
704 1
        node.remove(pos);
705 1
        assert_eq!(node.len(), 50);
706 1
        let res = node.find(&10);
707 1
        assert_eq!(PosRef::new(&10, 10, keep.unwrap(), keep_pre), res);
708 1
    }
709

710
    #[test]
711 1
    fn test_merge_leaf() {
712 1
        let mut leaf = Leaf::new();
713 1
        let mut leaf2 = Leaf::new();
714 1
        for n in 0..20 {
715 1
            leaf.insert_or_update(&n, &n, ValueMode::REPLACE, "aa")
716
                .expect("insert is ok");
717
        }
718

719 1
        for n in 20..40 {
720 1
            leaf2
721 1
                .insert_or_update(&n, &n, ValueMode::REPLACE, "aa")
722
                .expect("insert is ok");
723
        }
724 1
        leaf.merge_right(&mut leaf2);
725 1
        assert_eq!(leaf.len(), 40);
726 1
        assert_eq!(leaf2.len(), 0);
727 1
        let res = leaf.find(&35);
728 1
        assert_eq!(res, Ok((35, Value::SINGLE(35))));
729

730 1
        let mut leaf = Leaf::new();
731 1
        let mut leaf2 = Leaf::new();
732 1
        for n in 20..40 {
733 1
            leaf.insert_or_update(&n, &n, ValueMode::REPLACE, "aa")
734
                .expect("insert is ok");
735
        }
736

737 1
        for n in 0..20 {
738 1
            leaf2
739 1
                .insert_or_update(&n, &n, ValueMode::REPLACE, "aa")
740
                .expect("insert is ok");
741
        }
742 1
        leaf.merge_left(&mut leaf2);
743 1
        assert_eq!(leaf.len(), 40);
744 1
        assert_eq!(leaf2.len(), 0);
745 1
        let res = leaf.find(&35);
746 1
        assert_eq!(res, Ok((35, Value::SINGLE(35))));
747 1
    }
748

749
    #[test]
750 1
    fn test_merge_nodes() {
751 1
        let mut node = Nodes::new_from_split(random_pointer(), &[(0, random_pointer())]);
752 1
        for n in 1..20 {
753 1
            let pos = node.find(&n).pos;
754 1
            let point = random_pointer();
755 1
            node.add(pos, &n, point);
756
        }
757

758 1
        let mut node2 = Nodes::new_from_split(random_pointer(), &[(21, random_pointer())]);
759 1
        let mut keep_pre = None;
760 1
        let mut keep = None;
761 1
        for n in 22..40 {
762 1
            let pos = node2.find(&n).pos;
763 1
            let point = random_pointer();
764 1
            if n == 25 {
765 1
                keep_pre = Some(point.clone());
766
            }
767 1
            if n == 26 {
768 1
                keep = Some(point.clone());
769
            }
770 1
            node2.add(pos, &n, point);
771
        }
772

773 1
        node.merge_right(20, &mut node2);
774 1
        assert_eq!(node.len(), 41);
775 1
        assert_eq!(node2.len(), 0);
776 1
        let res = node.find(&26);
777 1
        assert_eq!(PosRef::new(&26, 27, keep.unwrap(), keep_pre), res);
778

779 1
        let mut node = Nodes::new_from_split(random_pointer(), &[(21, random_pointer())]);
780 1
        let mut keep_pre = None;
781 1
        let mut keep = None;
782 1
        for n in 22..40 {
783 1
            let pos = node.find(&n).pos;
784 1
            let point = random_pointer();
785 1
            if n == 25 {
786 1
                keep_pre = Some(point.clone());
787
            }
788 1
            if n == 26 {
789 1
                keep = Some(point.clone());
790
            }
791 1
            node.add(pos, &n, point);
792
        }
793

794 1
        let mut node2 = Nodes::new_from_split(random_pointer(), &[(0, random_pointer())]);
795 1
        for n in 1..20 {
796 1
            let pos = node2.find(&n).pos;
797 1
            let point = random_pointer();
798 1
            node2.add(pos, &n, point);
799
        }
800

801 1
        node.merge_left(20, &mut node2);
802 1
        assert_eq!(node.len(), 41);
803 1
        assert_eq!(node2.len(), 0);
804 1
        let res = node.find(&26);
805 1
        assert_eq!(PosRef::new(&26, 27, keep.unwrap(), keep_pre), res);
806 1
    }
807
}

Read our documentation on viewing source code .

Loading