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

use noodles_bgzf as bgzf;
use noodles_core::Position;

use super::Index;
use crate::binning_index::index::reference_sequence::bin::Chunk;

/// A linear index.
pub type LinearIndex = Vec<bgzf::VirtualPosition>;

// _Sequence Alignment/Map Format Specification_ (2023-05-24) § 5.1.3 "Combining with linear
// index": "...each tiling 16384bp window..."
const WINDOW_SIZE: usize = 1 << 14;

impl Index for LinearIndex {
    fn min_offset(&self, _: u8, _: u8, start: Position) -> bgzf::VirtualPosition {
        let i = (usize::from(start) - 1) / WINDOW_SIZE;
        self.get(i).copied().unwrap_or_default()
    }

    fn last_first_start_position(&self) -> Option<bgzf::VirtualPosition> {
        self.last().copied()
    }

    fn update(&mut self, _: u8, _: u8, _: Position, end: Position, chunk: Chunk) {
        let end_index = (usize::from(end) - 1) / WINDOW_SIZE;
        let new_len = end_index + 1;

        if new_len > self.len() {
            self.resize(new_len, chunk.start());
        }
    }
}

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

    #[test]
    fn test_update() -> Result<(), noodles_core::position::TryFromIntError> {
        const MIN_SHIFT: u8 = 14;
        const DEPTH: u8 = 5;

        let mut index = LinearIndex::new();

        let start = Position::try_from(16385)?;
        let end = Position::try_from(65536)?;
        let chunk = Chunk::new(
            bgzf::VirtualPosition::from(8),
            bgzf::VirtualPosition::from(13),
        );
        index.update(MIN_SHIFT, DEPTH, start, end, chunk);

        assert_eq!(
            index,
            [
                bgzf::VirtualPosition::from(8),
                bgzf::VirtualPosition::from(8),
                bgzf::VirtualPosition::from(8),
                bgzf::VirtualPosition::from(8),
            ]
        );

        let start = Position::try_from(32769)?;
        let end = Position::try_from(49152)?;
        let chunk = Chunk::new(
            bgzf::VirtualPosition::from(13),
            bgzf::VirtualPosition::from(21),
        );
        index.update(MIN_SHIFT, DEPTH, start, end, chunk);

        assert_eq!(
            index,
            [
                bgzf::VirtualPosition::from(8),
                bgzf::VirtualPosition::from(8),
                bgzf::VirtualPosition::from(8),
                bgzf::VirtualPosition::from(8),
            ]
        );

        let start = Position::try_from(98305)?;
        let end = Position::try_from(114688)?;
        let chunk = Chunk::new(
            bgzf::VirtualPosition::from(21),
            bgzf::VirtualPosition::from(34),
        );
        index.update(MIN_SHIFT, DEPTH, start, end, chunk);

        assert_eq!(
            index,
            [
                bgzf::VirtualPosition::from(8),
                bgzf::VirtualPosition::from(8),
                bgzf::VirtualPosition::from(8),
                bgzf::VirtualPosition::from(8),
                bgzf::VirtualPosition::from(21),
                bgzf::VirtualPosition::from(21),
                bgzf::VirtualPosition::from(21),
            ]
        );

        Ok(())
    }
}