oxihuman_core/
skip_list_simple.rs

1// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3#![allow(dead_code)]
4
5//! Skip list stub backed by a sorted Vec of i64 keys.
6
7pub struct SkipListSimple {
8    pub entries: Vec<i64>,
9    pub max_level: usize,
10}
11
12pub fn new_skip_list_simple(max_level: usize) -> SkipListSimple {
13    SkipListSimple {
14        entries: Vec::new(),
15        max_level,
16    }
17}
18
19pub fn skip_simple_insert(s: &mut SkipListSimple, key: i64) {
20    match s.entries.binary_search(&key) {
21        Ok(_) => {} // already exists
22        Err(pos) => s.entries.insert(pos, key),
23    }
24}
25
26pub fn skip_simple_contains(s: &SkipListSimple, key: i64) -> bool {
27    s.entries.binary_search(&key).is_ok()
28}
29
30pub fn skip_simple_remove(s: &mut SkipListSimple, key: i64) -> bool {
31    match s.entries.binary_search(&key) {
32        Ok(pos) => {
33            s.entries.remove(pos);
34            true
35        }
36        Err(_) => false,
37    }
38}
39
40pub fn skip_simple_len(s: &SkipListSimple) -> usize {
41    s.entries.len()
42}
43
44pub fn skip_simple_range(s: &SkipListSimple, lo: i64, hi: i64) -> Vec<i64> {
45    s.entries
46        .iter()
47        .copied()
48        .filter(|&k| k >= lo && k <= hi)
49        .collect()
50}
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_new_skip_list_simple() {
58        /* new list is empty */
59        let s = new_skip_list_simple(4);
60        assert_eq!(skip_simple_len(&s), 0);
61    }
62
63    #[test]
64    fn test_insert_and_contains() {
65        /* inserted key is contained */
66        let mut s = new_skip_list_simple(4);
67        skip_simple_insert(&mut s, 10);
68        assert!(skip_simple_contains(&s, 10));
69    }
70
71    #[test]
72    fn test_not_contains() {
73        /* not inserted key not found */
74        let mut s = new_skip_list_simple(4);
75        skip_simple_insert(&mut s, 5);
76        assert!(!skip_simple_contains(&s, 99));
77    }
78
79    #[test]
80    fn test_remove() {
81        /* removing existing key returns true and removes it */
82        let mut s = new_skip_list_simple(4);
83        skip_simple_insert(&mut s, 7);
84        assert!(skip_simple_remove(&mut s, 7));
85        assert!(!skip_simple_contains(&s, 7));
86    }
87
88    #[test]
89    fn test_remove_nonexistent() {
90        /* removing missing key returns false */
91        let mut s = new_skip_list_simple(4);
92        assert!(!skip_simple_remove(&mut s, 42));
93    }
94
95    #[test]
96    fn test_range_query() {
97        /* range query returns correct subset */
98        let mut s = new_skip_list_simple(4);
99        for k in [1i64, 3, 5, 7, 9] {
100            skip_simple_insert(&mut s, k);
101        }
102        let r = skip_simple_range(&s, 3, 7);
103        assert_eq!(r, vec![3, 5, 7]);
104    }
105
106    #[test]
107    fn test_sorted_order() {
108        /* entries remain sorted */
109        let mut s = new_skip_list_simple(4);
110        for k in [5i64, 1, 3, 2, 4] {
111            skip_simple_insert(&mut s, k);
112        }
113        assert_eq!(s.entries, vec![1, 2, 3, 4, 5]);
114    }
115}
oxihuman_core/skip_list_simple.rs

oxihuman_core/
skip_list_simple.rs
