README
¶
Generic containers for Go
Features
- Arrays: a value per
geom.Pointof a size, in one slice, with sides of any integer type. - Sets: immutable sorted sets of any
Compareelement, with union, intersection and difference.
The rules behind them are in the package documentation.
Installation
go get github.com/gravitton/container
import "github.com/gravitton/container"
Usage
Arrays
An Array[T, S] holds one value for every index of a size in columns and rows. S is the
integer type of its sides and indices, taken from the size it is made with. An array is a handle,
as a slice is: a copy shares its values, and Clone gives storage of its own.
a := container.Arr[int](geom.Sz(4, 3)) // an Array[int, int], every value zero
small := container.Arr[uint8](geom.Sz[int16](320, 200)) // an Array[uint8, int16], indexed by geom.Point[int16]
a.Set(geom.Pt(2, 1), 7)
*a.Get(geom.Pt(2, 1)) += 1 // a pointer into the array
a.Contains(geom.Pt(4, 0)) // false, the check before Get and Set, which panic outside
a.Size() // 4x3; also Width, Height and Len
snapshot := a.Clone() // storage of its own
Iteration
The values are stored row by row, and every traversal follows that order: Keys walks the
indices, Data is the storage itself.
for index, value := range a.All() { // also Keys and Values
*value += index.X
}
values := a.Data() // the values row by row as a slice into the array, the fastest loop
for i := range values {
values[i] = min(values[i], 9)
}
data, err := json.Marshal(a) // {"w":4,"h":3,"d":[…]}, the values row by row
err = json.Unmarshal(data, &a) // and back; an error where the values do not fill the size
Sets
A Set[E] holds any element with a Compare method, once each and in that order. It never
changes: every operation returns a set, so one is safe to copy and share.
a := container.SetOf(geom.Pt(1, 1), geom.Pt(2, 1), geom.Pt(1, 2), geom.Pt(2, 2))
from := container.SetFrom(points) // the same from a slice it takes as its own, without a copy
a.Contains(geom.Pt(2, 1)) // true, a binary search
a.Len() // 4; also IsEmpty
a.First() // (1,1), true; also Last
a.Index(geom.Pt(2, 1)) // 2, true, the index At reads it back from
Set operations
Each operation walks both sets once and allocates its result once, or not at all where it equals one of them.
b := container.SetOf(geom.Pt(2, 2), geom.Pt(3, 2), geom.Pt(2, 3), geom.Pt(3, 3))
a.Union(b) // (1,1) (1,2) (2,1) (2,2) (2,3) (3,2) (3,3)
a.Intersection(b) // (2,2)
a.Difference(b) // (1,1) (1,2) (2,1)
a.SymmetricDifference(b) // (1,1) (1,2) (2,1) (2,3) (3,2) (3,3)
a.Intersects(b) // true, without building the intersection
a.Encloses(b) // false, whether a holds every element of b
a.Equal(b) // false
A set is walked and stored in its order:
for p := range a.All() { // also Backward
draw(p)
}
a.Elements() // a fresh slice; also AppendElements
json.Marshal(a) // [{"x":1,"y":1},…], null for the empty set
Full reference: pkg.go.dev.
Not planned, by design
A container knows no layout: an array has no neighbors and a set no shape. Those belong to the package that gives the indices a meaning. A new container joins when a second package needs it, so there is no map, list, heap or queue until a game asks for one.
Credits
License
The MIT License (MIT). Please see License File for more information.
Documentation
¶
Overview ¶
Package container provides generic containers, each used as a value, that know no layout. It builds on github.com/gravitton/geometry for the points and sizes an array speaks.
Types ¶
- Array is a table of values, one for every index of a size in columns and rows, stored row by row. It is a handle: a copy shares its values.
- Set is an immutable set held in the order of its elements' Compare method, which alone decides that two elements are the same. SetOf copies the elements it is given; SetFrom takes the slice as its own.
Rules ¶
A Set never changes: every operation returns a set, and one that would equal a side is that side. The one way to change a set is a write to the slice given to SetFrom.
Compare must be a total order, and the same each time it is asked; on any other the answers of a set are undefined. Elements that compare the same are one element: where both sets hold it, a result may hold the one of either set.
The zero value of every container is the empty one, ready to use.
Allocations ¶
A slice or set result is allocated once, at its final size, and each slice result has an Append form that allocates nothing once the caller's slice has room. SetOf allocates once, for its copy of the elements, and SetFrom nothing. A read, a write and a test allocate nothing; Array.Data is a read, the array's own storage rather than a result.
Panics ¶
A degenerate value gets an answer; an argument with no meaning gets a panic, whose value is an error:
Index ¶
- type Array
- func (a Array[T, S]) All() iter.Seq2[geom.Point[S], *T]
- func (a Array[T, S]) Clear()
- func (a Array[T, S]) Clone() Array[T, S]
- func (a Array[T, S]) Contains(index geom.Point[S]) bool
- func (a Array[T, S]) Data() []T
- func (a Array[T, S]) Fill(value T)
- func (a Array[T, S]) Get(index geom.Point[S]) *T
- func (a Array[T, S]) Height() S
- func (a Array[T, S]) Keys() iter.Seq[geom.Point[S]]
- func (a Array[T, S]) Len() int
- func (a Array[T, S]) MarshalJSON() ([]byte, error)
- func (a Array[T, S]) Set(index geom.Point[S], value T)
- func (a Array[T, S]) Size() geom.Size[S]
- func (a *Array[T, S]) UnmarshalJSON(data []byte) error
- func (a Array[T, S]) Values() iter.Seq[*T]
- func (a Array[T, S]) Width() S
- type Set
- func (s Set[E]) All() iter.Seq[E]
- func (s Set[E]) AppendElements(dst []E) []E
- func (s Set[E]) At(i int) E
- func (s Set[E]) Backward() iter.Seq[E]
- func (s Set[E]) Contains(element E) bool
- func (s Set[E]) Difference(other Set[E]) Set[E]
- func (s Set[E]) Elements() []E
- func (s Set[E]) Encloses(other Set[E]) bool
- func (s Set[E]) Equal(other Set[E]) bool
- func (s Set[E]) First() (E, bool)
- func (s Set[E]) Index(element E) (int, bool)
- func (s Set[E]) Intersection(other Set[E]) Set[E]
- func (s Set[E]) Intersects(other Set[E]) bool
- func (s Set[E]) IsEmpty() bool
- func (s Set[E]) Last() (E, bool)
- func (s Set[E]) Len() int
- func (s Set[E]) MarshalJSON() ([]byte, error)
- func (s Set[E]) SymmetricDifference(other Set[E]) Set[E]
- func (s Set[E]) Union(other Set[E]) Set[E]
- func (s *Set[E]) UnmarshalJSON(data []byte) error
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Array ¶
Array is a table of values of type T, one for every index of a size in columns and rows, stored row by row. Its sides and indices are of the integer type S, which bounds each side by what S holds; only the number of values is an int. It is a handle: a copy shares its values, and Array.Clone gives storage of its own. The zero value is the empty array.
func Arr ¶
Arr returns an array of the given size, every value zero. It panics for a negative width or height, and for a size of more values than an int counts.
Example ¶
a := Arr[int](geom.Sz(4, 3))
small := Arr[uint8](geom.Sz[int16](320, 200))
a.Set(geom.Pt(2, 1), 7)
*a.Get(geom.Pt(2, 1)) += 1
snapshot := a.Clone()
for index, value := range a.All() {
*value += index.X
}
values := a.Data()
for i := range values {
values[i] = min(values[i], 9)
}
data, _ := json.Marshal(a)
var decoded Array[int, int]
err := json.Unmarshal(data, &decoded)
fmt.Println(a.Contains(geom.Pt(4, 0)), a.Size(), a.Len(), small.Size())
fmt.Println(snapshot.Data())
fmt.Println(a.Data())
fmt.Println(string(data))
fmt.Println(decoded.Data(), err)
Output: false 4x3 12 320x200 [0 0 0 0 0 0 8 0 0 0 0 0] [0 1 2 3 0 1 9 3 0 1 2 3] {"w":4,"h":3,"d":[0,1,2,3,0,1,9,3,0,1,2,3]} [0 1 2 3 0 1 9 3 0 1 2 3] <nil>
func (Array[T, S]) All ¶
All returns an iterator over every index with a pointer into the array to its value, in the order of Keys.
func (Array[T, S]) Clear ¶
func (a Array[T, S]) Clear()
Clear resets every value of the array to the zero value.
func (Array[T, S]) Clone ¶
Clone returns a copy of the array with storage of its own, its values copied as an assignment copies them.
func (Array[T, S]) Data ¶
func (a Array[T, S]) Data() []T
Data returns the values of the array row by row as a slice into the array: a write through it changes the array, and an append to it never does. It is nil for the zero array.
func (Array[T, S]) Fill ¶
func (a Array[T, S]) Fill(value T)
Fill sets every value of the array to value.
func (Array[T, S]) Get ¶
Get returns a pointer into the array to the value at the index: a write through it changes the array. It panics for an index outside the array.
func (Array[T, S]) Height ¶
func (a Array[T, S]) Height() S
Height returns the number of rows of the array.
func (Array[T, S]) Len ¶
Len returns the number of values of the array (width·height), an int whatever S is.
func (Array[T, S]) MarshalJSON ¶
MarshalJSON implements json.Marshaler with the size of the array, flat as geom.Size writes it, and its values row by row, null for the zero array.
func (*Array[T, S]) UnmarshalJSON ¶
UnmarshalJSON implements json.Unmarshaler, reading null as the zero array and null values as none. It returns an error for a size Arr panics for or S cannot hold, and for a number of values other than the width times the height, and leaves the array as it was on an error.
type Set ¶
type Set[E interface{ Compare(E) int }] struct {
// contains filtered or unexported fields
}
Set is an immutable set of elements, held once each in the order of their Compare method, which alone decides that two elements are the same and must be a total order. A set is safe to copy and share. The zero value is the empty set.
func SetFrom ¶
SetFrom returns the set of the given elements, in any order and with any repeats, taking the slice as its own: it rearranges what the slice holds, and a later write to it changes the set.
func SetOf ¶
SetOf returns the set of the given elements, in any order and with any repeats.
Example ¶
a := SetOf(geom.Pt(1, 1), geom.Pt(2, 1), geom.Pt(1, 2), geom.Pt(2, 2))
points := []geom.Point[int]{geom.Pt(2, 2), geom.Pt(1, 1), geom.Pt(2, 1), geom.Pt(1, 2), geom.Pt(1, 1)}
from := SetFrom(points)
first, ok := a.First()
index, found := a.Index(geom.Pt(2, 1))
fmt.Println(from.Equal(a), a.Contains(geom.Pt(2, 1)), a.Len())
fmt.Println(first, ok, index, found)
fmt.Println(slices.Collect(a.All()), slices.Collect(a.Backward()))
fmt.Println(a.Elements())
data, _ := json.Marshal(a)
fmt.Println(string(data))
Output: true true 4 (1,1) true 2 true [(1,1) (1,2) (2,1) (2,2)] [(2,2) (2,1) (1,2) (1,1)] [(1,1) (1,2) (2,1) (2,2)] [{"x":1,"y":1},{"x":1,"y":2},{"x":2,"y":1},{"x":2,"y":2}]
func (Set[E]) AppendElements ¶
func (s Set[E]) AppendElements(dst []E) []E
AppendElements appends the elements of Elements to dst and returns the extended slice.
func (Set[E]) At ¶
At returns the element at the index in the order of the set. It panics for an index outside the set.
func (Set[E]) Backward ¶
Backward returns an iterator over the elements of the set, in reverse order.
func (Set[E]) Difference ¶
Difference returns the set of the elements in s that are not in other.
func (Set[E]) Elements ¶
func (s Set[E]) Elements() []E
Elements returns the elements of the set in order, and nil for the empty set.
func (Set[E]) Encloses ¶
Encloses reports whether s holds every element of other. Every set encloses the empty one.
func (Set[E]) First ¶
First returns the first element in the order of the set and true, or false for the empty set.
func (Set[E]) Index ¶
Index returns the index of the element in the order of the set, the one At reads it back from, and true, or false where the set does not hold it.
func (Set[E]) Intersection ¶
Intersection returns the set of the elements in both s and other.
func (Set[E]) Intersects ¶
Intersects reports whether s and other hold an element in common.
func (Set[E]) Last ¶
Last returns the last element in the order of the set and true, or false for the empty set.
func (Set[E]) MarshalJSON ¶
MarshalJSON implements json.Marshaler with the elements as an array in order, null for the empty set.
func (Set[E]) SymmetricDifference ¶
SymmetricDifference returns the set of the elements in s or in other, and not in both.
func (Set[E]) Union ¶
Union returns the set of the elements in s, in other or in both.
Example ¶
a := SetOf(geom.Pt(1, 1), geom.Pt(2, 1), geom.Pt(1, 2), geom.Pt(2, 2)) b := SetOf(geom.Pt(2, 2), geom.Pt(3, 2), geom.Pt(2, 3), geom.Pt(3, 3)) fmt.Println(a.Union(b).Elements()) fmt.Println(a.Intersection(b).Elements()) fmt.Println(a.Difference(b).Elements()) fmt.Println(a.SymmetricDifference(b).Elements()) fmt.Println(a.Intersects(b), a.Encloses(b), a.Equal(b))
Output: [(1,1) (1,2) (2,1) (2,2) (2,3) (3,2) (3,3)] [(2,2)] [(1,1) (1,2) (2,1)] [(1,1) (1,2) (2,1) (2,3) (3,2) (3,3)] true false false
func (*Set[E]) UnmarshalJSON ¶
UnmarshalJSON implements json.Unmarshaler, reading an array of elements in any order and with any repeats, and null or an empty array as the empty set. It leaves the set as it was on an error.
Source Files