API Reference

DEFAULTNEARGAPBOXES

Default admissibility margin for isneargap, measured in units of the smaller box's halfsize.

The value 1.0 is the midpoint between touching boxes and the next non-neighbour on a common grid: those gaps are 0 and 2h, so every threshold in (0, 2h) preserves the usual 3^d near neighbourhood. The midpoint also gives independently built block-tree sides a real separation buffer without placing the boundary on a common-grid lattice value. additionalbufferboxes adds more half-sizes on top.

NEARGAPRELTOL

Relative tolerance for the box-gap near predicate.

This is only the numerical slack around the admissibility margin. The margin itself is DEFAULTNEARGAPBOXES.

AbstractAggregationPlan <: AbstractPlan

Supertype for upward traversal plans.

Aggregation plans visit nodes from fine to coarse levels. Concrete plans may either only aggregate stored moments or aggregate and translate in one pass.

AbstractDisaggregationPlan <: AbstractPlan

Supertype for downward traversal plans.

Disaggregation plans visit nodes from coarse to fine levels. Concrete plans may either only disaggregate stored moments or disaggregate and translate in one pass.

AbstractLatticeSymmetryGroup

Supertype for the symmetry policies accepted by symmetrygroup.

AbstractPlan

Common supertype for traversal plans.

Plans store tree nodes grouped by level and define the order in which a matrix factorization traversal visits those nodes.

AbstractPlanFamily

Marker supertype for the plan family stored in a PlanSet.

AbstractTranslationTrait

Supertype for translation-direction storage traits.

Translation traits control how translations deduplicates scheduled translation vectors before downstream translation operators are built.

AbstractTreeTrait

Supertype for tree-dispatch tags.

Algorithms that depend on tree geometry dispatch on these tags instead of on concrete tree types. New tree types can participate by defining treetrait.

AdmissibilityFinding

One problem reported by checkadmissibility.

severity is :error for a plan that contradicts its own isnear predicate or references nodes that cannot be resolved, and :warning for a plan that is internally consistent but contains geometrically marginal far pairs.

kind is one of :nearpairtranslated, :marginalgap, :wronglevel, :unknownnode, :coveragegap, :coverageduplicate.

Gap fields are missing for findings that are not about geometry.

AdmissibilityReport

Result of checkadmissibility. ok is true when no :error finding was produced. :warning findings do not clear it.

Inspect findings directly, or let show summarise it.

AggregateAllNodesFunctor()

Predicate that marks every node as an aggregation node.

AggregateMode <: FarMulMode

Far-field traversal mode using AggregatePlan with DisaggregateTranslatePlan.

AggregateOnlyRootFunctor(tree)

Predicate that marks only root(tree) as an aggregation node.

AggregatePlan

Upward traversal plan for one tree.

The plan stores aggregation nodes grouped by level, ordered from leaves toward the root. storenode marks the nodes whose moments must persist after aggregation for later translation. The matching downward translation plan is DisaggregateTranslatePlan.

AggregatePlan(tree, aggregatenode)

Build an AggregatePlan from aggregatenode(node).

A node is stored when aggregatenode(node) is true. Non-stored nodes are still visited when they lie below a stored ancestor, so all required upward paths are included.

Block trees are not supported by this constructor; specify the aggregation tree explicitly in a non-block-tree context.

AggregateTranslateBuild <: TranslatePlanBuildKind

Build-kind marker for AggregateTranslatePlan.

AggregateTranslateMode <: FarMulMode

Far-field traversal mode using AggregateTranslatePlan with DisaggregatePlan.

AggregateTranslatePlan

Upward traversal plan for translating/source moments.

The plan records which aggregation nodes must produce moments for far-field translation and groups them by receiving node and level. The matching downward non-translating plan is DisaggregatePlan.

AggregateTranslatePlan(tree, TranslatingNodesIterator)
AggregateTranslatePlan(testtree, trialtree, TranslatingNodesIterator)

Build an AggregateTranslatePlan from a translating-node iterator.

For a single tree, TranslatingNodesIterator(node) yields the receiving nodes that receive translated information from node.

For two trees, the plan is built on the first tree, while receiving nodes are selected from the second. Block trees must be unwrapped explicitly with this two-tree form.

AllTranslations <: AbstractTranslationTrait

Store one translation direction for every scheduled pair.

Use this when no direction reuse is available or when exact pair identity matters.

AutoMinLevel()

Sentinel requesting that a tree constructor choose its default minimum level.

AutoProtrusionCheck()

Sentinel requesting the default protrusion policy for the input type.

Plain point collections resolve to NoProtrusionCheck. Extensions can provide input-specific defaults, such as BEAST basis-function protrusions.

AxisPreservingSymmetry{A} <: AbstractLatticeSymmetryGroup

The symmetries that keep axis A on itself, possibly flipped, and let the other axes permute and change sign freely. (D-1)! * 2^D elements: 16 of the 48 in 3-D when A = 3.

BEASTProtrusionFunctor(space)

Protrusion evaluator backed by a BEAST space.

Concrete call methods for this type are provided by the H2BEASTTrees extension, which can evaluate basis-function support against candidate tree boxes.

BlockTree{T}

Container holding a pair of trees used as test and trial clusters.

BlockTree is the tree shape used for Petrov-Galerkin plans: the test and trial sides are built separately but adjusted to a compatible level scale.

BlockTree(testpositions, trialpositions; builder::BlockTreeBuilder=BlockTreeBuilder())

Construct a BlockTree from separate test and trial positions.

Prefer the canonical buildtree entry point; this method is the builder-backed constructor it forwards to. Side-specific protrusion defaults are resolved before the two inner TwoNTrees are built.

BlockTreeBuilder(; test=TwoNTreeBuilder(), trial=TwoNTreeBuilder())

Construction settings for a BlockTree.

test and trial are TwoNTreeBuilders. Their minhalfsize and root values must match so both sides use compatible level indexing.

BoundingBallData(values, center, radius, level)

Node payload for BoundingBallTree-style ball trees.

BoundingBallTree{N,D,T} <: H2ClusterTree

Cluster tree whose nodes are bounded by balls.

N is the ambient dimension, D is the node-data type, and T is the radius type. The cached TreeIndex is stored in a Ref so rebuildtreeindex! can replace it after topology-changing operations.

BoundingBallTree(points::AbstractVector{SVector{N,T}}; builder::BoundingBallTreeBuilder)

Construct a BoundingBallTree from points.

Points are recursively split with builder.splitter until the builder's stopping criteria are met. Prefer the canonical buildtree entry point; this method is what it forwards to.

BoundingBallTree(center, radius; minlevel=1, root=1, balldata=BoundingBallData)

Construct a one-node bounding-ball tree.

BoundingBallTree(nodes, root, center, radius, nodesatlevel)

Construct a BoundingBallTree from already materialized nodes and level storage, then rebuild the cached tree index.

BoundingBallTreeBuilder(; splitter, numsplits, minvalues=numsplits,
    minlevel=AutoMinLevel(), maxlevel=typemax(Int), root=1,
    balldata=BoundingBallData, updateradii=boundingsphere,
    splitterkwargs=NamedTuple())

Construction settings for BoundingBallTree. splitter is called via splitwrapper(points, values, level, numsplits, splitter; splitterkwargs...). For compatibility with existing custom ball splitters, the wrapper also accepts splitters that ignore level and implement (points, values, numsplits). updateradii computes the bounding ball for each node.

BoxData(sector, values, center, halfsize, level)

Node payload for TwoNTree-style box trees.

ChildIterator(tree, node)

Iterate over the direct children of node.

ComputeProtrusionFunctor

Default protrusion evaluator.

The center/halfsize call form represents relative protrusion normalized by 2 * halfsize of a box. The base implementation returns zero and is intended as a lightweight fallback and extension point.

(f::ComputeProtrusionFunctor)(center, halfsize, value)

Return the normalized protrusion of value relative to a candidate box.

The default implementation returns zero.

DepthFirstIterator(tree, node=root(tree))

Iterate over node and all of its descendants in depth-first order.

DirectionInvariance <: AbstractTranslationTrait

Share equal translation directions across all relevant levels.

For generic trees, equality is approximate. For TwoNTrees, directions are keyed by integer offsets on the finest common grid, allowing reuse across levels.

DirectionInvariancePerLevel <: AbstractTranslationTrait

Share equal translation directions within each level.

For generic trees, directions are deduplicated with approximate comparison. For TwoNTrees, the specialized translation path uses integer grid offsets, so directions on the same level are keyed exactly.

DisaggregatePlan

Downward traversal plan for already-translated moments.

The plan stores disaggregation nodes grouped by level, ordered from root toward the leaves. It is paired with AggregateTranslatePlan, which produces the translated moments this plan propagates.

DisaggregatePlan(tree, disaggregatenode)

Build a DisaggregatePlan from disaggregatenode(node).

disaggregatenode marks nodes that store moments directly; nodes below a marked ancestor are included in the disaggregation traversal even when they do not store directly.

This constructor is defined for non-BlockTree trees. For block trees, select the corresponding test or trial tree first.

DisaggregateTranslateBuild <: TranslatePlanBuildKind

Build-kind marker for DisaggregateTranslatePlan.

DisaggregateTranslatePlan

Downward traversal plan for receiving translated moments.

The plan records which receiving nodes collect far-field translations and which source nodes translate to them. It is paired with AggregatePlan, which produces the source moments.

DisaggregateTranslatePlan(tree, TranslatingNodesIterator)
DisaggregateTranslatePlan(testtree, trialtree, TranslatingNodesIterator)

Build a DisaggregateTranslatePlan from a translating-node iterator.

For a single tree, TranslatingNodesIterator(node) yields source nodes in tree that translate to node.

For two trees, the plan is built on the first tree, while source nodes are selected from the second. Block trees must be unwrapped explicitly with this two-tree form.

FarMulMode

Abstract supertype for far-field multiplication traversal modes.

Forest{N,T}

Fixed-size container for multiple trees.

The trees are stored in an SVector, so a forest has a statically known length and supports ordinary indexing and iteration.

FullLatticeSymmetry <: AbstractLatticeSymmetryGroup

All D! * 2^D symmetries.

Only use this if the representation is closed under every rotation and reflection of the cube.

GalerkinPlanFamily <: AbstractPlanFamily

Plan-family marker for single-tree Galerkin plans.

H2ClusterTree

Abstract supertype for concrete cluster-tree implementations.

tree(node)

Return the node object stored at global node id node.

IsNotTranslatingPlan <: AbstractPlanTranslationTrait

Trait for plans that only store traversal nodes.

IsTranslatingPlan <: AbstractPlanTranslationTrait

Trait for plans that also carry translating-node data.

KMeansSplitWrapper()

Split-wrapper adapter used by KMeansTree's underlying BoundingBallTree construction.

(wrapper::KMeansSplitWrapper)(points, globalpointids, level, numsplits; kwargs...)

Call kmeanswrapper for the selected point ids.

level is accepted to match the generic bounding-ball split-wrapper protocol; the K-means splitter itself does not use it.

KMeansTreeBuilder(; numberofclusters=4, minvalues=70,
    minlevel=AutoMinLevel(), root=1, balldata=BoundingBallData,
    updateradii=boundingsphere, splitterkwargs=(; rng=Random.MersenneTwister(1234)))

Construction settings for KMeansTree.

splitterkwargs defaults to a seeded rng, so KMeansTree(points) is deterministic unless the caller passes different k-means options.

LatticeSymmetry{D}

One symmetry of the cubic lattice: a permutation of the axes, each optionally flipped in sign.

permutation[i] says which axis the i-th output component comes from, and signs[i] whether it is negated:

(S q)[i] = signs[i] * q[permutation[i]]

That is applysymmetry. There are D! * 2^D such symmetries: 8 in 2-D, 48 in 3-D.

These maps preserve dot products, which is what lets one translation serve several offsets. If a translation operator depends on direction only through k̂ ⋅ d, then (S k̂) ⋅ (S d) == k̂ ⋅ d, and so T(k̂, S d) == T(S⁻¹ k̂, d).

MetisForestBuilder(; treebuilder=MetisTreeBuilder())

Construction settings for MetisForest. treebuilder is the MetisTreeBuilder used for each connected component.

MetisSplitWrapper(graph, pointgraphweights, splitunconnectedpartitions)

Split-wrapper state used by MetisTree's underlying BoundingBallTree construction.

(wrapper::MetisSplitWrapper)(points, globalpointids, level, numsplits; kwargs...)

Partition the subgraph induced by globalpointids.

level is accepted to match the generic bounding-ball split-wrapper protocol; the METIS splitter itself does not use it.

MetisTreeBuilder(; numdivisions=4, splitunconnectedpartitions=false,
    minvalues=numdivisions, minlevel=AutoMinLevel(),
    maxlevel=typemax(Int), root=1, balldata=BoundingBallData,
    updateradii=boundingsphere)

Construction settings for MetisTree.

numdivisions controls the requested METIS split count at each partitioning step. splitunconnectedpartitions=true post-processes disconnected METIS parts into connected components.

NearListCache

Per-node near-node lists, indexed by node id, used as the candidate set for near iteration.

Built by nearlistcache. Each entry is a superset of the node's true near nodes, so the consuming predicate must still be applied; see the discussion in nearlists.jl.

NoProtrusionCheck()

Disable protrusion-based subdivision checks.

NoSymmetry <: AbstractLatticeSymmetryGroup

The one-element group. Every offset is its own representative, so this gives the same result as plain direction deduplication.

Node(data, nextsibling, parent, firstchild)

Topology record stored by cluster trees.

NodeInformation(info)

Typed wrapper for a child-iterator state, including nothing.

NonLatticeTranslationError <: Exception

Thrown when SymmetryDirectionInvariancePerLevel meets a displacement that is not a lattice vector, which is the one configuration where a lattice symmetry cannot be applied.

A DISTINCT TYPE rather than a plain error, because consumers are expected to CATCH this specifically and fall back to DirectionInvariancePerLevel (MLFMA does). A broad catch around a collection construction would swallow method errors, out-of-memory and typos as "not lattice aligned" and silently produce an unreduced collection with no indication why, which is the failure mode this check exists to prevent.

PARAMETERIZED ON THE TREE'S OWN COORDINATE TYPE, not fixed to Float64. The fields were Vector{Float64}/Float64, which did NOT break the catchable-type contract, because Julia's default constructor converts, so a Float32, BigFloat or Rational tree still produced a genuine, catchable NonLatticeTranslationError. What it broke was the MESSAGE: a Float32 tree's halfsize of 0.8f0 was widened and printed as 0.800000011920929, showing the reader the binary expansion of a number their input never contained. BigFloat lost precision outright, and a coordinate type not convertible to Float64 at all would have raised a conversion error in place of this one.

OppositeSymmetry <: AbstractLatticeSymmetryGroup

The two-element group {identity, -identity}, treating q and -q as the same offset.

The weakest useful choice, and the safest: it asks only that the angular sampling be closed under k̂ -> -k̂.

ParentUpwardsIterator(tree, node)

Iterate from parent(tree, node) upward until the root has been reached.

PetrovAggregationFunctor(aggregatenode, blocktree, notnodetree, nodetree)

Adapt a block-tree aggregation predicate to the one-tree AggregatePlan API.

nodetree is the tree being aggregated; notnodetree is the opposite side of the Petrov block tree and is passed through so the predicate can evaluate test/trial geometry together.

PetrovDisaggregationFunctor(translatingnodesiterator, blocktree, notnodetree)

Adapt a block-tree translating-node iterator to the one-tree disaggregation plan API.

The concrete disaggregation tree is supplied at call time; notnodetree is the opposite side used to find translating nodes.

PetrovPlanFamily <: AbstractPlanFamily

Plan-family marker for two-tree Petrov-Galerkin plans.

PlanBuilder(; aggregationmode=AggregateMode(), isnear=H2Trees.isnear(),
    translatingnodesiterator=WellSeparatedIterator(; isnear=isnear),
    aggregatenode=istranslatingnode(; TranslatingNodesIterator=translatingnodesiterator),
    checkadmissibility=false)

Construction settings for buildplans.

translatingnodesiterator and aggregatenode both default from isnear, so overriding isnear alone (rather than reconstructing all three by hand) keeps them consistent. Passing an explicit translatingnodesiterator/aggregatenode overrides the chained default, e.g. to decouple the near/far classification used for translation from the one used elsewhere.

PlanSet(; trialaggregationplan, testdisaggregationplan, testaggregationplan,
    trialdisaggregationplan, relevantlevels, tree, mintranslationlevel=nothing,
    family)

Concrete container returned by buildplans.

PlanSet behaves like the named tuple used by the older API: it supports iteration, keys, values, pairs, symbol indexing, NamedTuple(plans), and merge. Prefer the accessor functions when writing new code.

ProtrusionCheck(; max, compute=ComputeProtrusionFunctor())

Subdivision policy that rejects a split when any value protrudes beyond max relative to a child box.

compute is called as compute(center, halfsize, value).

SimpleHybridTree{T} <: H2ClusterTree

A cluster tree that divides into upper and lower tree regions at a hybrid level.

The upper tree spans from the minimum level to hybridlevel, while the lower tree spans from hybridlevel+1 to the maximum level. This structure enables efficient hybrid algorithms that treat different tree regions differently.

Fields

• tree::T: The underlying cluster tree.
• hybridlevel::Int: The level that separates the upper and lower tree regions.

SimpleHybridTree(tree::TwoNTree; builder::SimpleHybridTreeBuilder)

Construct a SimpleHybridTree for a TwoNTree using a typed builder. Prefer the canonical buildtree entry point; this method is what it forwards to.

The hybrid level is determined by finding the first level whose halfsize is less than or equal to builder.hybridhalfsize. An error is raised if the hybrid halfsize is smaller than the minimum halfsize in the tree or if any leaf is below the computed hybrid level.

SimpleHybridTreeBuilder(; hybridhalfsize)

Construction settings for SimpleHybridTree.

hybridhalfsize selects the level at which the tree switches from the original tree representation to the hybrid wrapper.

StackElement(childreniterator, information)

Stack frame used by DepthFirstIterator.

StoreNoNodeFunctor(plan)

Callable predicate that never stores a node.

StoreNodeFunctor(plan)

Callable wrapper around storenode(plan, node).

SymmetryDirectionInvariancePerLevel(policy) <: AbstractTranslationTrait

Share translation directions related by a lattice SYMMETRY, within each level.

Where DirectionInvariancePerLevel shares a direction only between pairs whose integer offsets are equal, this shares one between every pair whose offsets lie in the same orbit of policy. The stored direction is the orbit's canonical representative and each interaction additionally records a symmetry ID, so the consumer can recover its own direction; see canonicalizetranslation for the reachability contract and the direction convention.

policy MUST be the subgroup the consumer can act with, not the largest one the lattice admits. A representative found by minimizing over a larger group is in general unreachable from the actual offset by any element of a smaller one, and the mismatch is silent on offsets that happen to be aligned. The default is OppositeSymmetry, which asks only that the consumer's representation be closed under the antipodal map.

Interactions carry a fourth field, symmetryID, that the other traits do not produce.

SymmetryGroup{D,P}

A policy's symmetries in D dimensions, plus the lookup table canonicalization needs.

elements[1] is the identity and the order is reproducible, so an index into elements is a stable symmetry ID, small enough to store once per interaction (a UInt8 is always enough). inverseindex[k] is where inversesymmetry(elements[k]) sits. It always exists, because a policy names a subgroup and subgroups are closed under inversion.

Build one with symmetrygroup.

TranslatePlanBuildKind

Internal strategy marker for the shared translating-plan builder.

_buildtranslateplan owns the traversal used by both AggregateTranslatePlan and DisaggregateTranslatePlan. Each build kind supplies only the plan-specific hooks: level storage order, dictionary recording, node-flag construction, empty-plan policy, and final materialization.

TreeIndex

Cached topology views for a tree.

TreeIndex stores nodes grouped by level, depth-first order, leaves, and the minimum/maximum levels. rebuildtreeindex! replaces the whole cached value in the tree's Ref, so callers never observe a half-updated index. The vectors inside the index are ordinary mutable arrays; treat them as read-only.

TreeIndex(tree)

Compute cached topology views for tree.

TwoNTree{N,D,T} <: H2ClusterTree

Cluster tree whose nodes are bounded by axis-aligned boxes.

N is the ambient dimension, D is the node-data type, and T is the coordinate/halfsize type. The cached TreeIndex is stored in a Ref so rebuildtreeindex! can replace it after topology-changing operations.

TwoNTree(positions; builder::TwoNTreeBuilder=TwoNTreeBuilder())

Construct a TwoNTree from positions.

Prefer the canonical buildtree entry point; this method is the builder-backed constructor it forwards to.

TwoNTree(nodes, root, center, halfsize, nodesatlevel)

Construct a TwoNTree from already materialized nodes and level storage, then rebuild the cached tree index.

TwoNTree(center, points, halfsize, minhalfsize; kwargs...)

Build a TwoNTree directly from root geometry and point positions.

Most callers should use buildtree or TwoNTree(positions; builder=...) instead; this method is the lower-level entry to bulkbuildtwontree.

TwoNTree(center, halfsize; minlevel=1, root=1, minvalues=0)

Construct a one-node TwoNTree.

TwoNTreeBuilder(; minhalfsize=0, minlevel=AutoMinLevel(), root=1, minvalues=70,
    protrusion=AutoProtrusionCheck())

Construction settings for TwoNTree.

The defaults build an adaptive tree driven mainly by minvalues: subdivision stops once a node holds at most minvalues values, unless minhalfsize, minlevel, or the protrusion policy impose a stronger constraint. AutoProtrusionCheck() lets the input type choose its default protrusion policy.

_CenterFunctor(tree)

Callable wrapper returning center(tree, node).

_CoverageIndex

Slot assignment for the coverage stamp: expected value v occupies slot v - offset.

isexpected is false for ids inside the span that no leaf actually stores, which is how a covered value that is not an expected value gets reported rather than silently accepted.

_HalfSizeFunctor(tree)

Callable wrapper returning halfsize(tree, node).

_LeafFunctor(tree)

Callable predicate returning isleaf(tree, node).

_LevelFunctor(tree)

Callable wrapper returning level(tree, node).

isAnyTree <: AbstractTreeTrait

Fallback trait used when code should exercise the most general tree path.

isBlockTree <: AbstractTreeTrait

Trait tag for a BlockTree, i.e. a test/trial tree pair.

isBoundingBallTree <: AbstractTreeTrait

Trait tag for ball-shaped trees, such as BoundingBallTree and KMeansTree.

isTwoNTree <: AbstractTreeTrait

Trait tag for box-shaped trees, such as TwoNTree.

eltype(tree::BlockTree)

Return the element type of the test-side tree.

eltype(tree::Union{BoundingBallTree,TwoNTree})

Return the static-vector coordinate type stored by tree geometry.

FarNodeIterator(testtree, trialtree, trialnode::Int; isfar=isfar)

Iterate over same-level nodes in testtree that are far from trialnode in trialtree.

FarNodeIterator(tree, node::Int; isfar=isfar)

Iterate over same-level nodes in tree that are far from node.

KMeansTree(points; builder=KMeansTreeBuilder())

Build a ball tree by recursively splitting point sets with K-means.

KMeansTree is implemented as a BoundingBallTree with a K-means-backed split wrapper. Load the H2ParallelKMeansTrees extension, or a package that activates it, so kmeanswrapper is available.

LevelIterator(tree, level::Int)

Return an iterator over nodes at level.

MetisForest(points, graph, weights; builder::MetisForestBuilder)

Construct a Forest of MetisTrees from the connected components of graph.

Each component is built as its own MetisTree, then leaf values are remapped from component-local indices back to the original global point ids. Prefer the canonical buildforest entry point.

MetisTree(points::AbstractVector{SVector{N,T}}, graph, pointgraphweights; builder::MetisTreeBuilder)

Construct a ball tree using METIS graph partitioning.

The tree is implemented as a BoundingBallTree whose split wrapper recursively partitions the induced subgraph of each node's point ids. Prefer the canonical buildtree entry point.

NearNodeIterator(testtree, trialtree, trialnode::Int; isnear=isnear)

Iterate over nodes in testtree near trialnode in trialtree.

Only nodes at level(trialtree, trialnode) are considered. The predicate is called as isnear(testtree, trialtree, candidate, trialnode).

NearNodeIterator(tree, node::Int; isnear=isnear, nearlists=nothing)

Iterate over same-level nodes in tree that are near node.

The predicate is called as isnear(tree, candidate, node).

nearlists optionally supplies a NearListCache to draw candidates from instead of scanning the level; see nearlistcache for when that is valid.

NodeFilterIterator(testtree, trialtree, trialnode::Int, filter)

Iterate over nodes in testtree at level(trialtree, trialnode).

The predicate is called as filter(testtree, trialtree, candidate, trialnode).

NodeFilterIterator(tree, node::Int, filter; nearlists=nothing)

Iterate over same-level nodes that pass filter.

For ordinary trees, candidates come from tree at level(tree, node) and the predicate is called as filter(tree, candidate, node). For block trees, node is interpreted as a trial-tree node and candidates come from the test tree.

Passing a NearListCache as nearlists narrows the candidate set to that node's cached near list instead of scanning the whole level. That is only correct when the cache contains every node filter could accept, such as near-type filters built by nearlistcache. It is never correct for a far filter.

SameLevelFilteredIterator(iteratedtree, anchortree, anchornode::Int, predicate)

Return nodes from iteratedtree at the same level as anchornode in anchortree for which predicate(iteratedtree, anchortree, iteratednode, anchornode) is true.

SameLevelIterator(tree, node::Int)

Return an iterator over nodes at the same level as node.

TranslatingNodesIterator

This is a wrapper for the `WellSeparatedIterator`.

WellSeparatedIterator(testtree, trialtree, trialnode::Int; iswellseparated=iswellseparated)

Constructs an iterator to identify which translations should occur and which should not. This determination is based on the concept of well-separated nodes. Two nodes are considered well-separated if their parents are near each other and the nodes themselves are far apart. This assumes that child clusters are completely inside their parent clusters.

Arguments

• testtree: the test tree
• trialtree: the trial tree
• trialnode: the node in the trial tree for which the translations happen
• iswellseparated: a function that returns true if two nodes are well-separated and false otherwise

Returns

An iterator that yields the nodes in the testtree that are well-separated from the specified trialnode in the trialtree.

WellSeparatedIterator(tree, node::Int; iswellseparated=iswellseparated)

Constructs an iterator to identify which translations should occur and which should not. This determination is based on the concept of well-separated nodes. Two nodes are considered well-separated if their parents are near each other and the nodes themselves are far apart. This assumes that child clusters are completely inside their parent clusters.

Arguments

• tree: the tree in which the translations occur
• node: the node for which the translations happen
• iswellseparated: a function that returns true if two nodes are well-separated and false otherwise

Returns

An iterator that yields the nodes that are well-separated from the specified node in the tree.

WellSeparatedIterator(; isnear=nothing, iswellseparated=nothing)

Constructs a functor that returns a WellSeparatedIterator if provided a tree. Two nodes are considered well-separated if their parents are near each other and the nodes themselves are far apart.

Arguments

• isnear: a function that takes a tree as input and returns another function. This returned function is then used to evaluate the isnear criterion.
• iswellseparated: a function that takes a tree as input and returns another function. This returned function is then used to evaluate the iswellseparated criterion.

Returns

A callable builder that returns a WellSeparatedIterator if provided with a tree.

Throws

• ArgumentError: if both isnear and iswellseparated are provided, or if neither is provided.

_allvalues(tree)

Return all stored values in the leaves of tree, sorted for coverage comparison.

_anyprotrudes(points, ids, center, halfsize, maxprotrusion, computeprotrusion)

Return whether any point id protrudes beyond the accepted protrusion threshold.

_appendchildrenofnearparents!(buffer, tree, node, nearlists, rootoffset)

Fill buffer with the children of every near neighbour of node's parent and return it.

This is the candidate superset of node's well-separated nodes; buffer is reused across nodes, so the result is only valid until the next call.

_appendnearvalues!(out, tree, receivingtree, translatingtree, leaf, nearpred, trait,
                   nearlists)

Append all near-field values for one receiving leaf.

For block trees, values are collected from the opposite side of the block tree.

_blocktwontree(testpositions, trialpositions, builder::BlockTreeBuilder)

Build a BlockTree of two TwoNTrees.

Each side is built with compatible root sizes and minimum levels so both trees can be used together in block-tree traversals.

_bucketbysector(points, ids, center, halfsize, nsectors)

Group point ids by their child sector relative to center and halfsize.

Only assigned buckets are initialized. Callers reconstruct child centers from the sector id when needed.

_buildgalerkinplans(tree, aggregatenode, translatingnodesiterator, aggregationmode)

Construct the four Galerkin plans for tree: trialaggregationplan, testdisaggregationplan, testaggregationplan, and trialdisaggregationplan.

The returned PlanSet also contains relevantlevels, defined from the minimum level at which aggregation and disaggregation are both meaningful up to the deepest level of tree. Use NamedTuple(plans) when raw named-tuple interoperability is required.

Internal: reached only through buildplans.

Assumptions:

• Aggregation and disaggregation are built on the same tree (tree is not a BlockTree).

_buildpetrovplans(tree, aggregatenode, translatingnodesiterator, aggregationmode)

Construct the four Petrov-Galerkin plans for a block tree tree: testaggregationplan, trialaggregationplan, testdisaggregationplan, and trialdisaggregationplan.

The returned PlanSet also contains:

• relevantlevels: levels where all generated plans are simultaneously relevant.
• mintranslationlevel: first level where translations appear in both test and trial disaggregation plans.

Use NamedTuple(plans) when raw named-tuple interoperability is required.

Internal: reached only through buildplans.

_buildtranslateplan(kind::TranslatePlanBuildKind, tree, TranslatingNodesIterator)

Shared construction algorithm for AggregateTranslatePlan (kind = AggregateTranslateBuild()) and DisaggregateTranslatePlan (kind = DisaggregateTranslateBuild()). Visits every tree level, marks a node for visiting if it (or an ancestor) has a nonempty TranslatingNodesIterator, and records the per-level translating/receiving pairs into a compacted, validated set of levels.

The builder preserves each concrete plan's storage convention: aggregation levels are stored from fine to coarse, while disaggregation levels are stored from coarse to fine.

_bulkbuildchildren!(nodes, points, buckets, parentcenter, nsectors, childhalfsize, ...)

Build all occupied children of one cell in ascending sector order.

Returns the global id of the first child, or 0 when no child was built.

Sibling order here is deliberately temporary. Node ids and sibling links produced by the recursive bulk build are construction details; _finishbulktwontree rewrites both into the final level-major, Hilbert-within-level layout before any TwoNTree/TreeIndex exists. Keeping Hilbert state out of this recursion leaves it a pure geometric partitioner.

_bulkbuildnode!(nodes, points, ids, center, halfsize, ...)

Append one bulk-built node and recursively build its descendants when the cell does not satisfy the stopping criteria.

_callsplitwrapper(splitwrapper, points, globalpointids, level, numsplits; kwargs...)

Call a bounding-ball split wrapper.

Split wrappers may accept either (points, values, level, numsplits; kwargs...) or the older (points, values, numsplits; kwargs...) shape.

_check_resolved_block_minlevel(requested, derived, side)

Validate an explicitly requested side minlevel after block-tree geometry has resolved the required value.

_checkleafcoverage!(findings, findinglock, got, tree, plan, nearpred, trait,
    maxfindings, receivingtree, translatingtree, planlevels, expected, leaf, nearlists,
    coverageindex, stamps, generation)

Check the coverage partition for one receiving leaf using got as reusable scratch storage.

_checknodelevel!(findings, findinglock, tree, node, planlevel, role, maxfindings)

Validate that node exists in tree and is filed under its actual level.

Returns false after recording a finding when geometric checks for that node should be skipped.

_checkplanadmissibility!(findings, findinglock, tree, plan, pred, trait,
    mingapboxes, maxfindings)

Check every translation pair scheduled by one translating plan.

Findings are appended for pairs filed at the wrong level, unresolved nodes, near pairs scheduled as far interactions, and far pairs whose geometric gap is below the configured margin.

_checkplancoverage!(findings, findinglock, tree, plan, nearpred, trait, maxfindings)

Check that near-field values plus plan-scheduled far-field values cover the translating side exactly once for every receiving leaf.

The far set is read from the plan, including translations scheduled on leaf ancestors, so omissions or duplicates in the assembled plan are detected directly.

_copyatlevel(data::BoundingBallData, level)

Copy node data while replacing its stored level.

_coverageindex(expected)

Build the stamp slots for expected (sorted), or nothing to keep the sorting path.

nothing is returned when the value ids span far more than they populate. The slot array is proportional to the span, so a sparse one would cost more than the sort it replaces. Also when expected contains a repeat, since then coverage is a multiset question that stamping cannot answer.

_finalnodeflags(kind, nodeflags, dicts, tree)

Return the node-flag vector stored by the materialized translating plan.

_findingsfull(findings, findinglock, maxfindings)

Return whether no more findings should be collected.

_finishbulktwontree(nodes, root, rootcenter, roothalfsize)

Materialize a bulk-built node vector as a TwoNTree, assigning final node ids first.

The bulk builder's ids and sibling links are temporary (ascending sector order, depth-first numbering). This is the one point where they become final: _hilbertlevelmajornodes rewrites both before the TwoNTree and TreeIndex exist. Nothing outside construction can observe the temporary ids.

Reordering lives here rather than in a TwoNTree(nodes, ...) constructor on purpose: a general constructor that silently permuted already-materialized nodes would invalidate node ids held by plans and other callers.

_firstduplicate(sortedvalues)

Return the first duplicated value in sorted storage, or nothing when all values are unique.

_galerkinplans(tree, aggregatenode, translatingnodesiterator, ::AggregateMode)

Build the forward Galerkin plan pair for aggregate-then-translate mode.

The upward side is an AggregatePlan; far-field translations are stored on the downward DisaggregateTranslatePlan.

_galerkinplans(tree, aggregatenode, translatingnodesiterator, ::AggregateTranslateMode)

Build the forward Galerkin plan pair for aggregate-translate mode.

The upward side is an AggregateTranslatePlan; the matching downward side is a non-translating DisaggregatePlan.

_hilbertlevelmajornodes(nodes, root, ::Val{N})

Return a new node vector renumbered level-major with Hilbert order inside each level.

Walks the temporary topology depth-first with children visited in Hilbert order, propagating the orientation state from the root via HilbertOrdering. A preorder walk in Hilbert child order visits each level's nodes in exactly that level's Hilbert order: a node's Hilbert index is (parent index) * 2^N + (position within parent), so grouping by ancestor in ancestor order and ordering within a group by position is Hilbert order, so bucketing nodes by level during the walk needs no sorting or per-node Hilbert keys.

Sibling links are rebuilt too, not just permuted: firstchild/nextsibling define the child traversal order that children exposes, so they must follow the Hilbert order the ids do.

The walk is iterative rather than recursive so this adds no stack-depth limit of its own beyond the one the recursive builder already imposes. Runs in O(length(nodes)); all scratch storage is released when construction finishes, and no Hilbert state is stored on the returned nodes.

The returned vector is allocated at exactly length(nodes), which also drops the oversized backing buffer the bulk builder's sizehint! leaves behind (that hint is a loose upper bound on the node count, so a finished tree could otherwise retain several megabytes of unused capacity for its whole lifetime.

_inverttranslatingdict(rnodes)

Invert a per-level translating-node dictionary.

The input maps receivingnode => translatingnodes; the result maps each forward translating node to the forward receiving nodes that depend on it. Level order is reversed because adjoint traversal runs in the opposite direction.

_levelstats(tree, level, trait)

Return the per-level values printed in the detailed tree summary.

_nearcandidates(nearlists, tree, node)

The set of nodes a near filter for node should be applied to: every node at its level when nearlists is nothing, or the cached candidate list otherwise.

_nearlists(tree, isnear)

Return per-node near-node lists indexed by node - (root(tree) - 1), in ascending node order, or nothing when no near predicate can be recovered from isnear.

Same top-down sweep as _translatinglists, but retaining near lists for every level.

_nearpredicate(x)

Return the tree-bound near predicate underlying a translating-nodes iterator, or nothing when it cannot be recovered.

nothing is not a failure: it selects the original full-level scan in _buildtranslateplan, which is correct for any predicate. Only the standard well-separated iterators expose a near predicate whose level-monotonicity is established, so only those take the interaction-list path.

_petrovplans(blocktree, testtree, trialtree, aggregatenode,
    translatingnodesiterator, ::AggregateMode)

Build the forward Petrov plan pair for aggregate-then-translate mode.

The trial tree is aggregated with an AggregatePlan, and the test tree receives translations through a DisaggregateTranslatePlan.

_petrovplans(blocktree, testtree, trialtree, aggregatenode,
    translatingnodesiterator, ::AggregateTranslateMode)

Build the forward Petrov plan pair for aggregate-translate mode.

The trial tree aggregates and translates with an AggregateTranslatePlan; the test tree is then handled by a non-translating DisaggregatePlan.

_pushfinding!(findings, findinglock, finding, maxfindings)

Append finding unless the report has reached maxfindings.

Returns whether the finding was stored.

_raise(report)

Emit warnings and throw on errors according to an AdmissibilityReport.

_recordtranslatenode!(kind, leveldict, nodeflags, node, nodeindex, tfnodes)

Record one visited translating-plan node into the per-level dictionary and node flags for kind.

_sharedtranslatingflags(aggregatenode, translatingnodesiterator, lists)

Flags derived from lists when _sharesiterator permits it, otherwise nothing so the plan builder evaluates the caller's own aggregatenode predicate.

_sharesiterator(aggregatenode, translatingnodesiterator)

Return whether aggregatenode is istranslatingnode over exactly translatingnodesiterator, so that "does this node translate?" and the interaction lists answer the same question.

This must be checked, not assumed. aggregatenode is a free choice: aggregateallnodes stores every node and aggregaterootonly stores just the root, and substituting translating-flags for either silently builds the wrong aggregation plan. Only the default PlanBuilder wiring, which threads one iterator into both, may share.

_splitboundingballnode!(tree, points, node, numsplits, splitwrapper; kwargs...)

Recursively split one bounding-ball node and append its children to tree.

The split wrapper returns child value partitions, centers, and radii. Internal node values are cleared after their children are created, so stored values live on leaves.

_staticchunks(n, nchunks)

Split 1:n into contiguous, roughly even ranges.

Used by the coverage pass to give each spawned task its own scratch buffer without relying on Threads.@threads :static, which cannot be nested or run concurrently.

_symmetrytranslationinfo(receivingnode, translatingnode, translationID, symmetryID)

Create the metadata record stored by SymmetryDirectionInvariancePerLevel.

It carries a fourth field the other traits do not produce, rather than widening the common record: every existing consumer reads a three-field record, and adding a field they would ignore to all of them would change a type used across package boundaries for the benefit of one trait.

_tallycoverage!(got, expected, coverageindex, stamps, generation)

Return (duplicate, covered) for one leaf's gathered values.

duplicate is the smallest value covered more than once, or nothing. covered is the number of distinct expected values covered, or -1 when got holds a value that is not an expected value at all. -1 never equals length(expected), so the caller reports the same coverage gap the sorted comparison used to.

Falls back to sorting when coverageindex is nothing; the two paths agree by construction, including which duplicate they name.

_translatingflags(tree, storenode)

Return a Bool vector indexed by node - (root(tree) - 1), true where storenode(node) is, or nothing when the fast path does not apply.

istranslatingnode answers "does this node translate to anything?" by scanning the level until the first hit. Deriving the answer from interaction lists makes it a lookup. Prefer _translatingflagsfromlists when the lists are already at hand.

_translatingflagsfromlists(lists)

Derive the per-node "does this node translate?" flags from already-built interaction lists, so a caller building both plans of a pair does not sweep the tree twice. Propagates nothing.

_translatinglists(tree, TranslatingNodesIterator)

Return lists, a vector indexed by node - (root(tree) - 1) holding each node's translating nodes in ascending node order, or nothing when the fast path does not apply.

The per-node lists are exactly what collect(Int, TranslatingNodesIterator(node)) produces; only the candidate set the predicate is applied to differs. Returning nothing leaves the caller on its original path.

_translatingplans(plans)

Return the translating plans exposed by a plan set.

Both the forward pair and the adjoint pair are checked when present. The helper also validates that each pair contains exactly one translating plan.

_translationinfo(receivingnode, translatingnode, translationID)

Create the compact metadata record stored in translationinfos.

_translations(..., ::DirectionInvariance; offset=zero(ELTYPE))

Deduplicate TwoNTree translations by integer offsets from the minimum halfsize shared by all relevant levels.

_translations(..., ::SymmetryDirectionInvariancePerLevel; offset=zero(ELTYPE))

Deduplicate TwoNTree translations by their lattice displacement up to a symmetry orbit.

The key is the CANONICAL displacement rather than the displacement itself, and the symmetry mapping the canonical back to the actual is recorded per interaction, so q == applysymmetry(group[symmetryID], canonical) holds for every interaction.

Unlike DirectionInvariancePerLevel, this requires every displacement to be a lattice vector. See _symmetrylatticeindex! for why a block tree with arbitrarily offset roots is refused rather than silently reduced.

_translations(..., ::AllTranslations)

Materialize one translation direction per scheduled pair.

_translations(..., ::DirectionInvariancePerLevel)

Deduplicate equal translation vectors separately on each relevant level.

_translations(..., ::DirectionInvariance)

Deduplicate equal translation vectors across all relevant levels.

_uniformseparationdepth(points, indices, center, halfsize, cutoff::Int=1)

Number of bisection levels needed until each cell holds at most cutoff points.

This uses the same sector rule as TwoNTree without building a tree. cutoff is the caller's minvalues, floored at 1.

Coincident points

Coincident points cannot be separated by bisection: they stay in the same sector at every level.

This throws ArgumentError when that would prevent termination, i.e. when a cell still holds more than cutoff points after halfsize has reached 0.0. It is NOT a general duplicate check: with cutoff > 1, coincident points that fit inside one <= cutoff cell simply stop the recursion normally and are never noticed. Duplicate input points are not permitted and are not validated; see bulkbuildtwontree.

_updatechild!(tree, node, child)

Set child as the first child of node.

_updatenextsibling!(tree, node, sibling)

Set sibling as the next sibling of node.

_updatevalues!(tree, localtoglobal)

Remap leaf values from component-local indices to global point ids.

Used after constructing one component of a MetisForest.

_validateprotrusion(protrusion)

Validate the protrusion-check object used by bulk TwoNTree construction.

_wellseparatedpredicate(builder)

Return the same-level predicate builder applies to its candidates, so the interaction-list path can call the very same function the full scan would have.

adjacencygraph(...)

Extension hook implemented by graph/visualization integrations.

adjointaggregation(aggregationplan, disaggregationplan)

Build the aggregation-side plan used by the adjoint traversal.

For a forward AggregatePlan/DisaggregateTranslatePlan pair, the adjoint must aggregate and translate on the forward disaggregation tree, so the translating dictionary is inverted.

adjointaggregation(aggregationplan::AggregateTranslatePlan, disaggregationplan::DisaggregatePlan)

Build the non-translating aggregation plan for the adjoint of a forward AggregateTranslatePlan/DisaggregatePlan pair.

adjointdisaggregation(aggregationplan, disaggregationplan)

Build the disaggregation-side plan used by the adjoint traversal.

For a forward AggregatePlan/DisaggregateTranslatePlan pair, the adjoint disaggregates the forward aggregation tree without translating.

adjointdisaggregation(aggregationplan::AggregateTranslatePlan, disaggregationplan::DisaggregatePlan)

Build the translating disaggregation plan for the adjoint of a forward AggregateTranslatePlan/DisaggregatePlan pair.

The forward aggregate-translation dictionary is inverted so adjoint receiving nodes point back to the forward translating nodes.

adjointplans(aggregationplan, disaggregationplan)

Return the adjoint pair (adjointaggregation, adjointdisaggregation) associated with the provided forward aggregationplan and disaggregationplan.

The forward pair must contain exactly one translating plan. The adjoint pair keeps that invariant while swapping the translating role to the opposite traversal direction.

adjusttwontreeblocktreeparameters(testhalfsize, trialhalfsize, minhalfsize)

Return compatible root halfsizes and minimum levels for the two sides of a BlockTree.

The smaller side may start at a deeper minimum level so both trees share the same geometric level scale where interactions are compared.

aggregationlevels(plan)

Return aggregation levels in traversal order, from fine to coarse.

aggregationnodes(plan)
aggregationnodes(plan, level)

Return the aggregation nodes grouped by level, or the nodes at one level.

anyvalue(f, tree, node::Int)

Return true when f(value) is true for any value contained in node's subtree.

appendfarnodevalues!(indices, testtree, trialtree, trialnode::Int; isfar=isfar)

Append two-tree far-node values from testtree to indices and return indices.

appendfarnodevalues!(indices, tree, node::Int; isfar=isfar)

Append single-tree far-node values to indices and return indices.

appendnearnodevalues!(indices, testtree, trialtree, trialnode::Int; isnear=isnear, storevalues=Val{:flattened}())

Append two-tree near-node values from testtree to indices and return indices.

appendnearnodevalues!(indices, tree, node::Int; isnear=isnear, storevalues=Val{:flattened}(), nearlists=nothing)

Append single-tree near-node values to indices and return indices.

appendsymmetrytranslationinfo!(translationinfos, rlevelid, receivingnode,
    translatingnode, translationID, symmetryID)

Append one symmetry-aware translation metadata record to a level-local vector.

appendtranslationinfo!(translationinfos, rlevelid, receivingnode,
    translatingnode, translationID)

Append one translation metadata record to a level-local vector.

appendvalues!(out, tree, nodes)

Append all values contained in every node in nodes to out.

appendvalues!(out, tree, node::Int)

Append all values contained in node's subtree to out.

For a leaf this appends the values physically stored on that node. For an internal node this walks the descendant leaves and appends their stored values directly, avoiding the temporary vector that values(tree, node) materializes.

applysymmetry!(destination, symmetry, q)

The vector form of applysymmetry, writing the result into destination.

destination and q must not be the same array.

applysymmetry(symmetry, q)

Apply symmetry to q: component i of the result is signs[i] * q[permutation[i]].

Takes and returns a tuple. Use applysymmetry! if you are working with vectors, as the translation build loop does.

averagenumberofchildren(tree, level)

Return the average number of children per node at level.

averagenumberofpoints(tree, level)

Return the average number of stored values per node at level.

balanceleaves!(tree::BoundingBallTree)

Extend shallower leaves with unary child nodes until all leaves have the same level.

The added child nodes keep the same bounding ball and values as the original leaf. The original leaf becomes an internal node and its values are cleared, matching the usual tree layout where values live on leaves.

ballgap(center_a, center_b, radius_a, radius_b)

Separation between two bounding balls: centre-to-centre distance minus both radii, floored at zero when the balls touch or overlap.

The BoundingBallTree/KMeansTree counterpart to boxgap: see nodegap for the dispatch that picks between the two.

boundingbox(points::Vector{SVector{D, T}})

Returns halfsize and center of bounding box of points. The halfsize is the half of the length of the edge of the bounding box.

boundingsphere(tree::BoundingBallTree, node::Int)

Compute the smallest enclosing ball of a tree node, as a (center, radius) tuple.

For a leaf the stored ball is returned unchanged. For an internal node the smallest ball enclosing all immediate child balls is computed via H2Trees.SEBB.smallest_enclosing_ball (Fischer & Gärtner 2004). This assumes the child balls are already up to date, which updateradii! guarantees by updating nodes bottom-up.

The ball is the exact optimum whenever the solver certifies it, and otherwise a strictly enclosing approximation (the solver warns once and never throws). Only containment matters here: a slightly larger node ball costs a marginally wider near field, nothing more.

Returns

A tuple (center, radius) representing the smallest enclosing ball.

boundingsphereofspheres(center1, radius1, center2, radius2)

Return the smallest ball enclosing the two input balls as a (center, radius) tuple.

This is the two-ball case of the SEBB problem and delegates to H2Trees.SEBB.smallest_enclosing_ball, so nested pairs correctly return the containing ball. The result is exact whenever the solver certifies it, and otherwise a strictly enclosing approximation: containment is guaranteed either way, minimality is not. See Fischer & Gärtner, The Smallest Enclosing Ball of Balls: Combinatorial Structure and Algorithms (2004).

boxgap(center_a, center_b, halfsize_a, halfsize_b)

Axis-aligned gap between two boxes: the Euclidean length of the per-axis overhangs, counting only axes where the boxes do not overlap. Zero when they touch or intersect.

This is the raw geometric quantity the admissibility predicate is built on (see isneargap) exposed separately so diagnostics can report the real gap independently of whatever predicate a plan happened to be built with.

buildforest(points, graph, weights; builder=MetisForestBuilder())

Construct a MetisForest, one tree per connected component of graph.

buildplans(tree; builder=PlanBuilder())

Build Galerkin plans for a single tree or Petrov plans for a block tree.

builder controls the aggregation mode, near/far predicate, translating-node iterator, stored-node predicate, and optional admissibility check. When builder.checkadmissibility is true, the generated plan set is validated with checkadmissibility before it is returned.

buildtree(points, graph, weights; builder=MetisTreeBuilder())

Build a MetisTree from points and a partitioning graph.

weights are the vertex weights used by METIS. The builder carries the partitioning and tree-construction settings.

buildtree(testpoints, trialpoints; builder=BlockTreeBuilder())

Build a BlockTree from test and trial point collections.

The BlockTreeBuilder carries the two side-specific TwoNTreeBuilders.

buildtree(input; builder=TwoNTreeBuilder())

Build a tree from one input object.

The builder selects the tree type and carries all construction settings. Supported builders include TwoNTreeBuilder, BoundingBallTreeBuilder, KMeansTreeBuilder, and SimpleHybridTreeBuilder. The SimpleHybrid builder expects an existing tree as input; the others expect a point collection.

bulkbuildtwontree(points, rootcenter, roothalfsize, minhalfsize, minlevel, root, minvalues, protrusion)

Build a complete TwoNTree in a single recursive pass over grouped point ids.

For each cell, decides whether to stop (create a leaf holding every point index in the cell) or continue (bucket by sectorcentersize and recurse into each non-empty child) using two different rules depending on minvalues/protrusion:

• the general adaptive rule: length(ids) <= minvalues, protrusion, halfsize <= minhalfsize, and the bisection depth _uniformseparationdepth computes;
• minvalues == 0 with NoProtrusionCheck: a uniform-depth rule bounded ONLY by halfsize <= minhalfsize, with no conformance computation at all (points landing in the same cell all the way down to minhalfsize simply share a leaf), implemented by passing _bulkbuildnode!/_bulkbuildchildren! a sentinel nlevels = typemax(Int) so the depth-based stopping condition never fires, skipping _uniformseparationdepth entirely (see the nlevels computation below).

Either way the recursion itself is purely geometric: children are appended in ascending sector order, and the resulting node ids and sibling links are temporary. _finishbulktwontree then assigns the final layout: level-major, Hilbert-ordered within each level, so firstchild/nextsibling and node ids alike are deterministic regardless of point processing order. See _hilbertlevelmajornodes for the guarantees that layout provides.

protrusion.compute is called as f(center, halfsize, value); tree/node-shaped construction-time protrusion functors are not supported by the bulk builder.

canonicalizetranslation!(canonical, scratch, q, group) -> symmetryid

The vector form of canonicalizetranslation: writes the representative into canonical and uses scratch as working space. Both need at least D entries, and neither may be the same array as q.

This is what the translation build loop uses, since it keeps its offsets in reused vectors rather than tuples.

canonicalizetranslation(q, group) -> (canonical, symmetryid)

Reduce q to the representative of its orbit under group, and return the ID of the symmetry that maps that representative back to q:

q == applysymmetry(group[symmetryid], canonical)

The stored symmetry goes from canonical to actual, not the other way round. That is the direction a consumer wants: it holds the one translation built for canonical and needs the one for q. If the operator depends on direction through k̂ ⋅ d, the consumer applies the inverse to its directions:

T(k̂, q) == T(applysymmetry(inversesymmetry(group[symmetryid]), k̂), canonical)

Worth knowing when testing this: the antipodal map is its own inverse, so OppositeSymmetry alone cannot tell the two directions apart, and a reversed convention would still pass.

Everything in one orbit reduces to the same representative, which is what makes the result usable as a deduplication key:

canonicalizetranslation(applysymmetry(R, q), group)[1] ==
    canonicalizetranslation(q, group)[1]        for every R in group

Ties go to the lowest-numbered symmetry, so offsets with small orbits (those lying on a symmetry axis or plane, like (3, 0, 0) or (3, 3, 3)) still give a deterministic answer.

julia> group = H2Trees.symmetrygroup(H2Trees.FullLatticeSymmetry(), Val(3));

julia> canonical, id = H2Trees.canonicalizetranslation((-2, 3, -1), group);

julia> canonical
(3, 2, 1)

julia> H2Trees.applysymmetry(group[id], canonical)
(-2, 3, -1)

center(tree, node=root(tree))
center(data)

Return a node or node-data center.

checkadmissibility(tree, plans; isnear=H2Trees.isnear(), mingapboxes=DEFAULTNEARGAPBOXES,
                   coverage=true, throw=true, maxfindings=200)

Validate an assembled translation scheme against its near/far geometry.

plans is normally the PlanSet returned by buildplans. isnear may be either a factory such as H2Trees.isnear() or an already resolved node-comparison predicate.

The report contains :error findings for impossible or inconsistent plan data (near pairs scheduled as far, wrong levels, unknown nodes, coverage gaps or duplicates) and :warning findings for marginal far pairs whose geometric gap is below mingapboxes * min(nodesize).

With coverage=true, the near field is compared with the far values actually scheduled by the translating plan, including translations addressed to ancestors and carried down by disaggregation. This is intentionally stronger than recomputing the far field from FarNodeIterator, but it is also expensive; use coverage=false on large diagnostic runs.

throw=true raises on errors and warns on warnings. Use throw=false to inspect the returned AdmissibilityReport. This is a diagnostic, not a matvec hot-path check.

checkbalancedtree(tree)

Return whether all leaves sit at the same tree level.

children(tree, node=root(tree))

Return an iterator over the direct children of node.

composesymmetry(a, b)

The symmetry that applies b first and then a:

applysymmetry(composesymmetry(a, b), q) == applysymmetry(a, applysymmetry(b, q))

computevectorbuffers(tree, T)

Allocate one vector buffer per leaf, sized to that leaf's stored values.

For block trees, returns separate dictionaries for the test and trial sides.

cornerpoints(tree::TwoNTree{N,D,T}, node::Int, i)

Return corner i of node's box.

Corners are numbered from 1 to 2^N.

data(tree, node)

Return the data payload stored on node.

defaultprotrusioncheck(input)

Return the default protrusion policy for input.

The fallback is NoProtrusionCheck. Extensions can specialize this for richer input types.

defaultprotrusionfunctor(input)

Return the default protrusion evaluator for input.

The fallback is ComputeProtrusionFunctor, which evaluates to zero.

depthfirstnodes(tree)

Return the cached depth-first node order.

determinant(symmetry) -> Int

The determinant of symmetry: +1 for a rotation, -1 for a reflection.

Computed exactly, as the permutation's parity times the product of the signs.

You need this when a symmetry acts on field components rather than just on positions. A pseudo-tensor (anything built from a curl or a cross product, such as a double-layer kernel) picks up the determinant where an ordinary tensor does not:

tensor         G(Sx) == S G(x) Sᵀ
pseudo-tensor  K(Sx) == det(S) · S K(x) Sᵀ

Both are 3x3, so their shape does not tell you which you have. Using the wrong rule flips the sign of the result on every reflection and is correct on every rotation. Reflections are half of any lattice symmetry group, so a test that only tries the identity or a rotation will not catch it.

disaggregationlevels(plan)

Return disaggregation levels in traversal order, from coarse to fine.

disaggregationnodes(plan)
disaggregationnodes(plan, level)

Return the disaggregation nodes grouped by level, or the nodes at one level.

farnodevalues(testtree, trialtree, trialnode::Int; isfar=isfar)

Collect values from far nodes in testtree for a reference node in trialtree.

farnodevalues(tree, node::Int; isfar=isfar)

Collect values stored in far nodes for node in a single tree.

findleafnode(tree, value::Int)

Return the leaf node containing value, or 0 when none is found.

foreachtranslationpair(f, translatingplan, relevantlevels, receivinglevel)

Call f(levelid, receivingnode, translatingnode) for every pair scheduled by a translating plan.

levelid indexes relevantlevels according to the receiving node's level.

foreachvalue(f, tree, node::Int)

Call f(value) for every value contained in node's subtree.

For a leaf this visits the values physically stored on that node. For an internal node this walks the child subtrees directly, avoiding the temporary leaf or value vectors materialized by leaves(tree, node) and values(tree, node).

halfsize(tree, node=root(tree))
halfsize(data::BoxData)

Return the halfsize of a box-tree node.

halfsizes(tree)

Return one representative halfsize per tree level.

haserrors(report)

Return whether an AdmissibilityReport contains at least one :error finding.

haswarnings(report)

Return whether an AdmissibilityReport contains at least one :warning finding.

identitysymmetry(Val(D))

The identity element of the D-dimensional lattice symmetry group.

inversesymmetry(symmetry)

The inverse of symmetry, satisfying composesymmetry(inversesymmetry(s), s) == identitysymmetry(Val(D)).

isdisaggregationnode(plan, node)

Return whether node is marked as a stored disaggregation node.

isfar(testtree, trialtree, testnode::Int, trialnode::Int)

Return the logical negation of the trait-dispatched two-tree isnear predicate.

isfar(tree, testnode::Int, trialnode::Int)

Return the logical negation of isnear(tree, testnode, trialnode).

isgalerkin(plans_or_family)
ispetrov(plans_or_family)

Return whether a PlanSet or plan-family marker represents Galerkin or Petrov-Galerkin plans.

isgalerkinsymmetric(T)
isgalerkinsymmetric(::Type{T})

Return whether a Galerkin operator type can be treated as symmetric.

Packages defining concrete operators can extend this hook. The fallback is false.

isin(tree, node, point)

Return whether point lies in node for tree.

isleaf(tree, node)

Return whether node has no children.

isnear(testtree, trialtree, testnode::Int, trialnode::Int; minlevel=level(testtree, root(testtree)), kwargs...)

Return whether two nodes, one from each tree, are near.

If either node level is below minlevel, this returns true immediately; otherwise it forwards to trait-dispatched isnear.

isnear(tree, testnode::Int, trialnode::Int; minlevel=level(tree, root(tree)), kwargs...)

Return whether two nodes in a single tree are near.

If level(tree, testnode) < minlevel, this returns true immediately; otherwise it forwards to trait-dispatched isnear.

isnear(; kwargs...)

Return a near-predicate factory.

The returned object resolves to the appropriate one-tree or block-tree predicate when called with a tree. Keyword arguments are forwarded to the concrete geometric predicate.

isneargap(center_a, center_b, halfsize_a, halfsize_b, additionalbufferboxes;
          gapboxes=DEFAULTNEARGAPBOXES, reltol=NEARGAPRELTOL)

Box-gap near predicate: near when the axis-aligned gap between the two boxes is at most (gapboxes + additionalbufferboxes) * min(halfsize), plus a small relative tolerance.

Preferred over isnearhalfsize for admissibility. It measures the actual box gap using each side's own halfsize, so independently built trees need not share a grid. See DEFAULTNEARGAPBOXES for why the default margin is one half-size.

isnearhalfsize(center_a, center_b, halfsize, additionalbufferboxes)

LEGACY centre-distance near predicate: near when the centres lie within sqrt((n+1)*12)*halfsize.

Retained as a named predicate, but not used for default admissibility. It assumes both boxes share one halfsize; use isneargap for independently built trees.

isnearradius(center1, center2, radius1, radius2; η=1)

Ball near predicate.

Two balls are near when one contains the other, or when their center distance is at most η * (radius1 + radius2) up to numerical slack. η must be at least one.

istranslatingplan(plan)

Return true when plan stores translating-node data in addition to traversal nodes.

isuppertreelevel(tree, level)
islowertreelevel(tree, level)
isuppertreenode(tree, node)
islowertreenode(tree, node)

Query whether a level or node belongs to the upper or lower part of a hybrid tree.

iswellseparated

kmeanswrapper(points, globalpointids, numberofclusters; kwargs...)

Extension hook implemented by H2ParallelKMeansTrees.

The core package declares the function so KMeansTree can be defined without loading ParallelKMeans.jl.

lastnode(tree)

Return the largest global node id in tree.

leafclusters(tree)

Return the leaf value vectors of tree.

leaves(tree, node::Int)

Return the leaf nodes below node.

When node is the root, the cached TreeIndex leaf list is reused and copied for caller ownership.

level(tree, node)
level(data)

Return the tree level of a node or node-data payload.

levelindex(tree, node)

Return the cached level-array index for node.

levelprotrusions(tree; compute=ComputeProtrusionFunctor())

Return the level-wise protrusion vector for tree.

This is the public keyword spelling used by tree-building diagnostics; it delegates to maxprotrusion.

levels(tree)

Return the level range covered by tree.

levels(plan)

Return the levels covered by plan, in the traversal order used by that plan.

leveltolevelid(tree, level::Int)

Convert a tree level to the cached level-array index.

leveltolevelid(plan::AbstractAggregationPlan, level)

Map a tree level to the storage index used by an aggregation plan.

leveltolevelid(plan::AbstractDisaggregationPlan, level)

Map a tree level to the storage index used by a disaggregation plan.

locatepoint(tree, point, targetlevel)

Find the node in tree at the given level whose box contains point.

Starting from the root, descends through child sectors until level is reached. Throws when the existing tree topology has no matching child on the path.

maxprotrusion(tree; computeprotrusion=ComputeProtrusionFunctor)

Compute the maximum protrusion per tree level.

For each leaf, this evaluates the protrusion of every stored value relative to the leaf box and records the maximum on that leaf's level. Specialized protrusion functors can use the allocation-friendly f(center, halfsize, value) form.

The level-wise values are propagated upward so each coarser level is at least half of the next finer level. A warning is emitted for values greater than or equal to 0.5. The result has one entry per level in levels(tree).

metispartition(graph, vertexweights, numberofdivisions; kwargs...)

Extension hook implemented by H2MetisTrees.

The core package declares the function so MetisTree and MetisForest can be defined without loading Metis.jl.

metiswrapper(graph, points, globalpointids, pointgraphweights, numdivisions; kwargs...)

Build child partitions, centers, and radii for one METIS tree node.

The returned point ids remain global to the original point vector. Empty partitions are removed before centers and bounding radii are computed.

minaggregationlevel(plan)

Return the finest aggregation level covered by plan.

mindisaggregationlevel(plan)

Return the coarsest level covered by a disaggregation plan.

minhalfsize(tree)

Return the halfsize at the deepest cached level.

minimumlevel(tree)

Return the minimum level stored by tree.

This is usually the root level, but it need not be 1.

minlevel(plan::AbstractAggregationPlan)

Return the finest level covered by an aggregation plan.

mintranslationlevel(tree; TranslatingNodesIterator=TranslatingNodesIterator)

Return the first tree level that contains at least one translating node.

A node is considered translating if istranslatingnode(tree, node; TranslatingNodesIterator=...) is true.

Returns

The minimum level with a translating node. If no translating node exists, the last level of tree is returned.

mintranslationlevel(plans)

Return the first level at which translations are relevant.

Galerkin plans do not store this separately, so the first relevant level is used.

nearcandidatepredicate(predicate)

Return a level-monotone near predicate whose near set contains predicate's, or nothing when no such predicate is known for it.

nothing is not a failure: it selects the original full-level scan, which is correct for any predicate. A non-nothing result means the returned predicate contains the original one. A wrapper that only narrows its inner predicate (as _LeafPredicateFunctor does) satisfies this by unwrapping to that inner predicate, which is the extension point for predicates defined outside H2Trees.

Whether the returned predicate is also level-monotone, the other half of what the sweep needs, depends on the tree's shape rather than on the predicate alone and is decided separately by supportsnearlists. The library's geometric predicates are recognised here for that reason: on the shapes supportsnearlists admits they are monotone, and on the shapes it rejects they never get the chance.

nearinteractions(testtree, trialtree; extractselfvalues=false, isnear=isnear)

Compute two-tree near interactions.

Returns (testvalues, trialvalues), where each testvalues[i] is paired with trialvalues[i]. extractselfvalues=true is not supported for two-tree interactions.

nearinteractions(tree, ::isBlockTree; kwargs...)

Compute near interactions for the two sides of a block tree.

This delegates to nearinteractions(testtree(tree), trialtree(tree); kwargs...).

nearinteractions(tree; kwargs...)

Compute near-interaction index lists for tree.

For a single tree, returns (values, nearvalues): each values[i] is paired with nearvalues[i]. Self-interactions are included by default.

Set extractselfvalues=true to return (selfvalues, values, nearvalues), where self-interactions are separated from non-self near interactions. Pass isnear to choose a custom near predicate.

nearinteractions(tree, trait; extractselfvalues=false, isnear=isnear)

Compute single-tree near interactions for the given tree trait.

When the tree is not balanced, ancestor-near leaves are included so near interactions remain complete across different leaf levels.

nearlistcache(tree, predicate)

Return a NearListCache usable as the candidate set for predicate, or nothing when the full-level scan must be kept.

nothing is returned for a tree shape supportsnearlists rejects (which includes block trees, whose pairs span two independently built trees a single-tree sweep cannot enumerate), for a predicate nearcandidatepredicate does not vouch for, and for a tree whose nodes are not all covered by levels(tree).

nearnodevalues(testtree, trialtree, trialnode::Int; isnear=isnear, storevalues=Val{:flattened}())

Collect values from near nodes in testtree for a reference node in trialtree.

The traversal first visits near nodes relative to trialnode, then walks upward through trial-tree parents and adds near leaf nodes. By default, returns a flattened Vector{Int}.

nearnodevalues(tree, node::Int; isnear=isnear, storevalues=Val{:flattened}(), nearlists=nothing)

Collect values stored in near nodes for node in a single tree.

The traversal first visits near nodes at the level of node, then walks upward through parents and includes near leaf nodes. By default, returns a flattened Vector{Int}.

Pass nearlists when calling this for many nodes of the same tree; see nearlistcache.

noboundingsphereupdate(tree, node::Int)

Return the stored center and radius of node.

nodegap(treea, nodea, treeb, nodeb)

Geometric separation between two tree nodes, dispatched on treea's own shape: boxgap for a box-shaped tree, ballgap for a ball-shaped one. treea and treeb are always the same shape in practice (a BlockTree's two sides are both TwoNTrees by construction) so dispatching on treea alone is sufficient.

nodes(tree)

Return the tree's node storage vector.

nodes(plan)
nodes(plan, level)

Return all planned nodes, or the nodes stored for one tree level.

nodesatlevel(tree)
nodesatlevel(tree, level)

Return cached nodes grouped by level, or the nodes at one level.

nodesatvalues(tree, boxes=valuesatnodes(tree))

Group value ids by the set of leaf nodes that contain them.

nodesize(tree, node)

The characteristic bounding-volume size checkadmissibility's gap margin is measured in: halfsize for a box-shaped tree (isTwoNTree), radius for a ball-shaped one (isBoundingBallTree).

numberoflevels(halfsize, minhalfsize)

Return the number of bisection levels needed to reach minhalfsize.

numberoflevels(tree)

Return the number of levels covered by tree.

numberofnodes(tree)

Return the number of nodes stored by tree.

numberofvalues(tree, node::Int=root(tree))

Number of values contained in node's subtree.

Walks the child subtrees directly, like appendvalues!/foreachvalue/ anyvalue, rather than materializing a leaf or value vector via leaves(tree, node)/ values(tree, node).

oppositesector(tree::TwoNTree, node)
oppositesector(N, sector)

Return the sector opposite to node's sector, or to sector in N dimensions.

ownedtree(plan)

Return the tree owned by one concrete plan.

parent(tree, node)
nextsibling(tree, node)
firstchild(tree, node)

Return topology links for node.

parentcenterminuschildcenter(tree::TwoNTree, child)

Return center(parent(tree, child)) - center(tree, child).

planfamily(plans)

Return the family marker stored in plans.

plantranslationtrait(plan)

Return the translation trait for plan.

Concrete translating plans override this to return IsTranslatingPlan.

printforest(io, forest)

Print the detailed multi-line forest summary used by show(io, MIME"text/plain"(), forest).

printtree(io, tree)

Print the detailed multi-line tree summary used by show(io, MIME"text/plain"(), tree).

protrusionreport(tree; compute=ComputeProtrusionFunctor())

Return the level with the largest protrusion and its value.

The result is a named tuple (level, value).

radius(tree, node)
radius(data::BoundingBallData)

Return the radius of a ball-tree node.

rebuildtreeindex!(tree)

Recompute and replace the cached TreeIndex for tree.

receivingtree(contexttree, plan)
translatingtree(contexttree, plan)

Resolve the receiving and translating trees for a translating plan.

For single-tree plans both trees are the same. For block-tree plans, contexttree must be the block tree used to build the plans so the owned side can be matched by object identity.

relevantlevels(plans)

Return the levels where all plans in plans are relevant to the traversal.

root(tree)

Return the root node id.

roothalfsize(rootsize, minhalfsize)

Return a root halfsize aligned to an integer number of bisections of minhalfsize.

rootoffset(plan)

Return the node-number offset used by plan for indexing per-node storage.

samelevelnodes(tree, node)

Return all nodes at node's level.

sector(tree, node)
sector(data::BoxData)

Return the sector stored for a box-tree node.

sectorcenter(sector, center, childhalfsize)

Return the child center for sector under a parent centered at center.

sectorcentersize(point, center, halfsize)

Return (sector, childcenter, childhalfsize) for point in the box centered at center with halfsize halfsize.

settranslationinfo!(translationinfos, rlevelid, levelindex, receivingnode,
    translatingnode, translationID)

Store one translation metadata record at a known level-local index.

splitplan(tree, plan)

Split a translating plan into two subplans at hybridlevel(tree).

The function returns (upperplan, lowerplan), both with the same concrete plan type as plan, where level sets are partitioned into levels at or above the hybrid level and levels below it.

storenode(plan)
storenode(plan, node)

Return the stored-node mask for non-translating plans, or query whether node is marked as stored.

supportsnearlists(tree)

Return whether the top-down near recursion is sound for tree's shape.

Only box trees (isTwoNTree) qualify. There, a parent's box contains its children's and the axis-aligned gap can only shrink going up while isneargap's allowance grows with the half-size, so a near child forces near parents.

Ball trees keep the original scan. Their current radius predicate is monotone under containment, but the measured speedup was small enough that enabling the cache remains a separate performance and accuracy decision.

A shape not covered here keeps the original full-level scan, which is correct for any tree.

symmetrygroup(policy, Val(D))

Build policy's symmetries in D dimensions as a SymmetryGroup.

Checks that the policy really is a subgroup: identity first, closed under composition and inversion. A policy that is not closed would not fail outright. It would quietly break canonicalization instead, because two offsets in the same orbit could reduce to different representatives.

julia> length(H2Trees.symmetrygroup(H2Trees.FullLatticeSymmetry(), Val(3)))
48

julia> length(H2Trees.symmetrygroup(H2Trees.AxisPreservingSymmetry(3), Val(3)))
16

symmetryorbit(q, group)

The set of distinct offsets reachable from q under group.

Orbits are smaller than the group for offsets fixed by some of its elements, which is why the achievable translation reduction is measured rather than read off the group order.

testtree(tree::BlockTree)

Return the test-side tree.

testtree(plans)
trialtree(plans)

Return the test or trial tree associated with plans.

For Galerkin plans, both accessors resolve to the same underlying tree.

traceball(...)
tracecube(...)

Extension hooks implemented by H2PlotlyJSTrees.

translatingplan(aggregationplan, disaggregationplan)

Return the one translating plan from a valid aggregation/disaggregation pair.

Exactly one side of a plan pair must carry translations: either AggregateTranslatePlan with DisaggregatePlan, or AggregatePlan with DisaggregateTranslatePlan.

The block-tree twin of the single-tree refusal above: BOTH sides must be TwoNTrees.

One side being non-lattice is enough to break the argument: the symmetry maps a displacement between the two trees, so it needs both endpoints on a common lattice. The ::isTwoNTree, ::isTwoNTree method below is strictly more specific and still wins; this catches every mixed pair.

translations(tree, translatingplan, translationtrait)

Compute translation vectors for a translating plan.

Returns (translationinfos, translationdirections, relevantlevels). translationinfos[levelid] stores named tuples with receivingnode, translatingnode, and translationID; translationdirections[translationID] stores the vector used by that pair.

The translationtrait controls how directions are deduplicated:

• AllTranslations: every scheduled pair gets its own direction.

• DirectionInvariancePerLevel: equal directions are shared within a level.

• DirectionInvariance: equal directions are shared across all relevant levels.

• SymmetryDirectionInvariancePerLevel: directions are shared within a level up to a LATTICE SYMMETRY, so one stored direction serves a whole orbit rather than only exact duplicates. Its translationinfos carry an extra symmetryID naming which group element maps the stored (canonical) direction onto the pair's own: every other trait's records have three fields, these have four, so a consumer reading them positionally must know which trait produced them.

  TWO REFUSALS ARE PART OF ITS CONTRACT, and they are deliberately different types. TwoNTree geometry is REQUIRED: any other tree, or a BlockTree with a non-TwoNTree side, is an ArgumentError, because a lattice symmetry has no meaning without a lattice. A TwoNTree pair whose roots are offset by a non-lattice vector instead throws a catchable NonLatticeTranslationError, which consumers are expected to handle by falling back to DirectionInvariancePerLevel. Configuration error versus fallback condition.

For BlockTrees, receiving and translating sides are resolved from the translating plan.

Refuse SymmetryDirectionInvariancePerLevel on a geometry that cannot carry it.

AN EXPLICIT CONTRACT, NOT AN ACCIDENTAL DISPATCH GAP. Without this method the generic translations(tree, ::AbstractTreeTrait, ...) above forwards to a seven-argument _translations, while the symmetry trait's own method takes eight (it additionally needs receivinghalfsize). The result was a MethodError naming _translations and a list of functors, which says nothing about the trait, the tree, or what to use instead.

DISTINCT FROM NonLatticeTranslationError, and the two must not be conflated. That one is a CATCHABLE FALLBACK CONDITION: the geometry is right, this particular root offset is not, and a consumer is expected to catch it and drop to DirectionInvariancePerLevel. This is a programmer or configuration error (the geometry itself cannot support lattice symmetries at any offset), so it is an ArgumentError and nothing should be catching it.

The ::isTwoNTree method below is strictly more specific and still wins.

tree(plan)

Return the tree associated with plan.

tree(plans)

Return the tree or block tree that plans were built from.

treeindex(tree)

Return the cached TreeIndex for tree.

treetrait(tree)

Return the AbstractTreeTrait tag for tree.

treetrait(::Type{<:BoundingBallTree})

Return isBoundingBallTree.

treetrait(::Type{<:TwoNTree})

Return isTwoNTree.

treetrait(::Type{<:BlockTree})

Return isBlockTree.

treewithmorelevels(blocktree)

Return the side of a block tree with at least as many levels as the other side.

trialaggregationplan(plans)
testdisaggregationplan(plans)
testaggregationplan(plans)
trialdisaggregationplan(plans)

Return the four concrete plans in a PlanSet.

trialtree(tree::BlockTree)

Return the trial-side tree.

unsafemaxradiusboundingsphere(tree, node::Int)

Return center(tree, node) and the maximum radius among node and its children.

updateradii!(tree::BoundingBallTree; update=boundingsphere)

Update every node radius and center with update(tree, node).

update may be boundingsphere, noboundingsphereupdate, or a custom function returning (center, radius).

values(tree, nodes)

Materialize all values contained in every node in nodes.

values(tree, node::Int)

Return the values contained in node's subtree.

For a leaf, the stored value vector is returned directly. For an internal node, the descendant leaf values are materialized into a new vector. Use appendvalues!, foreachvalue, or anyvalue in allocation-sensitive code.

values(data::Union{BoxData,BoundingBallData})

Return the value vector physically stored in a node-data payload.

valuesatnodes(tree; numberofvalues=H2Trees.numberofvalues(tree))

Return a vector mapping each stored value id to the leaves containing it.

@treewrapper WrapperType

Generate forwarding methods for a tree wrapper type.

WrapperType must store the wrapped tree in a field named tree. The generated methods forward the standard tree interface (treetrait, node/level accessors, geometry, child/parent navigation, stored values, and eltype) to that inner tree.

HilbertOrdering

Hilbert space-filling-curve helpers used by H2Trees.

The module is tree-independent. It operates only on dimension, orientation state, sector, and integer grid coordinates.

Supported dimensions are exactly 1, 2, and 3; anything else throws an ArgumentError rather than silently producing an invalid order.

Conventions:

• sectors are zero-based, 0:2^N-1, matching TwoNTree's sectorcentersize (dimension 1 is the least significant bit);
• Hilbert positions are zero-based, 0:2^N-1;
• orientation states are one-based (they index tables) and should be treated as opaque outside this module.

Not exported from H2Trees; reach it as H2Trees.HilbertOrdering.

hilbertcoordinates(::Val{N}, index, level)

Integer grid coordinates of the cell at position index along the level-level Hilbert curve.

Inverse of hilbertindex; returns an NTuple{N,Int}.

hilbertindex(::Val{N}, coords, level)

Position of the grid cell at integer coords along the level-level Hilbert curve.

coords holds N coordinates, each in 0:2^level-1. The result is in 0:2^(N*level)-1.

This is a validation/analysis primitive: tree construction does not need it (it propagates orientation state directly down the tree instead), and no Hilbert index is ever stored on a node.

hilbertnextstate(::Val{N}, state, sector)

Orientation state of the child in sector of a cell in orientation state.

Propagating this from the root is what makes the ordering a genuine recursive Hilbert curve rather than a per-level shuffle.

hilbertposition(::Val{N}, state, sector)

Zero-based position at which sector is visited by a cell in orientation state.

Ordering key for sectors in one cell. For the inverse mapping, use hilbertsectororder.

hilbertsectororder(::Val{N}, state)

Sectors of a cell in orientation state, in Hilbert traversal order.

The inverse permutation of hilbertposition: entry k is the sector visited at position k - 1.

initialstate(::Val{N})

Orientation state the Hilbert curve is entered in for dimension N.

This is the state that must be handed to the root of a traversal; child states then follow via hilbertnextstate.

SEBB

Smallest Enclosing Ball of Balls (SEBB) in dimensions 1, 2, and 3.

Exact (the certified minimal ball) whenever the configuration is resolvable at the caller's precision. A degenerate input never raises: the public solver warns once and returns a strictly enclosing approximation instead. Tests and diagnostics can inspect the internal certificate helper to distinguish exact from fallback results.

This submodule is tree-independent. H2Trees adapts trees to SEBB, not the reverse.

Public API

• Ball, center, radius
• encloses
• smallest_enclosing_ball

Ball{N,T<:AbstractFloat}

An immutable geometric ball in ambient dimension N with an SVector{N,T} center and a scalar radius::T.

Only dimensions N ∈ (1, 2, 3) are supported. Centers must be finite and radii must be finite and nonnegative. Zero radii are accepted as degenerate point balls.

Fields

• center::SVector{N,T}
• radius::T

Ball(center, radius)

Construct a Ball from any AbstractVector center and real radius, promoting the element type and radius to a common floating-point type.

QuadraticRoots{T}

Fixed-size result of real_roots: count ∈ (0, 1, 2) valid entries stored in roots in ascending order. Unused entries are zero. A fixed layout avoids a runtime union over the number of roots.

SEBBResult{N,T}

Internal result carrying the enclosing ball together with an optimality certificate: the support indices (into the caller's original ordering, unused entries zero), the barycentric weights of the center over the support centers (unused entries zero), and support_size.

The public API returns only .ball; this richer form is used by tests and diagnostics.

Tolerance{T}

A pair of tolerances (atol, rtol) used to build scale-aware thresholds through tolerance.

_approximateresult(balls, reason) -> SEBBResult

Warn, then return _fallbackball wrapped in a certificate-free SEBBResult.

Failing here instead would abort whatever is being built on top of the solver (a whole tree, and with it a whole matrix) over a configuration that is merely unresolvable in the caller's arithmetic. A ball that is guaranteed to enclose but only approximately minimal keeps every consumer correct, at the price of a marginally larger near field.

The warning uses maxlog = 1 on purpose: a tree build calls this once per internal node, and a systematically degenerate input would otherwise emit thousands of identical messages.

_candidate_many(balls, idx::NTuple{M,Int}, tol) -> Union{Nothing,SEBBResult}

Tangent ball of a size-M support (M ∈ (3, 4)) via the Fischer & Gärtner (2004) Lemma 3.1 construction: a Gram linear system parameterized by the radius, solved with a Cholesky factorization (never an explicit inverse), followed by a quadratic in the radius.

Returns nothing for affinely dependent (rank-deficient) supports and for roots that fail the radius / convex-weight / tangency checks.

_candidate_one(balls, i, tol) -> SEBBResult

The one-ball candidate is the input ball itself (weight one). Global feasibility is decided later by the enumeration. Handles single balls, nested balls, coincident centers, and duplicate largest balls.

_candidate_two(balls, i, j, tol) -> Union{Nothing,SEBBResult}

Exact two-ball tangent ball. Rejects coincident centers (a one-ball support handles those) and nested pairs (a barycentric weight leaves [0, 1]).

_enclosingradius(center, balls)

The exact radius a ball at center needs in order to contain every ball in balls, namely max(‖center - cᵢ‖ + rᵢ).

_fallbackball(balls) -> Ball

A ball that provably encloses every ball in balls and is approximately the smallest such.

Used by smallest_enclosing_ball when the exact enumeration cannot resolve the configuration. Deterministic, allocation free, and independent of the input order beyond tie-breaking: it seeds from the best input center and the exact two-ball solution of the farthest-apart pair, then runs _FALLBACKSTEPS Bădoiu-Clarkson steps, keeping the best center any of them produced.

The returned radius is _enclosingradius evaluated at the returned center, i.e. exactly the quantity a containment check recomputes, so containment cannot fail by a rounding margin.

_smallest_enclosing_ball_with_certificate(balls; atol, rtol) -> SEBBResult

Internal solver returning the enclosing ball together with its optimality certificate. The support indices in the returned certificate refer to the caller's original input ordering.

Never fails on a valid input: a configuration the exact enumeration cannot resolve falls back to _approximateresult, whose certificate is empty. Use isexactresult to tell the two apart.

_validate_result(result::SEBBResult, balls, tol::Tolerance) -> Bool

Return true when result.ball encloses every ball in balls within tolerance.

active_support(result::SEBBResult) -> Vector{Int}

Return the active (nonzero-slot) support indices of result.

active_weights(result::SEBBResult) -> Vector

Return the active barycentric weights of result.

center(ball::Ball)

Return the center of ball as an SVector.

containment_residual(outer::Ball, inner::Ball)

Return ‖c_outer - c_inner‖ + r_inner - r_outer.

This is nonpositive exactly when inner is contained in outer (up to rounding). The same expression is the internal-tangency residual: it is zero when inner is internally tangent to outer.

encloses(outer::Ball, inner::Ball; atol, rtol) -> Bool

Return true when inner is contained in outer within the scale-aware tolerance.

The containment residual ‖c_outer - c_inner‖ + r_inner - r_outer must not exceed atol + rtol * max(scale, 1), where scale = max(r_outer, r_inner, ‖c_outer - c_inner‖). The scale is purely relative, preserving translation invariance.

isexactresult(result::SEBBResult) -> Bool

Whether result carries an optimality certificate, i.e. whether it came from the exact enumeration rather than from the approximate _fallbackball.

A fallback result has an empty support, which is the only way a caller can tell the two apart: both are guaranteed to enclose every input, but only an exact result is guaranteed minimal.

radius(ball::Ball)

Return the radius of ball.

real_roots(A, B, C, tol::Tolerance) -> QuadraticRoots

Return the real roots of A R^2 + B R + C = 0, robust to degeneracy and cancellation.

The coefficients are normalized by their maximum magnitude. The equation is solved as linear only when the quadratic coefficient is exactly zero; otherwise the cancellation-resistant Citardauq pairing is used, which stays accurate for both roots however small the quadratic term becomes, so no threshold has to decide when a quadratic is "really" linear. A slightly negative discriminant is clamped to zero, coincident roots are deduplicated, and a root that overflows is dropped. Roots come back in ascending order.

smallest_enclosing_ball(centers, radii; atol, rtol) -> Ball

Convenience method taking parallel centers and radii collections. The ambient dimension and a common floating-point type are determined once, and a concretely-typed Vector{Ball{N,T}} is built before delegating to the core method.

smallest_enclosing_ball(balls::AbstractVector{Ball{N,T}}; atol, rtol) -> Ball{N,T}

Compute the unique smallest ball enclosing all input balls in ambient dimension 1, 2, or 3.

The algorithm deterministically enumerates support sets of at most N + 1 balls and solves the associated tangency equations (Fischer & Gärtner 2004). Negative radii and non-finite input are rejected at construction time; zero radii are accepted as degenerate point balls. The returned ball is guaranteed to enclose every input under the arithmetic of the caller (its radius is inflated by any tiny positive containment residual).

Never raises for a valid nonempty input. A configuration whose tangency algebra cannot be resolved at T precision warns once and returns an approximate (still strictly enclosing) ball instead; see _approximateresult.

Tolerances are scale-aware and relative; see Tolerance.

tolerance(tol::Tolerance, scale)

Return the scale-aware absolute threshold atol + rtol * max(scale, 1).

scale is a local geometric quantity (a radius, a relative distance, a normalized coefficient magnitude), never an absolute coordinate norm. Clamping the scale at one keeps a sensible floor for tiny/zero-radius configurations.

fallbackmetisoptions

METIS options used when weighted partitioning fails to split the graph.

The fallback keeps METIS_OPTION_CONTIG = 1 so each partition forms a connected subgraph, and fixes METIS_OPTION_SEED for reproducibility. All other options remain unset, letting METIS choose its defaults.

metisoptions

Default METIS options used by H2Trees.

The options request contiguous partitions, Julia-style 1-based numbering, and a fixed METIS_OPTION_SEED for reproducibility. All other options remain unset, letting METIS choose its defaults.

relaxedmetisoptions

METIS options used when a contiguous partition is infeasible.

METIS_OPTION_CONTIG requiring every partition to be internally connected also requires the input graph itself to already be connected; on a disconnected input graph (e.g. a mesh made of several physically separate pieces), some METIS builds return an error for this instead of silently falling back, so metispartition drops the contiguity constraint entirely as a last resort. METIS_OPTION_SEED is still fixed for reproducibility.

computemetisweights(::Type{T}, weights, targetmax=1000) where {T}

Convert floating-point-like weights into positive integer METIS vertex weights.

The input is transformed with log1p, normalized to [0, 1], scaled by targetmax, and rounded to integers. The output is clamped to be at least 1, as required by METIS.

partition(G::Metis.Graph, nparts::Integer; alg=:KWAY, options=metisoptions, vertexweights=true)

Partition a METIS graph into nparts parts.

This thin wrapper dispatches to either k-way partitioning (alg=:KWAY) or recursive bisection (alg=:RECURSIVE). Set vertexweights=false to ignore G.vwgt. The returned vector contains one partition label per vertex.

metispartition(G::Graphs.SimpleGraph, vertexweights, numberofdivisions::Int; splitunconnectedpartitions=false, alg=:KWAY)

Partition a simple graph using METIS with optional post-processing of disconnected parts.

METIS_OPTION_CONTIG requires the input graph to already be connected; requesting it anyway on a disconnected graph is undefined enough to be unsafe across platforms – some METIS builds return an error, others have been observed to crash natively (a segfault, which no Julia try/catch can intercept). So contiguity is only ever requested when G is actually connected; a disconnected G skips straight to relaxedmetisoptions. When contiguity is requested, weighted partitioning runs first and retries without vertex weights (fallbackmetisoptions) if METIS returns a single part or throws. Optionally, each resulting part can be split into connected components.

(f::BEASTProtrusionFunctor)(center::A, halfsize::T, value::Int) where {T,A<:AbstractVector{T}}

Compute the normalized protrusion of basis function value from a candidate box.

The box is centered at center with scalar halfsize. The returned value is the maximum normalized excess of any support vertex beyond the box boundary, measured over every coordinate direction. A value below or equal to the configured ProtrusionCheck.max means the basis function fits the candidate node closely enough for that protrusion policy.

BlockTree(testspace::BEAST.Space, trialspace::BEAST.Space; builder=BlockTreeBuilder())

Build a Petrov/block tree from a pair of BEAST spaces.

Each side resolves AutoProtrusionCheck() against its own BEAST space before the corresponding TwoNTree is built.

TwoNTree(space::BEAST.Space; builder=TwoNTreeBuilder())

Build a TwoNTree from the function positions of a BEAST space.

The default builder uses the BEAST protrusion policy from defaultprotrusioncheck. Passing NoProtrusionCheck() opts out, and an explicit ProtrusionCheck keeps its max while replacing only the generic point protrusion functor with BEASTProtrusionFunctor(space).

KMeansTree(space::BEAST.Space; builder=KMeansTreeBuilder())

Build a KMeansTree from BEAST.positions(space).

K-means trees use the point positions directly and do not apply a protrusion check.

MetisForest(basis::BEAST.Space; graphweights=adjacencygraph(basis), builder=MetisForestBuilder())

Construct a Forest of MetisTrees from a BEAST.Space.

This method builds (or accepts) a function adjacency graph and graph weights for basis, then delegates to the point/graph MetisForest constructor. The builder carries the METIS construction settings, such as the number of requested divisions per split.

MetisTree(basis::BEAST.Space; graphweights=adjacencygraph(basis), builder=MetisTreeBuilder())

Construct a MetisTree from a BEAST space using METIS graph partitioning.

This method builds (or accepts) a function adjacency graph and graph weights for basis, then delegates to the point/graph MetisTree constructor. The builder carries the METIS construction settings.

adjacencygraph(X::BEAST.Space)

Construct an adjacency graph and corresponding vertex weights for a BEAST space.

Two basis functions are considered adjacent if they are supported on touching mesh elements. The graph weights are assembled from element areas, distributed across all basis functions supported on each element.

buildforest(basis::BEAST.Space; graphweights=nothing, builder=MetisForestBuilder())

Build a METIS forest from a BEAST space using the builder workflow.

When graphweights is omitted, adjacencygraph(basis) supplies both the graph and vertex weights. Passing explicit graph weights reuses them without rebuilding the adjacency graph.

buildtree(testspace::BEAST.Space, trialspace::BEAST.Space; builder=BlockTreeBuilder())

Build a block tree from a BEAST test/trial space pair using builder.

The test and trial builders resolve AutoProtrusionCheck() independently from their corresponding BEAST spaces before delegating to the point-based builder workflow.

buildtree(space::BEAST.Space; builder=TwoNTreeBuilder(), graphweights=nothing)

Build a tree from a BEAST space using an explicit builder.

TwoNTreeBuilder resolves BEAST protrusion defaults as described by defaultprotrusioncheck. KMeansTreeBuilder uses only BEAST.positions(space). MetisTreeBuilder is accepted through this extension's METIS support; graphweights is only valid with that builder.

defaultprotrusioncheck(space::BEAST.Space)

Return the default protrusion policy for a BEAST space.

TwoNTreeBuilder() and each side of BlockTreeBuilder() default to AutoProtrusionCheck(). For a BEAST.Space, that resolves to ProtrusionCheck(; max=0.25, compute=BEASTProtrusionFunctor(space)), so TwoNTree(space)/buildtree(space) work out of the box with the BEAST protrusion check enabled. Pass NoProtrusionCheck() explicitly to opt out, or pass a ProtrusionCheck explicitly to choose a different maximum.

defaultprotrusionfunctor(space::BEAST.Space)

Return the BEAST-aware protrusion functor for space.

This is used when a ProtrusionCheck carries the generic ComputeProtrusionFunctor() sentinel: BEAST spaces replace that generic point functor with BEASTProtrusionFunctor(space) so construction measures protrusion against the actual basis-function support.

_computeradius(center, points, ids)

Return the maximum distance from center to the points indexed by ids.

kmeanswrapper(points, globalpointids, numberofclusters; kwargs...)

Partition a subset of points with ParallelKMeans.kmeans.

globalpointids selects the points to cluster and is preserved in the returned partitions. The result is (partitions, centers, radii), with empty clusters removed before returning.

traceball(center::H2ClusterTree, radius; n=30, kwargs...) where

Returns a trace, which can be used to plot a bounding ball of a BoundingBallTree in PlotlyJS. All 'kwargs' are passed to PlotlyJS.scatter or PlotlyJS.surface, respectively.

Arguments:

• tree::H2ClusterTree: Tree
• node: Cluster to plot.
• kwargs: keyword arguments passed to PlotlyJS

traceball(center::SVector{D,T}, radius; n=30, kwargs...) where {D,T}

Returns a trace, which can be used to plot a bounding ball in PlotlyJS. All 'kwargs' are passed to PlotlyJS.scatter or PlotlyJS.surface, respectively.

Arguments:

• center: Center of the bounding ball.
• radius: Radius of bounding ball.
• kwargs: keyword arguments passed to PlotlyJS

tracecube(tree::H2ClusterTree, node::Int; kwargs...)

Returns a trace, which can be used to plot a cluster of a TwoNTree in PlotlyJS. All 'kwargs' are passed to PlotlyJS.scatter or PlotlyJS.scatter3d, respectively.

Arguments:

• tree::H2ClusterTree: tree
• node::Int: Cluster to plot
• kwargs: keyword arguments passed to PlotlyJS

tracecube(center::SVector{D, T}, halfsize; kwargs...)

Returns a trace, which can be used to plot a bounding box in PlotlyJS. All 'kwargs' are passed to PlotlyJS.scatter or PlotlyJS.scatter3d, respectively.

Arguments:

• center: Center of the bounding box.
• halfsize: Halfsize of the bounding box, which is half of the length of the edge of the bounding box.
• kwargs: keyword arguments passed to PlotlyJS