oxihuman_core/
skip_list.rs

1#![allow(dead_code)]
2// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
3// SPDX-License-Identifier: Apache-2.0
4
5//! Simplified skip list (sorted linked structure using Vec).
6
7#[allow(dead_code)]
8#[derive(Debug, Clone)]
9pub struct SkipEntry {
10    pub key: i64,
11    pub value: String,
12}
13
14#[allow(dead_code)]
15#[derive(Debug, Clone, Default)]
16pub struct SkipList {
17    pub entries: Vec<SkipEntry>,
18}
19
20#[allow(dead_code)]
21pub fn new_skip_list() -> SkipList {
22    SkipList {
23        entries: Vec::new(),
24    }
25}
26
27#[allow(dead_code)]
28pub fn skip_insert(sl: &mut SkipList, key: i64, val: &str) {
29    match sl.entries.binary_search_by_key(&key, |e| e.key) {
30        Ok(pos) => sl.entries[pos].value = val.to_string(),
31        Err(pos) => sl.entries.insert(
32            pos,
33            SkipEntry {
34                key,
35                value: val.to_string(),
36            },
37        ),
38    }
39}
40
41#[allow(dead_code)]
42pub fn skip_find(sl: &SkipList, key: i64) -> Option<&str> {
43    sl.entries
44        .binary_search_by_key(&key, |e| e.key)
45        .ok()
46        .map(|pos| sl.entries[pos].value.as_str())
47}
48
49#[allow(dead_code)]
50pub fn skip_remove(sl: &mut SkipList, key: i64) -> bool {
51    match sl.entries.binary_search_by_key(&key, |e| e.key) {
52        Ok(pos) => {
53            sl.entries.remove(pos);
54            true
55        }
56        Err(_) => false,
57    }
58}
59
60#[allow(dead_code)]
61pub fn skip_range(sl: &SkipList, lo: i64, hi: i64) -> Vec<(&i64, &str)> {
62    sl.entries
63        .iter()
64        .filter(|e| e.key >= lo && e.key <= hi)
65        .map(|e| (&e.key, e.value.as_str()))
66        .collect()
67}
68
69#[allow(dead_code)]
70pub fn skip_len(sl: &SkipList) -> usize {
71    sl.entries.len()
72}
73
74#[allow(dead_code)]
75pub fn sl_insert(list: &mut SkipList, key: i64, value: &str) {
76    skip_insert(list, key, value);
77}
78
79#[allow(dead_code)]
80pub fn sl_get(list: &SkipList, key: i64) -> Option<&str> {
81    skip_find(list, key)
82}
83
84#[allow(dead_code)]
85pub fn sl_remove(list: &mut SkipList, key: i64) -> bool {
86    skip_remove(list, key)
87}
88
89#[allow(dead_code)]
90pub fn sl_len(list: &SkipList) -> usize {
91    skip_len(list)
92}
93
94#[allow(dead_code)]
95pub fn sl_contains(list: &SkipList, key: i64) -> bool {
96    skip_find(list, key).is_some()
97}
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102
103    #[test]
104    fn new_list_empty() {
105        let sl = new_skip_list();
106        assert_eq!(skip_len(&sl), 0);
107    }
108
109    #[test]
110    fn insert_and_find() {
111        let mut sl = new_skip_list();
112        skip_insert(&mut sl, 10, "ten");
113        assert_eq!(skip_find(&sl, 10), Some("ten"));
114    }
115
116    #[test]
117    fn find_missing_returns_none() {
118        let sl = new_skip_list();
119        assert!(skip_find(&sl, 42).is_none());
120    }
121
122    #[test]
123    fn sorted_after_insert() {
124        let mut sl = new_skip_list();
125        skip_insert(&mut sl, 30, "c");
126        skip_insert(&mut sl, 10, "a");
127        skip_insert(&mut sl, 20, "b");
128        assert_eq!(sl.entries[0].key, 10);
129        assert_eq!(sl.entries[1].key, 20);
130        assert_eq!(sl.entries[2].key, 30);
131    }
132
133    #[test]
134    fn update_existing_key() {
135        let mut sl = new_skip_list();
136        skip_insert(&mut sl, 5, "old");
137        skip_insert(&mut sl, 5, "new");
138        assert_eq!(skip_find(&sl, 5), Some("new"));
139        assert_eq!(skip_len(&sl), 1);
140    }
141
142    #[test]
143    fn remove_existing() {
144        let mut sl = new_skip_list();
145        skip_insert(&mut sl, 7, "seven");
146        assert!(skip_remove(&mut sl, 7));
147        assert!(skip_find(&sl, 7).is_none());
148    }
149
150    #[test]
151    fn remove_missing_returns_false() {
152        let mut sl = new_skip_list();
153        assert!(!skip_remove(&mut sl, 99));
154    }
155
156    #[test]
157    fn range_query() {
158        let mut sl = new_skip_list();
159        for i in 0i64..10 {
160            skip_insert(&mut sl, i, &i.to_string());
161        }
162        let r = skip_range(&sl, 3, 6);
163        assert_eq!(r.len(), 4);
164        assert_eq!(*r[0].0, 3);
165        assert_eq!(*r[3].0, 6);
166    }
167
168    #[test]
169    fn range_empty() {
170        let mut sl = new_skip_list();
171        skip_insert(&mut sl, 1, "a");
172        skip_insert(&mut sl, 5, "b");
173        let r = skip_range(&sl, 2, 4);
174        assert!(r.is_empty());
175    }
176
177    #[test]
178    fn len_tracks_inserts_and_removes() {
179        let mut sl = new_skip_list();
180        skip_insert(&mut sl, 1, "a");
181        skip_insert(&mut sl, 2, "b");
182        assert_eq!(skip_len(&sl), 2);
183        skip_remove(&mut sl, 1);
184        assert_eq!(skip_len(&sl), 1);
185    }
186}
oxihuman_core/skip_list.rs

oxihuman_core/
skip_list.rs
