Class Batfish::BKTree
In: lib/data/bktree.rb
Parent: Object

A BK-tree is a datastructure used for nearest neighbor lookup in a metric space. A metric space is any space with the following properties:

  • d(x,y) = 0 <=> x = y
  • d(x,y) = d(y,x)
  • d(x,z) <= d(x,y) + d(y,z)

To use this datastructure, the objects added to it must have a distance_to(other) class method defined.

Methods

<<   add   empty?   fetch_near   fetch_nearest   include?   include_near?   min_dist   new  

Classes and Modules

Class Batfish::BKTree::Node

Attributes

root  [R] 

Public Class methods

new()

Initialize a BKTree.

[Source]

# File lib/data/bktree.rb, line 19
    def initialize
      @root = nil
    end

Public Instance methods

<<(obj)

Alias for add

add(obj)

Add an object to the tree. Returns the tree itself so several adds may be chained together.

[Source]

# File lib/data/bktree.rb, line 26
    def add(obj)
      if @root
        @root.add(obj)
      else
        @root = Node.new(obj)
      end
      return self
    end
empty?()

Returns true if the tree is empty.

[Source]

# File lib/data/bktree.rb, line 37
    def empty?
      return @root.nil? ? true : false
    end
fetch_near(obj, threshold) {|item| ...}

Returns an array containing all object within threshold distance of the given object. If a block is given, it is called once for each objects within threshold distance of the given object.

[Source]

# File lib/data/bktree.rb, line 63
    def fetch_near(obj, threshold)
      objs = []
      @root.fetch_near(obj, threshold) do |item|
        yield(item) if block_given? 
        objs << item
      end
      return objs
    end
fetch_nearest(obj) {|item| ...}

Returns the nearest object to the given object.

[Source]

# File lib/data/bktree.rb, line 74
    def fetch_nearest(obj)
      threshold = 0
      nearests = []
      while nearests.empty?
        self.fetch_near(obj, threshold) do |item|
          yield(item) if block_given? 
          nearests << item
        end
        threshold += 1
      end
      return nearests
    end
include?(obj)

Returns true if the given object is present in the tree.

[Source]

# File lib/data/bktree.rb, line 43
    def include?(obj)
      self.include_near?(obj, 0)
    end
include_near?(obj, threshold)

Return true if the given object is within threshold distance of an object in the tree.

[Source]

# File lib/data/bktree.rb, line 50
    def include_near?(obj, threshold)
      self.fetch_near(obj, threshold) do
        return true
      end
      return false
    end
min_dist(obj)

Returns the minimum distance between the given object and an object in the tree.

[Source]

# File lib/data/bktree.rb, line 90
    def min_dist(obj)
      threshold = 0
      while !self.include_near?(obj, threshold)
        threshold += 1
      end
      return threshold
    end

[Validate]