package bst

  1. Overview
  2. Docs
package bst
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module Bisec_tree.MakeSource

Parameters

module P : Point

Signature

Sourcetype t

A Bisector Tree (BST).

Sourceval create : ?progress_callback:(int -> int -> unit) -> int -> vp_heuristic -> P.t array -> t

create k h points create the BST containing all points, using bucket size k and heuristic h. You can provide an optional progress_callback function to give some feedback to the user when indexing many points. If provided, progress_callback will be called upon progression of the indexing as progress_callback x y. x is the current number of points that have been indexed and y is the total number of points to index. The default progress_callback function does nothing.

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 partition : P.t -> float -> t -> P.t list * P.t list

partition q tol bst is like neighbors, but a pair (xs, ys) is returned, such that (d <= tol) for any x and (d > tol) for any y.

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).

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 bst, going down up to max_depth.

Sourceval get_addr : P.t -> t -> step list

get_addr q bst find the address of q in bst.

Sourceval add : P.t -> step list -> t -> t

add p addr bst add point p to bst at given address addr. addr _must_ be a valid address in bst. Call get_addr p bst to get a valid address for p in bst.

Sourceval to_string : t -> string

to_string bst create a string representation/summary for bst