moore_hilbert/
lib.rs

1use std::cmp::Ordering;
2use std::convert::TryInto;
3use std::mem;
4
5#[cfg(test)]
6mod tests {
7
8    use crate::*;
9
10    #[test]
11    fn test_increment_coordinates_beyond_bit_range() {
12        // Test that the increment doesn't increment out of bounds
13        let mut loop_coords = vec![0, 0];
14        for _incr_count in 0..1024 {
15            coordinates_increment(4, &mut loop_coords);
16            assert!(loop_coords[0] < 16, "x = {} < 16", loop_coords[0]);
17            assert!(loop_coords[1] < 16, "y = {} < 16", loop_coords[1]);
18        }
19    }
20
21    #[test]
22    fn test_iterate_dimensions() {
23        // 2 dimensions each using 4 bits
24        for x in 0..1 << 4 {
25            for y in 0..1 << 4 {
26                let coords = vec![x, y];
27                let _index = coordinates_to_index(4, &coords);
28            }
29        }
30    }
31}
32
33/// Represent an index on the Hilbert curve
34pub type HilbertIndex = moore_hilbert_sys::BitmaskT;
35
36/// Storage type for a single coordinate
37pub type HilbertCoordinate = u64;
38
39/// The datatype that contain the number of bits per dimension
40pub type BitsPerDimensionType = usize;
41
42/// The number of bits in each byte
43const BITS_PER_BYTE: usize = 8;
44
45/// Convert coordinates of a point on a Hilbert curve to its index
46///
47/// # Arguments
48///
49/// * `bits_per_dimension` - Number of bits/coordinate.
50/// * `coords` - Slice of coordinate values
51///
52/// # Returns
53///
54/// * `index` - Output index value.  nDims*nBits bits.
55///
56/// # Assumptions
57///
58/// `length of coords` * `bits_per_dimension` <= (sizeof `HilbertIndex`) * (`bits_per_byte`)
59///
60/// # Example
61///
62/// ```
63/// let bits_per_dimension = 8;
64/// let r = moore_hilbert::coordinates_to_index(bits_per_dimension, &vec![1,2,3]).unwrap();
65/// assert_eq!(r, 36);
66/// ```
67pub fn coordinates_to_index(
68    bits_per_dimension: BitsPerDimensionType,
69    coords: &[HilbertCoordinate],
70) -> Result<HilbertIndex, ()> {
71    if bits_per_dimension * coords.len() > mem::size_of::<HilbertIndex>() * BITS_PER_BYTE {
72        panic!("number of coordinates * bits_per_dimension > sizeof(HilbertIndex) * BITS_PER_BYTE");
73    }
74
75    unsafe {
76        return Ok(moore_hilbert_sys::hilbert_c2i(
77            coords.len().try_into().unwrap(),
78            bits_per_dimension.try_into().unwrap(),
79            coords.as_ptr(),
80        ));
81    }
82}
83
84/// Convert an index into a Hilbert curve to a set of coordinates
85///
86/// # Arguments
87///
88/// * `bits_per_dimension` - Number of bits per dimension
89/// * `index` - The index, contains the number of dimensions * `nBits` bits (so `nDims` * `nBits` must be <= `BITS_PER_BYTE` * sizeof(`HilbertIndex`)).
90/// * `coords` - The slice where the coordinates will be written
91///
92/// # Assumptions
93///
94/// `number of dimesions` * `bits_per_dimension` <= (sizeof `HilbertIndex`) * (`bits_per_byte`)
95///
96/// # Example
97///
98/// ```
99/// let bits_per_dimension = 8;
100///
101/// // Start by getting an index along the Hilbert curve for this point
102/// let start_vec = vec![1,2,3];
103/// let r = moore_hilbert::coordinates_to_index(bits_per_dimension, &start_vec).unwrap();
104/// assert_eq!(r, 36);
105///
106/// // A place to put the coordinates from the Hilbert curve index
107/// let mut extracted_coords = [0,0,0];
108/// moore_hilbert::index_to_coordinates(bits_per_dimension, r, &mut extracted_coords);
109///
110/// /// The coordinates should match.
111/// assert_eq!(start_vec, extracted_coords);
112///
113/// // increment the index and make sure the coords don't match
114/// moore_hilbert::index_to_coordinates(bits_per_dimension, r+1, &mut extracted_coords);
115/// assert_ne!(start_vec, extracted_coords);
116///
117/// ```
118pub fn index_to_coordinates(
119    bits_per_dimension: BitsPerDimensionType,
120    index: HilbertIndex,
121    coords: &mut [HilbertCoordinate],
122) -> () {
123    if bits_per_dimension as usize * coords.len() > mem::size_of::<HilbertIndex>() * BITS_PER_BYTE {
124        panic!("number of coordinates * bits_per_dimension > mem::size_of(HilbertIndex) * BITS_PER_BYTE");
125    }
126
127    unsafe {
128        return moore_hilbert_sys::hilbert_i2c(
129            coords.len().try_into().unwrap(),
130            bits_per_dimension.try_into().unwrap(),
131            index,
132            coords.as_mut_ptr(),
133        );
134    }
135}
136
137/// Determine which of two points lies further along the Hilbert curve
138///
139/// # Arguments
140///
141/// * `bits_per_dimension` - Number of bits/coordinate.
142/// * `coord1` - Slice of coordinates
143/// * `coord2` - Slice of coordinates
144///
145/// # Returns
146///
147/// * Ordering result that indicates the comparison of coord1 and coord2
148///
149/// # Assumptions
150///
151/// `nBits` <= (sizeof `HilbertIndex`) * `bits_per_byte`
152///
153/// # Example
154///
155/// ```
156/// use std::cmp::Ordering;
157/// let coords = vec![
158///   vec![1,2,3],
159///   vec![1,2,4],
160/// ];
161///
162/// let bits_per_dimension = 4;
163///
164/// assert_eq!(moore_hilbert::coordinates_compare(bits_per_dimension, &coords[0], &coords[1]), Ordering::Less);
165/// assert_eq!(moore_hilbert::coordinates_compare(bits_per_dimension, &coords[0], &coords[0]), Ordering::Equal);
166/// assert_eq!(moore_hilbert::coordinates_compare(bits_per_dimension, &coords[1], &coords[0]), Ordering::Greater);
167/// ```
168pub fn coordinates_compare(
169    bits_per_dimension: BitsPerDimensionType,
170    coord1: &[HilbertCoordinate],
171    coord2: &[HilbertCoordinate],
172) -> Ordering {
173    if bits_per_dimension as usize > mem::size_of::<HilbertIndex>() * BITS_PER_BYTE {
174        panic!("bits_per_dimension > mem::size_of::<HilbertIndex>() * BITS_PER_BYTE");
175    }
176
177    if coord1.len() != coord2.len() {
178        panic!("Coordinates supplied are not equal in length");
179    }
180
181    unsafe {
182        let r = moore_hilbert_sys::hilbert_cmp(
183            coord1.len().try_into().unwrap(),
184            mem::size_of::<HilbertCoordinate>().try_into().unwrap(),
185            bits_per_dimension.try_into().unwrap(),
186            coord1.as_ptr() as *const std::ffi::c_void,
187            coord2.as_ptr() as *const std::ffi::c_void,
188        );
189        if r == -1 {
190            return Ordering::Less;
191        }
192        if r == 0 {
193            return Ordering::Equal;
194        }
195        return Ordering::Greater;
196    }
197}
198
199/// Determine which of two points lies further along the Hilbert curve
200///
201/// # Arguments
202///
203/// * `coord1` - Slice of coordinates using floats
204/// * `coord2` - Slice of coordinates using floats
205///
206/// # Returns
207///
208/// * Ordering result that indicates the comparison of coord1 and coord2
209///
210/// ```
211/// use std::cmp::Ordering;
212/// let coords = vec![
213///   vec![1.0, 2.0, 3.0],
214///   vec![1.0, 2.0, 4.0],
215/// ];
216///
217///
218/// assert_eq!(moore_hilbert::coordinates_float_compare(&coords[0], &coords[0]), Ordering::Equal);
219/// assert_eq!(moore_hilbert::coordinates_float_compare(&coords[0], &coords[1]), Ordering::Greater);
220/// assert_eq!(moore_hilbert::coordinates_float_compare(&coords[1], &coords[0]), Ordering::Less);
221/// ```
222pub fn coordinates_float_compare(coord1: &[f64], coord2: &[f64]) -> Ordering {
223    if coord1.len() != coord2.len() {
224        panic!("Coordinates supplied are not equal in length");
225    }
226
227    unsafe {
228        let r = moore_hilbert_sys::hilbert_ieee_cmp(
229            coord1.len().try_into().unwrap(),
230            coord1.as_ptr(),
231            coord2.as_ptr(),
232        );
233        if r == -1 {
234            return Ordering::Less;
235        }
236        if r == 0 {
237            return Ordering::Equal;
238        }
239        return Ordering::Greater;
240    }
241}
242
243/// Advance from one point to its successor on a Hilbert curve
244///
245/// # Arguments
246///
247/// * `bits_per_dimension` - Number of bits/coordinate.
248/// * `coord` - Coordinates that will be modified to be the next point on the curve
249///
250/// # Assumptions
251///
252/// `bits_per_dimension` <= (sizeof `HilbertIndex`) * (`bits_per_byte`)
253///
254/// # Example
255///
256/// ```
257/// let bits_per_dimension = 8;
258/// let mut coords = vec![2, 2, 5];
259///
260/// /// Get the initial position along the Hilbert curve
261/// let first_index = moore_hilbert::coordinates_to_index(bits_per_dimension, &coords).unwrap();
262///
263/// /// Increment that position
264/// moore_hilbert::coordinates_increment(bits_per_dimension, &mut coords);
265///
266/// /// Convert the incremented position back to a new index on the Hilbert curve
267/// let new_index = moore_hilbert::coordinates_to_index(bits_per_dimension, &coords).unwrap();
268///
269/// /// The newly incremented index should advance along the curve by 1.
270/// assert_eq!(new_index-first_index, 1);
271///
272/// ```
273pub fn coordinates_increment(
274    bits_per_dimension: BitsPerDimensionType,
275    coord: &mut [HilbertCoordinate],
276) -> () {
277    if bits_per_dimension as usize > mem::size_of::<HilbertIndex>() * BITS_PER_BYTE {
278        panic!("bits_per_dimension > mem::size_of::<HilbertIndex>() * BITS_PER_BYTE");
279    }
280    unsafe {
281        moore_hilbert_sys::hilbert_incr(
282            coord.len().try_into().unwrap(),
283            bits_per_dimension.try_into().unwrap(),
284            coord.as_mut_ptr(),
285        );
286    }
287}
288
289/// Determine the first or last vertex of a box to lie on a Hilbert curve
290///
291/// # Arguments
292///
293/// * `bits_per_dimension`   - Number of bits per coordinate
294/// * `find_min` - Is the least vertex sought?
295/// * `coord1`      - One corner of box
296/// * `coord2`      - Opposite corner
297///
298/// # Returns
299///
300/// `coord1` and `coord2` modified to refer to selected corner
301/// value returned is log2 of size of largest power-of-two-aligned box that
302/// contains the selected corner and no other corners
303///
304/// # Assumptions
305///
306/// `bits_per_dimension` <= (sizeof `HilbertIndex`) * (`bits_per_byte`)
307///
308pub fn box_vertex(
309    bits_per_dimension: BitsPerDimensionType,
310    find_min: bool,
311    coord1: &mut [HilbertCoordinate],
312    coord2: &mut [HilbertCoordinate],
313) -> usize {
314    if coord1.len() != coord2.len() {
315        panic!("Coordinates supplied are not equal in length");
316    }
317
318    if bits_per_dimension as usize > mem::size_of::<HilbertIndex>() * BITS_PER_BYTE {
319        panic!("bits_per_dimension > mem::size_of::<HilbertIndex>() * BITS_PER_BYTE");
320    }
321
322    unsafe {
323        return moore_hilbert_sys::hilbert_box_vtx(
324            coord1.len().try_into().unwrap(),
325            mem::size_of::<HilbertCoordinate>().try_into().unwrap(),
326            bits_per_dimension.try_into().unwrap(),
327            if find_min { 1 } else { 0 },
328            coord1.as_ptr() as *mut std::ffi::c_void,
329            coord2.as_ptr() as *mut std::ffi::c_void,
330        ) as usize;
331    }
332}
333
334/// Determine the first or last vertex of a box to lie on a Hilbert curve
335///
336/// # Arguments
337///
338/// * `find_min` - Is the least vertex sought?
339/// * `c1`      - One corner of box
340/// * `c2`      - Opposite corner
341///
342/// # Returns
343/// `c1` and `c2` modified to refer to selected corder
344/// value returned is log2 of size of largest power-of-two-aligned box that
345/// contains the selected corner and no other corners
346///
347/// # Assumptions
348///
349/// `bits_per_dimension` <= (sizeof `HilbertIndex`) * (`bits_per_byte`)
350///
351pub fn box_float_vertex(find_min: bool, coord1: &mut [f64], coord2: &mut [f64]) -> usize {
352    if coord1.len() != coord2.len() {
353        panic!("Coordinates supplied are not equal in length");
354    }
355
356    unsafe {
357        return moore_hilbert_sys::hilbert_ieee_box_vtx(
358            coord1.len().try_into().unwrap(),
359            if find_min { 1 } else { 0 },
360            coord1.as_mut_ptr(),
361            coord2.as_mut_ptr(),
362        ) as usize;
363    }
364}
365
366/// Determine the first or last point of a box to lie on a Hilbert curve
367///
368/// # Arguments
369///
370/// * `bits_per_dimension` - Number of bits/coordinate.
371/// * `find_min` - Is it the least vertex sought?
372/// * `coord1` - Coordinates of one corner of box
373/// * `coord2` - Coordinates of the opposite corner of box
374///
375/// # Returns
376///
377/// `coord1` and `coord2` are modified to refer to the least point
378///
379/// # Assumptions
380///
381/// `bits_per_dimension` <= (sizeof `HilbertIndex`) * (`bits_per_byte`)
382///
383/// # Example
384///
385/// ```
386/// let bits_per_dimension = 8;
387/// let starting_corners = vec![
388///    vec![0, 0],  // smallest coordinate point
389///    vec![10, 10] // largest coordinate point
390/// ];
391///
392/// // Since the coordinates will be overwritten when finding the points of the box
393/// // make copies.
394///
395/// let mut low_corner_1 = starting_corners[0].clone();
396/// let mut high_corner_1 = starting_corners[1].clone();
397/// moore_hilbert::box_point(bits_per_dimension, true, &mut low_corner_1, &mut high_corner_1);
398///
399/// // Both points should equal each other after the function call
400/// assert_eq!(high_corner_1, low_corner_1);
401///
402/// let low_point = low_corner_1.clone();
403///
404/// // Now get the high point.
405/// low_corner_1 = starting_corners[0].clone();
406/// high_corner_1 = starting_corners[1].clone();
407/// moore_hilbert::box_point(bits_per_dimension, false, &mut low_corner_1, &mut high_corner_1);
408///
409/// // Both points should equal each other after the function call
410/// assert_eq!(high_corner_1, low_corner_1);
411///
412/// let high_point = low_corner_1.clone();
413///
414/// assert_eq!(low_point, vec![0, 0]);
415/// assert_eq!(high_point, vec![1, 10]);
416///
417/// ```
418pub fn box_point(
419    bits_per_dimension: BitsPerDimensionType,
420    find_min: bool,
421    coord1: &mut [HilbertCoordinate],
422    coord2: &mut [HilbertCoordinate],
423) -> usize {
424    if coord1.len() != coord2.len() {
425        panic!("Coordinates supplied are not equal in length");
426    }
427
428    unsafe {
429        return moore_hilbert_sys::hilbert_box_pt(
430            coord1.len().try_into().unwrap(),
431            mem::size_of::<HilbertCoordinate>().try_into().unwrap(),
432            bits_per_dimension.try_into().unwrap(),
433            if find_min { 1 } else { 0 },
434            coord1.as_mut_ptr() as *mut std::ffi::c_void,
435            coord2.as_mut_ptr() as *mut std::ffi::c_void,
436        ) as usize;
437    }
438}
439
440/// Determine the first or last point of a box to lie on a Hilbert curve
441///
442/// # Arguments
443///
444/// * `bits_per_dimension` - Number of bits/coordinate.
445/// * `find_min` - Is it the least vertex sought?
446/// * `coord1` - Coordinates of one corner of box
447/// * `coord2` - Coordinates of the opposite corner of box
448///
449/// # Returns
450///
451/// `coord1` and `coord2` are modified to refer to the least point
452///
453/// # Assumptions
454///
455/// `bits_per_dimension` <= (sizeof `HilbertIndex`) * (`bits_per_byte`)
456///
457pub fn box_point_float(find_min: bool, coord1: &mut [f64], coord2: &mut [f64]) -> usize {
458    if coord1.len() != coord2.len() {
459        panic!("Coordinates supplied are not equal in length");
460    }
461
462    unsafe {
463        return moore_hilbert_sys::hilbert_ieee_box_pt(
464            coord1.len().try_into().unwrap(),
465            if find_min { 1 } else { 0 },
466            coord1.as_mut_ptr(),
467            coord2.as_mut_ptr(),
468        ) as usize;
469    }
470}
471
472/// Determine the first point of a box after a given point to lie on a Hilbert curve.
473///
474/// # Arguments
475///
476/// * `bits_per_dimension`  - Number of bits per dimension
477/// * `find_prev`           - Is the previous point sought?
478/// * `coord1`              - Coordinates of one corner of the box
479/// * `coord2`              - Coordinates of the opposite corner of the box
480/// * `point`               - Coordinates which are a lower bound on the point returned
481///
482/// # Returns
483///
484/// If true `coord1` and `coord2` are modified to point to the least point after `point` in the box.
485///
486/// If false the arguments are unchanged and the point is beyond the last point of the box
487///
488/// # Assumptions
489///
490/// `bits_per_dimension` <= (sizeof `HilbertIndex`) * (`bits_per_byte`)
491///
492pub fn box_next_point(
493    bits_per_dimension: BitsPerDimensionType,
494    find_prev: bool,
495    coord1: &mut [HilbertCoordinate],
496    coord2: &mut [HilbertCoordinate],
497    point: &[HilbertCoordinate],
498) -> bool {
499    if coord1.len() != coord2.len() {
500        panic!("Coordinates supplied are not equal in length");
501    }
502
503    if point.len() != coord1.len() {
504        panic!("Coordinates supplied are not equal in length to the point supplied");
505    }
506
507    unsafe {
508        if moore_hilbert_sys::hilbert_nextinbox(
509            coord1.len().try_into().unwrap(),
510            mem::size_of::<HilbertCoordinate>().try_into().unwrap(),
511            bits_per_dimension.try_into().unwrap(),
512            if find_prev { 1 } else { 0 },
513            coord1.as_mut_ptr() as *mut std::ffi::c_void,
514            coord2.as_mut_ptr() as *mut std::ffi::c_void,
515            point.as_ptr() as *mut std::ffi::c_void,
516        ) == 1
517        {
518            true
519        } else {
520            false
521        }
522    }
523}
moore_hilbert/lib.rs

moore_hilbert/
lib.rs
