structures

package
v0.0.0-...-d99e8d0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Apr 24, 2018 License: MIT Imports: 5 Imported by: 0

Documentation

Overview

Kdtree is a very simple K-D tree implementation. This implementation uses a fixed value for K. The intention is to copy the code locally, change K to your needs, and change T.Data's type to suit your needs too.

This file was originally created by John Lindsay<jlindsay@uoguelph.ca>, March. 2015.

Index

Constants

View Source
const K = 2

K is the dimensionality of the points in this package's K-D trees.

Variables

View Source
var ArrayLengthError = errors.New("Incorrect array length: The specified data array must have rows * columns elements.")

errors

View Source
var NoDataError = errors.New("There has been an attempt to access a cell beyond the grid edges.")

Functions

func Create2dBoolArray

func Create2dBoolArray(rows, columns int) [][]bool

This can be used to create a 2d array of bool type in a way that guarantees that the allocations is localized in memory.

func Create2dByteArray

func Create2dByteArray(rows, columns int) [][]byte

This can be used to create a 2d array of byte type in a way that guarantees that the allocations is localized in memory.

func Create2dFloat64Array

func Create2dFloat64Array(rows, columns int) [][]float64

This can be used to create a 2d array of float64 type in a way that guarantees that the allocations is localized in memory.

func Create2dIntArray

func Create2dIntArray(rows, columns int) [][]int

This can be used to create a 2d array of int type in a way that guarantees that the allocations is localized in memory.

func Create2dStringArray

func Create2dStringArray(rows, columns int) [][]string

This can be used to create a 2d array of string type in a way that guarantees that the allocations is localized in memory.

Types

type PQType

type PQType int

PQType represents a priority queue ordering kind (see MAXPQ and MINPQ)

const (
	MAXPQ PQType = iota
	MINPQ
)

type PQueue

type PQueue struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

PQueue is a heap priority queue data structure implementation. It can be whether max or min ordered and it is synchronized and is safe for concurrent operations.

func NewPQueue

func NewPQueue(pqType PQType) *PQueue

NewPQueue creates a new priority queue with the provided pqtype ordering type

func (*PQueue) Len

func (pq *PQueue) Len() int

func (*PQueue) Pop

func (pq *PQueue) Pop() interface{}

Pop and returns the highest/lowest priority item (depending on whether you're using a MINPQ or MAXPQ) from the priority queue

func (*PQueue) Push

func (pq *PQueue) Push(value interface{}, priority int)

Push the value item into the priority queue with provided priority.

type ParallelRectangularArrayByte

type ParallelRectangularArrayByte struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

A fine-grained concurrent rectangular shaped array (matrix) of byte type. The array is thread-safe and uses mutexes on each cell.

func NewParallelRectangularArrayByte

func NewParallelRectangularArrayByte(rows, columns int) *ParallelRectangularArrayByte

func (*ParallelRectangularArrayByte) Decrement

func (r *ParallelRectangularArrayByte) Decrement(row, column int, value byte)

Decrements an individual cell value in the matrix.

func (*ParallelRectangularArrayByte) DecrementAndReturn

func (r *ParallelRectangularArrayByte) DecrementAndReturn(row, column int, value byte) byte

Decrements an individual cell value in the matrix and return the value.

func (*ParallelRectangularArrayByte) GetColumns

func (r *ParallelRectangularArrayByte) GetColumns() int

Returns the number of columns

func (*ParallelRectangularArrayByte) GetRowData

func (r *ParallelRectangularArrayByte) GetRowData(row int) []byte

func (*ParallelRectangularArrayByte) GetRows

func (r *ParallelRectangularArrayByte) GetRows() int

Returns the number of rows

func (*ParallelRectangularArrayByte) Increment

func (r *ParallelRectangularArrayByte) Increment(row, column int, value byte)

Increments an individual cell value in the matrix.

func (*ParallelRectangularArrayByte) IncrementAndReturn

func (r *ParallelRectangularArrayByte) IncrementAndReturn(row, column int, value byte) byte

Increments an individual cell value in the matrix and return the value.

func (*ParallelRectangularArrayByte) InitializeWithConstant

func (r *ParallelRectangularArrayByte) InitializeWithConstant(value byte)

Initializes all cells with a constant value.

func (*ParallelRectangularArrayByte) InitializeWithData

func (r *ParallelRectangularArrayByte) InitializeWithData(values []byte) error

Sets the data based on an existing array.

func (*ParallelRectangularArrayByte) SetRowData

func (r *ParallelRectangularArrayByte) SetRowData(row int, values []byte)

func (*ParallelRectangularArrayByte) SetValue

func (r *ParallelRectangularArrayByte) SetValue(row, column int, value byte)

Sets an individual cell value in the matrix.

func (*ParallelRectangularArrayByte) Value

func (r *ParallelRectangularArrayByte) Value(row, column int) byte

Retrives an individual cell value in the matrix.

type ParallelRectangularArrayFloat64

type ParallelRectangularArrayFloat64 struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

A fine-grained concurrent rectangular shaped array (matrix) of float64 type. The array is thread-safe and uses mutexes on each cell.

func NewParallelRectangularArrayFloat64

func NewParallelRectangularArrayFloat64(rows, columns int, nodata float64) *ParallelRectangularArrayFloat64

func (*ParallelRectangularArrayFloat64) Decrement

func (r *ParallelRectangularArrayFloat64) Decrement(row, column int, value float64)

Decrements an individual cell value in the matrix.

func (*ParallelRectangularArrayFloat64) DecrementAndReturn

func (r *ParallelRectangularArrayFloat64) DecrementAndReturn(row, column int, value float64) float64

Decrements an individual cell value in the matrix.

func (*ParallelRectangularArrayFloat64) GetColumns

func (r *ParallelRectangularArrayFloat64) GetColumns() int

Returns the number of columns

func (*ParallelRectangularArrayFloat64) GetNodata

Returns the nodata value

func (*ParallelRectangularArrayFloat64) GetRowData

func (r *ParallelRectangularArrayFloat64) GetRowData(row int) []float64

Returns an entire row of values.

func (*ParallelRectangularArrayFloat64) GetRows

func (r *ParallelRectangularArrayFloat64) GetRows() int

Returns the number of rows

func (*ParallelRectangularArrayFloat64) Increment

func (r *ParallelRectangularArrayFloat64) Increment(row, column int, value float64)

Increments an individual cell value in the matrix.

func (*ParallelRectangularArrayFloat64) IncrementAndReturn

func (r *ParallelRectangularArrayFloat64) IncrementAndReturn(row, column int, value float64) float64

Increments an individual cell value in the matrix.

func (*ParallelRectangularArrayFloat64) InitializeWithConstant

func (r *ParallelRectangularArrayFloat64) InitializeWithConstant(value float64)

Initializes all cells with a constant value.

func (*ParallelRectangularArrayFloat64) InitializeWithData

func (r *ParallelRectangularArrayFloat64) InitializeWithData(values []float64) error

Sets the data based on an existing array.

func (*ParallelRectangularArrayFloat64) SetNodata

func (r *ParallelRectangularArrayFloat64) SetNodata(value float64)

Sets the nodata value

func (*ParallelRectangularArrayFloat64) SetRowData

func (r *ParallelRectangularArrayFloat64) SetRowData(row int, values []float64)

Sets and entire row of values.

func (*ParallelRectangularArrayFloat64) SetValue

func (r *ParallelRectangularArrayFloat64) SetValue(row, column int, value float64)

Sets an individual cell value in the matrix.

func (*ParallelRectangularArrayFloat64) Value

func (r *ParallelRectangularArrayFloat64) Value(row, column int) float64

Retrives an individual cell value in the matrix.

type Point

type Point [K]float64

A Point is a location in K-dimensional space.

type RectangularArrayByte

type RectangularArrayByte struct {
	// contains filtered or unexported fields
}

A rectangular shaped array (matrix) of byte type. The array is not thread-safe. See ParallelRectangularArrayByte for a thread-safe implementation

func NewRectangularArrayByte

func NewRectangularArrayByte(rows, columns int) *RectangularArrayByte

func (*RectangularArrayByte) Decrement

func (r *RectangularArrayByte) Decrement(row, column int, values ...byte)

Decrements an individual cell value in the matrix.

func (*RectangularArrayByte) GetColumns

func (r *RectangularArrayByte) GetColumns() int

Returns the number of columns

func (*RectangularArrayByte) GetRowData

func (r *RectangularArrayByte) GetRowData(row int) []byte

func (*RectangularArrayByte) GetRows

func (r *RectangularArrayByte) GetRows() int

Returns the number of rows

func (*RectangularArrayByte) Increment

func (r *RectangularArrayByte) Increment(row, column int, values ...byte)

Increments an individual cell value in the matrix.

func (*RectangularArrayByte) InitializeWithConstant

func (r *RectangularArrayByte) InitializeWithConstant(value byte)

Initializes all cells with a constant value.

func (*RectangularArrayByte) InitializeWithData

func (r *RectangularArrayByte) InitializeWithData(values []byte) error

Sets the data based on an existing array.

func (*RectangularArrayByte) SetRowData

func (r *RectangularArrayByte) SetRowData(row int, values []byte)

func (*RectangularArrayByte) SetValue

func (r *RectangularArrayByte) SetValue(row, column int, value byte)

Sets an individual cell value in the matrix.

func (*RectangularArrayByte) Value

func (r *RectangularArrayByte) Value(row, column int) byte

Retrives an individual cell value in the matrix.

type RectangularArrayFloat64

type RectangularArrayFloat64 struct {
	// contains filtered or unexported fields
}

A rectangular shaped array (matrix) of float64 type. The array is thread-safe.

func NewRectangularArrayFloat64

func NewRectangularArrayFloat64(rows, columns int, nodata float64) *RectangularArrayFloat64

func (*RectangularArrayFloat64) Decrement

func (r *RectangularArrayFloat64) Decrement(row, column int, values ...float64)

Decrements an individual cell value in the matrix.

func (*RectangularArrayFloat64) GetColumns

func (r *RectangularArrayFloat64) GetColumns() int

Returns the number of columns

func (*RectangularArrayFloat64) GetNodata

func (r *RectangularArrayFloat64) GetNodata() float64

Returns the nodata value

func (*RectangularArrayFloat64) GetRowData

func (r *RectangularArrayFloat64) GetRowData(row int) []float64

Returns an entire row of values.

func (*RectangularArrayFloat64) GetRows

func (r *RectangularArrayFloat64) GetRows() int

Returns the number of rows

func (*RectangularArrayFloat64) Increment

func (r *RectangularArrayFloat64) Increment(row, column int, values ...float64)

Increments an individual cell value in the matrix.

func (*RectangularArrayFloat64) InitializeWithConstant

func (r *RectangularArrayFloat64) InitializeWithConstant(value float64)

Initializes all cells with a constant value.

func (*RectangularArrayFloat64) InitializeWithData

func (r *RectangularArrayFloat64) InitializeWithData(values []float64) error

Sets the data based on an existing array.

func (*RectangularArrayFloat64) SetNodata

func (r *RectangularArrayFloat64) SetNodata(value float64)

Sets the nodata value

func (*RectangularArrayFloat64) SetRowData

func (r *RectangularArrayFloat64) SetRowData(row int, values []float64)

Sets and entire row of values.

func (*RectangularArrayFloat64) SetValue

func (r *RectangularArrayFloat64) SetValue(row, column int, value float64)

Sets an individual cell value in the matrix.

func (*RectangularArrayFloat64) Value

func (r *RectangularArrayFloat64) Value(row, column int) float64

Retrives an individual cell value in the matrix.

type T

type T struct {
	// Point is the K-dimensional point associated with the
	// data of this node.
	Point
	// Data is auxiliary data associated with the point of this node.
	Data interface{}
	// contains filtered or unexported fields
}

A T is a the node of a K-D tree. A *T is the root of a K-D tree, and nil is an empty K-D tree.

func New

func New(nodes []*T) *T

New returns a new K-D tree built using the given nodes. Building a new tree with nodes that are already members of K-D trees invalidates those trees.

func (*T) Height

func (t *T) Height() int

Height returns the height of the K-D tree.

func (*T) InRange

func (t *T) InRange(pt Point, dist float64, nodes []*T) []*T

InRange appends all nodes in the K-D tree that are within a given distance from the given point to the given slice, which may be nil. To avoid allocation, the slice can be pre-allocated with a larger capacity and re-used across multiple calls to InRange.

func (*T) Insert

func (t *T) Insert(n *T) *T

Insert returns a new K-D tree with the given node inserted. Inserting a node that is already a member of a K-D tree invalidates that tree.

func (T) String

func (t T) String() string

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL