datastruct

package module
v0.0.0-...-fdb942b Latest Latest
Warning

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

 Go to latest Published: Aug 19, 2023 License: Apache-2.0 Imports: 3 Imported by: 2

README

datastruct

A KD tree

A priority list

A bounding box tree

A set

A bit array

Sorry about the lack of documentation - I'll fix it.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Bounds 

func Bounds(points ...[]float64) [][]float64

func Contains 

func Contains(a, b Set) bool

Contains returns true if b is completely contained in a.

func Disjoint 

func Disjoint(a, b Set) bool

Disjoint returns true if a and b share no elements in common.

func InvertSort 

func InvertSort(values []int) []int

InvertSort returns the list of switches that need to be made to render a list of integers into a sorted one.

func Within 

func Within(d1, d2, e float64) bool

Within returns true if the two values are within e of each other.

Types

type BBGrid 

type BBGrid struct {
	Rows, Columns int       // Grid cells down and across
	Min, Max      []float64 // Bounds of the space
	// contains filtered or unexported fields
}

func NewBBGrid 

func NewBBGrid(r, c int, bb [][]float64) *BBGrid

func (*BBGrid) Add 

func (g *BBGrid) Add(id int, bb [][]float64) error

func (*BBGrid) Cell 

func (g *BBGrid) Cell(r, c int) []int

func (*BBGrid) Len 

func (g *BBGrid) Len() int

func (*BBGrid) Location 

func (g *BBGrid) Location(p []float64) (int, int, error)

func (*BBGrid) Range 

func (g *BBGrid) Range(bb [][]float64) []int

func (*BBGrid) Remove 

func (g *BBGrid) Remove(id int)

This is expensive as every cell is checked

type BBNode 

type BBNode struct {
	Id       int
	Depth    int
	BBox     [][]float64
	Parent   *BBNode
	Children []*BBNode
}

func NewBBNode 

func NewBBNode(id int, parent *BBNode, bb [][]float64) *BBNode

func (*BBNode) Contains 

func (bn *BBNode) Contains(pt []float64) bool

func (*BBNode) Decompose 

func (bn *BBNode) Decompose(id int, bb [][]float64)

func (*BBNode) Flatten 

func (bn *BBNode) Flatten() [][][]float64

func (*BBNode) Intersection 

func (bn *BBNode) Intersection(bb [][]float64) [][]float64

Find the bounding box of the intersection of bb with bn.BBox

func (*BBNode) Leaves 

func (bn *BBNode) Leaves() [][][]float64

func (*BBNode) Search 

func (bn *BBNode) Search(pt []float64, path []*BBNode) []*BBNode

type BBTree 

type BBTree struct {
	Root *BBNode
}

func NewBBTree 

func NewBBTree() *BBTree

func (*BBTree) Flatten 

func (bt *BBTree) Flatten() [][][]float64

func (*BBTree) Insert 

func (bt *BBTree) Insert(id int, bb [][]float64)

func (*BBTree) Leaves 

func (bt *BBTree) Leaves() [][][]float64

func (*BBTree) Search 

func (bt *BBTree) Search(pt []float64) []*BBNode

type BRRow 

type BRRow struct {
	Columns  int     // Columns across
	Min, Max float64 // Bounds of the space
	// contains filtered or unexported fields
}

Bounded region row, like BBGrid but for 1D regions

func NewBRRow 

func NewBRRow(c int, b []float64) *BRRow

func (*BRRow) Add 

func (g *BRRow) Add(id int, br []float64) error

func (*BRRow) Cell 

func (g *BRRow) Cell(c int) []int

func (*BRRow) Len 

func (g *BRRow) Len() int

func (*BRRow) Location 

func (g *BRRow) Location(p float64) (int, error)

func (*BRRow) Remove 

func (g *BRRow) Remove(id int)

This is expensive as every column is checked

type Bits 

type Bits []uint64

Bits contains a compact representation of booleans in a uint64.

func BitsFromSlice 

func BitsFromSlice(in []bool) Bits

BitsFromSlice returns Bits initialized with the contents of the boolean slice

func NewBits 

func NewBits(n int) Bits

NewBits allocates a new Bits with the given length rounded up to the nearest whole uint64

func (Bits) Clear 

func (b Bits) Clear(i int)

Reset clears bit i

func (Bits) Get 

func (b Bits) Get(i int) bool

Get returns the state of bit i

func (Bits) Set 

func (b Bits) Set(i int)

Set sets bit i to true

func (Bits) Slice 

func (b Bits) Slice() []bool

Slice returns the bit array as a slice of bool

type KDNode 

type KDNode struct {
	Id    int
	Point []float64
	Left  *KDNode
	Right *KDNode
	Depth int
}

func (*KDNode) Insert 

func (n *KDNode) Insert(dims int, p []float64, axis int) *KDNode

func (*KDNode) Points 

func (n *KDNode) Points() [][]float64

func (*KDNode) String 

func (n *KDNode) String() string

type KDTree 

type KDTree struct {
	Dims  int
	Root  *KDNode
	Nodes []*KDNode
	Dist  func(a, b []float64) float64
}

func NewKDTree 

func NewKDTree(dims int, points ...[]float64) *KDTree

func (*KDTree) Balance 

func (t *KDTree) Balance()

func (*KDTree) DNN 

func (t *KDTree) DNN(pt []float64, d float64) ([][]float64, []float64, []int)

Find all points within d of pt. Note d must in in the same space as the Dist function

func (*KDTree) InOrderPoints 

func (t *KDTree) InOrderPoints() [][]float64

func (*KDTree) Insert 

func (t *KDTree) Insert(pt []float64) int

func (*KDTree) KNN 

func (t *KDTree) KNN(pt []float64, k int) ([][]float64, []float64, []int)

Find up to k nearest points to pt Returns points, distances, indices to kdnodes

func (*KDTree) Points 

func (t *KDTree) Points() [][]float64

Insertion order

func (*KDTree) RemoveById 

func (t *KDTree) RemoveById(id int) bool

func (*KDTree) RemoveByPoint 

func (t *KDTree) RemoveByPoint(pt []float64) bool

Poor man's expensive

func (*KDTree) String 

func (t *KDTree) String() string

type PointGrid 

type PointGrid struct {
	Rows, Columns int       // Grid cells down and across
	Min, Max      []float64 // Bounds of the space
	Wrap          bool      // Whether points should be wrapped in Min, Max
	// contains filtered or unexported fields
}

PointGrid provides a simple way of finding points that are close to eachother.

func NewPointGrid 

func NewPointGrid(rows, columns int, bounds [][]float64, wrap bool) *PointGrid

NewPointGrid creates a new PointGrid with the supplied attributes.

func (*PointGrid) Add 

func (g *PointGrid) Add(p []float64) (int, int, error)

Add adds a point to the appropriate cell and returns its location.

func (*PointGrid) AdjacentCells 

func (g *PointGrid) AdjacentCells(row, column int) [][]float64

AdjacentCells returns the points of the cell and the cells adjacent to it.

func (*PointGrid) Cell 

func (g *PointGrid) Cell(row, column int) [][]float64

Cell returns all the points in it.

func (*PointGrid) Len 

func (g *PointGrid) Len() int

Len returns the number of points stored in the grid.

func (*PointGrid) Location 

func (g *PointGrid) Location(p []float64) (int, int, error)

Location returns the grid location of a point (if it is within range).

func (*PointGrid) NearestPoint 

func (g *PointGrid) NearestPoint(p []float64) ([]float64, float64, error)

NearestPoint looks in the cell containing the point and adjacent cells for the closest point. Returns the point (if any) and its distance or an error. A very poor implementation of nearest neighbor.

type PriorityItem 

type PriorityItem struct {
	Priority float64
	Id       int
}

PriorityItem contains the priority value and an id.

type PriorityList 

type PriorityList []PriorityItem

PriorityList holds the prioritized list of items. The lower the priority, the closer to the start of the list the item is.

func NewPriorityList 

func NewPriorityList(items ...PriorityItem) *PriorityList

NewPriorityList creates a new PriorityList with the items inserted. Lower values are inserted before higher ones.

func (*PriorityList) Delete 

func (pq *PriorityList) Delete(v PriorityItem) bool

Delete removes the entry in the list with the item (if found) and returns true. If the item isn't then false is returned. The priority value in the item is used to find where the item occurs in the list.

func (*PriorityList) DeleteEntry 

func (pq *PriorityList) DeleteEntry(e int) bool

DeleteEntry removes an entry from the list, compacts it and returns true. If the entry is not in range then false is returned.

func (*PriorityList) DeleteId 

func (pq *PriorityList) DeleteId(id int) bool

DeleteId removes the entry in the list with the item id (if found) and returns true. If the id isn't found then false is returned. This function uses a linear scan to find the id.

func (*PriorityList) Insert 

func (pq *PriorityList) Insert(v PriorityItem) int

Insert inserts the item into the list at the correct point and returns that insertion point. Insertion is performed using a binary search and copy() for speed.

func (*PriorityList) Where 

func (pq *PriorityList) Where(v float64, left bool) int

Where returns where an item of priority pri would be inserted. The bool left indicates for priorities of the same value whether the new one should be inserted to the left or right of the current ones.

type Set 

type Set map[int]bool

Set represents a set of integer elements.

func Difference 

func Difference(a, b Set) Set

Difference returns a new set containing only the elements in either a or b but not in both (XOR).

func Intersection 

func Intersection(a, b Set) Set

Intersection returns a new set containing the intersection of a and b (AND).

func NewSet 

func NewSet(elts ...int) Set

NewSet returns a new set with the provided elements in it.

func Sub 

func Sub(a, b Set) Set

Sub returns a new set containing the elements in a which are not in b (SUB).

func Union 

func Union(a, b Set) Set

Union returns a new set containing the union of a and b (OR).

func (Set) Add 

func (s Set) Add(e int) bool

Add adds the element e to the set and returns true if it wasn't already in the set. Adding an element when it already exists is a no-op signified by false.

func (Set) Contains 

func (s Set) Contains(b Set) bool

Contains returns true if b is completely contained in the set.

func (Set) Copy 

func (s Set) Copy() Set

Copy makes a copy of the set.

func (Set) Difference 

func (s Set) Difference(b Set) Set

Difference returns a new set containing only the elements in either the set or b but not in both (XOR).

func (Set) Disjoint 

func (s Set) Disjoint(b Set) bool

Disjoint returns true if the set and b share no elements in common.

func (Set) Element 

func (s Set) Element(e int) bool

Element returns true if the set contains the element e.

func (Set) Empty 

func (s Set) Empty() bool

Empty returns true if the set is the empty set.

func (Set) Intersection 

func (s Set) Intersection(b Set) Set

Intersection returns a new set containing the intersection of the set and b (AND).

func (Set) Len 

func (s Set) Len() int

Len returns the number of elements in the set.

func (Set) Purge 

func (s Set) Purge()

Purge clears out removed entries from the set.

func (Set) Remove 

func (s Set) Remove(e int) bool

Remove removes element e from the set, if it exists by setting it to false, and returns true if it was in the set. Removing a non-existent element is a no-op signified by false. Use Purge() to actually shrink the set.

func (Set) Slice 

func (s Set) Slice() []int

Slice returns an unsorted slice representation of the set.

func (Set) String 

func (s Set) String() string

String returns a string representation of the set.

func (Set) Sub 

func (s Set) Sub(b Set) Set

Sub returns a new set containing the elements in the set which are not in b (SUB).

func (Set) Union 

func (s Set) Union(b Set) Set

Union returns a new set containing the union of the set and b (OR).

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.