1
use crate::{
2
    error::PersyError,
3
    index::{
4
        config::{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: IndexType, V: IndexType> Node<K, V> {
25 1
    pub fn merge_right(&mut self, k: K, node: &mut Node<K, V>) {
26 1
        match self {
27 1
            Node::NODE(n) => match node {
28 0
                Node::NODE(n1) => {
29 0
                    n.merge_right(k, n1);
30
                }
31
                Node::LEAF(_) => {
32 0
                    panic!("impossible merge a leaf to node");
33
                }
34
            },
35 1
            Node::LEAF(l) => match node {
36 1
                Node::NODE(_) => {
37 0
                    panic!("impossible merge a node to leaf");
38
                }
39 1
                Node::LEAF(l1) => {
40 1
                    l.merge_right(l1);
41
                }
42
            },
43
        }
44 1
    }
45 1
    pub fn len(&self) -> usize {
46 1
        match self {
47 1
            Node::NODE(n) => n.len(),
48 1
            Node::LEAF(l) => l.len(),
49
        }
50 1
    }
51 1
    pub fn split(&mut self, top_limit: usize) -> Vec<(K, Node<K, V>)> {
52 1
        match self {
53 1
            Node::NODE(n) => n.split(top_limit).into_iter().map(|x| (x.0, Node::NODE(x.1))).collect(),
54 1
            Node::LEAF(l) => l.split(top_limit).into_iter().map(|x| (x.0, Node::LEAF(x.1))).collect(),
55
        }
56 1
    }
57 1
    pub fn get_prev(&self) -> &Option<K> {
58 1
        match self {
59 1
            Node::NODE(n) => &n.prev,
60 1
            Node::LEAF(l) => &l.prev,
61
        }
62 1
    }
63 1
    pub fn get_next(&self) -> &Option<K> {
64 1
        match self {
65 1
            Node::NODE(n) => &n.next,
66 1
            Node::LEAF(l) => &l.next,
67
        }
68 1
    }
69 1
    pub fn check_range(&self, k: &K) -> bool {
70 1
        match self {
71 1
            Node::NODE(n) => n.check_range(k),
72 1
            Node::LEAF(l) => l.check_range(k),
73
        }
74 1
    }
75
}
76

77 1
pub(crate) fn compare<T: IndexType>(first: &T, second: &T) -> Ordering {
78 1
    first.cmp(second)
79 1
}
80

81 1
#[derive(Clone)]
82
pub struct Nodes<K> {
83 1
    pub keys: Vec<K>,
84 1
    pub pointers: Vec<NodeRef>,
85 1
    pub prev: Option<K>,
86 1
    pub next: Option<K>,
87
}
88

89
impl<K: IndexType> Nodes<K> {
90 1
    pub fn new_from_split(left: NodeRef, values: &[(K, NodeRef)]) -> Nodes<K> {
91 1
        let keys = values.iter().map(|z| z.0.clone()).collect();
92 1
        let mut pointers: Vec<NodeRef> = values.iter().map(|z| z.1.clone()).collect();
93 1
        pointers.insert(0, left);
94 1
        Nodes {
95 1
            keys,
96 1
            pointers,
97 1
            prev: None,
98 1
            next: None,
99
        }
100 1
    }
101

102 1
    pub fn add(&mut self, pos: usize, k: &K, node_ref: NodeRef) {
103 1
        self.keys.insert(pos, k.clone());
104 1
        self.pointers.insert(pos + 1, node_ref);
105 1
    }
106

107 1
    pub fn find(&self, k: &K) -> PosRef<K> {
108 1
        match self.keys.binary_search_by(|x| compare(x, k)) {
109 1
            Ok(index) => {
110 1
                let sibling = Some(self.pointers[index].clone());
111 1
                PosRef::new(k, index + 1, self.pointers[index + 1].clone(), sibling)
112
            }
113 1
            Err(index) => {
114 1
                let sibling = if index > 0 {
115 1
                    Some(self.pointers[index - 1].clone())
116 1
                } else if self.pointers.len() > index + 1 {
117 1
                    Some(self.pointers[index + 1].clone())
118
                } else {
119 0
                    None
120
                };
121 1
                PosRef::new(k, index, self.pointers[index].clone(), sibling)
122
            }
123
        }
124 1
    }
125 1
    pub fn find_write(&self, k: &K) -> Option<PosRef<K>> {
126 1
        let pos = self.find(k);
127 1
        if pos.pos == 0 {
128 1
            if let Some(pk) = &self.prev {
129 1
                if compare(k, pk) == Ordering::Less {
130 0
                    return None;
131
                }
132
            }
133 1
        } else if pos.pos == self.pointers.len() {
134 0
            if let Some(nk) = &self.next {
135 0
                if compare(k, nk) != Ordering::Less {
136 0
                    return None;
137
                }
138
            }
139
        }
140

141 1
        Some(pos)
142 1
    }
143

144 1
    pub fn get_key(&self, pos: usize) -> K {
145 1
        self.keys[pos].clone()
146 1
    }
147

148 1
    pub fn get(&self, pos: usize) -> NodeRef {
149 1
        self.pointers[pos].clone()
150 1
    }
151

152 1
    pub fn insert_after(&mut self, pos: usize, values: &mut Vec<(K, NodeRef)>) {
153 1
        values.reverse();
154 1
        for val in values.iter() {
155 1
            self.add(pos, &val.0, val.1.clone());
156
        }
157 1
    }
158

159 1
    pub fn remove(&mut self, pos: usize) -> Option<NodeRef> {
160 1
        if pos < self.pointers.len() {
161 1
            self.keys.remove(pos - 1);
162 1
            Some(self.pointers.remove(pos))
163
        } else {
164 0
            None
165
        }
166 1
    }
167

168 1
    pub fn len(&self) -> usize {
169 1
        self.pointers.len()
170 1
    }
171

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

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

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

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

228 1
    pub fn merge_right(&mut self, owner: K, nodes: &mut Nodes<K>) {
229 1
        self.keys.push(owner);
230 1
        self.keys.append(&mut nodes.keys);
231 1
        self.pointers.append(&mut nodes.pointers);
232 1
        self.next = nodes.next.clone();
233 1
    }
234

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

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

259
impl<V> IntoIterator for Value<V> {
260
    type Item = V;
261
    type IntoIter = IntoIter<V>;
262

263 1
    fn into_iter(self) -> IntoIter<V> {
264 1
        match self {
265 1
            Value::SINGLE(v) => vec![v].into_iter(),
266 0
            Value::CLUSTER(v) => v.into_iter(),
267
        }
268 1
    }
269
}
270

271
pub struct PageIter<K: IndexType, V: IndexType> {
272
    pub iter: Peekable<IntoIter<LeafEntry<K, V>>>,
273
}
274

275
pub struct PageIterBack<K: IndexType, V: IndexType> {
276
    pub iter: Peekable<Rev<IntoIter<LeafEntry<K, V>>>>,
277
}
278

279 1
#[derive(Clone)]
280
pub struct Leaf<K, V> {
281 1
    pub entries: Vec<LeafEntry<K, V>>,
282 1
    pub prev: Option<K>,
283 1
    pub next: Option<K>,
284
}
285

286 1
#[derive(Clone)]
287
pub struct LeafEntry<K, V> {
288 1
    pub key: K,
289 1
    pub value: Value<V>,
290
}
291

292
impl<K: IndexType, V: IndexType> Leaf<K, V> {
293 1
    pub fn new() -> Leaf<K, V> {
294 1
        Leaf {
295 1
            entries: Vec::new(),
296 1
            prev: None,
297 1
            next: None,
298
        }
299 1
    }
300

301 1
    pub fn add(&mut self, pos: usize, k: &K, v: &V, _value_mode: ValueMode) {
302 1
        self.entries.insert(
303
            pos,
304 1
            LeafEntry {
305 1
                key: k.clone(),
306 1
                value: Value::SINGLE(v.clone()),
307 0
            },
308
        );
309 1
    }
310

311 1
    pub fn find<'a>(&'a self, k: &K) -> Result<(K, Value<V>), usize> {
312 1
        self.entries
313 1
            .binary_search_by(|n| compare(&n.key, k))
314 1
            .map(|index| (self.entries[index].key.clone(), self.entries[index].value.clone()))
315 1
    }
316

317 1
    pub fn iter_from(&self, bound: Bound<&K>) -> IntoIter<LeafEntry<K, V>> {
318 1
        let index = match bound {
319 1
            Bound::Included(k) => match self.entries.binary_search_by(|n| compare(&n.key, k)) {
320 1
                Ok(index) => index,
321 0
                Err(index) => index,
322
            },
323 1
            Bound::Excluded(k) => match self.entries.binary_search_by(|n| compare(&n.key, k)) {
324 1
                Ok(index) => index + 1,
325 1
                Err(index) => index,
326
            },
327 1
            Bound::Unbounded => 0,
328
        };
329 1
        self.entries[index..].to_vec().into_iter()
330 1
    }
331

332 1
    pub fn back_iter_from(&self, bound: Bound<&K>) -> Rev<IntoIter<LeafEntry<K, V>>> {
333 1
        let index = match bound {
334 1
            Bound::Included(k) => match self.entries.binary_search_by(|n| compare(&n.key, k)) {
335 1
                Ok(index) => index + 1,
336 1
                Err(index) => index,
337
            },
338 1
            Bound::Excluded(k) => match self.entries.binary_search_by(|n| compare(&n.key, k)) {
339 1
                Ok(index) => index,
340 1
                Err(index) => index,
341
            },
342 1
            Bound::Unbounded => self.len(),
343
        };
344 1
        self.entries[..index].to_vec().into_iter().rev()
345 1
    }
346

347 1
    pub fn insert_or_update(&mut self, k: &K, v: &V, value_mode: ValueMode, index_name: &str) -> PRes<()> {
348 1
        match self.entries.binary_search_by(|n| compare(&n.key, k)) {
349 1
            Ok(index) => {
350 1
                let entry = &mut self.entries[index];
351 1
                match value_mode {
352 1
                    ValueMode::REPLACE => {
353 1
                        entry.value = Value::SINGLE(v.clone());
354
                    }
355
                    ValueMode::EXCLUSIVE => match entry.value {
356 1
                        Value::SINGLE(ref ev) => {
357 1
                            if compare(ev, v) != Ordering::Equal {
358 1
                                return Err(PersyError::IndexDuplicateKey(index_name.to_string(), format!("{}", k)));
359
                            }
360
                        }
361 0
                        _ => unreachable!("Exclusive leafs never have cluster values"),
362
                    },
363
                    ValueMode::CLUSTER => {
364 1
                        let mut new_value = None;
365 1
                        match entry.value {
366 1
                            Value::SINGLE(ref ev) => {
367 1
                                if compare(ev, v) != Ordering::Equal {
368 1
                                    new_value = Some(Value::CLUSTER(vec![ev.clone(), v.clone()]));
369
                                }
370
                            }
371 1
                            Value::CLUSTER(ref mut cl) => {
372 1
                                if let Err(index) = cl.binary_search_by(|x| compare(x, v)) {
373 1
                                    cl.insert(index, v.clone());
374
                                }
375
                            }
376
                        }
377 1
                        if let Some(v) = new_value {
378 1
                            entry.value = v;
379
                        }
380 1
                    }
381
                }
382
            }
383 1
            Err(index) => self.add(index, k, v, value_mode),
384
        }
385 1
        Ok(())
386 1
    }
387

388 1
    pub fn remove(&mut self, k: &K, v: &Option<V>) -> bool {
389 1
        match self.entries.binary_search_by(|n| compare(&n.key, k)) {
390 1
            Ok(index) => {
391 1
                if let Some(rv) = v {
392 1
                    let mut removed = false;
393
                    let remove_entry = {
394 1
                        let mut new_value = None;
395 1
                        let entry = &mut self.entries[index];
396 1
                        let remove_entry = match &mut entry.value {
397 1
                            Value::SINGLE(val) => {
398 1
                                if compare(val, rv) == Ordering::Equal {
399 1
                                    removed = true;
400 1
                                    true
401
                                } else {
402 1
                                    false
403
                                }
404
                            }
405 1
                            Value::CLUSTER(ref mut cl) => {
406 1
                                if let Ok(index) = cl.binary_search_by(|x| compare(x, rv)) {
407 1
                                    removed = true;
408 1
                                    cl.remove(index);
409
                                }
410 1
                                if cl.len() == 1 {
411 1
                                    new_value = Some(Value::SINGLE(cl.pop().unwrap()));
412 1
                                    false
413
                                } else {
414 1
                                    cl.is_empty()
415
                                }
416
                            }
417
                        };
418 1
                        if let Some(new) = new_value {
419 1
                            entry.value = new;
420
                        }
421 1
                        remove_entry
422 1
                    };
423 1
                    if remove_entry {
424 1
                        self.entries.remove(index);
425
                    }
426 1
                    removed
427
                } else {
428 1
                    self.entries.remove(index);
429 1
                    true
430
                }
431
            }
432 1
            Err(_) => false,
433
        }
434 1
    }
435

436 1
    pub fn len(&self) -> usize {
437 1
        self.entries.len()
438 1
    }
439

440 1
    pub fn split(&mut self, max: usize) -> Vec<(K, Leaf<K, V>)> {
441 1
        let mut split_result: Vec<(K, Leaf<K, V>)> = Vec::new();
442 1
        let size = self.entries.len();
443 1
        let n_split = size / max;
444 1
        let split_offset = size / (n_split + 1) + 1;
445 1
        let mut others = self.entries.split_off(split_offset);
446 1
        let pre_next = self.next.clone();
447 1
        while others.len() > max {
448 1
            let new = others.split_off(split_offset);
449 1
            let key = others[0].key.clone();
450 1
            if let Some((_, ref mut x)) = split_result.last_mut() {
451 1
                x.next = Some(key.clone());
452
            } else {
453 1
                self.next = Some(key.clone());
454
            }
455 1
            let leaf = Leaf {
456 1
                entries: others,
457 1
                prev: Some(key.clone()),
458 1
                next: None,
459 0
            };
460 1
            split_result.push((key, leaf));
461 1
            others = new;
462 1
        }
463

464 1
        let key = others[0].key.clone();
465 1
        if let Some((_, ref mut x)) = split_result.last_mut() {
466 1
            x.next = Some(key.clone());
467
        } else {
468 1
            self.next = Some(key.clone());
469
        }
470 1
        let leaf = Leaf {
471 1
            entries: others,
472 1
            prev: Some(key.clone()),
473 1
            next: pre_next,
474 0
        };
475 1
        split_result.push((key, leaf));
476
        split_result
477 1
    }
478

479
    #[allow(dead_code)]
480 1
    pub fn merge_left(&mut self, leaf: &mut Leaf<K, V>) {
481 1
        let mut entries = std::mem::replace(&mut leaf.entries, Vec::new());
482 1
        entries.append(&mut self.entries);
483 1
        self.entries = entries;
484 1
    }
485

486 1
    pub fn merge_right(&mut self, leaf: &mut Leaf<K, V>) {
487 1
        self.entries.append(&mut leaf.entries);
488 1
        self.next = leaf.next.clone();
489 1
    }
490 1
    fn check_range(&self, k: &K) -> bool {
491 1
        if let Some(x) = &self.prev {
492 1
            if compare(x, k) == Ordering::Greater {
493 0
                return false;
494
            }
495
        }
496 1
        if let Some(x) = &self.next {
497 1
            if compare(x, k) == Ordering::Less {
498 0
                return false;
499
            }
500
        }
501 1
        true
502 1
    }
503
}
504

505
#[cfg(test)]
506
mod tests {
507
    use super::{Leaf, NodeRef, Nodes, PosRef, Value, ValueMode};
508
    use crate::id::RecRef;
509
    use rand::random;
510

511 1
    fn random_pointer() -> NodeRef {
512 1
        RecRef::new(random::<u64>(), random::<u32>())
513 1
    }
514

515
    #[test]
516 1
    fn single_node_add_test() {
517 1
        let val1 = random_pointer();
518 1
        let val2 = random_pointer();
519 1
        let val3 = random_pointer();
520 1
        let val4 = random_pointer();
521 1
        let val5 = random_pointer();
522 1
        let val6 = random_pointer();
523 1
        let mut node = Nodes::new_from_split(val1, &[(0, val2)]);
524 1
        let pos = node.find(&2).pos;
525 1
        node.add(pos, &2, val3.clone());
526 1
        let pos = node.find(&5).pos;
527 1
        node.add(pos, &5, val4.clone());
528 1
        let pos = node.find(&6).pos;
529 1
        node.add(pos, &6, val5);
530 1
        let pos = node.find(&4).pos;
531 1
        node.add(pos, &4, val6.clone());
532

533 1
        let found = node.find(&4);
534 1
        assert_eq!(found.pos, 3);
535
        //If i search for 4 i get the one on the left of 4 so the value of 2 that is val3
536 1
        assert_eq!(found.node_ref, val6);
537

538 1
        let found = node.find(&5);
539 1
        assert_eq!(found.pos, 4);
540
        //If i search for 5 i get the one on the left of 5 so the value of 4 that is val6
541 1
        assert_eq!(found.node_ref, val4);
542

543 1
        let found = node.find(&3);
544
        //If i search for a value that do not exist i get the position of the value at is right
545
        //that is value 4 position 2
546 1
        assert_eq!(found.pos, 2);
547
        //If i search for 3 i get the value at the left of 4 that is val3
548 1
        assert_eq!(found.node_ref, val3);
549 1
    }
550

551
    #[test]
552 1
    fn single_leaf_insert_test() {
553 1
        let mut leaf = Leaf::new();
554 1
        for n in 0..50 {
555 1
            leaf.insert_or_update(&n, &n, ValueMode::REPLACE, "aa")
556
                .expect("insert is ok");
557
        }
558 1
        let res = leaf.find(&10);
559 1
        assert_eq!(Ok((10, Value::SINGLE(10))), res);
560

561 1
        let res = leaf.find(&60);
562 1
        assert_eq!(Err(50), res);
563 1
    }
564

565
    #[test]
566 1
    fn single_leaf_cluster_insert_test() {
567 1
        let mut leaf = Leaf::new();
568 1
        leaf.insert_or_update(&10, &1, ValueMode::CLUSTER, "aa")
569
            .expect("insert is ok");
570 1
        leaf.insert_or_update(&10, &2, ValueMode::CLUSTER, "aa")
571
            .expect("insert is ok");
572 1
        let res = leaf.find(&10);
573 1
        assert_eq!(Ok((10, Value::CLUSTER(vec![1, 2]))), res);
574 1
    }
575

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

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

600
    #[test]
601 1
    fn leaf_single_delete_not_exist_value_test() {
602 1
        let mut leaf = Leaf::new();
603 1
        leaf.insert_or_update(&10, &1, ValueMode::EXCLUSIVE, "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::SINGLE(1))), res);
608 1
    }
609

610
    #[test]
611 1
    fn leaf_duplicate_key_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
        let res = leaf.insert_or_update(&10, &2, ValueMode::EXCLUSIVE, "aa");
616 1
        assert!(res.is_err());
617 1
    }
618

619
    #[test]
620 1
    fn test_leaf_split() {
621 1
        let mut leaf = Leaf::new();
622

623 1
        for n in 0..103 {
624 1
            leaf.insert_or_update(&n, &n, ValueMode::REPLACE, "aa")
625
                .expect("insert is ok");
626
        }
627

628 1
        let res = leaf.split(21);
629 1
        assert_eq!(leaf.len(), 21);
630 1
        assert_eq!(res[0].1.len(), 21);
631 1
        assert_eq!(res[1].1.len(), 21);
632 1
        assert_eq!(res[2].1.len(), 21);
633 1
        assert_eq!(res[3].1.len(), 19);
634 1
    }
635

636
    #[test]
637 1
    fn test_node_split() {
638 1
        let mut node = Nodes::new_from_split(random_pointer(), &[(0, random_pointer())]);
639 1
        for n in 1..103 {
640 1
            let pos = node.find(&n).pos;
641 1
            node.add(pos, &n, random_pointer());
642
        }
643

644 1
        let res = node.split(21);
645 1
        assert_eq!(node.len(), 21);
646 1
        assert_eq!(node.pointers.len(), 21);
647 1
        assert_eq!(node.keys.len(), 20);
648 1
        assert_eq!(res[0].1.len(), 21);
649 1
        assert_eq!(res[0].1.pointers.len(), 21);
650 1
        assert_eq!(res[0].1.keys.len(), 20);
651 1
        assert_eq!(res[1].1.len(), 21);
652 1
        assert_eq!(res[1].1.pointers.len(), 21);
653 1
        assert_eq!(res[1].1.keys.len(), 20);
654 1
        assert_eq!(res[2].1.len(), 21);
655 1
        assert_eq!(res[2].1.pointers.len(), 21);
656 1
        assert_eq!(res[2].1.keys.len(), 20);
657 1
        assert_eq!(res[3].1.len(), 20);
658 1
        assert_eq!(res[3].1.pointers.len(), 20);
659 1
        assert_eq!(res[3].1.keys.len(), 19);
660 1
    }
661

662
    #[test]
663 1
    fn test_remove_from_leaf() {
664 1
        let mut leaf = Leaf::new();
665 1
        for n in 0..50 {
666 1
            leaf.insert_or_update(&n, &n, ValueMode::REPLACE, "aa")
667
                .expect("insert is ok");
668
        }
669 1
        assert!(leaf.remove(&10, &Some(10)));
670 1
        assert!(!leaf.remove(&100, &Some(100)));
671 1
        assert_eq!(leaf.len(), 49);
672 1
        let res = leaf.find(&10);
673 1
        assert_eq!(Err(10), res);
674 1
    }
675

676
    #[test]
677 1
    fn test_remove_from_node() {
678
        //TODO: check why the remove of 10 make to point to 9
679 1
        let mut node = Nodes::new_from_split(random_pointer(), &[(0, random_pointer())]);
680 1
        let mut keep_pre = None;
681 1
        let mut keep = None;
682 1
        for n in 1..50 {
683 1
            let pos = node.find(&n).pos;
684 1
            let point = random_pointer();
685 1
            if n == 8 {
686 1
                keep_pre = Some(point.clone());
687
            }
688 1
            if n == 9 {
689 1
                keep = Some(point.clone());
690
            }
691 1
            node.add(pos, &n, point);
692
        }
693 1
        let pos = node.find(&10).pos;
694 1
        node.remove(pos);
695 1
        assert_eq!(node.len(), 50);
696 1
        let res = node.find(&10);
697 1
        assert_eq!(PosRef::new(&10, 10, keep.unwrap(), keep_pre), res);
698 1
    }
699

700
    #[test]
701 1
    fn test_merge_leaf() {
702 1
        let mut leaf = Leaf::new();
703 1
        let mut leaf2 = Leaf::new();
704 1
        for n in 0..20 {
705 1
            leaf.insert_or_update(&n, &n, ValueMode::REPLACE, "aa")
706
                .expect("insert is ok");
707
        }
708

709 1
        for n in 20..40 {
710 1
            leaf2
711
                .insert_or_update(&n, &n, ValueMode::REPLACE, "aa")
712
                .expect("insert is ok");
713
        }
714 1
        leaf.merge_right(&mut leaf2);
715 1
        assert_eq!(leaf.len(), 40);
716 1
        assert_eq!(leaf2.len(), 0);
717 1
        let res = leaf.find(&35);
718 1
        assert_eq!(res, Ok((35, Value::SINGLE(35))));
719

720 1
        let mut leaf = Leaf::new();
721 1
        let mut leaf2 = Leaf::new();
722 1
        for n in 20..40 {
723 1
            leaf.insert_or_update(&n, &n, ValueMode::REPLACE, "aa")
724
                .expect("insert is ok");
725
        }
726

727 1
        for n in 0..20 {
728 1
            leaf2
729
                .insert_or_update(&n, &n, ValueMode::REPLACE, "aa")
730
                .expect("insert is ok");
731
        }
732 1
        leaf.merge_left(&mut leaf2);
733 1
        assert_eq!(leaf.len(), 40);
734 1
        assert_eq!(leaf2.len(), 0);
735 1
        let res = leaf.find(&35);
736 1
        assert_eq!(res, Ok((35, Value::SINGLE(35))));
737 1
    }
738

739
    #[test]
740 1
    fn test_merge_nodes() {
741 1
        let mut node = Nodes::new_from_split(random_pointer(), &[(0, random_pointer())]);
742 1
        for n in 1..20 {
743 1
            let pos = node.find(&n).pos;
744 1
            let point = random_pointer();
745 1
            node.add(pos, &n, point);
746
        }
747

748 1
        let mut node2 = Nodes::new_from_split(random_pointer(), &[(21, random_pointer())]);
749 1
        let mut keep_pre = None;
750 1
        let mut keep = None;
751 1
        for n in 22..40 {
752 1
            let pos = node2.find(&n).pos;
753 1
            let point = random_pointer();
754 1
            if n == 25 {
755 1
                keep_pre = Some(point.clone());
756
            }
757 1
            if n == 26 {
758 1
                keep = Some(point.clone());
759
            }
760 1
            node2.add(pos, &n, point);
761
        }
762

763 1
        node.merge_right(20, &mut node2);
764 1
        assert_eq!(node.len(), 41);
765 1
        assert_eq!(node2.len(), 0);
766 1
        let res = node.find(&26);
767 1
        assert_eq!(PosRef::new(&26, 27, keep.unwrap(), keep_pre), res);
768

769 1
        let mut node = Nodes::new_from_split(random_pointer(), &[(21, random_pointer())]);
770 1
        let mut keep_pre = None;
771 1
        let mut keep = None;
772 1
        for n in 22..40 {
773 1
            let pos = node.find(&n).pos;
774 1
            let point = random_pointer();
775 1
            if n == 25 {
776 1
                keep_pre = Some(point.clone());
777
            }
778 1
            if n == 26 {
779 1
                keep = Some(point.clone());
780
            }
781 1
            node.add(pos, &n, point);
782
        }
783

784 1
        let mut node2 = Nodes::new_from_split(random_pointer(), &[(0, random_pointer())]);
785 1
        for n in 1..20 {
786 1
            let pos = node2.find(&n).pos;
787 1
            let point = random_pointer();
788 1
            node2.add(pos, &n, point);
789
        }
790

791 1
        node.merge_left(20, &mut node2);
792 1
        assert_eq!(node.len(), 41);
793 1
        assert_eq!(node2.len(), 0);
794 1
        let res = node.find(&26);
795 1
        assert_eq!(PosRef::new(&26, 27, keep.unwrap(), keep_pre), res);
796 1
    }
797
}

Read our documentation on viewing source code .

Loading