mortie.prefix_trie

Compacted-trie polygon builders over morton words, and the trie node type they return.

MortonChild is documented as a return type: obtain nodes from the builders below, never by constructing one. Its read surface — characteristic, len, children, nchildren, mantissa_array, cell_area — is the frozen contract; the constructor is internal and its signature is not (espg-ratified on PR #130).

Prefix trie with greedy spanning-tree refinement for morton indices.

Builds a compacted prefix trie over the string representations of morton indices and uses a greedy algorithm to select the fewest prefix-cells that span the input data within a cell budget.

Key entry points:

• :func:split_children / :func:split_children_geo — build the trie
• :func:morton_polygon — refine to n_cells prefix-cells (n_cells=4 gives a bounding box, n_cells=12 gives a polygon)
• :func:geo_morton_polygon — geographic convenience wrapper

MortonChild

A node in the compacted prefix trie over morton index strings.

Each node owns a boolean mask into the shared character array and a characteristic prefix string. Children are created lazily when the column under the mask diverges.

Obtain nodes from :func:split_children / :func:split_children_geo (or the morton_polygon* helpers); do not construct them directly. The read surface below is the frozen 1.x contract: characteristic, len, children, nchildren, :attr:mantissa_array and :attr:cell_area. The constructor is internal and its signature is not part of that contract -- it takes the trie's internal representation (a shared character array plus row masks), which is free to change. The production path does not use it at all: split_children builds nodes in Rust and rebuilds them via __new__, bypassing __init__ entirely.

Parameters:

Name	Type	Description	Default
char_array	ndarray of shape (N, L), dtype='U1'	Shared 2-D character array (all rows same length).	required
mask	ndarray of shape (N,), dtype=bool	Which rows of char_array belong to this node.	required
start_col	int	Column index at which to resume scanning.	required
characteristic	str	Common prefix accumulated so far.	required
original_array	ndarray	The original integer morton array (shared reference).	required
max_depth	int or None	Maximum branching depth (None = unlimited).	None
_depth	int	Current branching depth (0 at root level).	0

Attributes:

Name	Type	Description
characteristic	str	Common prefix shared by every morton index under this node.
len	int	Number of morton indices under this node.
children	list of MortonChild	Child nodes, empty for a leaf.
nchildren	int	len(children).

Raises:

Type	Description
ValueError	If mask selects no rows, or — for a non-root node, i.e. one built with start_col > 0 — the masked rows do not share the expected leading character (an uncompressible mix of signs or base cells).

Source code in mortie/prefix_trie.py

class MortonChild:
    """A node in the compacted prefix trie over morton index strings.

    Each node owns a boolean mask into the shared character array and
    a characteristic prefix string.  Children are created lazily when
    the column under the mask diverges.

    Obtain nodes from :func:`split_children` / :func:`split_children_geo`
    (or the ``morton_polygon*`` helpers); **do not construct them
    directly.** The read surface below is the frozen 1.x contract:
    ``characteristic``, ``len``, ``children``, ``nchildren``,
    :attr:`mantissa_array` and :attr:`cell_area`. The constructor is
    internal and its signature is *not* part of that contract -- it takes
    the trie's internal representation (a shared character array plus row
    masks), which is free to change. The production path does not use it
    at all: ``split_children`` builds nodes in Rust and rebuilds them via
    ``__new__``, bypassing ``__init__`` entirely.

    Parameters
    ----------
    char_array : ndarray of shape (N, L), dtype='U1'
        Shared 2-D character array (all rows same length).
    mask : ndarray of shape (N,), dtype=bool
        Which rows of *char_array* belong to this node.
    start_col : int
        Column index at which to resume scanning.
    characteristic : str
        Common prefix accumulated so far.
    original_array : ndarray
        The original integer morton array (shared reference).
    max_depth : int or None
        Maximum branching depth (None = unlimited).
    _depth : int
        Current branching depth (0 at root level).

    Attributes
    ----------
    characteristic : str
        Common prefix shared by every morton index under this node.
    len : int
        Number of morton indices under this node.
    children : list of MortonChild
        Child nodes, empty for a leaf.
    nchildren : int
        ``len(children)``.

    Raises
    ------
    ValueError
        If *mask* selects no rows, or — for a non-root node, i.e. one built
        with ``start_col > 0`` — the masked rows do not share the expected
        leading character (an uncompressible mix of signs or base cells).
    """

    __slots__ = (
        "_char_array",
        "_mask",
        "_original_array",
        "_original_indices",
        "_max_depth",
        "_depth",
        "characteristic",
        "len",
        "children",
        "nchildren",
        "_cell_area",
    )

    def __init__(
        self,
        char_array,
        mask,
        start_col,
        characteristic,
        original_array,
        max_depth=None,
        _depth=0,
    ):
        self._char_array = char_array
        self._mask = mask
        self._original_array = original_array
        self._original_indices = None
        self._max_depth = max_depth
        self._depth = _depth
        self.characteristic = characteristic
        self.len = int(mask.sum())
        self.children = []
        self.nchildren = 0
        self._cell_area = None  # lazily cached by the `cell_area` property

        if self.len == 0:
            raise ValueError("Empty mask — no indices to compact")

        # Validate that all masked rows share the expected prefix: every row's
        # first column must agree (a divergent leading char means the caller fed
        # an uncompressible mix of signs/base cells).
        if start_col > 0:
            if len(np.unique(char_array[mask, 0])) > 1:
                raise ValueError(
                    "Input array is not compressible — "
                    "indices do not share expected prefix"
                )

        self._compact(start_col)

    def _compact(self, col):
        """Walk columns, extending characteristic while unique.

        Branch on divergence: while every masked row agrees on a column that
        character is appended to ``characteristic``; at the first column where
        they disagree a child is created per distinct character, unless
        ``_max_depth`` has been reached.

        Parameters
        ----------
        col : int
            Column index in the shared character array at which to resume
            scanning.
        """
        char_array = self._char_array
        mask = self._mask
        ncols = char_array.shape[1]

        while col < ncols:
            unique = np.unique(char_array[mask, col])

            if len(unique) == 1:
                self.characteristic += unique[0]
                col += 1
            else:
                # Divergence — create children if depth allows
                if self._max_depth is not None and self._depth >= self._max_depth:
                    break

                for val in unique:
                    child_mask = mask & (char_array[:, col] == val)
                    child = MortonChild(
                        char_array,
                        child_mask,
                        col + 1,
                        self.characteristic + val,
                        self._original_array,
                        max_depth=self._max_depth,
                        _depth=self._depth + 1,
                    )
                    self.children.append(child)
                self.nchildren = len(self.children)
                break

    @property
    def mantissa_array(self):
        """The original morton indices belonging to this node.

        Returns
        -------
        ndarray
            The slice of the original integer morton array under this node.
        """
        if self._original_indices is not None:
            return self._original_array[self._original_indices]
        return self._original_array[self._mask]

    @property
    def cell_area(self):
        """HEALPix cell area implied by this node's characteristic (cached).

        The characteristic encodes sign + digits; the *order* is the number of
        digits (excluding a leading '-')::

            1 digit  → base cell    → area = 1
            2 digits → area = 1/4
            k digits → area = 4^(-(k-1))

        The characteristic is fixed once compaction finishes, so the area is
        computed once and cached (the greedy expansion in
        :func:`morton_polygon` reads it per node every iteration).

        Returns
        -------
        float
            Cell area in units of one order-0 base cell.
        """
        if self._cell_area is None:
            ndigits = len(self.characteristic.lstrip("-"))
            self._cell_area = 4.0 ** (-(ndigits - 1))
        return self._cell_area

    def __repr__(self):
        """Return a debug representation naming the node's read surface.

        Returns
        -------
        str
            ``MortonChild(characteristic=..., len=..., nchildren=...)``.
        """
        return (
            f"MortonChild(characteristic={self.characteristic!r}, "
            f"len={self.len}, nchildren={self.nchildren})"
        )

cell_area property

HEALPix cell area implied by this node's characteristic (cached).

The characteristic encodes sign + digits; the order is the number of digits (excluding a leading '-')::

1 digit  → base cell    → area = 1
2 digits → area = 1/4
k digits → area = 4^(-(k-1))

The characteristic is fixed once compaction finishes, so the area is computed once and cached (the greedy expansion in :func:morton_polygon reads it per node every iteration).

Returns:

Type	Description
float	Cell area in units of one order-0 base cell.

mantissa_array property

The original morton indices belonging to this node.

Returns:

Type	Description
ndarray	The slice of the original integer morton array under this node.

__repr__()

Return a debug representation naming the node's read surface.

Returns:

Type	Description
str	MortonChild(characteristic=..., len=..., nchildren=...).

Source code in mortie/prefix_trie.py

def __repr__(self):
    """Return a debug representation naming the node's read surface.

    Returns
    -------
    str
        ``MortonChild(characteristic=..., len=..., nchildren=...)``.
    """
    return (
        f"MortonChild(characteristic={self.characteristic!r}, "
        f"len={self.len}, nchildren={self.nchildren})"
    )

morton_polygon(roots, n_cells)

Greedily expand tree nodes to minimize area within a cell budget.

Starting from the root-level children produced by :func:split_children, repeatedly replace the most "efficient" parent with its children until the budget of n_cells is reached.

Common n_cells values:

• n_cells=4 → bounding box (coarse, 4 prefix-cells)
• n_cells=12 → polygon (tighter fit, up to 12 prefix-cells)

Efficiency is defined as the area saved per additional cell consumed (see :func:_expansion_efficiency). An expanded node's children become new expansion candidates, so the frontier is maintained as a max-heap keyed by efficiency — each step pops the globally most efficient expandable node in O(log n) rather than rescanning the whole frontier O(n) per step. A node's efficiency and cost are fixed, and the remaining budget only shrinks, so a node popped when its cost no longer fits can be discarded permanently.

Coverage is preserved because expansion only replaces a parent with its exact children — no points are lost or duplicated.

Parameters:

Name	Type	Description	Default
roots	list of MortonChild	Root-level children from :func:split_children.	required
n_cells	int	Cell budget for the refinement (see Returns for the root-count floor).	required

Returns:

Type	Description
list of MortonChild	Refined prefix-cells, at most n_cells of them — unless roots is already longer than that, in which case it is returned as it stands (roots are only ever expanded, never merged, so len(roots) is a floor on the result).

Source code in mortie/prefix_trie.py

def morton_polygon(roots, n_cells):
    """Greedily expand tree nodes to minimize area within a cell budget.

    Starting from the root-level children produced by :func:`split_children`,
    repeatedly replace the most "efficient" parent with its children until the
    budget of *n_cells* is reached.

    Common *n_cells* values:

    - ``n_cells=4``  → bounding box (coarse, 4 prefix-cells)
    - ``n_cells=12`` → polygon (tighter fit, up to 12 prefix-cells)

    Efficiency is defined as the area saved per additional cell consumed
    (see :func:`_expansion_efficiency`).  An expanded node's children become new
    expansion candidates, so the frontier is maintained as a **max-heap keyed by
    efficiency** — each step pops the globally most efficient expandable node in
    ``O(log n)`` rather than rescanning the whole frontier ``O(n)`` per step.
    A node's efficiency and cost are fixed, and the remaining budget only
    shrinks, so a node popped when its cost no longer fits can be discarded
    permanently.

    Coverage is preserved because expansion only replaces a parent with its
    exact children — no points are lost or duplicated.

    Parameters
    ----------
    roots : list of MortonChild
        Root-level children from :func:`split_children`.
    n_cells : int
        Cell budget for the refinement (see Returns for the root-count
        floor).

    Returns
    -------
    list of MortonChild
        Refined prefix-cells, at most *n_cells* of them — unless *roots* is
        already longer than that, in which case it is returned as it stands
        (roots are only ever expanded, never merged, so ``len(roots)`` is a
        floor on the result).
    """
    # `current` holds the live frontier; expanding a node swaps it for its
    # children in place.  The heap mirrors the expandable nodes, keyed by
    # (-efficiency, seq) so the most efficient pops first, ties broken by
    # document order (insertion sequence) to match the original index scan.
    current = list(roots)
    count = len(current)
    seq = 0
    heap = []

    def _maybe_push(node):
        """Push *node* onto the frontier heap if its expansion fits the budget.

        Parameters
        ----------
        node : MortonChild
            Candidate for expansion.
        """
        # Only nodes whose expansion still fits the budget are scored: scoring
        # calls `_expansion_efficiency`, which sums every child's area, so it is
        # the dominant per-node cost.  `count` never decreases, so a node that
        # does not fit now never will — skip it before paying for the score.
        nonlocal seq
        if node.nchildren > 0 and count + (node.nchildren - 1) <= n_cells:
            heapq.heappush(heap, (-_expansion_efficiency(node), seq, node))
            seq += 1

    for node in roots:
        _maybe_push(node)

    while count < n_cells and heap:
        _, _, node = heapq.heappop(heap)
        cost = node.nchildren - 1
        if count + cost > n_cells:
            # Budget only shrinks from here, so this node can never fit again.
            continue
        idx = current.index(node)
        current[idx:idx + 1] = node.children
        count += cost
        for child in node.children:
            _maybe_push(child)

    return current

morton_polygon_from_array(morton_array, n_cells, max_depth=None)

Build trie and refine to n_cells in one call.

Parameters:

Name	Type	Description	Default
morton_array	array-like of int	Morton indices (packed uint64 words; base cells 7-11 set bit 63).	required
n_cells	int	Cell budget for the refinement (see Returns for the root-count floor).	required
max_depth	int or None	Maximum branching depth. When None (default), automatically derived from n_cells as ceil(log2(n_cells)) + 1.	None

Returns:

Type	Description
list of MortonChild	Refined prefix-cells, at most n_cells of them — unless the trie already has more root-level children than that, which are returned as they stand (:func:morton_polygon only ever expands roots, never merges them, so the root count is a floor on the result).

Source code in mortie/prefix_trie.py

def morton_polygon_from_array(morton_array, n_cells, max_depth=None):
    """Build trie and refine to *n_cells* in one call.

    Parameters
    ----------
    morton_array : array-like of int
        Morton indices (packed ``uint64`` words; base cells 7-11 set bit 63).
    n_cells : int
        Cell budget for the refinement (see Returns for the root-count
        floor).
    max_depth : int or None
        Maximum branching depth.  When *None* (default), automatically
        derived from *n_cells* as ``ceil(log2(n_cells)) + 1``.

    Returns
    -------
    list of MortonChild
        Refined prefix-cells, at most *n_cells* of them — unless the trie
        already has more root-level children than that, which are returned
        as they stand (:func:`morton_polygon` only ever expands roots, never
        merges them, so the root count is a floor on the result).
    """
    if max_depth is None:
        max_depth = _auto_max_depth(n_cells)
    roots = split_children(morton_array, max_depth=max_depth)
    return morton_polygon(roots, n_cells=n_cells)

geo_morton_polygon(lats, lons, n_cells, order=18, max_depth=None)

Compute a morton polygon from geographic coordinates.

Builds a prefix trie over the morton indices of the input coordinates and greedily refines it to at most n_cells prefix-cells. Common values:

• n_cells=4 → bounding box (4 prefix-cells)
• n_cells=12 → polygon (tighter fit, 12 prefix-cells)

Parameters:

Name	Type	Description	Default
lats	array - like	Latitude and longitude values in degrees.	required
lons	array - like	Latitude and longitude values in degrees.	required
n_cells	int	Cell budget for the refinement (see Returns for the root-count floor).	required
order	int	Morton tessellation order. Default is 18.	18
max_depth	int or None	Maximum branching depth. When None (default), automatically derived from n_cells as ceil(log2(n_cells)) + 1.	None

Returns:

Type	Description
list of MortonChild	Refined prefix-cells, at most n_cells of them — unless the trie already has more root-level children than that, which are returned as they stand (:func:morton_polygon only ever expands roots, never merges them, so the root count is a floor on the result).

Source code in mortie/prefix_trie.py

def geo_morton_polygon(lats, lons, n_cells, order=18, max_depth=None):
    """Compute a morton polygon from geographic coordinates.

    Builds a prefix trie over the morton indices of the input coordinates
    and greedily refines it to at most *n_cells* prefix-cells.  Common
    values:

    - ``n_cells=4``  → bounding box (4 prefix-cells)
    - ``n_cells=12`` → polygon (tighter fit, 12 prefix-cells)

    Parameters
    ----------
    lats, lons : array-like
        Latitude and longitude values in degrees.
    n_cells : int
        Cell budget for the refinement (see Returns for the root-count
        floor).
    order : int
        Morton tessellation order.  Default is 18.
    max_depth : int or None
        Maximum branching depth.  When *None* (default), automatically
        derived from *n_cells* as ``ceil(log2(n_cells)) + 1``.

    Returns
    -------
    list of MortonChild
        Refined prefix-cells, at most *n_cells* of them — unless the trie
        already has more root-level children than that, which are returned
        as they stand (:func:`morton_polygon` only ever expands roots, never
        merges them, so the root count is a floor on the result).
    """
    if max_depth is None:
        max_depth = _auto_max_depth(n_cells)
    roots = split_children_geo(lats, lons, order=order, max_depth=max_depth)
    return morton_polygon(roots, n_cells=n_cells)

split_children(morton_array, max_depth=4)

Build a compacted prefix trie over morton_array and return root children.

Parameters:

Name	Type	Description	Default
morton_array	array-like of int	Morton indices (packed uint64 words; base cells 7-11 set bit 63).	required
max_depth	int or None	Maximum branching depth. None means full recursion. Default is 4.	4

Returns:

Type	Description
list of MortonChild	One root-level child per (sign, first-digit) group.

Raises:

Type	Description
ValueError	If morton_array is empty or not 1-D.

Source code in mortie/prefix_trie.py

def split_children(morton_array, max_depth=4):
    """Build a compacted prefix trie over *morton_array* and return root children.

    Parameters
    ----------
    morton_array : array-like of int
        Morton indices (packed ``uint64`` words; base cells 7-11 set bit 63).
    max_depth : int or None
        Maximum branching depth.  ``None`` means full recursion.
        Default is 4.

    Returns
    -------
    list of MortonChild
        One root-level child per (sign, first-digit) group.

    Raises
    ------
    ValueError
        If *morton_array* is empty or not 1-D.
    """
    morton_array = np.ascontiguousarray(np.asarray(morton_array, dtype=np.uint64))
    if morton_array.ndim != 1 or len(morton_array) == 0:
        raise ValueError("morton_array must be a non-empty 1-D integer array")

    flat_nodes, permutation = _rust_split_children(
        morton_array, max_depth=max_depth
    )
    return _rebuild_tree_from_flat(flat_nodes, permutation, morton_array)

split_children_geo(lats, lons, order=18, max_depth=4)

Build compacted prefix trie from geographic coordinates.

Parameters:

Name	Type	Description	Default
lats	array - like	Latitude and longitude values in degrees.	required
lons	array - like	Latitude and longitude values in degrees.	required
order	int	Morton tessellation order. Default is 18.	18
max_depth	int or None	Maximum branching depth. Default is 4.	4

Returns:

Type	Description
list of MortonChild	One root-level child per (sign, first-digit) group.

Source code in mortie/prefix_trie.py

def split_children_geo(lats, lons, order=18, max_depth=4):
    """Build compacted prefix trie from geographic coordinates.

    Parameters
    ----------
    lats, lons : array-like
        Latitude and longitude values in degrees.
    order : int
        Morton tessellation order.  Default is 18.
    max_depth : int or None
        Maximum branching depth.  Default is 4.

    Returns
    -------
    list of MortonChild
        One root-level child per (sign, first-digit) group.
    """
    from .tools import geo2mort
    morton_array = geo2mort(lats, lons, order=order)
    return split_children(morton_array, max_depth=max_depth)