Skip to main content

ferrochart_orderflow/
grid.rs

1//! The sparse "time column × price level" grid shared by the footprint and
2//! the heatmap: columns in CSR form, levels ascending
3//! within a column, two values per cell. Only the last column changes; a new
4//! time unit opens a new column.
5
6use ferrochart_core::data::Timestamp;
7use ferrochart_core::error::{Error, Result};
8use ferrochart_core::plugin::MinMaxIndex;
9
10use crate::levels::PriceLevels;
11
12/// How a value is merged into a cell that already has one.
13#[derive(Clone, Copy, Debug, PartialEq, Eq)]
14pub(crate) enum Combine {
15    /// Add (traded volume).
16    Sum,
17    /// Keep the larger (resting size of several snapshots).
18    Max,
19}
20
21/// One column of a [`SparseGrid`]: levels ascending, with their two values.
22#[derive(Clone, Copy, Debug)]
23pub struct Column<'a> {
24    /// Level numbers, ascending.
25    pub levels: &'a [i32],
26    /// First value of each level (footprint: sell volume; heatmap: size).
27    pub a: &'a [f32],
28    /// Second value of each level (footprint: buy volume; heatmap: unused).
29    pub b: &'a [f32],
30}
31
32impl Column<'_> {
33    /// Number of levels.
34    pub fn len(&self) -> usize {
35        self.levels.len()
36    }
37
38    /// Whether the column has no levels.
39    pub fn is_empty(&self) -> bool {
40        self.levels.is_empty()
41    }
42
43    /// The values at `level` (0 when absent).
44    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/// Time columns of price levels with two `f32` values each.
53#[derive(Clone, Debug)]
54pub struct SparseGrid {
55    levels: PriceLevels,
56    col_times: Vec<Timestamp>,
57    /// Offset of each column's first cell in `level`/`a`/`b`.
58    col_start: Vec<u32>,
59    level: Vec<i32>,
60    a: Vec<f32>,
61    b: Vec<f32>,
62    /// Price extremes of each column (cell edges), for auto scaling.
63    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    /// The price grid.
84    pub fn price_levels(&self) -> PriceLevels {
85        self.levels
86    }
87
88    /// Number of columns.
89    pub fn columns(&self) -> usize {
90        self.col_times.len()
91    }
92
93    /// Number of cells in all columns.
94    pub fn cells(&self) -> usize {
95        self.level.len()
96    }
97
98    /// Column start times, strictly increasing.
99    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    /// Column `i`; `None` if out of range.
113    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    /// All cells as flat arrays (column `i` is `level[col_start[i]..]` up
126    /// to the next column's start), for uploads.
127    pub fn raw(&self) -> (&[u32], &[i32], &[f32], &[f32]) {
128        (&self.col_start, &self.level, &self.a, &self.b)
129    }
130
131    /// Price extremes (cell edges) of columns `from..to`.
132    pub fn extremes(&self, from: usize, to: usize) -> Option<(f64, f64)> {
133        self.extremes.query(from, to)
134    }
135
136    /// Merges `(a, b)` into the cell at `level` of the column starting at
137    /// `time`, opening a new column if `time` is after the last one.
138    /// Returns whether a column was opened.
139    ///
140    /// # Errors
141    ///
142    /// [`Error::TimeNotIncreasing`] if `time` is before the last column;
143    /// [`Error::OutOfMemory`].
144    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        // The column's range: its lowest and highest level.
194        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    /// Drops a column just opened (after an allocation failure).
209    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}