sortnet

Documentation

Index

• Constants
• func GeneratePermutationsByBitmap(channels int, src, dst *SetMetadata, hook PermutationGeneratorHook) bool
• func MapLegalPlacementsBitMap(constraints []BinarySequence, dst, src BinarySequence)
• func QuickValidatePermutationBitMapPositions(channels int, constraints []BinarySequence) bool
• type BinarySequence
  • func ApplyPermutation(src BinarySequence, permutation PermutationMap) BinarySequence
  • func PermutationBitMapPositions(channels int, dst, src *SetMetadata) []BinarySequence
  • func SequenceMask(channels int) BinarySequence
  • func (b BinarySequence) MostSignificantBitOffset() int
  • func (b BinarySequence) OnesCount() int
• type Comparator
  • func AllComparatorCombinations(sequenceSize int) []Comparator
• type ComparatorNetwork
  • func (n *ComparatorNetwork) Derive(comparators []Comparator) []Network
  • func (n *ComparatorNetwork) String() string
  • func (n *ComparatorNetwork) Transform(seq BinarySequence) BinarySequence
• type GeneratePermutationsFunc
• type Network
• type NetworkID
• type OutputSet
  • func PopulateOutputSet(set OutputSet, channels int) OutputSet
• type PermutationGeneratorHook
• type PermutationMap
• type SequenceIterator
  • func NewSequenceIterator(seq BinarySequence) *SequenceIterator
  • func (it *SequenceIterator) Empty() bool
  • func (it *SequenceIterator) Next() int
• type SetMetadata
  • func (md *SetMetadata) Add(seq BinarySequence, partition int)
  • func (md *SetMetadata) ST1(other *SetMetadata) bool
  • func (md *SetMetadata) ST2(other *SetMetadata) bool
  • func (md *SetMetadata) ST3(other *SetMetadata) bool
  • func (md *SetMetadata) ST4(other *SetMetadata) bool

Constants

const MaxChannels = 16

const MaxChannelsMask = 0b1111_1111_1111_1111

const None = 0

Functions

func GeneratePermutationsByBitmap

func GeneratePermutationsByBitmap(channels int, src, dst *SetMetadata, hook PermutationGeneratorHook) bool

GeneratePermutationsByBitmap will identify all plausible permutations using backtracking.

func MapLegalPlacementsBitMap

func MapLegalPlacementsBitMap(constraints []BinarySequence, dst, src BinarySequence)

func QuickValidatePermutationBitMapPositions

func QuickValidatePermutationBitMapPositions(channels int, constraints []BinarySequence) bool

QuickValidatePermutationBitMapPositions verifies: 1. that any position can be moved to at least one position 2. that the combined legal positions will at least once touch every position

Types

type BinarySequence

type BinarySequence uint16

func ApplyPermutation

func ApplyPermutation(src BinarySequence, permutation PermutationMap) BinarySequence

func PermutationBitMapPositions

func PermutationBitMapPositions(channels int, dst, src *SetMetadata) []BinarySequence

func SequenceMask

func SequenceMask(channels int) BinarySequence

func (BinarySequence) MostSignificantBitOffset

func (b BinarySequence) MostSignificantBitOffset() int

MostSignificantBitOffset returns offset for most significant set bit, -1 when there are no set bits.

func (BinarySequence) OnesCount

func (b BinarySequence) OnesCount() int

type Comparator

type Comparator struct {
	From int
	To   int
}

func AllComparatorCombinations

func AllComparatorCombinations(sequenceSize int) []Comparator

type ComparatorNetwork

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

func (*ComparatorNetwork) Derive

func (n *ComparatorNetwork) Derive(comparators []Comparator) []Network

func (*ComparatorNetwork) String

func (n *ComparatorNetwork) String() string

func (*ComparatorNetwork) Transform

func (n *ComparatorNetwork) Transform(seq BinarySequence) BinarySequence

type GeneratePermutationsFunc

type GeneratePermutationsFunc = func(channels int, dst, src *SetMetadata, hook PermutationGeneratorHook) bool

type Network

type Network interface {
	Transform(BinarySequence) BinarySequence
	Derive(comparators []Comparator) []Network
}

type NetworkID

type NetworkID int64

type OutputSet

type OutputSet interface {
	Derive(Network) OutputSet
	Add(sequence BinarySequence)
	Size() int
	IsSubset(OutputSet, PermutationMap) bool
	Contains(BinarySequence) bool
	ContainsInPartition(seq BinarySequence, partition int) bool
	Metadata() *SetMetadata
}

func PopulateOutputSet

func PopulateOutputSet(set OutputSet, channels int) OutputSet

type PermutationGeneratorHook

type PermutationGeneratorHook = func(PermutationMap) bool

type PermutationMap

type PermutationMap []int

PermutationMap delegates positional transformation for any binary sequence.

given the map (m) [0, 1, 2, 3], no transformation is required, as each index is in order
meaning applying this permutation would not actually change the binary sequence.

Given the map [0, 2, 1, 3] the 2th and 1th position would swap places, while 0th and 3th would
remain unchanged.

Given the binary position X of a sequence, it's bit value should be swapped with bit position m[x] of the permutation map.

type SequenceIterator

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

func NewSequenceIterator

func NewSequenceIterator(seq BinarySequence) *SequenceIterator

func (*SequenceIterator) Empty

func (it *SequenceIterator) Empty() bool

func (*SequenceIterator) Next

func (it *SequenceIterator) Next() int

Next returns the next most significant bit (offset). Returns -1 when there are no set bits / done iterating. You must call Empty() to avoid underflow scenarios, as this will run forever otherwise.

type SetMetadata

type SetMetadata struct {
	NetworkID
	Size           int
	PartitionSizes []int
	OnesMasks      []BinarySequence
	ZerosMasks     []BinarySequence
}

func (*SetMetadata) Add

func (md *SetMetadata) Add(seq BinarySequence, partition int)

func (*SetMetadata) ST1

func (md *SetMetadata) ST1(other *SetMetadata) bool

ST1 check total size of the output

func (*SetMetadata) ST2

func (md *SetMetadata) ST2(other *SetMetadata) bool

ST2 check the size of corresponding clusters/partitions

func (*SetMetadata) ST3

func (md *SetMetadata) ST3(other *SetMetadata) bool

ST3 check the ones and the zeros

func (*SetMetadata) ST4

func (md *SetMetadata) ST4(other *SetMetadata) bool

ST4 check all permutations