container

package module
v1.2.0 Latest Latest
Warning

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

 Go to latest Published: Jun 2, 2022 License: MIT Imports: 5 Imported by: 1

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrItemExists = errors.New("item already exists")
)

Functions

func Drain 

func Drain[T any](ch <-chan T) []T

Drain fetches all buffered items from a channel and returns them as a slice.

func SliceBinarySearch added in v1.2.0 

func SliceBinarySearch[T any, TV constraints.Ordered](s []T, getv func(T) TV, v TV) (pos int, exists bool)

SliceBinarySearch returns the index of the first element. If the element is not found, it returns where the element would be inserted.

func SliceInsert added in v1.2.0 

func SliceInsert[T any](s []T, k int, vs ...T) []T

SliceInsert only copies elements in a[i:] once and allocates at most once. But, as of Go toolchain 1.16, due to lacking of optimizations to avoid elements clearing in the "make" call, the verbose way is not always faster.

Future compiler optimizations might implement both in the most efficient ways.

func SliceToMap 

func SliceToMap[KT comparable, VT any](s []MI[KT, VT]) map[KT]VT

func Sort 

func Sort[T any](items []T, lessfn func(a, b T) bool)

Types

type CompareFn 

type CompareFn[T any] func(left, right T) int

type Dictionary 

type Dictionary[KT comparable, VT any] struct {
	// contains filtered or unexported fields
}

Dictionary is a thread-safe dictionary.

func (*Dictionary[KT, VT]) Clear 

func (m *Dictionary[KT, VT]) Clear()

func (*Dictionary[KT, VT]) Contains 

func (m *Dictionary[KT, VT]) Contains(k KT) bool

Contains returns true if the dictionary contains the key.

func (*Dictionary[KT, VT]) Each 

func (m *Dictionary[KT, VT]) Each(fn func(KT, VT) bool)

Each calls the given function for each key=value pair in the map. It creates a copy of the map to iterate, so setting a key inside the loop will not affect the iteration.

func (*Dictionary[KT, VT]) Get 

func (m *Dictionary[KT, VT]) Get(k KT) VT

func (*Dictionary[KT, VT]) Map 

func (m *Dictionary[KT, VT]) Map() map[KT]VT

Map returns a map copy of the dictionary.

func (*Dictionary[KT, VT]) Pop 

func (m *Dictionary[KT, VT]) Pop(k KT) (VT, bool)

Pop removes and returns the value of the key.

func (*Dictionary[KT, VT]) Remove 

func (m *Dictionary[KT, VT]) Remove(k KT) bool

Remove deletes the key from the dictionary.

func (*Dictionary[KT, VT]) Set 

func (m *Dictionary[KT, VT]) Set(k KT, v VT)

Set sets a key=value pair in the map.

type LinkedList 

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

func (*LinkedList[T]) Clear 

func (ll *LinkedList[T]) Clear()

Clear removes all items from the list.

func (*LinkedList[T]) Contains 

func (ll *LinkedList[T]) Contains(d T) bool

func (*LinkedList[T]) First 

func (ll *LinkedList[T]) First() Node[T]

func (*LinkedList[T]) Last 

func (ll *LinkedList[T]) Last() Node[T]

func (*LinkedList[T]) Len 

func (ll *LinkedList[T]) Len() int

func (*LinkedList[T]) Pop 

func (ll *LinkedList[T]) Pop() T

Pop removes the last item of the list and returns its data.

func (*LinkedList[T]) Push 

func (ll *LinkedList[T]) Push(data T) Node[T]

Push adds an item to the end of the list.

func (*LinkedList[T]) Remove 

func (ll *LinkedList[T]) Remove(d T) bool

func (*LinkedList[T]) Shift 

func (ll *LinkedList[T]) Shift() T

Shift removes the first item of the list and returns its data.

func (*LinkedList[T]) Unshift 

func (ll *LinkedList[T]) Unshift(data T) Node[T]

Unshift adds an item to the beginning of the list.

type List2D added in v1.0.1 

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

List2D is a 2D slice with some helper methods. It is NOT thread safe.

func NewList2D added in v1.0.1 

func NewList2D[T any](width, height int) *List2D[T]

func NewList2DFrom2DSlice added in v1.0.2 

func NewList2DFrom2DSlice[T any](src [][]T) *List2D[T]

NewList2DFrom2DSlice creates a new list from a [y][x] slice.

func (*List2D[T]) Copy added in v1.0.1 

func (l *List2D[T]) Copy() *List2D[T]

Copy returns a copy of the list

func (*List2D[T]) CopyRect added in v1.0.1 

func (l *List2D[T]) CopyRect(x, y, width, height int) *List2D[T]

Copy returns a copy of the list determined by the given parameters. It panics if the given parameters are out of bounds.

func (*List2D[T]) Get added in v1.0.1 

func (l *List2D[T]) Get(x, y int) T

func (*List2D[T]) GetRef added in v1.0.3 

func (l *List2D[T]) GetRef(x, y int) *T

func (*List2D[T]) GetW added in v1.0.1 

func (l *List2D[T]) GetW(x, y int) T

GetW is the same as Get, but wraps around if is out of bounds. It returns the zero value if the width or height is zero

func (*List2D[T]) Height added in v1.0.1 

func (l *List2D[T]) Height() int

func (List2D[T]) MarshalJSON added in v1.0.1 

func (l List2D[T]) MarshalJSON() ([]byte, error)

func (List2D[T]) MarshalText added in v1.0.1 

func (l List2D[T]) MarshalText() (text []byte, err error)

func (*List2D[T]) Resize added in v1.0.1 

func (l *List2D[T]) Resize(width, height int)

func (*List2D[T]) Set added in v1.0.1 

func (l *List2D[T]) Set(x, y int, v T)

func (*List2D[T]) Shift added in v1.0.1 

func (l *List2D[T]) Shift(xoffset, yoffset int)

ShiftX shifts all the elements in the x and y dimensions of the list by the offsets.

func (*List2D[T]) UnmarshalJSON added in v1.0.1 

func (l *List2D[T]) UnmarshalJSON(text []byte) error

func (*List2D[T]) UnmarshalText added in v1.0.1 

func (l *List2D[T]) UnmarshalText(text []byte) error

func (*List2D[T]) Width added in v1.0.1 

func (l *List2D[T]) Width() int

type MI 

type MI[KT comparable, VT any] struct {
	Key   KT
	Value VT
}

MI is the type returned when MapToSlice is called.

func MapToSlice 

func MapToSlice[KT comparable, VT any](m map[KT]VT) []MI[KT, VT]

type Node 

type Node[T comparable] interface {
	Data() T
	Prev() Node[T]
	Next() Node[T]
	Remove() bool
}

type Set 

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

func (*Set[T]) Add 

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

func (*Set[T]) Contains 

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

func (*Set[T]) Each 

func (s *Set[T]) Each(fn func(item T))

func (*Set[T]) Remove 

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

type SortedDictionary 

type SortedDictionary[KT constraints.Ordered, VT any] struct {
	// contains filtered or unexported fields
}

func (*SortedDictionary[KT, VT]) Clear 

func (m *SortedDictionary[KT, VT]) Clear()

func (*SortedDictionary[KT, VT]) Contains 

func (m *SortedDictionary[KT, VT]) Contains(k KT) bool

Contains returns true if the dictionary contains the key.

func (*SortedDictionary[KT, VT]) Each 

func (m *SortedDictionary[KT, VT]) Each(fn func(KT, VT) bool)

Each calls the given function for each key=value pair in the map. It creates a copy of the map to iterate, so setting a key inside the loop will not affect the iteration.

func (*SortedDictionary[KT, VT]) Get 

func (m *SortedDictionary[KT, VT]) Get(k KT) VT

func (*SortedDictionary[KT, VT]) Index 

func (m *SortedDictionary[KT, VT]) Index(k KT) int

Index returns the index of the key in the dictionary.

func (*SortedDictionary[KT, VT]) Keys 

func (m *SortedDictionary[KT, VT]) Keys() []KT

Keys returns a slice copy of the keys.

func (*SortedDictionary[KT, VT]) Len added in v1.1.1 

func (m *SortedDictionary[KT, VT]) Len() int

Len returns the number of items in the dictionary.

func (*SortedDictionary[KT, VT]) Pop 

func (m *SortedDictionary[KT, VT]) Pop() VT

Pop removes and returns the value of the first item.

func (*SortedDictionary[KT, VT]) Remove 

func (m *SortedDictionary[KT, VT]) Remove(k KT) bool

Remove deletes the key from the dictionary.

func (*SortedDictionary[KT, VT]) Set 

func (m *SortedDictionary[KT, VT]) Set(k KT, v VT)

Set sets a key=value pair in the map.

func (*SortedDictionary[KT, VT]) Values 

func (m *SortedDictionary[KT, VT]) Values() []VT

Values returns a slice copy of the values.

type Treap 

type Treap[T any] struct {
	Value       T
	Priority    int
	Left, Right *Treap[T]
}

Treap is the basic recursive treap data structure Package treap implements a persistent treap (tree/heap combination).

https://en.wikipedia.org/wiki/Treap

A treap is a binary search tree for storing ordered distinct values (duplicates not allowed). In addition, each node actually a random priority field which is stored in heap order (i.e. all children have lower priority than the parent)

This provides the basis for efficient immutable ordered Set operations. See the ordered map example for how this can be used as an ordered map

Much of this is based on "Fast Set Operations Using Treaps" by Guy E Blelloch and Margaret Reid-Miller: https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf

Benchmark

The most interesting benchmark is the performance of insert where a single random key is inserted into a 5k sized map. As the example shows, the treap structure does well here as opposed to a regular persistent map (which involves full copying). This benchmark does not take into account the fact that the regular maps are not sorted unlike treaps.

The intersection benchmark compares the case where two 10k sets with 5k in common being interesected. The regular persistent array is about 30% faster but this is still respectable showing for treaps. 

$ go test --bench=. -benchmem
goos: darwin
goarch: amd64
cpu: Intel(R) Core(TM) i5-8210Y CPU @ 1.60GHz
BenchmarkInsert-4                         650380              1925 ns/op            1146 B/op         35 allocs/op
BenchmarkInsertRegularMap-4                 1627            755162 ns/op          336394 B/op          9 allocs/op
BenchmarkIntersection-4                      526           2428991 ns/op         1144594 B/op      35734 allocs/op
BenchmarkIntersectionRegularMap-4            475           2484496 ns/op          626639 B/op        124 allocs/op
BenchmarkUnion-4                             970           1439862 ns/op          626906 B/op      19579 allocs/op
BenchmarkDiff-4                              391           2749617 ns/op         1172926 B/op      36608 allocs/op
PASS

func TreapUnion 

func TreapUnion[T any](comparer CompareFn[T], priority int, items ...T) *Treap[T]

Union combines two or more treaps. In case of duplicates, the overwrite field controls whether the union keeps the original value or whether it is updated based on value in the items

func (*Treap[T]) Delete 

func (n *Treap[T]) Delete(v T, c CompareFn[T]) *Treap[T]

Delete removes a node if it exists.

func (*Treap[T]) Diff 

func (n *Treap[T]) Diff(other *Treap[T], c CompareFn[T]) *Treap[T]

Diff finds all elements of current treap which aren't present in the other heap

func (*Treap[T]) Find 

func (n *Treap[T]) Find(v T, c CompareFn[T]) *Treap[T]

Find finds the node in the treap with matching value

func (*Treap[T]) ForEach 

func (n *Treap[T]) ForEach(fn func(v T))

ForEach does inorder traversal of the treap

func (*Treap[T]) Intersection 

func (n *Treap[T]) Intersection(other *Treap[T], c CompareFn[T]) *Treap[T]

Intersection returns a new treap with all the common values in the two treaps.

see https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf "Fast Set Operations Using Treaps" 

by Guy E Blelloch and Margaret Reid-Miller.

The algorithm is a very slight variation on that.

func (*Treap[T]) Split 

func (n *Treap[T]) Split(v T, c CompareFn[T]) (left, mid, right *Treap[T])

Split splits the treap into all nodes that compare less-than, equal and greater-than the provided value. The resulting values are properly formed treaps or nil if they contain no values.

func (*Treap[T]) Union 

func (n *Treap[T]) Union(other *Treap[T], c CompareFn[T], overwrite bool) *Treap[T]

Union combines any two treaps. In case of duplicates, the overwrite field controls whether the union keeps the original value or whether it is updated based on value in the "other" arg

Source Files

View all Source files

Directories

Path Synopsis
Package linq provides methods for querying and manipulating slices.
 Package linq provides methods for querying and manipulating slices.

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.