Module `Bisec_tree.Make`Source

Parameters

module P : Point

Signature

Sourcetype t

A Bisector Tree (BST).

Sourceval create : int -> vp_heuristic -> P.t array -> t

create points create the BST containing all points.

Sourceval sample_distances : int -> P.t array -> float array

sample_distances n points get distances found in n pairs of randomly-chosen points. The result is sorted.

Sourceval nearest_neighbor : P.t -> t -> P.t * float

nearest_neighbor q bst return the distance along with the nearest neighbor to query point q in bst. Warning: there may be several points at this distance from q in bst, but a single (arbitrary) one is returned. If you are not happy with this, use a point type that is deduplicated (i.e. a point that holds the info for all points with the same coordinates).

Sourceval neighbors : P.t -> float -> t -> P.t list

neighbors q tol bst return all points in bst within tol distance from query point q. I.e. all points returned are within (d <= tol) distance from q.

Sourceval to_list : t -> P.t list

to_list bst return the list of points inside bst, in an unspecified order.

Sourceval length : t -> int

length bst return the number of elements inside bst. I.e. how many points are indexed by this bst.

Sourceval is_empty : t -> bool

is_empty bst test if bst is empty.

Sourceval find : P.t -> t -> P.t

find q bst return the first point with distance to q = 0.0.

raises Not_found
if no such element exists. Warning: there may be several points at this distance from q in bst, but a single (arbitrary) one is returned.

Sourceval mem : P.t -> t -> bool

mem q bst return true if q can be found in bst, false otherwise.

Sourceval root : t -> P.t

root bst return the first point found in bst (either a bucket's vantage point or a node's left vantage point).

raises Not_found
if is_empty bst.

Sourceval check : t -> bool

check bst test the invariant of bst. Should always be true. If invariant doesn't hold, then this library has a bug or your P.dist function is not a proper metric.

Sourceval inspect : t -> P.t list

inspect bst extract the vantage points of bst in an unspecified order.

Sourceval dump : int -> t -> (direction list * P.t list) list

dump max_depth bst list points and paths to reach them in the vpt, going down up to max_depth.

package bst

Module Bisec_tree.MakeSource

Parameters

Signature

Module `Bisec_tree.Make`Source