hierarchical operations for the nested scheme

[keewis]

The nested scheme (and therefore unique, too) is hierarchical, and thus it is possible to have the arrange the cells into a tree. For various applications (e.g. aggregation) it is important to be able to query the hierarchy for parents, siblings, children. This can be as simple as

fn parent(&self, cell_id: u64, depth: u8) -> u64 {
    if self.depth < depth {
        panic!("Parent depth must be smaller than current depth, but got {} and {}", depth, self.depth)
    } elif self.depth == depth {
        cell_id
    } else {
        cell_id >> (2 * (self.depth - depth))
    }
}

fn siblings(&self, cell_id: u64) -> Vec<u64> {
    if self.depth == 0 {
        // 0..12
    } else {
        let parent = self.parent(cell_id, self.depth - 1);
        // parent..parent + 4
    }
}

fn children(&self, cell_id: u64, depth: u8) -> Vec<u64> {
    if self.depth >= depth {
        panic!("Child depth must be greater than the current depth, but got {} and {}", depth, self.depth)
    } else {
        // cell_id << (2 * (depth - self.depth))..(cell_id + 1) << (2 * (depth - self.depth))
    }
}

I couldn't quite figure out how to best convert ranges to vec right now, so I'll leave that for when I attempt an implementation.

Did I miss anything? Do you think something like this would make sense to add to this library, or would it be better to have it live elsewhere?

[fxpineau]

The hierarchical aspect of cells numbering is valid for nested only.
Getting parent/children/sibling numbers for a given cell is less simple in ring.

For nested, those relations -- albeit using delta_depth << 1 instead of 2 * delta_depth -- are so simple that they are used implicitly throughout the code, especially in the MOC library.

I could have made macros to make their usage more explicit.

To convert ranges to vec you can simply use collect, e.g. you can try this in Rust playground:

fn main() {
    let r = 0u8..5;
    let v = r.collect::<Vec<u8>>();
    println!("{:?}", v);
}

[keewis]

would you be interested in adding these (as functions, preferably)? No pressure, though, since I don't need to access internal functionality I can very easily add these to a separate library.

[fxpineau]

Not yet commited, but I have add the following code to the nested module.
(Note that I am using const fn and prefer relying on delta_depth: u8 than on the explicit depths.)

/// Return the hash value of the parent of the given `hash` at a depth equals to the `hash` depth minus `delta_depth`.
/// I.e., for `delta_depth = 1`, the returned value is the value of the direct parent of the given `hash` value.
/// For `delta_depth = 1`, the "grandparent" is returned, and so on.
///
/// # Params
/// * `hash`: a pixel index at a given (unspecified) depth
/// * `delta_depth`: hash depth minus the target parent depth
///
/// # Warning
/// The calling code is responsible for ensuring that the `hash` depth minus `delta_depth`
/// is not smaller than 0.
/// But such a case is harmless here since the result will simply be equal to 0.
pub const fn parent(hash: u64, delta_depth: u8) -> u64 {
  hash >> (delta_depth << 1)
}

/// Returns a range representing the set of values of all the siblings if the given hash value
/// (including the value itself).
///
/// # Params
/// * `depth`: depth of the hash value, must be in `[0, 29]`
/// * `hash`: hash value, i.e. cell number
///
/// # Warning
/// * not check is performed on `depth`n the calling code must ensure that depth is <= 29.
///
pub const fn siblings(depth: u8, hash: u64) -> RangeInclusive<u64> {
  if depth == 0 {
    0..=11
  } else {
    let hash = hash & 0xFFFFFFFFFFFFFFFC; // <=> 0b1111..111100
    hash..=(hash | 3)
  }
}

/// Returns the range representing the set of values of all the child of the given `hash`
/// at a depth equals to the (unspecified) hash depth + the given `delta_depth`.
///
/// # Warning
/// THe calling code must ensure that hash depth + delta_depth is <= 29.
///
pub const fn childs(hash: u64, delta_depth: u8) -> Range<u64> {
  let twice_dd = delta_depth << 1;
  (hash >> twice_dd)..((hash + 1) >> twice_dd)
}

[fxpineau]

If you are ok with commit 6eace2f, I let you close the issue.

[keewis]

I'm mostly happy with these, thanks a lot. The only thing I'd like to point out is that the plural of "child" is "children" (see the comments on the commit you linked to).

Do you need any ideas for tests?

[fxpineau]

Re-reading this, I realized that the bit shift it not the right one in children. I just pushed a fixed version.

Also, note that those methods are low level and speed is preferred over safety.
One can make 'safe' versions decorating those methods:

• additionally taking the hash depth
• returning a result ensuring that:
  • depth + delta_depth is in 0..=29
  • also possibly checking that the hash is in the good value range

If you want to add tests, please go ahead (I only have basic ideas).

[keewis]

I've added something similar in keewis/healpix-geo#24, which I'm planning to add to cds-healpix-python at some point (just like the kth_neighbourhood from #15). Not sure how I'd translate the tests there to rust, though, but I might get to that next week (if you're not faster).

Maybe for siblings we can assert that we get 4 siblings, that they're sequential, and that the original hash is one of them (and probably also that the smallest hash is a multiple of 4)? For children we can also do the same, except for the containment check (and the size should be 4^delta_depth), but not sure about what to check for parents. Maybe that any four (grand-) children return the same parent?