memds

package
v0.2.1 Latest Latest
Warning

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

 Go to latest Published: Feb 9, 2024 License: MIT Imports: 8 Imported by: 0

README

In-Memory Data Structures

Documentation

Index

Constants

View Source 
const (
	ThreadSafe   = ThreadSafety(true)
	ThreadUnsafe = ThreadSafety(false)
)

Variables

View Source 
var (
	ErrSelfEdgeNotSupportedYet        = errors.New("self edge not supported yet")
	ErrNodeNotFound                   = errors.New("node not found")
	ErrUnsupportedSingleNodeRetrieval = errors.New("unsupported single node retrieval")
)
View Source 
var (
	ErrInvalidOrOutOfBoundsNodeId = errors.New("invalid or out of bound node id")
	ErrSrcNodeNotExist            = errors.New("source node does not exist")
	ErrDestNodeNotExist           = errors.New("destination node does not exist")
)
View Source 
var (
	ErrFullGraph32 = errors.New("Graph32 is full")
)
View Source 
var (
	ErrFullMap32 = errors.New("Map32 is full")
)
View Source 
var (
	ErrNodeSameStringDataAlreadyInGraph = errors.New("a node with the same data is already in the graph")
)
View Source 
var (
	ErrOutOfBoundsBit32Index = errors.New("out of bounds Bit32Index")
)

Functions

This section is empty.

Types

type ArrayQueue 

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

thread unsafe array queue.

func NewArrayQueue 

func NewArrayQueue[T any]() *ArrayQueue[T]

func (*ArrayQueue[T]) Clear 

func (q *ArrayQueue[T]) Clear()

Clear removes all elements from the queue.

func (*ArrayQueue[T]) Dequeue 

func (q *ArrayQueue[T]) Dequeue() (value T, ok bool)

Dequeue removes first element of the queue and returns it, or nil if queue is empty. Second return parameter is true, unless the queue was empty and there was nothing to dequeue.

func (*ArrayQueue[T]) Empty 

func (q *ArrayQueue[T]) Empty() bool

Empty returns true if queue does not contain any elements.

func (*ArrayQueue[T]) Enqueue 

func (q *ArrayQueue[T]) Enqueue(value T)

Enqueue adds a value to the end of the queue.

func (*ArrayQueue[T]) ForEachElem 

func (q *ArrayQueue[T]) ForEachElem(fn func(i int, e T) error) error

func (*ArrayQueue[T]) Iterator 

func (q *ArrayQueue[T]) Iterator() *ArrayQueueIterator[T]

func (*ArrayQueue[T]) Peek 

func (q *ArrayQueue[T]) Peek() (value T, ok bool)

Peek returns first element of the queue without removing it, or nil if queue is empty. Second return parameter is true, unless the queue was empty and there was nothing to peek.

func (*ArrayQueue[T]) Size 

func (q *ArrayQueue[T]) Size() int

Size returns the number of elements within the queue.

func (*ArrayQueue[T]) Values 

func (q *ArrayQueue[T]) Values() []T

Values returns all elements in the queue (FIFO order).

type ArrayQueueIterator 

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

thread unsafe array queue iterator

func (*ArrayQueueIterator[T]) Index 

func (it *ArrayQueueIterator[T]) Index() int

func (*ArrayQueueIterator[T]) Next 

func (it *ArrayQueueIterator[T]) Next() bool

func (*ArrayQueueIterator[T]) Value 

func (it *ArrayQueueIterator[T]) Value() T

type Bit32Index 

type Bit32Index uint8

type BitSet32 

type BitSet32 uint32

A BitSet32 is a bit set that performs no allocations and can store up to 32 bits.

func (*BitSet32) CountSet 

func (s *BitSet32) CountSet() int

func (*BitSet32) ForEachSet 

func (s *BitSet32) ForEachSet(fn func(index Bit32Index) error) error

func (*BitSet32) IsSet 

func (s *BitSet32) IsSet(index Bit32Index) bool

func (*BitSet32) Set 

func (s *BitSet32) Set(index Bit32Index)

func (*BitSet32) SetAll 

func (s *BitSet32) SetAll()

func (*BitSet32) Unset 

func (s *BitSet32) Unset(index Bit32Index)

type DirectedGraph 

type DirectedGraph[NodeData, EdgeData any, InternalData any] struct {
	// contains filtered or unexported fields
}

DirectedGraph is a directed graph.

func NewDirectedGraph 

func NewDirectedGraph[NodeData, EdgeData any](threadSafety ThreadSafety) *DirectedGraph[NodeData, EdgeData, struct{}]

NewDirectedGraph returns a DirectedGraph with no special abilities.

func NewDirectedGraphUniqueString 

func NewDirectedGraphUniqueString[NodeData ~string, EdgeData any](threadSafety ThreadSafety) *DirectedGraph[NodeData, EdgeData, map[NodeData]NodeId]

NewDirectedGraphUniqueString returns a directed graph that supports WithData, adding two nodes with the same data is forbidden.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) AddNode 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) AddNode(data NodeData) NodeId

AddNode creates an node with the passed data and returns the new node's id. Node ids start at 0.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) CountSourceNodes 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) CountSourceNodes(id NodeId) int

CountToTo returns the number of nodes in g that can reach directly to n.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) DestinationIds 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) DestinationIds(id NodeId) []NodeId

From returns the ids of nodes in g that can be reached directly from n.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) DestinationNodes 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) DestinationNodes(id NodeId) []GraphNode[NodeData]

From returns all nodes in g that can be reached directly from n.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) Edge 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) Edge(srcId, destId NodeId) (GraphEdge[EdgeData], bool)

Edge returns the edge from srcId to destId if such an edge exists. The destination node must be directly reachable from the source node.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) EdgeCount 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) EdgeCount() int64

func (*DirectedGraph[NodeData, EdgeData, InternalData]) Edges 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) Edges() []GraphEdge[EdgeData]

Edges returns all the edges in the graph.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) GetNode 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) GetNode(retrievalType SingleNodeRetrievalType, data any) (node GraphNode[NodeData], finalErr error)

GetNode retrieves a node using the specified retrieval type or returns the error ErrNodeNotFound. If the retrieval type is not supported ErrUnsupportedSingleNodeRetrieval is returned.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) HasCycleOrCircuit 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) HasCycleOrCircuit() bool

(WIP) HasCycleOrCircuit detects if there is a cycle or a circuit in g, time complexity is O(N^2), space complexity is O(N). HasCycleOrCircuit only uses two bitsets of size ~N.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) HasEdgeBetween 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) HasEdgeBetween(xid, yid NodeId) bool

HasEdgeBetween returns whether an edge exists between nodes x and y without considering direction.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) HasEdgeFromTo 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) HasEdgeFromTo(srcId, destId NodeId) bool

HasEdgeFromTo returns whether an edge exists in the graph from srcId to destId.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) HasNode 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) HasNode(retrievalType SingleNodeRetrievalType, data any) (found bool, finalErr error)

HasNode determines if a node existing using the specified retrieval type. If the retrieval type is not supported ErrUnsupportedSingleNodeRetrieval is returned.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) LongestPath 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) LongestPath() (nodesInPath []NodeId, pathLength int)

LongestPathLen returns one of the longest path found in g and the length of the path, if g has a cycle or a circuit -1 is returned. If there is no cycle or circuit len(nodesInPath) is equal to pathLength + 1.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) LongestPathLen 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) LongestPathLen() int

LongestPathLen returns the length of the longest path found in g, if g has a cycle or a circuit -1 is returned.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) Node 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) Node(id NodeId) (GraphNode[NodeData], bool)

Node returns the node with the given ID if it exists in the graph.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) NodeCount 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) NodeCount() int

func (*DirectedGraph[NodeData, EdgeData, InternalData]) NodeData 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) NodeData(id NodeId) (_ NodeData, _ bool)

Node returns the data of the node with the given ID if it exists in the graph.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) NodeIds 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) NodeIds() []NodeId

NodeIds returns all the node ids in the graph.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) NodeWithID 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) NodeWithID(id NodeId) (n GraphNode[NodeData], found bool)

NodeWithID returns a Node with the given ID if found.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) RandomNode 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) RandomNode() (NodeId, bool)

RandomNode returns the id of a pseudo randomly picked node.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) RemoveEdge 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) RemoveEdge(srcId, destId NodeId)

RemoveEdge removes the edge with the given end point IDs from the graph, leaving the terminal nodes. If the edge does not exist it is a no-op.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) RemoveNode 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) RemoveNode(id NodeId)

RemoveNode removes the node with the given ID from the graph, as well as any edges attached to it. If the node is not in the graph it is a no-op.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) SetEdge 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) SetEdge(from, to NodeId, data EdgeData)

SetEdge adds e, an edge from one node to another. The nodes must exist. It will panic if the target node is the same as the source node.

func (*DirectedGraph[NodeData, EdgeData, InternalData]) SourceNodes 

func (g *DirectedGraph[NodeData, EdgeData, InternalData]) SourceNodes(id NodeId) []GraphNode[NodeData]

To returns all nodes in g that can reach directly to n.

type Graph32 

type Graph32[T constraints.Ordered] struct {
	// contains filtered or unexported fields
}

A Graph32 is a directed graph that performs no allocations and has a capacity of 32 nodes.

func (*Graph32[T]) AddEdge 

func (g *Graph32[T]) AddEdge(fromNodeId, toNodeId NodeId)

func (*Graph32[T]) AddNode 

func (g *Graph32[T]) AddNode(data T) Graph32Node[T]

func (*Graph32[T]) Capacity 

func (g *Graph32[T]) Capacity() int

func (Graph32[T]) HasEdgeFromTo 

func (g Graph32[T]) HasEdgeFromTo(fromNodeId, toNodeId NodeId) bool

func (Graph32[T]) HasNodeOfId 

func (g Graph32[T]) HasNodeOfId(id NodeId) bool

func (Graph32[T]) IdOfNode 

func (g Graph32[T]) IdOfNode(v T) (NodeId, bool)

func (Graph32[T]) IteratorDirectlyReachableNodes 

func (g Graph32[T]) IteratorDirectlyReachableNodes(fromNodeId NodeId) Graph32Iterator[T]

IteratorDirectlyReachableNodes returns an iterator that iterates over the nodes directly reachable from the node of id fromNodeId.

func (Graph32[T]) IteratorFrom 

func (g Graph32[T]) IteratorFrom(fromNodeId NodeId) Graph32Iterator[T]

IteratorDirectlyReachableNodes returns an iterator that iterates over all nodes directly and indirectly reachable from the node of id fromNodeId. The iteration start at this node.

func (Graph32[T]) MustGetIdOfNode 

func (g Graph32[T]) MustGetIdOfNode(v T) NodeId

func (Graph32[T]) NodeOfId 

func (g Graph32[T]) NodeOfId(id NodeId) (node Graph32Node[T], found bool)

func (*Graph32[T]) Size 

func (g *Graph32[T]) Size() int

type Graph32Iterator 

type Graph32Iterator[T constraints.Ordered] struct {
	// contains filtered or unexported fields
}

func (*Graph32Iterator[T]) Next 

func (it *Graph32Iterator[T]) Next() bool

func (*Graph32Iterator[T]) Node 

func (it *Graph32Iterator[T]) Node() Graph32Node[T]

type Graph32Node 

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

func (Graph32Node[T]) Id 

func (n Graph32Node[T]) Id() NodeId

type GraphEdge 

type GraphEdge[EdgeData any] struct {
	From NodeId
	To   NodeId
	Data EdgeData
}

type GraphNode 

type GraphNode[T any] struct {
	Id   NodeId
	Data T
}

type Map32 

type Map32[K constraints.Ordered, V any] struct {
	// contains filtered or unexported fields
}

A Map32 is a map that performs no allocations and has a capacity of 32.

func (*Map32[K, V]) Get 

func (m *Map32[K, V]) Get(key K) (v V, found bool)

func (*Map32[K, V]) IsFull 

func (m *Map32[K, V]) IsFull() bool

func (*Map32[K, V]) MustGet 

func (m *Map32[K, V]) MustGet(key K) V

func (*Map32[K, V]) Set 

func (m *Map32[K, V]) Set(key K, v V) error

func (*Map32[K, V]) Size 

func (m *Map32[K, V]) Size() int

type Node 

type Node interface {
	Id() NodeId
}

type NodeId 

type NodeId int64

type RWLocker 

type RWLocker interface {
	Lock()
	Unlock()

	RLock()
	RUnlock()
}

type SingleNodeRetrievalType 

type SingleNodeRetrievalType int
const (
	WithData SingleNodeRetrievalType = iota + 1
)

type StringMap32Entry 

type StringMap32Entry[K constraints.Ordered, V any] struct {
	// contains filtered or unexported fields
}

type TSArrayQueue 

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

Thread safe array queue

func NewTSArrayQueue 

func NewTSArrayQueue[T any]() *TSArrayQueue[T]

func NewTSArrayQueueWithConfig 

func NewTSArrayQueueWithConfig[T any](config TSArrayQueueConfig[T]) *TSArrayQueue[T]

func (*TSArrayQueue[T]) AutoRemove 

func (q *TSArrayQueue[T]) AutoRemove()

AutoRemove removes all elements that validate the autoremove condition. If there is not autoremove condition the function does nothing.

func (*TSArrayQueue[T]) Clear 

func (q *TSArrayQueue[T]) Clear()

Clear removes all elements from the queue.

func (*TSArrayQueue[T]) Dequeue 

func (q *TSArrayQueue[T]) Dequeue() (value T, ok bool)

Dequeue removes first element of the queue and returns it, or nil if queue is empty. Second return parameter is true, unless the queue was empty and there was nothing to dequeue.

func (*TSArrayQueue[T]) DequeueAll 

func (q *TSArrayQueue[T]) DequeueAll() []T

Dequeue removes all the elements of the queue and returns them. The first element of the queue is the first element in the returned slice.

func (*TSArrayQueue[T]) Enqueue 

func (q *TSArrayQueue[T]) Enqueue(value T)

Enqueue adds a value to the end of the queue

func (*TSArrayQueue[T]) EnqueueAll 

func (q *TSArrayQueue[T]) EnqueueAll(values ...T)

Enqueue adds zero or more values to the end of the queue

func (*TSArrayQueue[T]) EnqueueAllAutoRemove 

func (q *TSArrayQueue[T]) EnqueueAllAutoRemove(values ...T)

EnqueueAllAutoRemove does the same as EnqueueAllAutoRemove but also removes all elements that validate the autoremove condition.

func (*TSArrayQueue[T]) EnqueueAutoRemove 

func (q *TSArrayQueue[T]) EnqueueAutoRemove(value T)

EnqueueAutoRemove does the same as Enqueue but also removes all elements that validate the autoremove condition.

func (*TSArrayQueue[T]) HasNeverHadElements 

func (q *TSArrayQueue[T]) HasNeverHadElements() bool

HasNeverHadElements returns true if no element was ever added to the queue.

func (*TSArrayQueue[T]) IsEmpty 

func (q *TSArrayQueue[T]) IsEmpty() bool

IsEmpty returns true if queue does not contain any elements.

func (*TSArrayQueue[T]) Iterator 

func (q *TSArrayQueue[T]) Iterator() *ArrayQueueIterator[T]

func (*TSArrayQueue[T]) Peek 

func (q *TSArrayQueue[T]) Peek() (value T, ok bool)

Peek returns first element of the queue without removing it, or nil if queue is empty. Second return parameter is true, unless the queue was empty and there was nothing to peek.

func (*TSArrayQueue[T]) Size 

func (q *TSArrayQueue[T]) Size() int

Size returns the number of elements within the queue.

func (*TSArrayQueue[T]) Values 

func (q *TSArrayQueue[T]) Values() []T

Values returns all elements in the queue (FIFO order).

type TSArrayQueueConfig 

type TSArrayQueueConfig[T any] struct {
	AutoRemoveCondition func(v T) bool
}

type ThreadSafety 

type ThreadSafety bool

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.