Documentation
¶
Index ¶
- func AnyTopologicalOrderPermutation[T comparable](p *PartiallyOrderedSet[T]) []T
- type Builder
- type EligibleSet
- type EnumeratingIterator
- func Permutations[T comparable](set []T) EnumeratingIterator[T]
- func SatisfyingPermutations[T comparable](p *PartiallyOrderedSet[T], targetPermutation []T, ...) EnumeratingIterator[T]
- func SatisfyingPermutationsWithMapper[T, P comparable](p *PartiallyOrderedSet[T], targetPermutation []P, domainMapper func(T) P, ...) EnumeratingIterator[T]
- func TopologicalOrderPermutations[T comparable](p *PartiallyOrderedSet[T]) EnumeratingIterator[T]
- type MapEntry
- type PartiallyOrderedSet
- func EmptyPartiallyOrderedSet[T comparable]() *PartiallyOrderedSet[T]
- func MapAll[T, R comparable](p *PartiallyOrderedSet[T], m map[T]R) *PartiallyOrderedSet[R]
- func NewPartiallyOrderedSet[T comparable](set []T, dependencyMap SetMultimap[T]) *PartiallyOrderedSet[T]
- func NewPartiallyOrderedSetFromFunc[T comparable](set []T, dependsOnFn func(T) map[T]struct{}) *PartiallyOrderedSet[T]
- func NewPartiallyOrderedSetInverted[T comparable](set []T, dependencyMap SetMultimap[T]) *PartiallyOrderedSet[T]
- func (p *PartiallyOrderedSet[T]) DependencyMap() SetMultimap[T]
- func (p *PartiallyOrderedSet[T]) DualOrder() *PartiallyOrderedSet[T]
- func (p *PartiallyOrderedSet[T]) EligibleSet() *EligibleSet[T]
- func (p *PartiallyOrderedSet[T]) Equal(other *PartiallyOrderedSet[T]) bool
- func (p *PartiallyOrderedSet[T]) FilterElements(predicate func(T) bool) *PartiallyOrderedSet[T]
- func (p *PartiallyOrderedSet[T]) IsEmpty() bool
- func (p *PartiallyOrderedSet[T]) Set() []T
- func (p *PartiallyOrderedSet[T]) SetLookup() map[T]struct{}
- func (p *PartiallyOrderedSet[T]) Size() int
- func (p *PartiallyOrderedSet[T]) String() string
- func (p *PartiallyOrderedSet[T]) TransitiveClosure() SetMultimap[T]
- type SetMultimap
- func FromFunctionalDependencies[T comparable](set map[T]struct{}, dependsOnFn func(T) map[T]struct{}) SetMultimap[T]
- func InvertFromFunctionalDependencies[T comparable](set map[T]struct{}, dependsOnFn func(T) map[T]struct{}) SetMultimap[T]
- func NewSetMultimap[T comparable]() SetMultimap[T]
- func TransitiveClosure[T comparable](p *PartiallyOrderedSet[T]) SetMultimap[T]
- func (m SetMultimap[T]) Clone() SetMultimap[T]
- func (m SetMultimap[T]) Contains(key, value T) bool
- func (m SetMultimap[T]) Entries() []MapEntry[T]
- func (m SetMultimap[T]) Get(key T) map[T]struct{}
- func (m SetMultimap[T]) Inverse() SetMultimap[T]
- func (m SetMultimap[T]) IsEmpty() bool
- func (m SetMultimap[T]) Put(key, value T)
- func (m SetMultimap[T]) Size() int
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func AnyTopologicalOrderPermutation ¶
func AnyTopologicalOrderPermutation[T comparable](p *PartiallyOrderedSet[T]) []T
AnyTopologicalOrderPermutation returns a single valid topological ordering, or nil if none exists (circular dependencies).
Types ¶
type Builder ¶
type Builder[T comparable] struct { // contains filtered or unexported fields }
Builder for constructing PartiallyOrderedSet incrementally.
func NewBuilder ¶
func NewBuilder[T comparable]() *Builder[T]
func (*Builder[T]) AddDependency ¶
AddDependency adds a dependency: target depends on source.
func (*Builder[T]) AddListWithDependencies ¶
AddListWithDependencies adds elements in order, creating a dependency chain: each element depends on the previous one.
func (*Builder[T]) Build ¶
func (b *Builder[T]) Build() *PartiallyOrderedSet[T]
type EligibleSet ¶
type EligibleSet[T comparable] struct { // contains filtered or unexported fields }
EligibleSet computes subsets of elements that are minimal (no unsatisfied dependencies). Used for iterative topological consumption.
func (*EligibleSet[T]) EligibleElements ¶
func (e *EligibleSet[T]) EligibleElements() map[T]struct{}
func (*EligibleSet[T]) IsEmpty ¶
func (e *EligibleSet[T]) IsEmpty() bool
func (*EligibleSet[T]) PartialOrder ¶
func (e *EligibleSet[T]) PartialOrder() *PartiallyOrderedSet[T]
func (*EligibleSet[T]) RemoveEligibleElements ¶
func (e *EligibleSet[T]) RemoveEligibleElements(toRemove map[T]struct{}) *EligibleSet[T]
RemoveEligibleElements removes the given elements (which must be currently eligible) and returns a new EligibleSet reflecting the reduced partial order.
type EnumeratingIterator ¶
type EnumeratingIterator[T comparable] interface { // Next returns the next permutation, or nil if exhausted. Next() []T // Skip advances past all permutations sharing the prefix up to // and including the given zero-indexed level. Skip(level int) }
EnumeratingIterator iterates over permutations of a set, optionally respecting partial-order constraints. Supports skip() for pruning.
Mirrors Java's EnumeratingIterator + EnumeratingIterable.
func Permutations ¶
func Permutations[T comparable](set []T) EnumeratingIterator[T]
Permutations returns an iterator over all permutations of the set (no dependency constraints).
func SatisfyingPermutations ¶
func SatisfyingPermutations[T comparable]( p *PartiallyOrderedSet[T], targetPermutation []T, satisfiabilityFn func([]T) int, ) EnumeratingIterator[T]
SatisfyingPermutations returns an iterator that yields only permutations where the first len(targetPermutation) elements match the target (via domainMapper), using the satisfiability function to prune. The satisfiability function returns the index up to which the permutation satisfies the target; if it equals len(targetPermutation), the permutation is accepted.
func SatisfyingPermutationsWithMapper ¶
func SatisfyingPermutationsWithMapper[T, P comparable]( p *PartiallyOrderedSet[T], targetPermutation []P, domainMapper func(T) P, satisfiabilityFn func([]T) int, ) EnumeratingIterator[T]
SatisfyingPermutationsWithMapper is like SatisfyingPermutations but with a domain mapper function that maps elements from T to the target domain P.
func TopologicalOrderPermutations ¶
func TopologicalOrderPermutations[T comparable](p *PartiallyOrderedSet[T]) EnumeratingIterator[T]
TopologicalOrderPermutations returns an iterator over all permutations of the partial order that respect its dependency constraints.
type MapEntry ¶
type MapEntry[T comparable] struct { Key T Value T }
MapEntry is a key-value pair from a SetMultimap.
type PartiallyOrderedSet ¶
type PartiallyOrderedSet[T comparable] struct { // contains filtered or unexported fields }
PartiallyOrderedSet represents a partially ordered set of elements. A partial order over a set is a relation that is irreflexive, transitive, and asymmetric. The dependency map encodes "key depends on value" edges.
Mirrors Java's com.apple.foundationdb.record.query.combinatorics.PartiallyOrderedSet.
func EmptyPartiallyOrderedSet ¶
func EmptyPartiallyOrderedSet[T comparable]() *PartiallyOrderedSet[T]
EmptyPartiallyOrderedSet returns an empty partial order.
func MapAll ¶
func MapAll[T, R comparable](p *PartiallyOrderedSet[T], m map[T]R) *PartiallyOrderedSet[R]
MapAll maps this partial order to a different domain while maintaining dependencies. Elements not in the map (and elements depending on unmapped elements with no alternative dependency chain) are removed. See Java's PartiallyOrderedSet.mapAll(Map).
func NewPartiallyOrderedSet ¶
func NewPartiallyOrderedSet[T comparable](set []T, dependencyMap SetMultimap[T]) *PartiallyOrderedSet[T]
NewPartiallyOrderedSet creates a new PartiallyOrderedSet from a set and dependency map. The dependency map is cleansed: entries referencing elements not in the set are removed.
func NewPartiallyOrderedSetFromFunc ¶
func NewPartiallyOrderedSetFromFunc[T comparable](set []T, dependsOnFn func(T) map[T]struct{}) *PartiallyOrderedSet[T]
NewPartiallyOrderedSetFromFunc creates a partial order from a set and a depends-on function.
func NewPartiallyOrderedSetInverted ¶
func NewPartiallyOrderedSetInverted[T comparable](set []T, dependencyMap SetMultimap[T]) *PartiallyOrderedSet[T]
NewPartiallyOrderedSetInverted creates a partial order with inverted dependencies.
func (*PartiallyOrderedSet[T]) DependencyMap ¶
func (p *PartiallyOrderedSet[T]) DependencyMap() SetMultimap[T]
func (*PartiallyOrderedSet[T]) DualOrder ¶
func (p *PartiallyOrderedSet[T]) DualOrder() *PartiallyOrderedSet[T]
DualOrder returns the partial order with all dependency edges reversed.
func (*PartiallyOrderedSet[T]) EligibleSet ¶
func (p *PartiallyOrderedSet[T]) EligibleSet() *EligibleSet[T]
EligibleSet returns a new EligibleSet for iterative consumption of this partial order.
func (*PartiallyOrderedSet[T]) Equal ¶
func (p *PartiallyOrderedSet[T]) Equal(other *PartiallyOrderedSet[T]) bool
Equal checks equality via set equality and transitive closure equality.
func (*PartiallyOrderedSet[T]) FilterElements ¶
func (p *PartiallyOrderedSet[T]) FilterElements(predicate func(T) bool) *PartiallyOrderedSet[T]
FilterElements returns a new partial order retaining only elements passing the predicate. Filtering respects dependency chains (see MapAll).
func (*PartiallyOrderedSet[T]) IsEmpty ¶
func (p *PartiallyOrderedSet[T]) IsEmpty() bool
func (*PartiallyOrderedSet[T]) Set ¶
func (p *PartiallyOrderedSet[T]) Set() []T
func (*PartiallyOrderedSet[T]) SetLookup ¶
func (p *PartiallyOrderedSet[T]) SetLookup() map[T]struct{}
func (*PartiallyOrderedSet[T]) Size ¶
func (p *PartiallyOrderedSet[T]) Size() int
func (*PartiallyOrderedSet[T]) String ¶
func (p *PartiallyOrderedSet[T]) String() string
func (*PartiallyOrderedSet[T]) TransitiveClosure ¶
func (p *PartiallyOrderedSet[T]) TransitiveClosure() SetMultimap[T]
type SetMultimap ¶
type SetMultimap[T comparable] map[T]map[T]struct{}
SetMultimap maps each key to a set of values.
func FromFunctionalDependencies ¶
func FromFunctionalDependencies[T comparable](set map[T]struct{}, dependsOnFn func(T) map[T]struct{}) SetMultimap[T]
FromFunctionalDependencies builds a dependency multimap from a set and a function that returns the dependencies of each element.
func InvertFromFunctionalDependencies ¶
func InvertFromFunctionalDependencies[T comparable](set map[T]struct{}, dependsOnFn func(T) map[T]struct{}) SetMultimap[T]
InvertFromFunctionalDependencies builds an inverted dependency multimap.
func NewSetMultimap ¶
func NewSetMultimap[T comparable]() SetMultimap[T]
func TransitiveClosure ¶
func TransitiveClosure[T comparable](p *PartiallyOrderedSet[T]) SetMultimap[T]
TransitiveClosure computes the transitive closure of the dependency map in the given partial order using Kahn's algorithm (topological order). Panics on circular dependencies.
Mirrors Java's TransitiveClosure.transitiveClosure.
func (SetMultimap[T]) Clone ¶
func (m SetMultimap[T]) Clone() SetMultimap[T]
func (SetMultimap[T]) Contains ¶
func (m SetMultimap[T]) Contains(key, value T) bool
func (SetMultimap[T]) Entries ¶
func (m SetMultimap[T]) Entries() []MapEntry[T]
func (SetMultimap[T]) Get ¶
func (m SetMultimap[T]) Get(key T) map[T]struct{}
func (SetMultimap[T]) Inverse ¶
func (m SetMultimap[T]) Inverse() SetMultimap[T]
func (SetMultimap[T]) IsEmpty ¶
func (m SetMultimap[T]) IsEmpty() bool
func (SetMultimap[T]) Put ¶
func (m SetMultimap[T]) Put(key, value T)
func (SetMultimap[T]) Size ¶
func (m SetMultimap[T]) Size() int
Source Files