conspire/geometry/ntree/balance/quadtree/
mod.rs

1use crate::geometry::ntree::node::slot::Slot;
2#[cfg(test)]
3mod test;
4
5use crate::geometry::ntree::{
6    Orthotree,
7    balance::{Balance, Balancing},
8    node::cell::Cell,
9    pair::Pairing,
10};
11
12const D: usize = 2;
13const L: usize = 2;
14const M: usize = 4;
15const N: usize = 4;
16
17const FACE_ORTHANTS: [[usize; 2]; M] = [[1, 3], [0, 2], [2, 3], [0, 1]];
18
19impl<T, U, V> Orthotree<D, L, M, N, T, U, V>
20where
21    T: Cell,
22    U: Slot,
23{
24    fn deep_toward(&self, cell: U, orthants: &[usize], depth: usize) -> bool {
25        match self[cell].orthants() {
26            None => false,
27            Some(children) => {
28                depth == 0
29                    || orthants
30                        .iter()
31                        .any(|&orthant| self.deep_toward(children[orthant], orthants, depth - 1))
32            }
33        }
34    }
35    fn deep(&self, cell: U, face: usize, depth: usize) -> bool {
36        self.deep_toward(cell, &FACE_ORTHANTS[face], depth)
37    }
38    fn diagonally_deep(&self, children: &[U; N], face: usize, depth: usize) -> bool {
39        let (axis, side) = (face / 2, face % 2);
40        let other = 1 - axis;
41        (0..2).any(|beyond| {
42            let adjacent = ((1 - side) << axis) | (beyond << other);
43            self[children[adjacent]].facets()[2 * other + beyond].is_some_and(|vertex| {
44                let toward = ((1 - side) << axis) | ((1 - beyond) << other);
45                self.deep_toward(vertex, &[toward], depth - 1)
46            })
47        })
48    }
49}
50
51impl<T, U, V> Balance for Orthotree<D, L, M, N, T, U, V>
52where
53    T: Cell,
54    U: Slot,
55    V: Copy,
56{
57    fn balance(&mut self, balancing: Balancing) -> bool {
58        self.balanced = balancing;
59        let mut balanced;
60        let mut balanced_already = true;
61        let mut index;
62        let mut subdivide;
63        loop {
64            balanced = true;
65            index = 0;
66            subdivide = false;
67            while index < self.len() {
68                if !self.nodes[index].is_unit() && self.nodes[index].is_leaf() {
69                    'faces: for (face, face_cell) in self.nodes[index].facets().iter().enumerate() {
70                        if let Some(neighbor) = face_cell
71                            && let Some(children) = self[*neighbor].orthants()
72                        {
73                            let unbalanced = match balancing {
74                                Balancing::Weak(depth) => self.deep(*neighbor, face, depth),
75                                Balancing::Strong(depth) => {
76                                    self.deep(*neighbor, face, depth)
77                                        || self.diagonally_deep(children, face, depth)
78                                }
79                                Balancing::None => false,
80                            };
81                            if unbalanced {
82                                subdivide = true;
83                                break 'faces;
84                            }
85                        }
86                    }
87                    if subdivide {
88                        self.subdivide(index).unwrap();
89                        balanced = false;
90                        balanced_already = false;
91                        subdivide = false;
92                    }
93                }
94                index += 1;
95            }
96            if balanced {
97                break;
98            }
99        }
100        balanced_already
101    }
102    fn pair_up(&mut self, pairing: Pairing) -> Result<bool, &'static str> {
103        self.paired = pairing;
104        self.pair(pairing)
105    }
106}
conspire/geometry/ntree/balance/quadtree/mod.rs

conspire/geometry/ntree/balance/quadtree/
mod.rs
