ff_structure/
pair_table.rs

1use std::ops::{Deref, DerefMut};
2use std::convert::TryFrom;
3use crate::StructureError;
4use crate::{DotBracket, DotBracketVec};
5
6#[derive(Debug, Clone, PartialEq, Eq)]
7pub struct PairTable(pub Vec<Option<usize>>);
8
9impl PairTable {
10    /// Check if the substructure from `i..j` is well-formed:
11    /// - All pairings are internal to the interval
12    pub fn is_well_formed(&self, i: usize, j: usize) -> bool {
13        assert!(j <= self.len(), "Invalid interval: j must be <= length");
14
15        for k in i..j {
16            if let Some(l) = self[k] {
17                if l < i || l >= j {
18                    return false; // points outside
19                }
20            }
21        }
22        true
23    }
24}
25
26impl Deref for PairTable {
27    type Target = [Option<usize>];
28
29    fn deref(&self) -> &Self::Target {
30        &self.0
31    }
32}
33
34impl DerefMut for PairTable {
35    fn deref_mut(&mut self) -> &mut Self::Target {
36        &mut self.0
37    }
38}
39
40impl TryFrom<&str> for PairTable {
41    type Error = StructureError;
42
43    fn try_from(s: &str) -> Result<Self, Self::Error> {
44        let mut stack = Vec::new();
45        let mut table = vec![None; s.len()];
46
47        for (i, c) in s.chars().enumerate() {
48            match c {
49                '(' => stack.push(i),
50                ')' => {
51                    let j = stack.pop().ok_or(StructureError::UnmatchedClose(i))?;
52                    table[i] = Some(j);
53                    table[j] = Some(i);
54                }
55                '.' => (),
56                _ => return Err(StructureError::InvalidToken(format!("character '{}'", c), "structure".to_string(), i)),
57            }
58        }
59
60        if let Some(i) = stack.pop() {
61            return Err(StructureError::UnmatchedOpen(i));
62        }
63        Ok(PairTable(table))
64    }
65}
66
67impl TryFrom<&DotBracketVec> for PairTable {
68    type Error = StructureError;
69
70    fn try_from(db: &DotBracketVec) -> Result<Self, Self::Error> {
71        let mut stack: Vec<usize> = Vec::new();
72        let mut table = vec![None; db.len()];
73
74        for (i, dot) in db.iter().enumerate() {
75            match dot {
76                DotBracket::Open => stack.push(i),
77                DotBracket::Close => {
78                    let j = stack.pop().ok_or(StructureError::UnmatchedClose(i))?;
79                    table[i] = Some(j);
80                    table[j] = Some(i);
81                }
82                DotBracket::Unpaired => {}
83                DotBracket::Break => unreachable!("unexpected Break in single-stranded case"),
84            }
85        }
86
87        if let Some(i) = stack.pop() {
88            return Err(StructureError::UnmatchedOpen(i));
89        }
90
91        Ok(PairTable(table))
92    }
93}
94
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99
100    #[test]
101    fn test_valid_pair_table() {
102        let pt = PairTable::try_from("((..))").unwrap();
103        assert_eq!(pt.len(), 6);
104        assert_eq!(pt[0], Some(5));
105        assert_eq!(pt[1], Some(4));
106        assert_eq!(pt[2], None);
107        assert_eq!(pt[3], None);
108        assert_eq!(pt[4], Some(1));
109        assert_eq!(pt[5], Some(0));
110    }
111
112    #[test]
113    fn test_unmatched_open() {
114        let err = PairTable::try_from("(()").unwrap_err();
115        assert_eq!(format!("{}", err), "Unmatched '(' at position 0");
116    }
117
118    #[test]
119    fn test_unmatched_close() {
120        let err = PairTable::try_from("())").unwrap_err();
121        assert_eq!(format!("{}", err), "Unmatched ')' at position 2");
122    }
123
124    #[test]
125    fn test_invalid_token() {
126        let err = PairTable::try_from("(x)").unwrap_err();
127        assert_eq!(format!("{}", err), "Invalid character 'x' in structure at position 1");
128    }
129
130    #[test]
131    fn test_well_formed_empty_interval() {
132        let pt= PairTable::try_from("...").unwrap();
133        assert!(pt.is_well_formed(0, 0)); 
134        assert!(pt.is_well_formed(0, 1)); 
135        assert!(pt.is_well_formed(0, 2)); 
136        assert!(pt.is_well_formed(0, 3)); 
137        assert!(pt.is_well_formed(1, 3)); 
138        assert!(pt.is_well_formed(2, 3)); 
139        assert!(pt.is_well_formed(3, 3)); 
140    }
141
142    #[test]
143    fn test_well_formed_pairings_within_interval() {
144        let pt = PairTable::try_from(".(.).").unwrap();
145        assert!(pt.is_well_formed(0, 5)); // Full interval -- 0-based
146        assert!(pt.is_well_formed(0, 4)); 
147        assert!(pt.is_well_formed(1, 5));
148        assert!(pt.is_well_formed(1, 4));
149        assert!(pt.is_well_formed(1, 4));
150        assert!(pt.is_well_formed(2, 3));
151        assert!(!pt.is_well_formed(0, 3)); 
152        assert!(!pt.is_well_formed(1, 3)); 
153        assert!(!pt.is_well_formed(2, 4)); 
154    }
155
156    #[test]
157    #[should_panic(expected = "Invalid interval: j must be <= length")]
158    fn test_well_formed_out_of_bounds_assert() {
159        let pt = PairTable::try_from("..").unwrap();
160        pt.is_well_formed(0, 3); // j = pt.len(), should panic
161    }
162}
163
164
165
ff_structure/pair_table.rs

ff_structure/
pair_table.rs
