Documentation
¶
Overview ¶
Package anf provides an implementation of sets that are stored in Algebraic Normal Form (ANF).
In ANF, each set is stored as the symmetric difference of intersections (or in boolean terms, as the XOR of ANDs).
Index ¶
- type Property
- type Set
- func (s Set) Clone() Set
- func (s Set) Contains(element any) bool
- func (lhs Set) Difference(rhs Set) Set
- func (s Set) Equal(other Set) bool
- func (s Set) ForEach(f func([]Property))
- func (s Set) Format(f fmt.State, verb rune)
- func (s Set) IncludesUniverse() bool
- func (lhs Set) Intersection(rhs Set) Set
- func (s Set) IsEmpty() bool
- func (s Set) Negated() Set
- func (s Set) String() string
- func (lhs Set) SymmetricDifference(rhs Set) Set
- func (lhs Set) Union(rhs Set) Set
- type Simplification
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Property ¶
type Property interface {
// Equal returns whether this property is equal to another.
Equal(other Property) bool
// IsSatisfied returns whether this property is true for a particular
// element.
IsSatisfied(element any) bool
// Precedence returns an ordering for [Property] instances, to help you
// ensure that [Property.Intersection] and [Property.SymmetricDifference]
// are symmetric.
Precedence() int
// Intersection determines whether the intersection of this property and
// another is empty; and if not, whether it can be represented by a
// different, simpler, [Property] instance.
//
// If the two properties are disjoint, then their intersection is empty. In
// that case, return [Remove].
//
// If the intersection is non-empty, and there is a simpler, single
// [Property] instance that contains EXACTLY the same elements as the
// intersection, return [Replace] along with the simplified property. If
// not (that is, the two existing Property instances are the best
// representation of their intersection), then return [Keep].
//
// As a common case of the above, we will test ourselves whether the two
// properties are equal, in which case they will be replaced with a single
// copy of the property. You do not have to test for that situation.
//
// To help you ensure that this method is symmetric, we will always ensure
// that the precedence of the method receiver is <= the precedence of other.
Intersection(other Property) (Simplification, Property)
// SymmetricDifference determines whether the symmetric difference of this
// property and another is empty; and if not, whether it can be represented
// by a different, simpler, [Property] instance.
//
// If the two properties are equivalent, then their symmetric difference is
// empty. In that case, return [Remove].
//
// If the symmetric difference is non-empty, and there is a simpler, single
// [Property] instance that contains EXACTLY the same elements as the
// symmetric difference, return [Replace] along with the simplified
// property. If not (that is, the two existing [Property] instances are the
// best representation of their symmetric difference), then return [Keep].
//
// As a common case of the above, we will test ourselves whether the two
// properties are equal, in which case they will be removed. You do not
// have to test for that situation.
//
// To help you ensure that this method is symmetric, we will always ensure
// that the precedence of the method receiver is <= the precedence of other.
SymmetricDifference(other Property) (Simplification, Property)
}
Property defines a property that may be true or false for each possible element. Each property must match at least one element, and must reject at least one element.
Implementations must be:
Symmetric: p1.Intersection(p2) and p2.Intersection(p1) must return the same result. (Ditto for SymmetricDifference)
Confluent: Given any number of properties, calling Intersection or SymmetricDifference on them in any order must produce the same result.
(Note that this interface is parameterized on itself as well as the element type, so that we can ensure that the interface methods operate on properties of the same type.)
type Set ¶
type Set struct {
// contains filtered or unexported fields
}
Set is a set of elements stored in algebraic normal form. E is the type of the elements stored in the set. P defines properties that may be true or false for each possible element. A set is then the XOR of zero or more clauses, each of which is the AND of one or more properties.
func Intersection ¶
Intersection returns the intersection of zero or more sets.
func SymmetricDifference ¶
SymmetricDifference returns the symmetric difference of zero or more sets.
func (Set) Difference ¶
Difference returns a set that includes elements that are in this set but not in `other`.
func (Set) IncludesUniverse ¶
IncludesUniverse returns whether this set includes the universe (the set containing all possible elements) as one of its clauses. (In ANF terms, this is whether the set includes 1⊕... as one of its terms.)
func (Set) Intersection ¶
Intersection returns a set that includes elements that are in both this set and `other`.
func (Set) Negated ¶
Negated returns a set that contains exactly the opposite elements as the current one.
func (Set) SymmetricDifference ¶
SymmetricDifference returns a set that includes element are in either one set or another, but not both.
type Simplification ¶
type Simplification int
Simplification indicates what kind of result is returned from Property.Intersection and Property.SymmetricDifference.
const ( // Remove indicates that the two properties being simplified cancel each // other out and should both be removed. Remove Simplification = iota // Keep indicates that the two properties cannot be simplified, and should // be kept as-is. Keep // Replace indicates that the two properties can be simplified, and should // collectively be replaced with a different property. Replace )
Source Files
Directories