oxihuman-core 0.1.2

Core data structures, algorithms, and asset management for OxiHuman
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
// SPDX-License-Identifier: Apache-2.0
#![allow(dead_code)]

//! Rabin-Karp style rolling hash for sliding window operations.

use std::collections::VecDeque;

pub struct RollingHashNew {
    pub window: VecDeque<u8>,
    pub hash: u64,
    pub base: u64,
    pub modulus: u64,
    pub window_size: usize,
}

pub fn new_rolling_hash_new(window_size: usize) -> RollingHashNew {
    RollingHashNew {
        window: VecDeque::new(),
        hash: 0,
        base: 257,
        modulus: 1_000_000_007,
        window_size,
    }
}

pub fn rh_new_push(r: &mut RollingHashNew, byte: u8) {
    if r.window_size == 0 {
        return;
    }
    if r.window.len() == r.window_size {
        r.window.pop_front();
    }
    r.window.push_back(byte);
    // Recompute hash over current window
    let mut h: u64 = 0;
    for &b in &r.window {
        h = (h.wrapping_mul(r.base).wrapping_add(b as u64)) % r.modulus;
    }
    r.hash = h;
}

pub fn rh_new_hash(r: &RollingHashNew) -> u64 {
    r.hash
}

pub fn rh_new_window_full(r: &RollingHashNew) -> bool {
    r.window.len() == r.window_size
}

pub fn rh_new_window_size(r: &RollingHashNew) -> usize {
    r.window_size
}

pub fn rh_new_reset(r: &mut RollingHashNew) {
    r.window.clear();
    r.hash = 0;
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_new_rolling_hash() {
        /* new hash starts empty */
        let r = new_rolling_hash_new(4);
        assert_eq!(rh_new_hash(&r), 0);
        assert!(!rh_new_window_full(&r));
        assert_eq!(rh_new_window_size(&r), 4);
    }

    #[test]
    fn test_push_fills_window() {
        /* pushing window_size bytes fills the window */
        let mut r = new_rolling_hash_new(3);
        rh_new_push(&mut r, b'a');
        rh_new_push(&mut r, b'b');
        rh_new_push(&mut r, b'c');
        assert!(rh_new_window_full(&r));
    }

    #[test]
    fn test_push_beyond_window() {
        /* window size stays fixed after overflow */
        let mut r = new_rolling_hash_new(3);
        for b in b"abcdef" {
            rh_new_push(&mut r, *b);
        }
        assert!(rh_new_window_full(&r));
        assert_eq!(r.window.len(), 3);
    }

    #[test]
    fn test_hash_changes_on_push() {
        /* hash changes as bytes are pushed */
        let mut r = new_rolling_hash_new(4);
        rh_new_push(&mut r, b'x');
        let h1 = rh_new_hash(&r);
        rh_new_push(&mut r, b'y');
        let h2 = rh_new_hash(&r);
        assert_ne!(h1, h2);
    }

    #[test]
    fn test_reset_clears_state() {
        /* reset clears window and hash */
        let mut r = new_rolling_hash_new(4);
        rh_new_push(&mut r, b'a');
        rh_new_reset(&mut r);
        assert_eq!(rh_new_hash(&r), 0);
        assert!(!rh_new_window_full(&r));
    }

    #[test]
    fn test_same_sequence_same_hash() {
        /* same byte sequence produces same hash */
        let mut r1 = new_rolling_hash_new(3);
        let mut r2 = new_rolling_hash_new(3);
        for b in b"abc" {
            rh_new_push(&mut r1, *b);
            rh_new_push(&mut r2, *b);
        }
        assert_eq!(rh_new_hash(&r1), rh_new_hash(&r2));
    }

    #[test]
    fn test_window_size_zero() {
        /* zero-size window does nothing */
        let mut r = new_rolling_hash_new(0);
        rh_new_push(&mut r, b'a');
        assert_eq!(rh_new_hash(&r), 0);
    }
}