Boundary traversal engines
This reference is for contributors implementing or tuning boundary traversal. For the public operations and their index conventions, see Region boundaries.
Boundary iterators
DiscreteGlobalGrids.Engine.SubtreeHaloIterator Type
SubtreeHaloIterator(sys, c, l; connectivity = Vertex())The halo of c's subtree at level l, lazily: every level-l cell that is not a descendant of c but has a neighbour that is, in ascending canonical order, each cell exactly once.
What halo returns for a region that is a whole rooted subtree, with cells = true. l == level(c) is c's own one-ring, sorted. l < level(c) and l > maxlevel(sys) throw an ArgumentError.
globalindex(levelgrid(sys, l), x) is strictly increasing over the walk, which is what halo's index form reads. This differs from the rotational ordering of neighbors.
Construction does not materialize the halo. The iterator holds O(depth) walk state and bounded neighbour containers.
Base.IteratorSize is HasLength() only when an engine derives an exact count; otherwise it is SizeUnknown(), and sizehint is the inexact estimate.
DiscreteGlobalGrids.Engine.SubsetHaloIterator Type
SubsetHaloIterator(subset, connectivity, engine)What halo returns, with cells = true, for a region that is not a rooted complete subtree. Construction is O(1); iteration uses an O(depth) frame stack and prunes with subset_span. Its size is unknown.
DiscreteGlobalGrids.Engine.RegionSide Type
RegionSideThe lazy walk border and interior return. Its engine yields (index, cell) pairs and the wrapper projects them to whichever of the two the caller asked for, so cells = true costs no second pass.
DiscreteGlobalGrids.Fallbacks.EdgeCellIterator Type
EdgeCellIterator(sys, c, l; connectivity = Vertex())The border of c's subtree at level l, lazily: every level-l descendant of c with a neighbour that is not one, in ascending canonical order.
The walk border(subtree(sys, c, l)) reads. l == level(c) yields exactly c — a cell is its own border. l < level(c) and l > maxlevel(sys) throw an ArgumentError, as the eager verb does.
Memory is O(depth) and independent of the border's size: IGeo7, H3, HEALPix, ISEA4R and S2 walk a pruned subtree from an isbits stack and allocate nothing per element. eltype is cellindextype(sys).
Base.IteratorSize is HasLength() wherever the count is closed-form — 3^(d+1)-3 / 5(3^d-1)/2 on the two hexagonal systems, 4·2^d-4 on the three square ones, d = l - level(c) — and SizeUnknown() for the generic scan, which has no count short of running it. There is no length that would.
See also InnerCellIterator, the complement, and descendant_range.
DiscreteGlobalGrids.Fallbacks.InnerCellIterator Type
InnerCellIterator(sys, c, l; connectivity = Vertex())The interior of c's subtree at level l, lazily: the level-l descendants that are not on the border, in ascending canonical order.
The walk interior(subtree(sys, c, l)) reads, and together with EdgeCellIterator it partitions descendants(sys, c, l). l == level(c) is empty.
The interior is generated from branches pruned by the border walk. The automaton prunes exactly where a branch goes wholly interior, so the interior is a disjoint union of complete sub-subtrees, emitted in place. No membership set, and the border is never materialised to be subtracted.
Memory and eltype are EdgeCellIterator's. The count is closed-form on the five systems with an automaton ((2^d-2)^2 on the square ones), so IteratorSize is HasLength() there and SizeUnknown() for the generic scan.
Iterator indices and sizing
DiscreteGlobalGrids.Engine.halo_indices Function
halo_indices(it) -> HaloIndexIteratorAn id halo walk read as GLOBAL INDICES on the grid it was cut from: strictly increasing, lazily, with the walk's own O(depth) state. halo(region) already answers in indices; this is the wrapper it uses, for a walk obtained with cells = true.
DiscreteGlobalGrids.Engine.HaloIndexIterator Type
HaloIndexIterator(halo, grid)A halo walk read as global indices on grid, lazily — what halo returns by default, and what halo_indices wraps an id walk in.
Yields Int, strictly increasing, one per cell of the underlying walk and in the same order. Everything else is the wrapped iterator's: Base.IteratorSize, the length that exists on exactly two engines and on no others, resumability, and the O(depth) state.
DiscreteGlobalGrids.Engine.sizehint Function
sizehint(walk) -> Union{Int,Nothing}An approximate count of what walk will yield, or nothing when no cheap bound exists. Suitable only for sizehint!.
h = sizehint(w)
out = eltype(w)[]
h === nothing || sizehint!(out, h)
for x in w; push!(out, x); endUnlike length, an estimate may over- or undershoot: Base.IteratorSize has no inexact slot, and this is the inexact answer. Engines with an exact count return it; seam bands use 4·side + 8, hexagonal walks 3^(d+1) + 3, and the scanning and outside-first walks return nothing because no general perimeter bound is available.
Engine selection
A boundary operation selects an engine to enumerate candidates and test their adjacency. A grid system can provide a specialised halo_engine method to use its topology efficiently. These interfaces are internal and may change.
Every engine returns exact results. A candidate band can be larger than the halo; adjacency tests filter it before the iterator yields cells.
DiscreteGlobalGrids.halo_engine Function
border_engine(sys, c, target::Int, connectivity)
interior_engine(sys, c, target::Int, connectivity)
halo_engine(sys, c, target::Int, connectivity)Return the iteration engine used by EdgeCellIterator, InnerCellIterator, or SubtreeHaloIterator. A system may override these methods with an O(border) or O(halo) traversal; eager operations collect the same engine.
An engine is any iterator over cellindextype(sys). All three methods own their level validation, so their ArgumentErrors are the ones the eager verbs raise.
Engine selection uses private dispatch on the system type and is not part of the public compatibility surface.
The generic border and interior engines scan descendant_range, or materialize descendants when has_sorted_subtrees is false. The generic halo engine walks cells outside the subtree because a halo is not a single descendant interval.
Specializations may enumerate conservative candidates, but must filter them by the requested adjacency. If their preconditions cannot be verified, they must return generic_halo_engine(sys, c, target, connectivity).
DiscreteGlobalGrids.Engine.generic_halo_engine Function
generic_halo_engine(sys, c, target, connectivity)Return the generic halo engine after level validation: RingHaloEngine at depth zero, OutsideWalkEngine for sorted subtrees, or ScanHaloEngine when no descendant range is available. Specialized engines call this method when their preconditions fail.
DiscreteGlobalGrids.Engine.RingHaloEngine Type
RingHaloEngine(ring)c's own one-ring, ascending, by selection emit. O(degree^2) time with degree <= maxneighbors(sys, connectivity), no allocation, isbits state.
length equals length(ring), requiring native one-rings to contain no duplicates. collect_subtree reports a count mismatch if this invariant fails.
DiscreteGlobalGrids.Engine.OutsideWalkEngine Type
OutsideWalkEngine(system, grid, root, rootlevel, target, lo, hi, rootcap,
roots, provider, connectivity)The correctness fallback: outside cells in canonical hierarchy order, the subject subtree skipped whole, nodes pruned by cap, survivors tested by provider.
Each outside cell is considered at most once, so there is no seen-set and no final sort; the walk state is one O(depth) frame stack of (cell, next child) pairs, and the geometry provider's descendant cursor is a second one. This path may do more work than an indexed specialization — it is the correctness fallback, and with ForcedGeometry it is the independent oracle those specializations are checked against.
Requires more than has_sorted_subtrees, which promises only that a subtree's target-level descendants are CONTIGUOUS in index. This walk emits in the order it meets cells, with no sort to repair it, so it additionally requires that children(sys, c) and rootcells(sys) are each ordered by their elements' TARGET-LEVEL descendant ranges — sibling i before sibling j exactly when first(descendant_range(sys, kids[i], target)) < first(descendant_range(sys, kids[j], target)), at every level and for every target. Contiguity without that ordering still produces contiguous blocks, just visited out of order, and the walk would emit a mis-sorted halo with no error raised anywhere. Every bundled system satisfies it, and test/systems/crosssystem/subtree_halos.jl is what says so: its law compares this walk element for element against an ascending-INDEX scan of the target level. A system that does not satisfy it must supply its own halo_engine rather than inherit this one.
DiscreteGlobalGrids.Engine.ScanHaloEngine Type
ScanHaloEngine(system, grid, root, rootlevel, target, provider, connectivity)Every cell of the target level in index order, the descendants skipped and the rest tested. O(1) memory and canonical by construction, but O(ncells) time — the price of a system with no descendant_range to prune by, and A5 is the only one. See the comment above this type for what a dedicated A5 engine would have to prove first.
DiscreteGlobalGrids.Engine.subset_halo_engine Function
subset_halo_engine(sys, subset, complete, target, connectivity)Return the outside-first engine for an arbitrary subset. It uses SubsetMembership and subset index spans instead of a subtree root range or cap. The subtree-skip fields are inert so an absent cell inside the subset's span can still be emitted as a halo cell. Nodes are descended only when the subset touches them or one of their same-level neighbours.
O(depth) memory beyond the subset's own storage. A system with no descendant_range gets ScanHaloEngine, for the same reason it does at a subtree.
This is not a system extension point because its subject is an arbitrary membership predicate rather than a root cell.
sourceDiscreteGlobalGrids.Engine.geometry_halo_engine Function
geometry_halo_engine(sys, c, target, connectivity)The generic walk forced onto ForcedGeometry, whatever fast path the system would otherwise take. Not a public verb and not reachable from SubtreeHaloIterator's keyword constructor: it exists so a test can build the oracle explicitly and hand it to the positional constructor.
The aperture-4 band
HEALPix, S2 and ISEA4R: a subtree is an aligned square block in one face's lattice, and its halo is the width-one band around it.
DiscreteGlobalGrids.Engine.SquareBandEngine Type
SquareBandEngine(curve, check, level, faceside, homeface, x0, y0, side, corners, rects)The halo of the side x side block at lattice origin (x0, y0) of homeface, in ascending id, by one pruned quadtree descent per rectangle in rects — which are one per face and ascending by face, so the concatenation is already the canonical merge.
faceside is a face's full lattice side at level. Yields LevelIndex on SquareBorderEngine's reasoning and takes the same quadrant_step curves. O(candidates + depth) time, O(depth) memory.
check decides both the emit rule and the count contract:
NoCheck— the block is nowhere flush with its face edge, the one rectangle is the width-1 band, and band and halo are the same set. The count is closed form,4·side + 4or4·sideunderEdge(), soBase.IteratorSizeisHasLength().NativeCheck— the block is flush somewhere, the rectangles are a conservative superset, and every candidate is tested before it is yielded. No perimeter formula survives a seam (a cube corner is three cells, not four; an ISEA4R icosahedral vertex is five), soIteratorSizeisSizeUnknown()and there is nolengthmethod at all.
SIZE, WHICH IS NOT FREE EVEN WHERE TIME IS. rects is a fixed _BAND_RECT_CAP-slot inline list, so an engine is 352 bytes on the in-face path (SquareBandEngine{MortonCurve,NoCheck}), 296 of them the rectangle list with exactly one slot used. Nothing is heap-allocated and no measured time is spent on the unused slots — the descent reads length(rects), never the capacity — but the in-face path is "free" in TIME only, and an engine returned by value costs that copy. Shrinking it would mean a second engine type for the one-rectangle case, which is not worth two monomorphic walks.
DiscreteGlobalGrids.Engine.square_halo_engine Function
square_halo_engine(sys, curve, c, target, connectivity, x0, y0, side, face, n)The halo engine for the side x side block at lattice origin (x0, y0) of 0-based face, on a face of side n at level target. The quad-face family's halo_engine is this call plus lattice_decode.
Away from the face edge it is the exact width-1 band, unchecked and counted. Flush with it, _seam_band_engine takes over. side == 1 never reaches here.
DiscreteGlobalGrids.Engine.FaceRect Type
FaceRect(face, orientation, x0, y0, x1, y1)One face's candidate rectangle: the inclusive lattice box [x0, x1] x [y0, y1] on 0-based face, to be descended under curve state orientation (the state that face's ROOT is read under, from face_orientation).
The rectangles of a SquareBandEngine are one per face and sorted by face, which is what makes walking them a canonical merge.
Int32 BOUNDS BIND AT LEVEL 32, NOT AT maxlevel. A level-l lattice coordinate runs to 2^l - 1, so Int32 holds one through level 31 (2^31 - 1 == typemax(Int32)) and overflows at level 32. S2's maxlevel of 30 is the deepest registered system, so there is exactly ONE level of headroom, and the quantity to compare a future maxlevel bump against is 31 — not 30, and not _SQUARE_CAP. Past it the failure is an InexactError raised by this constructor from inside square_halo_engine, i.e. from iterator construction, which is loud but says nothing about the cause; widen these six fields to Int64 (they are Int32 only to keep _BAND_RECT_CAP rectangles inline and cheap to copy) rather than clamping. test/systems/crosssystem/subtree_halos.jl walks a maxlevel block on all three systems, so the level-31 boundary is approached from one level below on every run.
DiscreteGlobalGrids.Engine.SquareBandWalk Type
SquareBandWalk(rect, stack, code, x, y)The walk state: which rectangle is being descended, the frame stack, and the within-face curve code and lattice origin of the sub-square on top of it. Frame k's node has side faceside >> (k - 1), so none of the last three needs storing per frame — all are restored on pop by replaying the parent's last quadrant_step.
DiscreteGlobalGrids.Engine.NoCheck Type
NoCheck()The emit rule of an exact band: a surviving leaf IS a halo cell, subject only to Edge() dropping the four diagonal corners. Zero-size, so an engine carrying it costs nothing for the distinction.
DiscreteGlobalGrids.Engine.NativeCheck Type
NativeCheck(system, grid, root, rootlevel, connectivity)The emit rule of a conservative band: a candidate is a halo cell only if the system's own one-ring puts a descendant of root next to it,
any(nb -> ancestor(sys, nb, rootlevel) == root,
neighbors(grid, x, 1; connectivity))which is the exact definition, applied to every candidate before it is yielded. O(degree · depth) per candidate.
The aperture-7 directed walk
IGeo7 and H3: a subtree's halo lies under the root's own same-level neighbours, and is reached by seeding each neighbour's border automaton with the arc that faces the root.
DiscreteGlobalGrids.Engine.hex_halo_engine Function
hex_halo_engine(sys, c, target, connectivity)Return the calibrated halo engine used by H3 and IGeo7. Fall back to generic_halo_engine whenever a precondition fails.
The system must have sorted subtrees, the target must be deeper than c, the neighbour ring must fit its fixed capacity, every neighbour must calibrate, and depths of at least three must pass _hex_validate.
The initial ring probe uses Vertex() because an edge halo is a subset of the vertex halo. Calibration and validation use the requested connectivity. If that connectivity produces an unsupported arc, the method returns the generic engine.
DiscreteGlobalGrids.Engine.HexChildHaloEngine Type
HexChildHaloEngine(system, grid, root, rootlevel, target, connectivity, ring)target == rootlevel + 1: each neighbour's children in turn, native-checked, the neighbours in descendant-range order. No automaton and no calibration — at this depth the children ARE the candidates.
children is re-read per step rather than stored, which keeps the walk state two integers and costs a bounded-container rebuild of at most seven ids.
DiscreteGlobalGrids.Engine.HexChildWalk Type
HexChildWalk(slot, next)Which neighbour of the ring is being read, and which of its children comes next.
sourceDiscreteGlobalGrids.Engine.HexArcHaloEngine Type
HexArcHaloEngine(system, grid, root, rootlevel, target, connectivity, ring)target > rootlevel + 1: the system's own border automaton seeded with each neighbour's calibrated arc, walked to target, every leaf native-checked before it is yielded. The ring is in descendant-range order and the blocks are disjoint, so concatenating the neighbours' streams is already the canonical merge.
Memory is O(depth): one seeded engine and frame stack plus the fixed ring. Base.IteratorSize is SizeUnknown() and length is not defined. The formula used by sizehint has not been derived for every seeded transition and therefore is not an exact-length contract.
DiscreteGlobalGrids.Engine.HexArcWalk Type
HexArcWalk(slot, arc, state)The walk state: which neighbour of the ring is being descended, that neighbour's seeded automaton, and the automaton's own frame stack. All three are isbits, and the engine is rebuilt rather than stored per slot, so resuming needs nothing that was not returned.
sourceDiscreteGlobalGrids.Engine.HexNeighbour Type
HexNeighbour(cell, lo, arclen, start)One of root's same-level neighbours, with the arc (arclen, start) calibrated to face root and lo = first(descendant_range(sys, cell, target)), the key the ring is kept sorted by. arclen == 0 marks an uncalibrated entry, which only the depth-one engine holds.
DiscreteGlobalGrids.Engine._hex_calibrate Function
_hex_calibrate(sys, grid1, root, rootlevel, nb, connectivity) -> (arclen, start)The arc of nb that faces root, derived by asking which of nb's children are halo cells of root's subtree one level down, or (0, 0) if any of the guards fails.
Measured over 52,182 (root, neighbour) pairs on both systems, root levels 0-11: the number of touching children is ALWAYS exactly two, the minimal covering arc is always unique, and its length is 2 in 98.6% of cases and 3 in the remaining 1.4% — never 1, never 4 or more. The arc-3 case is fully characterised: nb is a pentagon and its deleted direction lies strictly between the two touching children. Nothing else predicts it, which is the other reason this is measured per call rather than looked up.
So none of the returns below was observed to fire. That is what a guard on a structural claim should look like — it is here because the claim is evidence and not yet a theorem, and a system whose one-ring changed would meet it rather than meeting a wrong answer.
sourceDiscreteGlobalGrids.Engine._hex_validate Function
_hex_validate(sys, root, rootlevel, ring, connectivity) -> BoolReturn whether every depth-two halo cell under each neighbour occurs in that neighbour's calibrated walk. hex_halo_engine runs this bounded validation for depths of at least three. Both sequences are ascending, so containment uses a two-pointer merge without allocation.
DiscreteGlobalGrids.Engine._minimal_arc Function
_minimal_arc(p, q) -> (arclen, start)The shortest arc of the six-direction ring containing both p and q, or (0, 0) when there is not exactly one such arc or its length is not 2 or 3.
The scan is the definition rather than the closed form (arclen is the ring distance plus one, taken the short way round) so that the UNIQUENESS question is answered by counting, not argued: two directions exactly opposite each other admit two four-arcs and no shorter one, and this returns (0, 0) there instead of picking one. Thirty-six iterations of integer work, once per neighbour.
Adjacency providers
The traversal chooses candidate cells; an adjacency provider tests whether they touch the subject. The geometry provider gives an independent check of results from the topology-based provider.
DiscreteGlobalGrids.Engine.IndexedNeighbors Type
IndexedNeighbors()Adjacency by the system's native one-ring: x touches the subtree when one of its neighbours has root as its ancestor. O(degree · depth) per candidate and allocation-free wherever neighbors is.
DiscreteGlobalGrids.Engine.ForcedGeometry Type
ForcedGeometry()Adjacency by unit-sphere boundary comparison: x touches the subtree when its boundary shares a vertex (Vertex) or two (Edge) with the boundary of some target-level descendant of root.
Descendants are visited through a second pruned hierarchy walk using O(depth) memory. This provider is independent of IndexedNeighbors's index arithmetic and can validate specialized engines.
Comparison is against target-level descendant boundaries, not root's own polygon: H3, IGeo7 and A5 descendants can overhang their parent.
DiscreteGlobalGrids.Engine.SubsetMembership Type
SubsetMembership(subset, complete)Adjacency to a SUBSET rather than to a subtree: x is a halo cell when the subset does not hold it and does hold one of its neighbours,
localindex(subset, x) === nothing &&
any(nb -> localindex(subset, nb) !== nothing,
neighbors(complete, x, 1; connectivity))This predicate tests both non-membership and contact because an arbitrary subset has no root ancestor or descendant range. Consequently, an absent interior cell is emitted when it touches a member.
complete is levelgrid(system, level), because subset adjacency is clipped to membership. Membership costs O(log(number of windows)) for CellVector and O(log(number of cells)) for PartialGrid.
The border automata the halo walks borrow
DiscreteGlobalGrids.Fallbacks.SquareBorderEngine Type
SquareBorderEngine(curve, base, level, side, orientation)The perimeter of the side x side block whose first cell has raw index base, in ascending id. 4·side - 4 cells for side > 1, O(depth) memory, O(border) time.
Yields LevelIndex because the traversal constructs each dense id as base plus its curve offset. Systems using another id type require a different engine or a cell-construction parameter.
DiscreteGlobalGrids.Fallbacks.SquareInteriorEngine Type
SquareInteriorEngine(curve, base, level, side, orientation)The block's interior, as the disjoint union of the sub-squares the border walk prunes: each is emitted as its contiguous run of ids, so no border membership is ever tested or stored. (side - 2)^2 cells, O(depth) memory.
DiscreteGlobalGrids.Fallbacks.ScanBorderEngine Type
ScanBorderEngine(sys, grid, root, rootlevel, first, last, connectivity)Walk the subtree's index range and keep the cells with a neighbour outside it. O(subtree · degree) time, O(1) memory, and lazy — the border is never collected. Requires has_sorted_subtrees.
DiscreteGlobalGrids.Fallbacks.MortonCurve Type
MortonCurve()Z-order: curve position p's low bit is the x half and its high bit the y half, at every level and in every orientation.
DiscreteGlobalGrids.Fallbacks.quadrant_step Function
quadrant_step(curve, orientation, p) -> (i, j, child_orientation)Which half of its parent square in x (i) and y (j) the sub-square at curve position p is, and the orientation state its own children are read under. Orientation is inert for MortonCurve; S2's Hilbert curve advances it.
Dispatches on the curve used by SquareBorderEngine. A system supplies a curve type and a method for its quadrant transition.
DiscreteGlobalGrids.face_orientation Function
lattice_decode(sys, c) -> (ix, iy, face)
lattice_cell(sys, level::Int, ix, iy, face) -> cell
face_orientation(sys, face) -> UInt8Define the face-lattice operations used by the shared square halo traversal. Only systems with an aligned square lattice per face implement these methods.
lattice_decode and lattice_cell convert between cell ids and face-local coordinates, with face 0-based and (ix, iy) in 0:2^level - 1. face_orientation is the curve state a face's root uses before consuming position bits.
The traversal derives seam rectangles by decoding neighbours of border cells.
SquareBandEngine also requires these invariants:
cellindextype(sys) === LevelIndex. The engine emitsLevelIndexand declares it as itseltype, unconditionally.Ids follow
face * faceside^2 + curvecode, with 0-based face and curve code. The emit step constructs ids with this arithmetic.Interior face adjacency is the 3×3 lattice, so an in-face band requires no additional adjacency check.
A fourth square system holding all three subtypes AbstractQuadFaceGridSystem and writes only the three methods above. One that does not writes its own halo_engine instead.
DiscreteGlobalGrids.Fallbacks.cells_cap Function
cells_cap(grid, ids) -> SphericalCapBound a batch of cell boundaries. Return the full sphere after UNION_CAP_BATCH_LIMIT cells.
The result bounds the geometry of the listed cells only. It covers neither their descendants nor any cap derived from them, so it is not a node_extent for any cell whose subtree reaches below grid's level.