frozen

package module
v1.6.0 Latest Latest
Warning

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

 Go to latest Published: Oct 27, 2023 License: Apache-2.0 Imports: 10 Imported by: 9

README

Frozen

Go build status

Efficient immutable data types.

Types

Map and Set both use a hashed array trie.

  • Map: Associates keys with values.
  • Set: Stores sets of values.

Performance

The following benchmarks test the base node implementation against several other key-value map implementations. All implementations are tested for insertions against an empty map, a map prepopulated with 1k elements and one prepopulated with 1M elements. The implementations are as follows:

Benchmark Type
MapInt map[int]int
MapInterface map[any]any
FrozenMap frozen.Map
FrozenNode frozen.node
SetInt set = map[int]struct{}
SetInterface set = map[any]struct{}
FrozenSet frozen.Set

In all cases, ints are mapped to ints.

$ go test -run ^$ -cpuprofile cpu.prof -memprofile mem.prof -benchmem -bench ^BenchmarkInsert .
goos: linux
goarch: amd64
pkg: github.com/arr-ai/frozen
BenchmarkInsertMapInt0-24           	 8532830	       175 ns/op	      72 B/op	       0 allocs/op
BenchmarkInsertMapInt1k-24          	10379329	       164 ns/op	      60 B/op	       0 allocs/op
BenchmarkInsertMapInt1M-24          	 6760242	       185 ns/op	      78 B/op	       0 allocs/op
BenchmarkInsertMapInterface0-24     	 3579843	       348 ns/op	     152 B/op	       2 allocs/op
BenchmarkInsertMapInterface1k-24    	 3675631	       365 ns/op	     148 B/op	       2 allocs/op
BenchmarkInsertMapInterface1M-24    	 6517272	       354 ns/op	     115 B/op	       2 allocs/op
BenchmarkInsertFrozenMap0-24        	 5443401	       225 ns/op	     240 B/op	       6 allocs/op
BenchmarkInsertFrozenMap1k-24       	 2553954	       446 ns/op	     635 B/op	      10 allocs/op
BenchmarkInsertFrozenMap1M-24       	 1263691	       960 ns/op	     954 B/op	      13 allocs/op
BenchmarkInsertFrozenNode0-24       	 8220901	       141 ns/op	     144 B/op	       4 allocs/op
BenchmarkInsertFrozenNode1k-24      	 3294789	       388 ns/op	     539 B/op	       8 allocs/op
BenchmarkInsertFrozenNode1M-24      	 1316443	       871 ns/op	     858 B/op	      11 allocs/op
BenchmarkInsertSetInt0-24           	12816358	       155 ns/op	      29 B/op	       0 allocs/op
BenchmarkInsertSetInt1k-24          	12738687	       155 ns/op	      29 B/op	       0 allocs/op
BenchmarkInsertSetInt1M-24          	 7613054	       171 ns/op	      39 B/op	       0 allocs/op
BenchmarkInsertSetInterface0-24     	 5121948	       302 ns/op	      58 B/op	       1 allocs/op
BenchmarkInsertSetInterface1k-24    	 5051988	       303 ns/op	      58 B/op	       1 allocs/op
BenchmarkInsertSetInterface1M-24    	 3172472	       329 ns/op	      62 B/op	       1 allocs/op
BenchmarkInsertFrozenSet0-24        	 5400745	       236 ns/op	     296 B/op	       6 allocs/op
BenchmarkInsertFrozenSet1k-24       	 2460313	       512 ns/op	     787 B/op	      11 allocs/op
BenchmarkInsertFrozenSet1M-24       	 1132215	      1046 ns/op	    1106 B/op	      14 allocs/op
PASS
ok  	github.com/arr-ai/frozen	65.909s

Benchmarks Graph

Documentation

Overview

Package frozen provides immutable data structures.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func MapToGoMap added in v1.5.0 

func MapToGoMap[K comparable, V any](m Map[K, V]) map[K]V

MapToGoMap transforms a Map[K, V] to a map[K]V. K must be comparable.

Types

type BitIterator 

type BitIterator uintptr

BitIterator represents a set of one-bits and the ability to enumerate them.

func (BitIterator) Count 

func (b BitIterator) Count() int

func (BitIterator) Has 

func (b BitIterator) Has(i int) bool

func (BitIterator) Index 

func (b BitIterator) Index() int

func (BitIterator) Next 

func (b BitIterator) Next() BitIterator

func (BitIterator) String 

func (b BitIterator) String() string

func (BitIterator) With 

func (b BitIterator) With(i int) BitIterator

func (BitIterator) Without 

func (b BitIterator) Without(i int) BitIterator

type IntSet 

type IntSet[I integer] struct {
	// contains filtered or unexported fields
}

func NewIntSet 

func NewIntSet[I integer](is ...I) IntSet[I]

NewIntSet returns an IntSet with the values provided.

func (IntSet[I]) Any 

func (s IntSet[I]) Any() I

Any returns a random value from s.

func (IntSet[I]) Count 

func (s IntSet[I]) Count() int

Count returns the number of elements in IntSet.

func (IntSet[I]) Elements 

func (s IntSet[I]) Elements() []I

Elements returns all the values of IntSet.

func (IntSet[I]) Equal added in v1.2.0 

func (s IntSet[I]) Equal(t IntSet[I]) bool

Equal returns true if both IntSets are equal.

func (IntSet[I]) EqualSet 

func (s IntSet[I]) EqualSet(t IntSet[I]) bool

EqualSet is deprecated. Use Equal instead.

func (IntSet[I]) Format added in v0.21.0 

func (s IntSet[I]) Format(f fmt.State, verb rune)

Format formats IntSet.

func (IntSet[I]) Has 

func (s IntSet[I]) Has(val I) bool

Has returns true if value exists in the IntSet and false otherwise.

func (IntSet[I]) Hash added in v1.2.0 

func (s IntSet[I]) Hash(seed uintptr) uintptr

func (IntSet[I]) Intersection 

func (s IntSet[I]) Intersection(t IntSet[I]) IntSet[I]

Intersection returns an IntSet whose values exists in s and t.

func (IntSet[I]) IsEmpty 

func (s IntSet[I]) IsEmpty() bool

IsEmpty returns true if there is no values in s and false otherwise.

func (IntSet[I]) IsSubsetOf 

func (s IntSet[I]) IsSubsetOf(t IntSet[I]) bool

IsSubsetOf returns true if s is a subset of t and false otherwise.

func (IntSet[I]) Map 

func (s IntSet[I]) Map(f func(elem I) I) IntSet[I]

Map returns an IntSet with whose values are mapped from s.

func (IntSet[I]) Range 

func (s IntSet[I]) Range() Iterator[I]

Range returns the iterator for IntSet.

func (IntSet[I]) Same added in v1.2.0 

func (s IntSet[I]) Same(t any) bool

Equal returns true if t is an IntSet and a and b are equal.

func (IntSet[I]) String 

func (s IntSet[I]) String() string

String returns a string representation of IntSet.

func (IntSet[I]) Union 

func (s IntSet[I]) Union(t IntSet[I]) IntSet[I]

Union returns an integer set that is a union of s and t.

func (IntSet[I]) Where 

func (s IntSet[I]) Where(pred func(elem I) bool) IntSet[I]

Where returns an IntSet whose values fulfill the provided condition.

func (IntSet[I]) With 

func (s IntSet[I]) With(i I) IntSet[I]

With returns a new IntSet with the values of s and the provided values.

func (IntSet[I]) Without 

func (s IntSet[I]) Without(i I) IntSet[I]

Without returns an IntSet without the provided values.

type Iterator 

type Iterator[T any] interface {
	Next() bool
	Value() T
}

Iterator provides for iterating over a Set.

type Key 

type Key[T any] interface {
	value.Equaler[T]
	hash.Hashable
}

Key represents a type that can be used as a key in a Map or a Set.

type KeyValue 

type KeyValue[K, V any] struct {
	Key   K
	Value V
}

KeyValue[K, V] represents a key-value pair for insertion into a Map.

func KV 

func KV[K, V any](k K, v V) KeyValue[K, V]

KV creates a KeyValue[K, V].

func (KeyValue[K, V]) Equal 

func (kv KeyValue[K, V]) Equal(kv2 KeyValue[K, V]) bool

func (KeyValue[K, V]) Format added in v0.21.0 

func (kv KeyValue[K, V]) Format(f fmt.State, verb rune)

String returns a string representation of a KeyValue[K, V].

func (KeyValue[K, V]) Hash 

func (kv KeyValue[K, V]) Hash(seed uintptr) uintptr

Hash computes a hash for a KeyValue[K, V].

func (KeyValue[K, V]) Same added in v0.21.0 

func (kv KeyValue[K, V]) Same(a any) bool

func (KeyValue[K, V]) String 

func (kv KeyValue[K, V]) String() string

String returns a string representation of a KeyValue[K, V].

type Map 

type Map[K any, V any] struct {
	// contains filtered or unexported fields
}

Map maps keys to values. The zero value is the empty Map.

func MapMap added in v0.21.0 

func MapMap[K, V, U any](m Map[K, V], f func(key K, val V) U) Map[K, U]

Map returns a Map with keys from this Map, but the values replaced by the result of calling f.

func NewMap 

func NewMap[K any, V any](kvs ...KeyValue[K, V]) Map[K, V]

NewMap creates a new Map with kvs as keys and values.

func NewMapFromGoMap 

func NewMapFromGoMap[K comparable, V any](m map[K]V) Map[K, V]

NewMapFromGoMap takes a map[K]V and returns a frozen Map from it.

func NewMapFromKeys 

func NewMapFromKeys[K any, V any](keys Set[K], f func(key K) V) Map[K, V]

NewMapFromKeys creates a new Map in which values are computed from keys.

func SetGroupBy added in v0.21.0 

func SetGroupBy[T, K any](s Set[T], key func(el T) K) Map[K, Set[T]]

GroupBy returns a Map that groups elements in the Set by their key.

func (Map[K, V]) Any 

func (m Map[K, V]) Any() (key K, value V)

Any returns an arbitrary entry from the Map.

func (Map[K, V]) Count 

func (m Map[K, V]) Count() int

Count returns the number of entries in the Map.

func (Map[K, V]) DebugReport added in v0.20.0 

func (m Map[K, V]) DebugReport(debug.Tag) string

DebugReport is for internal use.

func (Map[K, V]) EqArgs added in v0.20.0 

func (m Map[K, V]) EqArgs() *tree.EqArgs[mapEntry[K, V]]

func (Map[K, V]) EqKeyArgs added in v0.21.0 

func (m Map[K, V]) EqKeyArgs() *tree.EqArgs[mapEntry[K, V]]

func (Map[K, V]) Equal 

func (m Map[K, V]) Equal(n Map[K, V]) bool

Equal returns true iff i is a Map with all the same key-value pairs as this Map.

func (Map[K, V]) Format 

func (m Map[K, V]) Format(f fmt.State, verb rune)

Format writes a string representation of the Map into state.

func (Map[K, V]) Get 

func (m Map[K, V]) Get(key K) (_ V, _ bool)

Get returns the value associated with key in m and true iff the key is found.

func (Map[K, V]) GetElse 

func (m Map[K, V]) GetElse(key K, deflt V) V

GetElse returns the value associated with key in m or deflt if the key is not found.

func (Map[K, V]) GetElseFunc 

func (m Map[K, V]) GetElseFunc(key K, deflt func() V) V

GetElseFunc returns the value associated with key in m or the result of calling deflt if the key is not found.

func (Map[K, V]) Has 

func (m Map[K, V]) Has(key K) bool

Has returns true iff the key exists in the map.

func (Map[K, V]) Hash 

func (m Map[K, V]) Hash(seed uintptr) uintptr

Hash computes a hash val for s.

func (Map[K, V]) IsEmpty 

func (m Map[K, V]) IsEmpty() bool

IsEmpty returns true if the Map has no entries.

func (Map[K, V]) Keys 

func (m Map[K, V]) Keys() Set[K]

Keys returns a Set with all the keys in the Map.

func (Map[K, V]) MarshalJSON 

func (m Map[K, V]) MarshalJSON() ([]byte, error)

MarshalJSON implements json.Marshaler.

func (Map[K, V]) Merge 

func (m Map[K, V]) Merge(n Map[K, V], resolve func(key K, a, b V) V) Map[K, V]

Merge returns a map from the merging between two maps, should there be a key overlap, the value that corresponds to key will be replaced by the value resulted from the provided resolve function.

func (Map[K, V]) MustGet 

func (m Map[K, V]) MustGet(key K) V

MustGet returns the value associated with key in m or panics if the key is not found.

func (Map[K, V]) Project 

func (m Map[K, V]) Project(keys ...K) Map[K, V]

Project returns a Map with only keys included from this Map.

func (Map[K, V]) Range 

func (m Map[K, V]) Range() MapIterator[K, V]

Range returns a MapIterator over the Map.

func (Map[K, V]) Same added in v0.21.0 

func (m Map[K, V]) Same(a any) bool

Same returns true iff a is a Map and m and n have all the same key-values.

func (Map[K, V]) String 

func (m Map[K, V]) String() string

String returns a string representatio of the Map.

func (Map[K, V]) Update 

func (m Map[K, V]) Update(n Map[K, V]) Map[K, V]

Update returns a Map with key-value pairs from n added or replacing existing keys.

func (Map[K, V]) Values 

func (m Map[K, V]) Values() Set[V]

Values returns a Set with all the Values in the Map.

func (Map[K, V]) Where 

func (m Map[K, V]) Where(pred func(key K, val V) bool) Map[K, V]

Where returns a Map with only key-value pairs satisfying pred.

func (Map[K, V]) With 

func (m Map[K, V]) With(key K, val V) Map[K, V]

With returns a new Map with key associated with val and all other keys retained from m.

func (Map[K, V]) Without 

func (m Map[K, V]) Without(key K) Map[K, V]

Without returns a new Map with all keys retained from m except the elements of keys.

type MapBuilder 

type MapBuilder[K any, V any] struct {
	// contains filtered or unexported fields
}

MapBuilder[K, V] provides a more efficient way to build Maps incrementally.

func NewMapBuilder 

func NewMapBuilder[K any, V any](capacity int) *MapBuilder[K, V]

func (*MapBuilder[K, V]) Count 

func (b *MapBuilder[K, V]) Count() int

Count returns the number of entries in the Map under construction.

func (*MapBuilder[K, V]) Finish 

func (b *MapBuilder[K, V]) Finish() Map[K, V]

Finish returns a Map containing all entries added since the MapBuilder[K, V] was initialised or the last call to Finish.

func (*MapBuilder[K, V]) Get 

func (b *MapBuilder[K, V]) Get(key K) (V, bool)

Get returns the value for key from the Map under construction or false if not found.

func (*MapBuilder[K, V]) Has added in v0.20.0 

func (b *MapBuilder[K, V]) Has(key K) bool

func (*MapBuilder[K, V]) Put 

func (b *MapBuilder[K, V]) Put(key K, value V)

Put adds or changes an entry into the Map under construction.

func (*MapBuilder[K, V]) Remove 

func (b *MapBuilder[K, V]) Remove(key K)

Remove removes an entry from the Map under construction.

type MapIterator 

type MapIterator[K any, V any] struct {
	// contains filtered or unexported fields
}

MapIterator provides for iterating over a Map.

func (*MapIterator[K, V]) Entry 

func (i *MapIterator[K, V]) Entry() (key K, value V)

Entry returns the current key-value pair as two return values.

func (*MapIterator[K, V]) Key 

func (i *MapIterator[K, V]) Key() K

Key returns the key for the current entry.

func (*MapIterator[K, V]) Next 

func (i *MapIterator[K, V]) Next() bool

Next moves to the next key-value pair or returns false if there are no more.

func (*MapIterator[K, V]) Value 

func (i *MapIterator[K, V]) Value() V

Value returns the value for the current entry.

type Set 

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

Set holds a set of values of type T. The zero value is the empty Set.

func Intersection 

func Intersection[T any](sets ...Set[T]) Set[T]

Intersection returns the n-ary intersection of a Set of Sets.

func Iota 

func Iota[T ~int](stop T) Set[T]

Iota returns Iota3(0, stop, 1).

func Iota2 

func Iota2[T ~int](start, stop T) Set[T]

Iota2 returns Iota3(start, stop, 1).

func Iota3 

func Iota3[T ~int](start, stop, step T) Set[T]

Iota3 returns a Set with elements {start, start+step, start+2*step, ...} up to but not including stop. Negative steps are allowed.

func NewSet 

func NewSet[T any](values ...T) Set[T]

NewSet creates a new Set with values as elements.

func NewSetFromMask64 

func NewSetFromMask64(mask uint64) Set[int]

NewSetFromMask64 returns a Set containing all elements 2**i such that bit i of mask is set.

func Powerset added in v0.21.0 

func Powerset[T any](s Set[T]) Set[Set[T]]

func SetAs added in v0.21.0 

func SetAs[U, T any](s Set[T]) Set[U]

func SetMap added in v0.21.0 

func SetMap[T, U any](s Set[T], f func(elem T) U) Set[U]

// Map returns a Set with all the results of applying f to all elements in s.

func Union 

func Union[T any](sets ...Set[T]) Set[T]

Union returns the n-ary union of a Set of Sets.

func (Set[T]) Any 

func (s Set[T]) Any() T

Any returns an arbitrary element from the Set.

func (Set[T]) AnyN 

func (s Set[T]) AnyN(n int) Set[T]

AnyN returns a set of N arbitrary elements from the Set.

func (Set[T]) AsSetAny added in v0.21.0 

func (s Set[T]) AsSetAny() Set[any]

func (Set[T]) Count 

func (s Set[T]) Count() int

Count returns the number of elements in the Set.

func (Set[T]) Difference 

func (s Set[T]) Difference(t Set[T]) Set[T]

Difference returns a Set with all elements that are s but not in t.

func (Set[T]) Elements 

func (s Set[T]) Elements() []T

func (Set[T]) Equal 

func (s Set[T]) Equal(t Set[T]) bool

Equal returns true iff s and set have all the same elements.

func (Set[T]) First 

func (s Set[T]) First(less tree.Less[T]) any

First returns the first element in a defined order.

func (Set[T]) FirstN 

func (s Set[T]) FirstN(n int, less tree.Less[T]) Set[T]

FirstN returns a set of the first n elements in a defined order.

func (Set[T]) Format 

func (s Set[T]) Format(f fmt.State, verb rune)

Format writes a string representation of the Set into state.

func (Set[T]) Has 

func (s Set[T]) Has(val T) bool

Has returns the value associated with key and true iff the key was found.

func (Set[T]) Hash 

func (s Set[T]) Hash(seed uintptr) uintptr

Hash computes a hash value for s.

func (Set[T]) Intersection 

func (s Set[T]) Intersection(t Set[T]) Set[T]

Intersection returns a Set with all elements that are in both s and t.

func (Set[T]) IsEmpty 

func (s Set[T]) IsEmpty() bool

IsEmpty returns true iff the Set has no elements.

func (Set[T]) IsSubsetOf 

func (s Set[T]) IsSubsetOf(t Set[T]) bool

IsSubsetOf returns true iff no element in s is not in t.

func (Set[T]) MarshalJSON 

func (s Set[T]) MarshalJSON() ([]byte, error)

MarshalJSON implements json.Marshaler.

func (Set[T]) OrderedElements 

func (s Set[T]) OrderedElements(less tree.Less[T]) []T

OrderedElements takes elements in a defined order.

func (Set[T]) OrderedFirstN 

func (s Set[T]) OrderedFirstN(n int, less tree.Less[T]) []T

OrderedFirstN returns a list of elements in a defined order.

func (Set[T]) OrderedRange 

func (s Set[T]) OrderedRange(less tree.Less[T]) Iterator[T]

OrderedRange returns a SetIterator for the Set that iterates over the elements in a specified order.

func (Set[T]) Range 

func (s Set[T]) Range() Iterator[T]

Range returns an Iterator over the Set.

func (Set[T]) Reduce 

func (s Set[T]) Reduce(reduce func(elems ...T) T) (T, bool)

Reduce returns the result of applying reduce to the elements of s or false if s.IsEmpty(). The result of each call is used as the acc argument for the next element.

The reduce function must have the following properties:

  • commutative: reduce(a, b, c) == reduce(c, a, b)
  • associative: reduce(reduce(a, b), c) == reduce(a, reduce(b, c))

By implication, reduce must accept its own output as input.

elems will never be empty.

func (Set[T]) Reduce2 

func (s Set[T]) Reduce2(reduce func(a, b T) T) (T, bool)

Reduce2 is a convenience wrapper for `Reduce`, allowing the caller to implement a simpler, albeit less efficient, binary `reduce` function instead of an n-adic one.

func (Set[T]) Same added in v0.21.0 

func (s Set[T]) Same(a any) bool

Same returns true iff a is a Set and s and a have all the same elements.

func (Set[T]) String 

func (s Set[T]) String() string

String returns a string representation of the Set.

func (Set[T]) SymmetricDifference 

func (s Set[T]) SymmetricDifference(t Set[T]) Set[T]

SymmetricDifference returns a Set with all elements that are s or t, but not both.

func (Set[T]) Union 

func (s Set[T]) Union(t Set[T]) Set[T]

Union returns a Set with all elements that are in either s or t.

func (Set[T]) Where 

func (s Set[T]) Where(pred func(elem T) bool) Set[T]

Where returns a Set with all elements that are in s and satisfy pred.

func (Set[T]) With 

func (s Set[T]) With(v T) Set[T]

With returns a new Set retaining all the elements of the Set as well as values.

func (Set[T]) Without 

func (s Set[T]) Without(v T) Set[T]

Without returns a new Set with all values retained from Set except values.

type SetBuilder 

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

SetBuilder[T] provides a more efficient way to build sets incrementally.

func NewSetBuilder 

func NewSetBuilder[T any](capacity int) *SetBuilder[T]

func (*SetBuilder[T]) Add 

func (b *SetBuilder[T]) Add(v T)

Add adds el to the Set under construction.

func (*SetBuilder[T]) Count 

func (b *SetBuilder[T]) Count() int

Count returns the count of the Set that will be returned from Finish().

func (*SetBuilder[T]) Finish 

func (b *SetBuilder[T]) Finish() Set[T]

Finish returns a Set containing all elements added since the SetBuilder[T] was initialised or the last call to Finish.

func (SetBuilder[T]) Format added in v0.20.0 

func (b SetBuilder[T]) Format(f fmt.State, verb rune)

func (*SetBuilder[T]) Has 

func (b *SetBuilder[T]) Has(v T) bool

func (*SetBuilder[T]) Remove 

func (b *SetBuilder[T]) Remove(v T)

Remove removes el to the Set under construction.

func (SetBuilder[T]) String added in v0.20.0 

func (b SetBuilder[T]) String() string

Source Files

View all Source files

Directories

Path Synopsis
internal
pkg/debug
pkg/depth
pkg/fu
pkg/iterator
pkg/masker
pkg/test
pkg/test/set
pkg/tree
pkg/value
pkg/vetctl
pkg
errors
rel

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.