ds

package
v0.5.5 Latest Latest
Warning

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

 Go to latest Published: Jan 7, 2025 License: Apache-2.0 Imports: 2 Imported by: 1

Documentation

Overview

Package ds defines and implements a collection of data structures, designed to hold cross-products of two Set structures in a succinct and canonical way. The most important interface is Product. It is implemented by ProductLeft using injective (one-to-one) mapping from sets to sets, where each key-value pair defines a complete cross product of the two sets.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Comparable 

type Comparable[Self any] interface {
	Equal(Self) bool
	Copy() Self
}

type Disjoint 

type Disjoint[L Set[L], R Set[R]] struct {
	// contains filtered or unexported fields
}

Disjoint is the union of two disjoint (tagged) sets L and R.

func NewDisjoint 

func NewDisjoint[L Set[L], R Set[R]](left L, right R) *Disjoint[L, R]

NewDisjoint creates a new Disjoint set from two sets. This is the only way to create a Disjoint set, since Go does not support creating an empty value of a generic type.

func (*Disjoint[L, R]) Copy 

func (c *Disjoint[L, R]) Copy() *Disjoint[L, R]

Copy returns a deep copy of the Disjoint set.

func (*Disjoint[L, R]) Equal 

func (c *Disjoint[L, R]) Equal(other *Disjoint[L, R]) bool

Equal returns true if both left and right sets are equal to the other's left and right sets.

func (*Disjoint[L, R]) Hash 

func (c *Disjoint[L, R]) Hash() int

Hash returns the hash value of the Disjoint set.

func (*Disjoint[L, R]) Intersect 

func (c *Disjoint[L, R]) Intersect(other *Disjoint[L, R]) *Disjoint[L, R]

Intersect returns the intersection of the left set with the other's left set and the right set with the other's right set.

func (*Disjoint[L, R]) IsEmpty 

func (c *Disjoint[L, R]) IsEmpty() bool

IsEmpty returns true if both left and right sets are empty.

func (*Disjoint[L, R]) IsSubset 

func (c *Disjoint[L, R]) IsSubset(other *Disjoint[L, R]) bool

IsSubset returns true if both left and right sets are subsets of the other's left and right sets.

func (*Disjoint[L, R]) Left 

func (c *Disjoint[L, R]) Left() L

Left returns the left-tagged set of the Disjoint set.

func (*Disjoint[L, R]) Right 

func (c *Disjoint[L, R]) Right() R

Right returns the right-tagged set of the Disjoint set.

func (*Disjoint[L, R]) Size 

func (c *Disjoint[L, R]) Size() int

Size returns the sum of the sizes of the left and right sets.

func (*Disjoint[L, R]) Subtract 

func (c *Disjoint[L, R]) Subtract(other *Disjoint[L, R]) *Disjoint[L, R]

Subtract returns the subtraction of the left set with the other's left set and the right set with the other's right set.

func (*Disjoint[L, R]) Union 

func (c *Disjoint[L, R]) Union(other *Disjoint[L, R]) *Disjoint[L, R]

Union returns the union of the left set with the other's left set and the right set with the other's right set.

type HashMap 

type HashMap[K Hashable[K], V Comparable[V]] struct {
	// contains filtered or unexported fields
}

HashMap is a generic hash map with keys of a Hashable type K and values of Comparable type V.

func NewHashMap 

func NewHashMap[K Hashable[K], V Comparable[V]]() *HashMap[K, V]

NewHashMap creates a new empty hash map.

func (*HashMap[K, V]) At 

func (m *HashMap[K, V]) At(k K) (res V, ok bool)

At returns a pair of a value and a boolean indicating whether the key exists in the map. The value is only valid if the boolean is true.

func (*HashMap[K, V]) Copy 

func (m *HashMap[K, V]) Copy() *HashMap[K, V]

Copy returns a deep copy of the map.

func (*HashMap[K, V]) Delete 

func (m *HashMap[K, V]) Delete(k K)

Delete a key and its value from the map, if it exists.

func (*HashMap[K, V]) Equal 

func (m *HashMap[K, V]) Equal(other *HashMap[K, V]) bool

Equal returns true if the map holds the same key-value pairs as the other map.

func (*HashMap[K, V]) Insert 

func (m *HashMap[K, V]) Insert(k K, v V)

Insert a mapping from a copy of a key k to a copy of a value v into the map.

func (*HashMap[K, V]) IsEmpty 

func (m *HashMap[K, V]) IsEmpty() bool

IsEmpty returns true if the map is empty.

func (*HashMap[K, V]) Keys 

func (m *HashMap[K, V]) Keys() []K

Keys returns a slice of all keys in the map.

func (*HashMap[K, V]) Pairs 

func (m *HashMap[K, V]) Pairs() []Pair[K, V]

Pairs returns a slice of all key-value pairs in the map.

func (*HashMap[K, V]) Size 

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

Size returns the number of key-value pairs in the map.

func (*HashMap[K, V]) Values 

func (m *HashMap[K, V]) Values() []V

Values returns a slice of all (not necessarily unique) values in the map.

type HashSet 

type HashSet[V Hashable[V]] struct {
	// contains filtered or unexported fields
}

HashSet is a generic set with elements of a Hashable type V.

func NewHashSet 

func NewHashSet[V Hashable[V]](items ...V) *HashSet[V]

NewHashSet creates a new hash set with the given elements. Repeated elements are ignored.

func (*HashSet[V]) Contains 

func (m *HashSet[V]) Contains(v V) bool

Contains returns true if the value exists in the set.

func (*HashSet[V]) Copy 

func (m *HashSet[V]) Copy() *HashSet[V]

Copy returns a deep copy of the set.

func (*HashSet[V]) Delete 

func (m *HashSet[V]) Delete(v V)

Delete a value from the set, if it exists.

func (*HashSet[V]) Equal 

func (m *HashSet[V]) Equal(other *HashSet[V]) bool

Equal returns true if the set contains exactly the same elements as the other set.

func (*HashSet[V]) Insert 

func (m *HashSet[V]) Insert(v V)

Insert a value into the set, if it does not already exist.

func (*HashSet[V]) IsEmpty 

func (m *HashSet[V]) IsEmpty() bool

IsEmpty returns true if the set is empty.

func (*HashSet[V]) Items 

func (m *HashSet[V]) Items() []V

Items returns a slice of all (non-repeated) values in the set.

func (*HashSet[V]) Size 

func (m *HashSet[V]) Size() int

Size returns the number of elements in the set.

type Hashable 

type Hashable[Self any] interface {
	Comparable[Self]
	Hash() int
}

type LeftTripleSet 

type LeftTripleSet[S1 Set[S1], S2 Set[S2], S3 Set[S3]] struct {
	// contains filtered or unexported fields
}

LeftTripleSet is a left-associative 3-product of sets (S1 x S2) x S3

func AsLeftTripleSet added in v0.5.4 

func AsLeftTripleSet[S1 Set[S1], S2 Set[S2], S3 Set[S3]](other TripleSet[S1, S2, S3]) *LeftTripleSet[S1, S2, S3]

func CartesianLeftTriple 

func CartesianLeftTriple[S1 Set[S1], S2 Set[S2], S3 Set[S3]](s1 S1, s2 S2, s3 S3) *LeftTripleSet[S1, S2, S3]

func NewLeftTripleSet 

func NewLeftTripleSet[S1 Set[S1], S2 Set[S2], S3 Set[S3]]() *LeftTripleSet[S1, S2, S3]

func (*LeftTripleSet[S1, S2, S3]) Copy 

func (c *LeftTripleSet[S1, S2, S3]) Copy() TripleSet[S1, S2, S3]

func (*LeftTripleSet[S1, S2, S3]) Equal 

func (c *LeftTripleSet[S1, S2, S3]) Equal(other TripleSet[S1, S2, S3]) bool

func (*LeftTripleSet[S1, S2, S3]) Hash 

func (c *LeftTripleSet[S1, S2, S3]) Hash() int

func (*LeftTripleSet[S1, S2, S3]) Intersect 

func (c *LeftTripleSet[S1, S2, S3]) Intersect(other TripleSet[S1, S2, S3]) TripleSet[S1, S2, S3]

func (*LeftTripleSet[S1, S2, S3]) IsEmpty 

func (c *LeftTripleSet[S1, S2, S3]) IsEmpty() bool

func (*LeftTripleSet[S1, S2, S3]) IsSubset 

func (c *LeftTripleSet[S1, S2, S3]) IsSubset(other TripleSet[S1, S2, S3]) bool

IsSubset returns true if c is subset of other

func (*LeftTripleSet[S1, S2, S3]) NumPartitions 

func (c *LeftTripleSet[S1, S2, S3]) NumPartitions() int

func (*LeftTripleSet[S1, S2, S3]) Partitions 

func (c *LeftTripleSet[S1, S2, S3]) Partitions() []Triple[S1, S2, S3]

func (*LeftTripleSet[S1, S2, S3]) Size 

func (c *LeftTripleSet[S1, S2, S3]) Size() int

func (*LeftTripleSet[S1, S2, S3]) String 

func (c *LeftTripleSet[S1, S2, S3]) String() string

func (*LeftTripleSet[S1, S2, S3]) Subtract 

func (c *LeftTripleSet[S1, S2, S3]) Subtract(other TripleSet[S1, S2, S3]) TripleSet[S1, S2, S3]

func (*LeftTripleSet[S1, S2, S3]) Union 

func (c *LeftTripleSet[S1, S2, S3]) Union(other TripleSet[S1, S2, S3]) TripleSet[S1, S2, S3]

type MultiMap 

type MultiMap[K Hashable[K], V Hashable[V]] struct {
	// contains filtered or unexported fields
}

MultiMap is a mapping from keys to sets of values

func InverseMap 

func InverseMap[K Hashable[K], V Hashable[V]](m *HashMap[K, V]) *MultiMap[V, K]

InverseMap take a HashMap and returns a new multimap where every value in the original map is a key in the new map.

func NewMultiMap 

func NewMultiMap[K Hashable[K], V Hashable[V]]() *MultiMap[K, V]

NewMultiMap creates a new empty multimap

func (*MultiMap[K, V]) At 

func (m *MultiMap[K, V]) At(k K) *HashSet[V]

At returns a copy of the set of values for a key k

func (*MultiMap[K, V]) Copy 

func (m *MultiMap[K, V]) Copy() *MultiMap[K, V]

Copy returns a deep copy of the multimap

func (*MultiMap[K, V]) Delete 

func (m *MultiMap[K, V]) Delete(k K)

Delete k and all its values from the map

func (*MultiMap[K, V]) Equal 

func (m *MultiMap[K, V]) Equal(other *MultiMap[K, V]) bool

Equal returns true if the multimap is equal to the other multimap. That is, if they have the same set of Pairs().

func (*MultiMap[K, V]) Insert 

func (m *MultiMap[K, V]) Insert(k K, v V)

Insert a mapping from a key k to a value v into the multimap

func (*MultiMap[K, V]) IsEmpty 

func (m *MultiMap[K, V]) IsEmpty() bool

IsEmpty returns true if the multimap is empty

func (*MultiMap[K, V]) Keys 

func (m *MultiMap[K, V]) Keys() []K

Keys returns a slice of unique keys in the multimap

func (*MultiMap[K, V]) MultiPairs 

func (m *MultiMap[K, V]) MultiPairs() []Pair[K, *HashSet[V]]

MultiPairs returns a slice of (key, set of values) pairs in the multimap. The keys are unique.

func (*MultiMap[K, V]) Pairs 

func (m *MultiMap[K, V]) Pairs() []Pair[K, V]

Pairs returns a slice of (key, value) pairs in the multimap. It is a flattened version of MultiPairs.

func (*MultiMap[K, V]) Size 

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

Size returns the number of key-value pairs in the multimap, that is the length of Pairs()

func (*MultiMap[K, V]) Values 

func (m *MultiMap[K, V]) Values() []V

Values returns a slice of all (possibly repeating) values in the multimap

type OuterTripleSet 

type OuterTripleSet[S1 Set[S1], S2 Set[S2], S3 Set[S3]] struct {
	// contains filtered or unexported fields
}

OuterTripleSet is an outer-associative 3-product of sets (S1 x S3) x S2, created as LeftTripleSet[S1, S3, S2] (Product[Product[S1, S3], S2])

func AsOuterTripleSet added in v0.5.4 

func AsOuterTripleSet[S1 Set[S1], S2 Set[S2], S3 Set[S3]](other TripleSet[S1, S2, S3]) *OuterTripleSet[S1, S2, S3]

func CartesianOuterTriple 

func CartesianOuterTriple[S1 Set[S1], S2 Set[S2], S3 Set[S3]](s1 S1, s2 S2, s3 S3) *OuterTripleSet[S1, S2, S3]

func NewOuterTripleSet 

func NewOuterTripleSet[S1 Set[S1], S2 Set[S2], S3 Set[S3]]() *OuterTripleSet[S1, S2, S3]

func (*OuterTripleSet[S1, S2, S3]) Copy 

func (c *OuterTripleSet[S1, S2, S3]) Copy() TripleSet[S1, S2, S3]

func (*OuterTripleSet[S1, S2, S3]) Equal 

func (c *OuterTripleSet[S1, S2, S3]) Equal(other TripleSet[S1, S2, S3]) bool

func (*OuterTripleSet[S1, S2, S3]) Hash 

func (c *OuterTripleSet[S1, S2, S3]) Hash() int

func (*OuterTripleSet[S1, S2, S3]) Intersect 

func (c *OuterTripleSet[S1, S2, S3]) Intersect(other TripleSet[S1, S2, S3]) TripleSet[S1, S2, S3]

func (*OuterTripleSet[S1, S2, S3]) IsEmpty 

func (c *OuterTripleSet[S1, S2, S3]) IsEmpty() bool

func (*OuterTripleSet[S1, S2, S3]) IsSubset 

func (c *OuterTripleSet[S1, S2, S3]) IsSubset(other TripleSet[S1, S2, S3]) bool

IsSubset returns true if c is subset of other

func (*OuterTripleSet[S1, S2, S3]) Partitions 

func (c *OuterTripleSet[S1, S2, S3]) Partitions() []Triple[S1, S2, S3]

func (*OuterTripleSet[S1, S2, S3]) Size 

func (c *OuterTripleSet[S1, S2, S3]) Size() int

func (*OuterTripleSet[S1, S2, S3]) String 

func (c *OuterTripleSet[S1, S2, S3]) String() string

func (*OuterTripleSet[S1, S2, S3]) Subtract 

func (c *OuterTripleSet[S1, S2, S3]) Subtract(other TripleSet[S1, S2, S3]) TripleSet[S1, S2, S3]

func (*OuterTripleSet[S1, S2, S3]) Union 

func (c *OuterTripleSet[S1, S2, S3]) Union(other TripleSet[S1, S2, S3]) TripleSet[S1, S2, S3]

type Pair 

type Pair[L, R any] struct {
	Left  L
	Right R
}

type Product 

type Product[S1 Set[S1], S2 Set[S2]] interface {
	Set[Product[S1, S2]]

	// Partitions returns a slice of pairs such that, for (p Product):
	// 	  p.Equal(Union(CartesianPairLeft(s1, s2) for _, (s1, s2) := range p.Partitions())
	// (note that the order is arbitrary; we do not return HashSet because Pair is not Hashable)
	// Partitions returns a slice of pairs in the product set  (note that the order is arbitrary)
	Partitions() []Pair[S1, S2]

	// NumPartitions returns len(Partitions()). It is different from Size() which should return the number of concrete pairs of elements.
	NumPartitions() int

	// Left returns the left projection from pairs in the product set on S1, given input of an empty set in S1.
	Left(empty S1) S1

	// Right returns the right projection from pairs in the product set S2, given input of an empty set in S2.
	Right(empty S2) S2

	// Swap returns a new Product object, built from the input object, with left and right swapped.
	Swap() Product[S2, S1]
}

Product is a cartesian product of sets S1 x S2

type ProductLeft 

type ProductLeft[K Set[K], V Set[V]] struct {
	// contains filtered or unexported fields
}

ProductLeft is a cartesian product of two sets The implementation represents the sets succinctly, merging keys with equivalent values to a single key, so the mapping is injective (one-to-one).

func CartesianPairLeft 

func CartesianPairLeft[K Set[K], V Set[V]](k K, v V) *ProductLeft[K, V]

CartesianPairLeft returns a new Product object holding the cartesian product of the input sets k x v. If either k or v is empty, the result is an empty Product object.

func NewProductLeft 

func NewProductLeft[K Set[K], V Set[V]]() *ProductLeft[K, V]

NewProductLeft with parameters [K, V] creates an empty Product[K, V] object, implemented using K sets are keys and V sets as values.

func (*ProductLeft[K, V]) Copy 

func (m *ProductLeft[K, V]) Copy() Product[K, V]

Copy returns a deep copy of the Product object.

func (*ProductLeft[K, V]) Equal 

func (m *ProductLeft[K, V]) Equal(other Product[K, V]) bool

Equal returns true if this and other are equivalent Product object.

func (*ProductLeft[K, V]) Hash 

func (m *ProductLeft[K, V]) Hash() int

Hash returns the hash value of the Product object

func (*ProductLeft[K, V]) Intersect 

func (m *ProductLeft[K, V]) Intersect(other Product[K, V]) Product[K, V]

Intersect returns a new Product object that results from intersection of m with other.

func (*ProductLeft[K, V]) IsEmpty 

func (m *ProductLeft[K, V]) IsEmpty() bool

IsEmpty returns true if the Product object is empty.

func (*ProductLeft[K, V]) IsSubset 

func (m *ProductLeft[K, V]) IsSubset(other Product[K, V]) bool

IsSubset returns true if m is a subset of other.

func (*ProductLeft[K, V]) Left 

func (m *ProductLeft[K, V]) Left(empty K) K

Left returns the projection Product[K, V] on the set K.

func (*ProductLeft[K, V]) NumPartitions 

func (m *ProductLeft[K, V]) NumPartitions() int

NumPartitions returns the number of unique partitions in the Product object

func (*ProductLeft[K, V]) Partitions 

func (m *ProductLeft[K, V]) Partitions() []Pair[K, V]

Partitions returns a slice of all unique partitions in the Product object

func (*ProductLeft[K, V]) Right 

func (m *ProductLeft[K, V]) Right(empty V) V

Right returns the projection Product[K, V] on the set V.

func (*ProductLeft[K, V]) Size 

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

Size returns the number of unique pairs in the Product object

func (*ProductLeft[K, V]) String 

func (m *ProductLeft[K, V]) String() string

func (*ProductLeft[K, V]) Subtract 

func (m *ProductLeft[K, V]) Subtract(other Product[K, V]) Product[K, V]

Subtract returns a new Product object that results from subtraction other from m.

func (*ProductLeft[K, V]) Swap 

func (m *ProductLeft[K, V]) Swap() Product[V, K]

Swap returns a new Product object, built from the input Product object, with left and right swapped

func (*ProductLeft[K, V]) Union 

func (m *ProductLeft[K, V]) Union(other Product[K, V]) Product[K, V]

Union returns a new Product object that results from union of m with other.

type RightTripleSet 

type RightTripleSet[S1 Set[S1], S2 Set[S2], S3 Set[S3]] struct {
	// contains filtered or unexported fields
}

RightTripleSet is a right-associative 3-product of sets S1 x (S2 x S3), created as LeftTripleSet[S2, S3, S1] (Product[Product[S2, S3], S1])

func AsRightTripleSet added in v0.5.4 

func AsRightTripleSet[S1 Set[S1], S2 Set[S2], S3 Set[S3]](other TripleSet[S1, S2, S3]) *RightTripleSet[S1, S2, S3]

func CartesianRightTriple 

func CartesianRightTriple[S1 Set[S1], S2 Set[S2], S3 Set[S3]](s1 S1, s2 S2, s3 S3) *RightTripleSet[S1, S2, S3]

func NewRightTripleSet 

func NewRightTripleSet[S1 Set[S1], S2 Set[S2], S3 Set[S3]]() *RightTripleSet[S1, S2, S3]

func (*RightTripleSet[S1, S2, S3]) Copy 

func (c *RightTripleSet[S1, S2, S3]) Copy() TripleSet[S1, S2, S3]

func (*RightTripleSet[S1, S2, S3]) Equal 

func (c *RightTripleSet[S1, S2, S3]) Equal(other TripleSet[S1, S2, S3]) bool

func (*RightTripleSet[S1, S2, S3]) Hash 

func (c *RightTripleSet[S1, S2, S3]) Hash() int

func (*RightTripleSet[S1, S2, S3]) Intersect 

func (c *RightTripleSet[S1, S2, S3]) Intersect(other TripleSet[S1, S2, S3]) TripleSet[S1, S2, S3]

func (*RightTripleSet[S1, S2, S3]) IsEmpty 

func (c *RightTripleSet[S1, S2, S3]) IsEmpty() bool

func (*RightTripleSet[S1, S2, S3]) IsSubset 

func (c *RightTripleSet[S1, S2, S3]) IsSubset(other TripleSet[S1, S2, S3]) bool

IsSubset returns true if c is subset of other

func (*RightTripleSet[S1, S2, S3]) Partitions 

func (c *RightTripleSet[S1, S2, S3]) Partitions() []Triple[S1, S2, S3]

func (*RightTripleSet[S1, S2, S3]) Size 

func (c *RightTripleSet[S1, S2, S3]) Size() int

func (*RightTripleSet[S1, S2, S3]) String 

func (c *RightTripleSet[S1, S2, S3]) String() string

func (*RightTripleSet[S1, S2, S3]) Subtract 

func (c *RightTripleSet[S1, S2, S3]) Subtract(other TripleSet[S1, S2, S3]) TripleSet[S1, S2, S3]

func (*RightTripleSet[S1, S2, S3]) Union 

func (c *RightTripleSet[S1, S2, S3]) Union(other TripleSet[S1, S2, S3]) TripleSet[S1, S2, S3]

type Set 

type Set[Self any] interface {
	Hashable[Self]
	Sized
	IsSubset(Self) bool
	Union(Self) Self
	Intersect(Self) Self
	Subtract(Self) Self
	String() string
}

type Sized 

type Sized interface {
	IsEmpty() bool

	// Size returns the actual, full size of the set.
	// For Product, it returns the number of pairs of concrete elements that belong to the product, not the number of Partitions().
	// In other words, for Product, p.Size() == sum(s1.Size() * s2.Size() for _, (s1, s2) := range p.Partitions())
	Size() int
}

type Triple 

type Triple[S1, S2, S3 any] struct {
	S1 S1
	S2 S2
	S3 S3
}

func (Triple[S1, S2, S3]) ID 

func (t Triple[S1, S2, S3]) ID() Triple[S1, S2, S3]

func (Triple[S1, S2, S3]) ShiftLeft 

func (t Triple[S1, S2, S3]) ShiftLeft() Triple[S2, S3, S1]

func (Triple[S1, S2, S3]) ShiftRight 

func (t Triple[S1, S2, S3]) ShiftRight() Triple[S3, S1, S2]

func (Triple[S1, S2, S3]) Swap12 

func (t Triple[S1, S2, S3]) Swap12() Triple[S2, S1, S3]

func (Triple[S1, S2, S3]) Swap13 

func (t Triple[S1, S2, S3]) Swap13() Triple[S3, S2, S1]

func (Triple[S1, S2, S3]) Swap23 

func (t Triple[S1, S2, S3]) Swap23() Triple[S1, S3, S2]

type TripleSet 

type TripleSet[S1 Set[S1], S2 Set[S2], S3 Set[S3]] interface {
	Set[TripleSet[S1, S2, S3]]
	Partitions() []Triple[S1, S2, S3]
}

TripleSet is a 3-product of sets S1 x S2 x S3

func MapTripleSet 

func MapTripleSet[S1 Set[S1], S2 Set[S2], S3 Set[S3], T1 Set[T1], T2 Set[T2], T3 Set[T3]](c TripleSet[S1, S2, S3],
	f func(Triple[S1, S2, S3]) Triple[T1, T2, T3]) TripleSet[T1, T2, T3]

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.