morton_index/morton.rs
1use std::fmt::Debug;
2use std::hash::Hash;
3use std::num::NonZeroUsize;
4
5/// When converting a Morton index to a string, these are the different ways to construct the string
6#[derive(Debug, Copy, Clone)]
7pub enum MortonIndexNaming {
8 /// Construct a string by concatenating the cells of the N-ary tree at each level. Each cell can be represented by
9 /// a number in `[0;(2^N)-1]`, resulting in a string such as '2630'. This represents a 4-level Morton index with cell
10 /// '2' below the root, cell '6' below cell '2', cell '3' below cell '6', and finally cell '0' below cell '3'.
11 CellConcatenation,
12 /// Like `CellConcatenation`, but prefixes all strings with `r`, so that an empty Morton index yields `r` instead of
13 /// the empty string
14 CellConcatenationWithRoot,
15 /// Converts the Morton index to an index within an N-dimensional grid together with the depth of the Morton index.
16 /// For a 3D Morton index with depth 4, this might yield the string `4-15-7-3`, which can be read as `depth: 4`,
17 /// `x-index: 15`, `y-index: 7`, `z-index: 3`. Each index is a number in `[0;(2^N)-1]`. This uses the default `CellOrdering`
18 /// to compute the grid index, as given by the `Dimension` of the respective `MortonIndex`.
19 GridIndex,
20}
21
22/// Trait for any type of Morton index, independent of the maximum levels or dimensionality. This contains a core set of common
23/// functions that are identical to all Morton indices:
24/// - Getting/setting cell values at specific levels
25/// - Querying the depth of the Morton index
26/// - Conversion to a `String`
27/// - Conversion to an index within an N-dimensional grid
28pub trait MortonIndex: PartialOrd + Ord + PartialEq + Eq + Debug + Hash {
29 type Dimension: crate::dimensions::Dimension;
30
31 /// Returns the cell at the given `level`.
32 ///
33 /// This performs a depth check, if you want to omit it consider using the `get_cell_at_level_unchecked` variant.
34 ///
35 /// # Panics
36 ///
37 /// If `level` is `>= self.depth()`
38 fn get_cell_at_level(
39 &self,
40 level: usize,
41 ) -> <Self::Dimension as crate::dimensions::Dimension>::Cell;
42 /// Returns the cell at the given `level`. Performs no depth checks.
43 ///
44 /// # Safety
45 ///
46 /// Calling this function with a value for `level` that is `>= self.depth()` is UB
47 unsafe fn get_cell_at_level_unchecked(
48 &self,
49 level: usize,
50 ) -> <Self::Dimension as crate::dimensions::Dimension>::Cell;
51 /// Sets the cell at the given `level` to `cell`. Note that some Morton indices are able to store a variable number of levels,
52 /// so these implementations will provide methods to append cells to increase the number of levels.
53 ///
54 /// This performs a depth check, if you want to omit it consider using the `set_cell_at_level_unchecked` variant.
55 ///
56 /// # Panics
57 ///
58 /// If `level` is `>= self.depth()`
59 fn set_cell_at_level(
60 &mut self,
61 level: usize,
62 cell: <Self::Dimension as crate::dimensions::Dimension>::Cell,
63 );
64 /// Sets the cell at the given `level` to `cell`. Performs no depth checks.
65 ///
66 /// # Safety
67 ///
68 /// Calling this function with a value for `level` that is `>= self.depth()` is UB
69 unsafe fn set_cell_at_level_unchecked(
70 &mut self,
71 level: usize,
72 cell: <Self::Dimension as crate::dimensions::Dimension>::Cell,
73 );
74 /// Returns the current depth of this `MortonIndex`. A depth of `0` is equal to an empty Morton index. By definition, such an index
75 /// always represents the root node of an N-ary tree
76 fn depth(&self) -> usize;
77 /// Converts this `MortonIndex` into a `String` representation, using the given `naming` convention
78 fn to_string(&self, naming: MortonIndexNaming) -> String;
79 /// Converts this `MortonIndex` into a N-dimensional grid index, using the given `ordering`. This index describes the position
80 /// of the cell that the `MortonIndex` corresponds to in an N-dimensional grid. There is an intimate relationship between
81 /// N-ary trees and N-dimensional grids when it comes to Morton indices, which is illustrated in the following image for the
82 /// 2D case:
83 /// ```text
84 /// ₀ ₁ ₂ ₃ ₄ ₅ ₆ ₇
85 /// ┌──┬──┬──┬──┬──┬──┬──┬──┐ ┌───────────┬─────┬─────┐
86 /// ⁰ ├──┼──┼──┼──┼──┼──┼──┼──┤ │ │ │ │
87 /// ¹ ├──┼──┼──┼──┼──┼──┼──┼──┤ │ ├──┬──┼─────┤
88 /// ² ├──┼──┼──┼──┼──┼──┼──┼──┤ │ ├──┼──┤ │
89 /// ³ ├──┼──┼──┼──┼──┼──┼──┼──┤ ├───────────┼──┴──┴─────┤
90 /// ⁴ ├──┼──┼──┼──┼──┼──┼──┼──┤ │ │ │
91 /// ⁵ ├──┼──┼──┼──┼──┼──┼──┼──┤ │ │ │
92 /// ⁶ ├──┼──┼──┼──┼──┼──┼──┼──┤ │ │ │
93 /// ⁷ └──┴──┴──┴──┴──┴──┴──┴──┘ └───────────┴───────────┘
94 /// ```
95 ///
96 /// Each N-ary tree is a 'less dense' version of the corresponding N-dimensional grid. As such, each node in an N-ary tree
97 /// corresponds to a cell in an N-dimensional grid with a resolution of `2 ^ D`, where `D` is the depth of the node in the
98 /// N-ary tree.
99 fn to_grid_index(
100 &self,
101 ordering: <Self::Dimension as crate::dimensions::Dimension>::CellOrdering,
102 ) -> <Self::Dimension as crate::dimensions::Dimension>::GridIndex;
103 /// Returns an inverted Morton index. This reverses the order of the cells, causing the lowest cell to become the highest
104 /// cell and vice versa
105 fn inverted(&self) -> Self
106 where
107 Self: Sized + Clone,
108 {
109 let mut ret = self.clone();
110 let max_level = self.depth();
111 for level in 0..max_level {
112 let inverted_level = max_level - level - 1;
113 unsafe {
114 ret.set_cell_at_level_unchecked(
115 inverted_level,
116 self.get_cell_at_level_unchecked(level),
117 );
118 }
119 }
120 ret
121 }
122}
123
124/// Trait for Morton index types that support variable depth. Provides methods to quickly obtain Morton indices for parent
125/// and child nodes.
126pub trait VariableDepthMortonIndex: MortonIndex + Sized {
127 /// Returns a Morton index for the ancestor node that is `generations` levels above this node.
128 /// As an example, `ancestor(1)` is the parent node of this node, `ancestor(2)` the parent of the parent, and so on.
129 /// Returns `None` if `generations`is larger than `self.depth()`.
130 fn ancestor(&self, generations: NonZeroUsize) -> Option<Self>;
131 /// Returns a Morton index representing the parent node of this Morton index. Returns `None` if this Morton index
132 /// represents the root node, i.e. `self.depth() == 0`.
133 fn parent(&self) -> Option<Self> {
134 self.ancestor(unsafe { NonZeroUsize::new_unchecked(1) })
135 }
136 /// Returns a Morton index representing the node with the given `new_depth`. `new_depth` must be less than or equal to
137 /// `self.depth()`, otherwise `None` is returned.
138 fn with_depth(&self, new_depth: usize) -> Option<Self>
139 where
140 Self: Clone,
141 {
142 if new_depth > self.depth() {
143 return None;
144 }
145 let generations = self.depth() - new_depth;
146 if generations == 0 {
147 return Some(self.clone());
148 }
149 self.ancestor(unsafe { NonZeroUsize::new_unchecked(generations) })
150 }
151 /// Returns a Morton index for the descendant node with the given `cells` below this node.
152 /// As an example, `descendant(&[Quadrant::One])` is the child node at quadrant 1 of this node, `descendant(&[Quadrant::One, Quadrant::Two])`
153 /// is the child node at quadrant 2 below the child node at quadrant 1 below this node, and so on.
154 /// Returns `None` if the number of cells of the descendant node exceeds the maximum capacity of the Morton index type
155 fn descendant(
156 &self,
157 cells: &[<Self::Dimension as crate::dimensions::Dimension>::Cell],
158 ) -> Option<Self>;
159 /// Returns a Morton index for the child node at `cell` of this node.
160 /// Returns `None` if the number of cells of the child node exceeds the maximum capacity of the Morton index type
161 fn child(&self, cell: <Self::Dimension as crate::dimensions::Dimension>::Cell) -> Option<Self> {
162 self.descendant(&[cell])
163 }
164}