trit_core/
bulk.rs

1//! 位切片三值向量：与二进制位平面零拷贝互操作。
2//!
3//! 三值是双导轨 `(ones, unknowns)`：`(0,0)=False`、`(1,0)=True`、`(0,1)=Unknown`。
4//! 二进制数据就是 `unknowns` 缺失（`None`）的 `TriVec`：
5//!
6//! ```
7//! use trit_core::{TriVec, Ternary};
8//! let words = vec![0b1010u64];
9//! let v = TriVec::from_binary(words, 4);
10//! assert_eq!(v.unknowns(), None);
11//! assert_eq!(v.get(1), Ternary::True);
12//! assert_eq!(v.get(0), Ternary::False);
13//! assert_eq!(v.to_bools().unwrap(), vec![false, true, false, true]);
14//! ```
15//!
16//! `from_binary` 直接接管 `Vec<u64>`，不复制、不分配 unknown 平面；
17//! 只有显式写入 `Unknown` 时才分配第二个平面。
18
19use crate::algebra::Algebra;
20use crate::bits::TriBit;
21use crate::value::Ternary;
22
23/// `TriVec` 形状错误。
24#[derive(Debug, thiserror::Error)]
25#[error("TriVec 长度不匹配：{left} vs {right}")]
26pub struct ShapeError {
27    /// 左操作数长度。
28    pub left: usize,
29    /// 右操作数长度。
30    pub right: usize,
31}
32
33/// `TriVec` 构造/访问错误。
34#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
35pub enum TriVecError {
36    /// 位平面字数不足。
37    #[error("位平面不足以覆盖 {len} 位：需要 {need} words，实际 {actual}")]
38    PlaneTooSmall {
39        /// 声明的位数。
40        len: usize,
41        /// 需要的字数。
42        need: usize,
43        /// 实际字数。
44        actual: usize,
45    },
46    /// 元素索引越界。
47    #[error("索引 {index} 越界（len={len}）")]
48    IndexOutOfRange {
49        /// 索引。
50        index: usize,
51        /// 向量长度。
52        len: usize,
53    },
54    /// 字索引越界。
55    #[error("字索引 {word} 越界（words={words}）")]
56    WordOutOfRange {
57        /// 字索引。
58        word: usize,
59        /// 字数。
60        words: usize,
61    },
62}
63
64/// 位切片的三值向量。
65///
66/// **相等语义按值**：两个 `TriVec` 只要长度与逐元素取值一致就相等，
67/// 与内部是否分配了全零的 `unknowns` 平面无关。
68#[derive(Debug, Clone)]
69pub struct TriVec {
70    len: usize,
71    ones: Vec<u64>,
72    unknowns: Option<Vec<u64>>,
73}
74
75impl PartialEq for TriVec {
76    fn eq(&self, other: &Self) -> bool {
77        if self.len != other.len {
78            return false;
79        }
80        for (w, ones) in self.ones.iter().enumerate() {
81            let left = self.unknowns.as_ref().map_or(0, |p| p[w]);
82            let right = other.unknowns.as_ref().map_or(0, |p| p[w]);
83            if *ones != other.ones[w] || left != right {
84                return false;
85            }
86        }
87        true
88    }
89}
90
91impl Eq for TriVec {}
92
93impl TriVec {
94    /// 零拷贝接管二进制位平面：`ones` 的位为 1 表示 `True`，0 表示 `False`。
95    ///
96    /// `ones` 必须至少覆盖 `len` 位；多余字会被截断，末尾多余位会被清零。
97    ///
98    /// # Panics
99    ///
100    /// `ones` 字数不足时 panic；边界输入请用 [`TriVec::try_from_binary`]。
101    pub fn from_binary(ones: Vec<u64>, len: usize) -> Self {
102        Self::try_from_binary(ones, len).unwrap_or_else(|e| panic!("{e}"))
103    }
104
105    /// 同 [`TriVec::from_binary`]，但字数不足时返回错误。
106    pub fn try_from_binary(mut ones: Vec<u64>, len: usize) -> Result<Self, TriVecError> {
107        let need = len.div_ceil(64);
108        if ones.len() < need {
109            return Err(TriVecError::PlaneTooSmall {
110                len,
111                need,
112                actual: ones.len(),
113            });
114        }
115        ones.truncate(need);
116        if let Some(last) = ones.last_mut() {
117            *last &= last_mask(len);
118        }
119        Ok(Self {
120            len,
121            ones,
122            unknowns: None,
123        })
124    }
125
126    /// 从 `bool` 切片打包。
127    pub fn from_bools(bits: &[bool]) -> Self {
128        let mut ones = vec![0u64; bits.len().div_ceil(64)];
129        for (i, &bit) in bits.iter().enumerate() {
130            if bit {
131                ones[i / 64] |= 1u64 << (i % 64);
132            }
133        }
134        Self {
135            len: bits.len(),
136            ones,
137            unknowns: None,
138        }
139    }
140
141    /// 从标量三值切片打包。
142    pub fn from_ternary(values: &[Ternary]) -> Self {
143        let mut ones = vec![0u64; values.len().div_ceil(64)];
144        let mut unknowns: Option<Vec<u64>> = None;
145        for (i, &value) in values.iter().enumerate() {
146            match value {
147                Ternary::False => {}
148                Ternary::True => ones[i / 64] |= 1u64 << (i % 64),
149                Ternary::Unknown => {
150                    let planes = unknowns.get_or_insert_with(|| vec![0u64; ones.len()]);
151                    planes[i / 64] |= 1u64 << (i % 64);
152                }
153            }
154        }
155        Self {
156            len: values.len(),
157            ones,
158            unknowns,
159        }
160    }
161
162    /// 若全部是二值，解包成 `bool`；含 `Unknown` 时返回 `None`。
163    pub fn to_bools(&self) -> Option<Vec<bool>> {
164        if !self.is_binary() {
165            return None;
166        }
167        let mut out = Vec::with_capacity(self.len);
168        for i in 0..self.len {
169            out.push(self.get(i).is_true());
170        }
171        Some(out)
172    }
173
174    /// 长度。
175    pub fn len(&self) -> usize {
176        self.len
177    }
178
179    /// 是否为空。
180    pub fn is_empty(&self) -> bool {
181        self.len == 0
182    }
183
184    /// 位平面字数。
185    pub fn words(&self) -> usize {
186        self.ones.len()
187    }
188
189    /// 是否为纯二值（没有 `Unknown`）。
190    pub fn is_binary(&self) -> bool {
191        self.unknowns
192            .as_ref()
193            .is_none_or(|planes| planes.iter().all(|&w| w == 0))
194    }
195
196    /// `ones` 位平面（只读）。
197    pub fn ones(&self) -> &[u64] {
198        &self.ones
199    }
200
201    /// `unknowns` 位平面；`None` 表示纯二值。
202    pub fn unknowns(&self) -> Option<&[u64]> {
203        self.unknowns.as_deref()
204    }
205
206    /// 取第 `i` 个三值。
207    ///
208    /// # Panics
209    ///
210    /// `i` 越界时 panic；边界输入请用 [`TriVec::try_get`]。
211    pub fn get(&self, i: usize) -> Ternary {
212        self.try_get(i).unwrap_or_else(|e| panic!("{e}"))
213    }
214
215    /// 取第 `i` 个三值；越界返回错误。
216    pub fn try_get(&self, i: usize) -> Result<Ternary, TriVecError> {
217        if i >= self.len {
218            return Err(TriVecError::IndexOutOfRange {
219                index: i,
220                len: self.len,
221            });
222        }
223        let ones = (self.ones[i / 64] >> (i % 64)) & 1;
224        let unknowns = self
225            .unknowns
226            .as_ref()
227            .map_or(0, |planes| (planes[i / 64] >> (i % 64)) & 1);
228        Ok(match (ones, unknowns) {
229            (1, 0) => Ternary::True,
230            (0, 1) => Ternary::Unknown,
231            _ => Ternary::False,
232        })
233    }
234
235    /// 写第 `i` 个三值；首次写 `Unknown` 时分配 unknown 平面。
236    ///
237    /// # Panics
238    ///
239    /// `i` 越界时 panic；边界输入请用 [`TriVec::try_set`]。
240    pub fn set(&mut self, i: usize, value: Ternary) {
241        self.try_set(i, value).unwrap_or_else(|e| panic!("{e}"));
242    }
243
244    /// 写第 `i` 个三值；越界返回错误。
245    pub fn try_set(&mut self, i: usize, value: Ternary) -> Result<(), TriVecError> {
246        if i >= self.len {
247            return Err(TriVecError::IndexOutOfRange {
248                index: i,
249                len: self.len,
250            });
251        }
252        let word = i / 64;
253        let bit = 1u64 << (i % 64);
254        let mut cleared_last_unknown = false;
255        match value {
256            Ternary::False => {
257                self.ones[word] &= !bit;
258                if let Some(planes) = &mut self.unknowns {
259                    planes[word] &= !bit;
260                    cleared_last_unknown = planes.iter().all(|w| *w == 0);
261                }
262            }
263            Ternary::True => {
264                self.ones[word] |= bit;
265                if let Some(planes) = &mut self.unknowns {
266                    planes[word] &= !bit;
267                    cleared_last_unknown = planes.iter().all(|w| *w == 0);
268                }
269            }
270            Ternary::Unknown => {
271                let planes = self
272                    .unknowns
273                    .get_or_insert_with(|| vec![0u64; self.ones.len()]);
274                planes[word] |= bit;
275                self.ones[word] &= !bit;
276            }
277        }
278        if cleared_last_unknown {
279            self.unknowns = None;
280        }
281        Ok(())
282    }
283
284    /// `Unknown` 的个数。
285    pub fn count_unknowns(&self) -> usize {
286        self.unknowns.as_ref().map_or(0, |planes| {
287            planes.iter().map(|w| w.count_ones() as usize).sum()
288        })
289    }
290
291    /// 取整个字（64 路）的位并行表示。
292    ///
293    /// # Panics
294    ///
295    /// 字索引越界时 panic；边界输入请用 [`TriVec::try_word`]。
296    pub fn word(&self, word: usize) -> TriBit {
297        self.try_word(word).unwrap_or_else(|e| panic!("{e}"))
298    }
299
300    /// 取整个字的位并行表示；越界返回错误。
301    pub fn try_word(&self, word: usize) -> Result<TriBit, TriVecError> {
302        if word >= self.ones.len() {
303            return Err(TriVecError::WordOutOfRange {
304                word,
305                words: self.ones.len(),
306            });
307        }
308        Ok(TriBit {
309            ones: crate::bits::BitPlane(self.ones[word]),
310            unknowns: crate::bits::BitPlane(
311                self.unknowns.as_ref().map_or(0, |planes| planes[word]),
312            ),
313        })
314    }
315
316    /// 原地取反：`True`/`False` 互换，`Unknown` 不变。
317    pub fn not(&mut self) {
318        let mask = last_mask(self.len);
319        for (w, ones) in self.ones.iter_mut().enumerate() {
320            let x = self.unknowns.as_ref().map_or(0, |planes| planes[w]);
321            *ones = !(*ones | x) & mask_of(w, self.len, mask);
322        }
323    }
324
325    /// 原地与。K3/Ł3 用格序，B3 用毒值。
326    pub fn and_assign(&mut self, other: &Self, alg: Algebra) -> Result<(), ShapeError> {
327        self.check_shape(other)?;
328        let mask = last_mask(self.len);
329        let both_binary = self.unknowns.is_none() && other.unknowns.is_none();
330        let mut new_unknowns = if both_binary {
331            None
332        } else {
333            Some(Vec::with_capacity(self.ones.len()))
334        };
335        for w in 0..self.ones.len() {
336            let o1 = self.ones[w];
337            let o2 = other.ones[w];
338            let x1 = self.unknowns.as_ref().map_or(0, |p| p[w]);
339            let x2 = other.unknowns.as_ref().map_or(0, |p| p[w]);
340            let m = mask_of(w, self.len, mask);
341            let (o, x) = match alg {
342                Algebra::Bochvar => {
343                    let x_out = (x1 | x2) & m;
344                    ((o1 & o2) & !x_out & m, x_out)
345                }
346                Algebra::Kleene | Algebra::Lukasiewicz => {
347                    let f1 = !o1 & !x1;
348                    let f2 = !o2 & !x2;
349                    let o_out = (o1 & o2) & m;
350                    let f_out = (f1 | f2) & m;
351                    (o_out, !(o_out | f_out) & m)
352                }
353            };
354            self.ones[w] = o;
355            if let Some(planes) = &mut new_unknowns {
356                planes.push(x);
357            }
358        }
359        match new_unknowns {
360            Some(planes) => self.replace_unknowns(planes),
361            None => self.unknowns = None,
362        }
363        Ok(())
364    }
365
366    /// 原地或。K3/Ł3 用格序，B3 用毒值。
367    pub fn or_assign(&mut self, other: &Self, alg: Algebra) -> Result<(), ShapeError> {
368        self.check_shape(other)?;
369        let mask = last_mask(self.len);
370        let both_binary = self.unknowns.is_none() && other.unknowns.is_none();
371        let mut new_unknowns = if both_binary {
372            None
373        } else {
374            Some(Vec::with_capacity(self.ones.len()))
375        };
376        for w in 0..self.ones.len() {
377            let o1 = self.ones[w];
378            let o2 = other.ones[w];
379            let x1 = self.unknowns.as_ref().map_or(0, |p| p[w]);
380            let x2 = other.unknowns.as_ref().map_or(0, |p| p[w]);
381            let m = mask_of(w, self.len, mask);
382            let (o, x) = match alg {
383                Algebra::Bochvar => {
384                    let x_out = (x1 | x2) & m;
385                    ((o1 | o2) & !x_out & m, x_out)
386                }
387                Algebra::Kleene | Algebra::Lukasiewicz => {
388                    let f1 = !o1 & !x1;
389                    let f2 = !o2 & !x2;
390                    let o_out = (o1 | o2) & m;
391                    let f_out = (f1 & f2) & m;
392                    (o_out, !(o_out | f_out) & m)
393                }
394            };
395            self.ones[w] = o;
396            if let Some(planes) = &mut new_unknowns {
397                planes.push(x);
398            }
399        }
400        match new_unknowns {
401            Some(planes) => self.replace_unknowns(planes),
402            None => self.unknowns = None,
403        }
404        Ok(())
405    }
406
407    fn replace_unknowns(&mut self, planes: Vec<u64>) {
408        if planes.iter().all(|&w| w == 0) {
409            self.unknowns = None;
410        } else {
411            self.unknowns = Some(planes);
412        }
413    }
414
415    fn check_shape(&self, other: &Self) -> Result<(), ShapeError> {
416        if self.len == other.len {
417            Ok(())
418        } else {
419            Err(ShapeError {
420                left: self.len,
421                right: other.len,
422            })
423        }
424    }
425}
426
427fn last_mask(len: usize) -> u64 {
428    match len % 64 {
429        0 => u64::MAX,
430        r => (1u64 << r) - 1,
431    }
432}
433
434fn mask_of(word: usize, len: usize, last: u64) -> u64 {
435    let words = len.div_ceil(64);
436    if word + 1 == words { last } else { u64::MAX }
437}
438
439#[cfg(test)]
440mod tests {
441    use super::*;
442
443    fn sample(len: usize, seed: u64) -> Vec<Ternary> {
444        let mut x = seed;
445        (0..len)
446            .map(|_| {
447                x = x.wrapping_mul(6364136223846793005).wrapping_add(1);
448                match (x >> 32) % 3 {
449                    0 => Ternary::False,
450                    1 => Ternary::True,
451                    _ => Ternary::Unknown,
452                }
453            })
454            .collect()
455    }
456
457    #[test]
458    fn binary_view_is_zero_copy_and_roundtrips() {
459        for len in [0usize, 1, 63, 64, 65, 130] {
460            let bits: Vec<bool> = (0..len).map(|i| i % 3 == 0).collect();
461            let v = TriVec::from_bools(&bits);
462            assert_eq!(v.unknowns(), None);
463            assert!(v.is_binary());
464            assert_eq!(v.to_bools().unwrap(), bits);
465            let words = v.ones().to_vec();
466            let moved = TriVec::from_binary(words, len);
467            assert_eq!(moved.to_bools().unwrap(), bits);
468        }
469    }
470
471    #[test]
472    fn from_binary_normalizes_oversized_planes() {
473        let normalized = TriVec::from_binary(vec![0, 0], 1);
474        assert_eq!(normalized.words(), 1);
475        assert_eq!(normalized, TriVec::from_binary(vec![0], 1));
476
477        // 尾部 padding 必须被清零
478        let masked = TriVec::from_binary(vec![u64::MAX], 3);
479        assert_eq!(masked.to_bools().unwrap(), vec![true, true, true]);
480
481        // 物理字数不同的两个向量可以安全运算
482        let mut left = TriVec::from_binary(vec![1, 0], 1);
483        let right = TriVec::from_binary(vec![1], 1);
484        left.and_assign(&right, Algebra::Kleene).unwrap();
485        assert_eq!(left.to_bools().unwrap(), vec![true]);
486    }
487
488    #[test]
489    fn unknown_allocates_lazily() {
490        let mut v = TriVec::from_bools(&[true, false]);
491        assert_eq!(v.unknowns(), None);
492        v.set(1, Ternary::Unknown);
493        assert!(v.unknowns().is_some());
494        assert_eq!(v.get(1), Ternary::Unknown);
495        assert_eq!(v.to_bools(), None);
496        assert_eq!(v.count_unknowns(), 1);
497    }
498
499    #[test]
500    fn bit_ops_match_scalar() {
501        for alg in Algebra::ALL {
502            let a = sample(130, 7);
503            let b = sample(130, 11);
504            let mut va = TriVec::from_ternary(&a);
505            let vb = TriVec::from_ternary(&b);
506            va.and_assign(&vb, alg).unwrap();
507            for i in 0..a.len() {
508                assert_eq!(va.get(i), alg.and(a[i], b[i]), "{alg:?} and at {i}");
509            }
510            let mut va = TriVec::from_ternary(&a);
511            va.or_assign(&vb, alg).unwrap();
512            for i in 0..a.len() {
513                assert_eq!(va.get(i), alg.or(a[i], b[i]), "{alg:?} or at {i}");
514            }
515        }
516    }
517
518    #[test]
519    fn not_matches_scalar() {
520        let a = sample(96, 3);
521        let mut v = TriVec::from_ternary(&a);
522        v.not();
523        for (i, &value) in a.iter().enumerate() {
524            assert_eq!(v.get(i), Algebra::Kleene.not(value), "not at {i}");
525        }
526    }
527
528    #[test]
529    fn shape_mismatch_is_an_error() {
530        let mut a = TriVec::from_bools(&[true, false]);
531        let b = TriVec::from_bools(&[true]);
532        assert!(a.and_assign(&b, Algebra::Kleene).is_err());
533    }
534
535    #[test]
536    fn eq_compares_values_not_storage() {
537        let mut a = TriVec::from_ternary(&[Ternary::Unknown]);
538        assert!(a.unknowns().is_some());
539        a.set(0, Ternary::False);
540        // 清掉最后一个 Unknown 后平面被规范化，表示差异不能影响相等。
541        assert_eq!(a.unknowns(), None);
542        assert_eq!(a, TriVec::from_bools(&[false]));
543        assert_ne!(a, TriVec::from_bools(&[true]));
544        // 未知平面非零时不能与二值零向量相等
545        assert_ne!(
546            TriVec::from_ternary(&[Ternary::Unknown]),
547            TriVec::from_bools(&[false])
548        );
549    }
550
551    #[test]
552    fn fallible_constructors_and_accessors_report_bounds() {
553        assert_eq!(
554            TriVec::try_from_binary(vec![], 1).unwrap_err(),
555            TriVecError::PlaneTooSmall {
556                len: 1,
557                need: 1,
558                actual: 0
559            }
560        );
561        let v = TriVec::from_bools(&[true]);
562        assert_eq!(
563            v.try_get(1).unwrap_err(),
564            TriVecError::IndexOutOfRange { index: 1, len: 1 }
565        );
566        assert_eq!(
567            v.try_word(1).unwrap_err(),
568            TriVecError::WordOutOfRange { word: 1, words: 1 }
569        );
570        let mut w = v.clone();
571        assert!(w.try_set(1, Ternary::False).is_err());
572        assert_eq!(w, v);
573    }
574}
trit_core/bulk.rs

trit_core/
bulk.rs
