frozen

package module
v0.14.0 Latest Latest
Warning

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

 Go to latest Published: Apr 29, 2020 License: Apache-2.0 Imports: 12 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[interface{}]interface{}
FrozenMap frozen.Map
FrozenNode frozen.node
SetInt set = map[int]struct{}
SetInterface set = map[interface{}]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 Equal 

func Equal(a, b interface{}) bool

Equal returns true iff a == b. If a or b implements Equatable, that is used to perform the test.

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 Equatable 

type Equatable interface {
	Equal(interface{}) bool
}

Equatable represents a type that can be compared for equality with another value.

type IntIterator 

type IntIterator interface {
	Next() bool
	Value() int
}

type IntLess 

type IntLess func(a, b int) bool

IntLess dictates the order of two elements.

type IntSet 

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

func NewIntSet 

func NewIntSet(is ...int) IntSet

NewIntSet returns an IntSet with the values provided.

func (IntSet) Any 

func (s IntSet) Any() int

Any returns a random value from s.

func (IntSet) Count 

func (s IntSet) Count() int

Count returns the number of elements in IntSet.

func (IntSet) Elements 

func (s IntSet) Elements() []int

Elements returns all the values of IntSet.

func (IntSet) EqualSet 

func (s IntSet) EqualSet(t IntSet) bool

EqualSet returns true if both IntSets are equal.

func (IntSet) Has 

func (s IntSet) Has(val int) bool

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

func (IntSet) Intersection 

func (s IntSet) Intersection(t IntSet) IntSet

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

func (IntSet) IsEmpty 

func (s IntSet) IsEmpty() bool

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

func (IntSet) IsSubsetOf 

func (s IntSet) IsSubsetOf(t IntSet) bool

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

func (IntSet) Map 

func (s IntSet) Map(f func(elem int) int) IntSet

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

func (IntSet) Range 

func (s IntSet) Range() IntIterator

Range returns the iterator for IntSet.

func (IntSet) String 

func (s IntSet) String() string

String returns a string representation of IntSet.

func (IntSet) Union 

func (s IntSet) Union(t IntSet) IntSet

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

func (IntSet) Where 

func (s IntSet) Where(pred func(elem int) bool) IntSet

Where returns an IntSet whose values fulfill the provided condition.

func (IntSet) With 

func (s IntSet) With(is ...int) IntSet

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

func (IntSet) Without 

func (s IntSet) Without(is ...int) IntSet

Without returns an IntSet without the provided values.

type Iterator 

type Iterator interface {
	Next() bool
	Value() interface{}
}

Iterator provides for iterating over a Set.

type Key 

type Key interface {
	Equatable
	hash.Hashable
}

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

type KeyValue 

type KeyValue struct {
	Key, Value interface{}
}

KeyValue represents a key-value pair for insertion into a Map.

func KV 

func KV(key, val interface{}) KeyValue

KV creates a KeyValue.

func (KeyValue) Equal 

func (kv KeyValue) Equal(i interface{}) bool

Equal returns true iff i is a KeyValue whose key equals this KeyValue's key.

func (KeyValue) Hash 

func (kv KeyValue) Hash(seed uintptr) uintptr

Hash computes a hash for a KeyValue.

func (KeyValue) String 

func (kv KeyValue) String() string

String returns a string representation of a KeyValue.

type Less 

type Less func(a, b interface{}) bool

Less dictates the order of two elements.

type Map 

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

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

func NewMap 

func NewMap(kvs ...KeyValue) Map

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

func NewMapFromGoMap 

func NewMapFromGoMap(m map[interface{}]interface{}) Map

NewMapFromGoMap takes a map[interface{}]interface{} and returns a frozen Map from it.

func NewMapFromKeys 

func NewMapFromKeys(keys Set, f func(key interface{}) interface{}) Map

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

func (Map) Any 

func (m Map) Any() (key, value interface{})

Any returns an arbitrary entry from the Map.

func (Map) Count 

func (m Map) Count() int

Count returns the number of entries in the Map.

func (Map) Equal 

func (m Map) Equal(i interface{}) bool

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

func (Map) Format 

func (m Map) Format(state fmt.State, _ rune)

Format writes a string representation of the Map into state.

func (Map) Get 

func (m Map) Get(key interface{}) (interface{}, bool)

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

func (Map) GetElse 

func (m Map) GetElse(key, deflt interface{}) interface{}

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

func (Map) GetElseFunc 

func (m Map) GetElseFunc(key interface{}, deflt func() interface{}) interface{}

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

func (Map) Has 

func (m Map) Has(key interface{}) bool

Has returns true iff the key exists in the map.

func (Map) Hash 

func (m Map) Hash(seed uintptr) uintptr

Hash computes a hash val for s.

func (Map) IsEmpty 

func (m Map) IsEmpty() bool

IsEmpty returns true if the Map has no entries.

func (Map) Keys 

func (m Map) Keys() Set

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

func (Map) Map 

func (m Map) Map(f func(key, val interface{}) interface{}) Map

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

func (Map) MarshalJSON 

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

MarshalJSON implements json.Marshaler.

func (Map) Merge 

func (m Map) Merge(n Map, resolve func(key, a, b interface{}) interface{}) Map

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) MustGet 

func (m Map) MustGet(key interface{}) interface{}

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

func (Map) Project 

func (m Map) Project(keys Set) Map

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

func (Map) Range 

func (m Map) Range() *MapIterator

Range returns a MapIterator over the Map.

func (Map) Reduce 

func (m Map) Reduce(f func(acc, key, val interface{}) interface{}, acc interface{}) interface{}

Reduce returns the result of applying f to each key-value pair on the Map. The result of each call is used as the acc argument for the next element.

func (Map) String 

func (m Map) String() string

String returns a string representatio of the Map.

func (Map) Update 

func (m Map) Update(n Map) Map

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

func (Map) Values 

func (m Map) Values() Set

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

func (Map) Where 

func (m Map) Where(pred func(key, val interface{}) bool) Map

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

func (Map) With 

func (m Map) With(key, val interface{}) Map

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

func (Map) Without 

func (m Map) Without(keys Set) Map

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

type MapBuilder 

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

MapBuilder provides a more efficient way to build Maps incrementally.

func NewMapBuilder 

func NewMapBuilder(capacity int) *MapBuilder

func (*MapBuilder) Count 

func (b *MapBuilder) Count() int

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

func (*MapBuilder) Finish 

func (b *MapBuilder) Finish() Map

Finish returns a Map containing all entries added since the MapBuilder was initialised or the last call to Finish.

func (*MapBuilder) Get 

func (b *MapBuilder) Get(key interface{}) (interface{}, bool)

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

func (*MapBuilder) Put 

func (b *MapBuilder) Put(key, value interface{})

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

func (*MapBuilder) Remove 

func (b *MapBuilder) Remove(key interface{})

Remove removes an entry from the Map under construction.

type MapIterator 

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

MapIterator provides for iterating over a Map.

func (*MapIterator) Entry 

func (i *MapIterator) Entry() (key, value interface{})

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

func (*MapIterator) Key 

func (i *MapIterator) Key() interface{}

Key returns the key for the current entry.

func (*MapIterator) Next 

func (i *MapIterator) Next() bool

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

func (*MapIterator) Value 

func (i *MapIterator) Value() interface{}

Value returns the value for the current entry.

type MaskIterator 

type MaskIterator uint16

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

func (MaskIterator) Count 

func (b MaskIterator) Count() int

func (MaskIterator) Has 

func (b MaskIterator) Has(i int) bool

func (MaskIterator) Index 

func (b MaskIterator) Index() int

func (MaskIterator) Next 

func (b MaskIterator) Next() MaskIterator

func (MaskIterator) String 

func (b MaskIterator) String() string

func (MaskIterator) With 

func (b MaskIterator) With(i int) MaskIterator

func (MaskIterator) Without 

func (b MaskIterator) Without(i int) MaskIterator

type Set 

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

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

func CartesianProduct 

func CartesianProduct(relations ...Set) Set

func Intersection 

func Intersection(sets Set) Set

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

func Iota 

func Iota(stop int) Set

Iota returns Iota3(0, stop, 1).

func Iota2 

func Iota2(start, stop int) Set

Iota2 returns Iota3(start, stop, 1).

func Iota3 

func Iota3(start, stop, step int) Set

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

func Join 

func Join(relations Set) Set

Join returns the n-ary join of a Set of Sets.

func NewRelation 

func NewRelation(header []interface{}, rows ...[]interface{}) Set

NewRelation returns a new set of maps, each having the same keys.

func NewSet 

func NewSet(values ...interface{}) Set

NewSet creates a new Set with values as elements.

func NewSetFromMask64 

func NewSetFromMask64(mask uint64) Set

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

func NewSetFromStrings 

func NewSetFromStrings(values ...string) Set

NewSetFromStrings creates a new Set with values as elements.

func Union 

func Union(sets ...Set) Set

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

func (Set) Any 

func (s Set) Any() interface{}

Any returns an arbitrary element from the Set.

func (Set) AnyN 

func (s Set) AnyN(n int) Set

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

func (Set) CartesianProduct 

func (s Set) CartesianProduct(t Set) Set

func (Set) Count 

func (s Set) Count() int

Count returns the number of elements in the Set.

func (Set) Difference 

func (s Set) Difference(t Set) Set

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

func (Set) Elements 

func (s Set) Elements() []interface{}

func (Set) Equal 

func (s Set) Equal(t interface{}) bool

Equal implements Equatable.

func (Set) EqualSet 

func (s Set) EqualSet(t Set) bool

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

func (Set) First 

func (s Set) First(less Less) interface{}

First returns the first element in a defined order.

func (Set) FirstN 

func (s Set) FirstN(n int, less Less) Set

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

func (Set) Format 

func (s Set) Format(state fmt.State, _ rune)

Format writes a string representation of the Set into state.

func (Set) GroupBy 

func (s Set) GroupBy(key func(el interface{}) interface{}) Map

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

func (Set) Has 

func (s Set) Has(val interface{}) bool

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

func (Set) Hash 

func (s Set) Hash(seed uintptr) uintptr

Hash computes a hash value for s.

func (Set) Intersection 

func (s Set) Intersection(t Set) Set

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

func (Set) IsEmpty 

func (s Set) IsEmpty() bool

IsEmpty returns true iff the Set has no elements.

func (Set) IsSubsetOf 

func (s Set) IsSubsetOf(t Set) bool

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

func (Set) Join 

func (s Set) Join(t Set) Set

Join returns all {x, y, z} such that s has {x, y} and t has {y, z}. x, y and z represent sets of keys: 

x: keys unique to maps in s
y: keys common to maps in both
z: keys unique to maps in t

It is assumed that all maps in s have the same keys and likewise for t.

func (Set) Map 

func (s Set) Map(f func(elem interface{}) interface{}) Set

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

func (Set) MarshalJSON 

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

MarshalJSON implements json.Marshaler.

func (Set) Nest 

func (s Set) Nest(attrAttrs Map) Set

Nest returns a relation with some attributes nested as subrelations.

Example: 

input:
   _c_ _a__
  |_1_|_10_|
  |_1_|_11_|
  |_2_|_13_|
  |_3_|_11_|
  |_4_|_14_|
  |_3_|_10_|
  |_4_|_13_|

nest(input, ("aa": {"a"})):
   _c_ ___aa___
  | 1 |  _a__  |
  |   | |_10_| |
  |___|_|_11_|_|
  | 2 |  _a__  |
  |___|_|_13_|_|
  | 3 |  _a__  |
  |   | |_10_| |
  |___|_|_11_|_|
  | 4 |  _a__  |
  |   | |_13_| |
  |___|_|_14_|_|

func (Set) OrderedElements 

func (s Set) OrderedElements(less Less) []interface{}

OrderedElements takes elements in a defined order.

func (Set) OrderedFirstN 

func (s Set) OrderedFirstN(n int, less Less) []interface{}

OrderedFirstN returns a list of elements in a defined order.

func (Set) OrderedRange 

func (s Set) OrderedRange(less Less) Iterator

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

func (Set) Powerset 

func (s Set) Powerset() Set

func (Set) Project 

func (s Set) Project(attrs Set) Set

Project returns a Set with the result of projecting each map.

func (Set) Range 

func (s Set) Range() Iterator

Range returns an Iterator over the Set.

func (Set) Reduce 

func (s Set) Reduce(reduce func(elems ...interface{}) interface{}) interface{}

Reduce returns the result of applying `reduce` to the elements of `s` or `nil` 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) Reduce2 

func (s Set) Reduce2(reduce func(a, b interface{}) interface{}) interface{}

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) String 

func (s Set) String() string

String returns a string representation of the Set.

func (Set) SymmetricDifference 

func (s Set) SymmetricDifference(t Set) Set

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

func (Set) Union 

func (s Set) Union(t Set) Set

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

func (Set) Unnest 

func (s Set) Unnest(attrs Set) Set

Unnest returns a relation with some subrelations unnested. This is the reverse of Nest.

func (Set) Where 

func (s Set) Where(pred func(elem interface{}) bool) Set

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

func (Set) With 

func (s Set) With(values ...interface{}) Set

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

func (Set) Without 

func (s Set) Without(values ...interface{}) Set

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

type SetBuilder 

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

SetBuilder provides a more efficient way to build sets incrementally.

func NewSetBuilder 

func NewSetBuilder(capacity int) *SetBuilder

func (*SetBuilder) Add 

func (b *SetBuilder) Add(v interface{})

Add adds el to the Set under construction.

func (*SetBuilder) Count 

func (b *SetBuilder) Count() int

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

func (*SetBuilder) Finish 

func (b *SetBuilder) Finish() Set

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

func (*SetBuilder) Has 

func (b *SetBuilder) Has(el interface{}) bool

func (*SetBuilder) Remove 

func (b *SetBuilder) Remove(v interface{})

Remove removes el to the Set under construction.

Source Files

View all Source files

Directories

Path Synopsis

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.