docvortex_core/
note_index.rs

1//! 纵向前缀的持久化高度计数树，仅保存本次候选构建的数值。
2
3#[derive(Clone, Copy, Default)]
4struct Node {
5    left: usize,
6    right: usize,
7    count: usize,
8}
9
10pub struct HeightIndex {
11    nodes: Vec<Node>,
12    roots: Vec<usize>,
13    centers: Vec<f64>,
14    heights: Vec<f64>,
15}
16
17impl HeightIndex {
18    /// 高度平局保留输入顺序，中心排序也稳定，查询不复制高度样本。
19    pub fn new(items: &[(i64, f64, f64)]) -> Self {
20        let mut order: Vec<usize> = (0..items.len()).collect();
21        order.sort_by(|&a, &b| items[a].2.partial_cmp(&items[b].2).unwrap());
22        let mut ranks = vec![0; items.len()];
23        let heights = order.iter().map(|&i| items[i].2).collect();
24        for (rank, &index) in order.iter().enumerate() {
25            ranks[index] = rank;
26        }
27        order.sort_by(|&a, &b| items[a].1.partial_cmp(&items[b].1).unwrap());
28        let mut result = Self {
29            nodes: vec![Node::default()],
30            roots: vec![0],
31            centers: Vec::new(),
32            heights,
33        };
34        for index in order {
35            let root = result.insert(*result.roots.last().unwrap(), 0, items.len(), ranks[index]);
36            result.roots.push(root);
37            result.centers.push(items[index].1);
38        }
39        result
40    }
41
42    /// 仅复制根到新增高度叶子的路径，共享所有未变化节点。
43    fn insert(&mut self, previous: usize, low: usize, high: usize, rank: usize) -> usize {
44        let mut node = self.nodes[previous];
45        node.count += 1;
46        if high - low > 1 {
47            let middle = (low + high) / 2;
48            if rank < middle {
49                node.left = self.insert(node.left, low, middle, rank);
50            } else {
51                node.right = self.insert(node.right, middle, high, rank);
52            }
53        }
54        self.nodes.push(node);
55        self.nodes.len() - 1
56    }
57
58    /// 在左前缀加完整集合减右前缀的有序多重集合中查找零起算位置。
59    fn select(&self, mut left: usize, mut total: usize, mut right: usize, mut rank: usize) -> f64 {
60        let (mut low, mut high) = (0, self.heights.len());
61        while high - low > 1 {
62            let a = self.nodes[left];
63            let b = self.nodes[total];
64            let c = self.nodes[right];
65            let count =
66                self.nodes[a.left].count + self.nodes[b.left].count - self.nodes[c.left].count;
67            let middle = (low + high) / 2;
68            if rank < count {
69                left = a.left;
70                total = b.left;
71                right = c.left;
72                high = middle;
73            } else {
74                rank -= count;
75                left = a.right;
76                total = b.right;
77                right = c.right;
78                low = middle;
79            }
80        }
81        self.heights[low]
82    }
83
84    /// 闭区间纵向排除后，精确读取最高四分位的一个或两个中位数值。
85    pub fn height(&self, top: f64, bottom: f64, fallback: f64) -> Option<f64> {
86        if !top.is_finite() || !bottom.is_finite() || top > bottom || !fallback.is_finite() {
87            return None;
88        }
89        let left = self.centers.partition_point(|&y| y < top);
90        let right = self.centers.partition_point(|&y| y <= bottom);
91        let n = left + self.centers.len() - right;
92        if n < 4 {
93            return Some(fallback);
94        }
95        let count = n.div_ceil(4);
96        let rank = n - count + count / 2;
97        let a = self.select(
98            self.roots[left],
99            *self.roots.last().unwrap(),
100            self.roots[right],
101            rank,
102        );
103        let result = if count % 2 == 1 {
104            a
105        } else {
106            let b = self.select(
107                self.roots[left],
108                *self.roots.last().unwrap(),
109                self.roots[right],
110                rank - 1,
111            );
112            (b + a) / 2.0
113        };
114        result.is_finite().then_some(result)
115    }
116}
117
118pub struct CoreRows {
119    pub members: Vec<Vec<i64>>,
120    size: usize,
121    extents: Vec<(f64, f64)>,
122}
123
124impl CoreRows {
125    /// 将同一来源的所有中心纳入行范围，避免重复来源落在排除区间外时误省略。
126    pub fn new(
127        members: Vec<Vec<i64>>,
128        extents: &std::collections::HashMap<i64, (f64, f64)>,
129    ) -> Self {
130        let size = members.len().max(1).next_power_of_two();
131        let mut tree = vec![(f64::INFINITY, f64::NEG_INFINITY); size * 2];
132        for (row, ids) in members.iter().enumerate() {
133            for id in ids {
134                if let Some(&(a, b)) = extents.get(id) {
135                    tree[size + row].0 = tree[size + row].0.min(a);
136                    tree[size + row].1 = tree[size + row].1.max(b);
137                }
138            }
139        }
140        for i in (1..size).rev() {
141            tree[i] = (
142                tree[i * 2].0.min(tree[i * 2 + 1].0),
143                tree[i * 2].1.max(tree[i * 2 + 1].1),
144            );
145        }
146        Self {
147            members,
148            size,
149            extents: tree,
150        }
151    }
152
153    /// 查询连续行中所有核心来源的中心范围，无需传输或展开成员列表。
154    pub fn contained(&self, start: usize, end: usize, top: f64, bottom: f64) -> bool {
155        let (mut l, mut r) = (start + self.size, end + self.size);
156        while l < r {
157            if l % 2 == 1 {
158                if self.extents[l].0 < top || self.extents[l].1 > bottom {
159                    return false;
160                }
161                l += 1;
162            }
163            if r % 2 == 1 {
164                r -= 1;
165                if self.extents[r].0 < top || self.extents[r].1 > bottom {
166                    return false;
167                }
168            }
169            l /= 2;
170            r /= 2;
171        }
172        true
173    }
174}
docvortex_core/note_index.rs

docvortex_core/
note_index.rs
