1use ferrochart_core::data::Timestamp;
7use ferrochart_core::error::{Error, Result};
8use ferrochart_core::plugin::MinMaxIndex;
9
10use crate::levels::PriceLevels;
11
12#[derive(Clone, Copy, Debug, PartialEq, Eq)]
14pub(crate) enum Combine {
15 Sum,
17 Max,
19}
20
21#[derive(Clone, Copy, Debug)]
23pub struct Column<'a> {
24 pub levels: &'a [i32],
26 pub a: &'a [f32],
28 pub b: &'a [f32],
30}
31
32impl Column<'_> {
33 pub fn len(&self) -> usize {
35 self.levels.len()
36 }
37
38 pub fn is_empty(&self) -> bool {
40 self.levels.is_empty()
41 }
42
43 pub fn at(&self, level: i32) -> (f32, f32) {
45 match self.levels.binary_search(&level) {
46 Ok(k) => (self.a[k], self.b[k]),
47 Err(_) => (0.0, 0.0),
48 }
49 }
50}
51
52#[derive(Clone, Debug)]
54pub struct SparseGrid {
55 levels: PriceLevels,
56 col_times: Vec<Timestamp>,
57 col_start: Vec<u32>,
59 level: Vec<i32>,
60 a: Vec<f32>,
61 b: Vec<f32>,
62 extremes: MinMaxIndex,
64}
65
66fn reserve<T>(v: &mut Vec<T>) -> Result<()> {
67 v.try_reserve(1).map_err(|_| Error::OutOfMemory)
68}
69
70impl SparseGrid {
71 pub(crate) fn new(levels: PriceLevels) -> Self {
72 Self {
73 levels,
74 col_times: Vec::new(),
75 col_start: Vec::new(),
76 level: Vec::new(),
77 a: Vec::new(),
78 b: Vec::new(),
79 extremes: MinMaxIndex::new(),
80 }
81 }
82
83 pub fn price_levels(&self) -> PriceLevels {
85 self.levels
86 }
87
88 pub fn columns(&self) -> usize {
90 self.col_times.len()
91 }
92
93 pub fn cells(&self) -> usize {
95 self.level.len()
96 }
97
98 pub fn times(&self) -> &[Timestamp] {
100 &self.col_times
101 }
102
103 fn bounds(&self, i: usize) -> (usize, usize) {
104 let start = self.col_start[i] as usize;
105 let end = self
106 .col_start
107 .get(i + 1)
108 .map_or(self.level.len(), |&s| s as usize);
109 (start, end)
110 }
111
112 pub fn column(&self, i: usize) -> Option<Column<'_>> {
114 if i >= self.col_times.len() {
115 return None;
116 }
117 let (s, e) = self.bounds(i);
118 Some(Column {
119 levels: &self.level[s..e],
120 a: &self.a[s..e],
121 b: &self.b[s..e],
122 })
123 }
124
125 pub fn raw(&self) -> (&[u32], &[i32], &[f32], &[f32]) {
128 (&self.col_start, &self.level, &self.a, &self.b)
129 }
130
131 pub fn extremes(&self, from: usize, to: usize) -> Option<(f64, f64)> {
133 self.extremes.query(from, to)
134 }
135
136 pub(crate) fn add(
145 &mut self,
146 time: Timestamp,
147 level: i32,
148 a: f32,
149 b: f32,
150 combine: Combine,
151 ) -> Result<bool> {
152 let opened = match self.col_times.last() {
153 Some(&last) if time < last => {
154 return Err(Error::TimeNotIncreasing {
155 index: self.col_times.len(),
156 });
157 }
158 Some(&last) if time == last => false,
159 _ => {
160 let start = u32::try_from(self.level.len()).map_err(|_| Error::OutOfMemory)?;
161 reserve(&mut self.col_times)?;
162 reserve(&mut self.col_start)?;
163 self.col_times.push(time);
164 self.col_start.push(start);
165 true
166 }
167 };
168 let last = self.col_times.len() - 1;
169 let (s, e) = self.bounds(last);
170 match self.level[s..e].binary_search(&level) {
171 Ok(k) => {
172 let k = s + k;
173 match combine {
174 Combine::Sum => {
175 self.a[k] += a;
176 self.b[k] += b;
177 }
178 Combine::Max => {
179 self.a[k] = self.a[k].max(a);
180 self.b[k] = self.b[k].max(b);
181 }
182 }
183 }
184 Err(k) => {
185 reserve(&mut self.level)?;
186 reserve(&mut self.a)?;
187 reserve(&mut self.b)?;
188 self.level.insert(s + k, level);
189 self.a.insert(s + k, a);
190 self.b.insert(s + k, b);
191 }
192 }
193 let (s, e) = self.bounds(last);
195 let lo = self.levels.edges(self.level[s]).0;
196 let hi = self.levels.edges(self.level[e - 1]).1;
197 if opened {
198 if let Err(err) = self.extremes.push(lo, hi) {
199 self.undo_open(s);
200 return Err(err);
201 }
202 } else {
203 self.extremes.set_last(lo, hi);
204 }
205 Ok(opened)
206 }
207
208 fn undo_open(&mut self, start: usize) {
210 self.col_times.pop();
211 self.col_start.pop();
212 self.level.truncate(start);
213 self.a.truncate(start);
214 self.b.truncate(start);
215 }
216}
217
218#[cfg(test)]
219mod tests {
220 #![allow(clippy::float_cmp)]
221
222 use super::*;
223
224 #[test]
225 fn columns_stay_sorted_and_sparse() {
226 let mut g = SparseGrid::new(PriceLevels::new(0.5, 1).unwrap());
227 assert!(g.add(60, 4, 1.0, 0.0, Combine::Sum).unwrap());
228 assert!(!g.add(60, 2, 0.0, 2.0, Combine::Sum).unwrap());
229 assert!(!g.add(60, 4, 1.0, 3.0, Combine::Sum).unwrap());
230 assert!(g.add(120, 3, 5.0, 0.0, Combine::Max).unwrap());
231 assert!(!g.add(120, 3, 4.0, 1.0, Combine::Max).unwrap());
232 assert_eq!(g.columns(), 2);
233 let c = g.column(0).unwrap();
234 assert_eq!(c.levels, &[2, 4]);
235 assert_eq!((c.a, c.b), (&[0.0, 2.0][..], &[2.0, 3.0][..]));
236 assert_eq!(c.at(3), (0.0, 0.0));
237 assert_eq!(g.column(1).unwrap().at(3), (5.0, 1.0));
238 assert_eq!(g.extremes(0, 1), Some((0.75, 2.25)));
239 assert_eq!(g.extremes(1, 2), Some((1.25, 1.75)));
240 assert!(matches!(
241 g.add(60, 1, 1.0, 1.0, Combine::Sum),
242 Err(Error::TimeNotIncreasing { .. })
243 ));
244 assert!(g.column(2).is_none());
245 let (start, level, _, _) = g.raw();
246 assert_eq!((start, level), (&[0, 2][..], &[2, 4, 3][..]));
247 }
248}