ds

package module
v0.0.0-...-53c60ec Latest Latest
Warning

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

 Go to latest Published: Aug 8, 2023 License: Apache-2.0 Imports: 7 Imported by: 1

README

A collection of data structures

Docs

Documentation

Overview

Collection of data structures and algorithms. Most are available elsewhere with better testing and performance. We reinvent the wheel for fun and practice.

Index

Constants

View Source 
const QueueDefaultSize = 16

Variables

This section is empty.

Functions

func GetMapKeysSorted 

func GetMapKeysSorted[K constraints.Ordered, V any](m map[K]V) []K

Get the keys of a map sorted by key value

func PathSearchNoHeuristic 

func PathSearchNoHeuristic(a, b Node) int

Used in PathSearch in place of an actual heuristic function. Returns 0.

func SortMapByValue 

func SortMapByValue[K constraints.Ordered, V any](m map[K]V, sortFn func(a, b V) bool) []K

Get the keys of a map sorted by the map value. Provide a function to do the value sort test.

Types

type GraphNode 

type GraphNode[T any] struct {
	K    NodeKey
	Data T
	// contains filtered or unexported fields
}

A generic implementation of Node. GraphNodes can hold any data. The transition weights (costs) are positive ints.

func NewGraphNode 

func NewGraphNode[T any](data T, key NodeKey) *GraphNode[T]

func (*GraphNode[T]) Cost 

func (g *GraphNode[T]) Cost(node Node) int

Cost of moving into this node.

func (*GraphNode[T]) Key 

func (g *GraphNode[T]) Key() NodeKey

func (*GraphNode[T]) LinkBidirectional 

func (g *GraphNode[T]) LinkBidirectional(node *GraphNode[T], costTo, costBack int)

Set node as neighbour of current node and current node as neighbour of node.

func (*GraphNode[T]) LinkTo 

func (g *GraphNode[T]) LinkTo(node *GraphNode[T], cost int)

Set node as neighbour of current node.

func (*GraphNode[T]) Neighbours 

func (g *GraphNode[T]) Neighbours() []Node

Get neighbours of node.

type Grid 

type Grid[T any] struct {
	// contains filtered or unexported fields
}

A generic grid for pathfinding.

func NewGrid 

func NewGrid[T any](w, h int) *Grid[T]

Construct a new grid with given dimensions.

func (*Grid[T]) Dimensions 

func (g *Grid[T]) Dimensions() (x, y int)

Return grid width and height.

func (*Grid[T]) Get 

func (g *Grid[T]) Get(x, y int) T

Return grid contents at x,y.

func (*Grid[T]) GetCost 

func (g *Grid[T]) GetCost(x, y int) int

Get cost needed to move into x,y.

func (*Grid[T]) GetFromNodeKey 

func (g *Grid[T]) GetFromNodeKey(key NodeKey) (int, int)

Returns x,y from a NodeKey

func (*Grid[T]) GetNode 

func (g *Grid[T]) GetNode(x, y int) GridNode[T]

Convert a cell into a GridNode which can be used as input in the path search methods.

func (*Grid[T]) InBounds 

func (g *Grid[T]) InBounds(x, y int) bool

Are the coords x,y valid.

func (*Grid[T]) IsBlocked 

func (g *Grid[T]) IsBlocked(x, y int) bool

Check if cell is blocked (inaccessible to pathfinding).

func (*Grid[T]) Set 

func (g *Grid[T]) Set(x, y int, data T)

Store data to grid cell x,y.

func (*Grid[T]) SetAll 

func (g *Grid[T]) SetAll(data T)

Set all grid cells to the same value.

func (*Grid[T]) SetAllCosts 

func (g *Grid[T]) SetAllCosts(cost int)

Set all travel costs to the same value.

func (*Grid[T]) SetBlocked 

func (g *Grid[T]) SetBlocked(x, y int)

Set grid cell to blocked. Blocked cells are ignored when pathfinding.

func (*Grid[T]) SetCost 

func (g *Grid[T]) SetCost(x, y, cost int)

Store travel cost to enter grid cell x,y.

func (*Grid[T]) SetNeighbourHoodMode4 

func (g *Grid[T]) SetNeighbourHoodMode4()

Set neighbourhood mode to 4 neighbours (top, bot, left, right). Cost of traveling to neighbours is the whatever the Cost() of that cell is.

func (*Grid[T]) SetNeighbourHoodMode8 

func (g *Grid[T]) SetNeighbourHoodMode8(dcost float32)

Set neighbourhood mode to 8 neighbours (top, bot, left, right, top-left, top-right, bot-left, bot-right). When moving diagonally, cost is calculated as cell cost multiplied by dcost (typically sqrt(2)).

func (*Grid[T]) SetUnBlocked 

func (g *Grid[T]) SetUnBlocked(x, y, cost int)

Set grid cell to unblocked. Provide a travel cost for the unblocked cell. Unblocked cells can be traversed when pathfinding.

func (*Grid[T]) String 

func (g *Grid[T]) String() string

type GridNode 

type GridNode[T any] struct {
	// contains filtered or unexported fields
}

GridNode satisfies Node interface so it can be used for pathfinding. Grid can convert its cells to a GridNode using GetNode.

func (*GridNode[T]) Cost 

func (g *GridNode[T]) Cost(node Node) int

Returns the cost of traveling from this current node to node. It is taken from the Cost() method of the grid data at the node's (destination's) location. If current and node are diagonal, the cost is multiplied by a diagonal cost multiplier (controlled with Grid.SetNeighbourHoodMode8).

func (*GridNode[T]) Key 

func (g *GridNode[T]) Key() NodeKey

Grid cells are uniquly identifiable by their x,y coords. We combine into one key using the index formula: y*width+x.

func (*GridNode[T]) Neighbours 

func (g *GridNode[T]) Neighbours() []Node

Get the neighbours of this node. Will return 4 if grid is set to fourNeibourhood(4N) or 8 if set to eightNeibourhood(8N). Edges of the grid will return 3(4N)/5(8N) nodes and corners will return 2(4N)/3(8N) nodes.

type Heap 

type Heap[T HeapNode] struct {
	// contains filtered or unexported fields
}

A binary heap implemented with an array. It is a max heap by default, but can be changed to a min heap. Switching can happen in place if needed, at cost O(n). It accepts data that implements the HeapNode interface.

func NewHeap 

func NewHeap[T HeapNode](data []T, minHeap bool) *Heap[T]

Creates a new Heap of type T.

func (*Heap[T]) IsEmpty 

func (h *Heap[T]) IsEmpty() bool

Is the Heap empty?

func (*Heap[T]) PeekTop 

func (h *Heap[T]) PeekTop() T

Return the top of the heap without removing it.

func (*Heap[T]) Pop 

func (h *Heap[T]) Pop() T

Remove the item at the top of the heap.

func (*Heap[T]) Push 

func (h *Heap[T]) Push(val T)

Push an item to the heap.

func (*Heap[T]) SetMaxHeapMode 

func (h *Heap[T]) SetMaxHeapMode()

Max priority at the top of the heap. Will reorganize elements if needed. Max is the default.

func (*Heap[T]) SetMinHeapMode 

func (h *Heap[T]) SetMinHeapMode()

Min priority at the top of the heap. Will reorganize elements if needed.

type HeapNode 

type HeapNode interface {
	Priority() int
}

Data going in Heap must implement Priority() which lets the Heap decide which element is on top.

type MappedSlice 

type MappedSlice[ST any, MT comparable] struct {
	S []ST
	M map[MT]mappedSliceRange
}

MappedSlice is an indexed slice. It can be used to retrieve specific sub-portions of the slice without searching. Can be used in cases where map-like access is required (where a map would be appropriate) and the whole slice is often iterated upon (where a slice is faster than a map). Can also be used to store multiple small slices in a continuous piece of memory.

func (*MappedSlice[ST, MT]) AddMapped 

func (i *MappedSlice[ST, MT]) AddMapped(data ST, key MT)

Add data and index it with key.

func (*MappedSlice[ST, MT]) AddSliceMapped 

func (i *MappedSlice[ST, MT]) AddSliceMapped(data []ST, key MT)

Add a data slice and index it with a key.

func (MappedSlice[ST, MT]) Get 

func (i MappedSlice[ST, MT]) Get(key MT) []ST

Get slice portion indexed with key.

func (MappedSlice[ST, MT]) New 

func (i MappedSlice[ST, MT]) New() MappedSlice[ST, MT]

type Node 

type Node interface {
	Key() NodeKey
	// Gets the neighbours of node
	Neighbours() []Node
	// Cost of going to node. Return negative cost if Node is not a neighbour
	Cost(Node) int
}

Node is the interface of a graph node. See GraphNode for a generic implementation.

type NodeKey 

type NodeKey int

Identifier for graph nodes.

func PathSearch 

func PathSearch(start, end Node, heuristic func(a, b Node) int) []NodeKey

Search for a path to a specific node. Faster than PathSearchAll since it can exit as soon as it reaches the destination. Pass a heuristic funcion to prioritize node evaluation. For example, on a grid, the heuristic can be the Manhattan distance of the two nodes which turns PathSearch into A*. Pass PathSearchNoHeuristic to do Dijkstra with early exit.

type Paths 

type Paths struct {
	Start NodeKey
	// contains filtered or unexported fields
}

Paths is the result of running PathSearchAll and stores all paths starting at node Start. To get a path to a specific destination use PathTo.

func PathSearchAll 

func PathSearchAll(start Node) Paths

Search all paths starting at node. Uses Dijkstra's method. Returns a Paths object which contains a map with destination->source entries. Use Paths.PathTo() to get paths from start to specific nodes.

func (Paths) PathTo 

func (p Paths) PathTo(node NodeKey) []NodeKey

Get the path to a specific node.

type Queue 

type Queue[T any] struct {
	// contains filtered or unexported fields
}

FIFO Q

func (*Queue[T]) DataLength 

func (q *Queue[T]) DataLength() int

Length of data in the q.

func (*Queue[T]) Init 

func (q *Queue[T]) Init(size int)

Initialize q to a size. Will delete existing data.

func (*Queue[T]) Pop 

func (q *Queue[T]) Pop() (T, error)

Get and remove last oldest element.

func (*Queue[T]) Push 

func (q *Queue[T]) Push(data T)

Add to the q.

func (*Queue[T]) SetResizeChunk 

func (q *Queue[T]) SetResizeChunk(i int)

How much to increase the q by when it runs out of space.

type Set 

type Set[T comparable] struct {
	// contains filtered or unexported fields
}

A map implementation of a set. Important set operations are currently missing (intersect, diff, union).

func NewSet 

func NewSet[T comparable]() *Set[T]

Initialize a new set.

func (*Set[T]) Add 

func (s *Set[T]) Add(item T)

Add item to the set.

func (*Set[T]) Cardinality 

func (s *Set[T]) Cardinality() int

Number of items it the set.

func (*Set[T]) Has 

func (s *Set[T]) Has(item T) bool

Is item in the set?

func (*Set[T]) Length 

func (s *Set[T]) Length() int

Same as Cardinality.

func (*Set[T]) Remove 

func (s *Set[T]) Remove(item T)

Remove item from set. Remove is a O(1) operation but does not release used memory.

type Stack 

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

A LIFO stack.

func (*Stack) Peek 

func (s *Stack) Peek() any

Get the top of the q without removing it.

func (*Stack) Pop 

func (s *Stack) Pop() any

Remove and return topmost data.

func (*Stack) Push 

func (s *Stack) Push(v any)

Push data in the q.

func (*Stack) Shrink 

func (s *Stack) Shrink()

Shrink reallocates the stack so it doesn't have unused space.

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.