jet

package
v0.0.0-...-05bc493 Latest Latest
Warning

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

Go to latest
Published: Sep 20, 2023 License: MIT Imports: 10 Imported by: 0

Documentation

Index

Constants

View Source
const (
	RawSerializeV1 = 1
	LZWSerializeV1 = 2
)
View Source
const IDBitLen = 16

Variables

This section is empty.

Functions

This section is empty.

Types

type DropID

type DropID uint64 // ID + current Pulse

func (DropID) CreatedAt

func (v DropID) CreatedAt() pulse.Number

func (DropID) ID

func (v DropID) ID() ID

func (DropID) IsValid

func (v DropID) IsValid() bool

func (DropID) String

func (v DropID) String() string

type ExactID

type ExactID uint32 // ID + MSB 8bit length
const (
	GenesisExactID ExactID = 1 << exactLenOfs
	UnknownExactID ExactID = 0
)

func NoLengthExactID

func NoLengthExactID(id ID) ExactID

func (ExactID) AsDrop

func (v ExactID) AsDrop(pn pulse.Number) DropID

func (ExactID) AsLeg

func (v ExactID) AsLeg(createdAt pulse.Number) LegID

func (ExactID) BitLen

func (v ExactID) BitLen() uint8

func (ExactID) HasLength

func (v ExactID) HasLength() bool

func (ExactID) ID

func (v ExactID) ID() ID

func (ExactID) IsZero

func (v ExactID) IsZero() bool

func (ExactID) String

func (v ExactID) String() string

type ID

type ID uint16

func (ID) AsDrop

func (v ID) AsDrop(createdAt pulse.Number) DropID

func (ID) AsExact

func (v ID) AsExact(bitLen uint8) ExactID

func (ID) AsLeg

func (v ID) AsLeg(bitLen uint8, createdAt pulse.Number) LegID

func (ID) AsPrefix

func (v ID) AsPrefix() Prefix

func (ID) BitLen

func (v ID) BitLen() int

type LegID

type LegID uint64 // ExactID + Split/Merge Pulse

func (LegID) AsDrop

func (v LegID) AsDrop() DropID

func (LegID) CreatedAt

func (v LegID) CreatedAt() pulse.Number

func (LegID) ExactID

func (v LegID) ExactID() ExactID

func (LegID) IsValid

func (v LegID) IsValid() bool

func (LegID) String

func (v LegID) String() string

type Prefix

type Prefix uint32

func (Prefix) AsID

func (v Prefix) AsID() ID

type PrefixTree

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

func NewPrefixTree

func NewPrefixTree(autoPropagate bool) PrefixTree

func (*PrefixTree) Cleanup

func (p *PrefixTree) Cleanup()

TODO remove?

func (*PrefixTree) Count

func (p *PrefixTree) Count() int

Returns a total number of jets in this tree. Always >= 1. O(log n)

func (*PrefixTree) Enum

func (p *PrefixTree) Enum(fn func(Prefix, uint8) bool) bool

func (*PrefixTree) GetPrefix

func (p *PrefixTree) GetPrefix(prefix Prefix) (Prefix, uint8)

Returns number of denotative bits for the given prefix and masked prefix, with denotative bits only. Number of denotative bits is [0..16]. O(log n) for non-propagating and O(1) for propagating mode.

func (*PrefixTree) Init

func (p *PrefixTree) Init()

Converts zero state tree to a proper empty tree. Only useful for the zero state, is not necessary to call.

func (*PrefixTree) IsEmpty

func (p *PrefixTree) IsEmpty() bool

True when there is only a root jet.

func (*PrefixTree) IsZero

func (p *PrefixTree) IsZero() bool

func (*PrefixTree) MakePerfect

func (p *PrefixTree) MakePerfect(depth uint8)

MakePerfect fills an empty tree with branches of the given depth - makes a perfect binary tree.

func (*PrefixTree) MaxDepth

func (p *PrefixTree) MaxDepth() uint8

Maximum prefix length of a jet in this tree.

func (*PrefixTree) Merge

func (p *PrefixTree) Merge(prefix Prefix, prefixLimit uint8)

Merges the given sub-jet with its pair into a jet (a full node with 2 leafs is converted into a leaf). (prefix) - must be zero-branch jet (has the highest denotative bit =0, or prefix[prefixLen]=0) (prefixLimit) - number of valuable bits in the given prefix. Will panic when prefixLimit is less than actual prefix length for the given prefix.

O(1) for non-propagating and amortized O(log n) for propagating mode.

func (*PrefixTree) MinDepth

func (p *PrefixTree) MinDepth() uint8

Minimum prefix length of a jet in this tree.

func (*PrefixTree) PrintTable

func (p *PrefixTree) PrintTable()

Prints a list of jets to StdOut

func (*PrefixTree) PrintTableAll

func (p *PrefixTree) PrintTableAll()

Prints a list of jets and propagated jets to StdOut

func (*PrefixTree) SetPropagate

func (p *PrefixTree) SetPropagate()

func (*PrefixTree) Split

func (p *PrefixTree) Split(prefix Prefix, prefixLimit uint8)

Splits the given jet into 2 sub-jets (converts a leaf node into a full node with 2 leafs). (prefixLimit) - number of valuable bits in the given prefix. Will panic when prefixLimit is less than actual prefix length for the given prefix.

O(1) for non-propagating and amortized O(log n) for propagating mode.

func (*PrefixTree) String

func (p *PrefixTree) String() string

type PrefixTreeDeserializer

type PrefixTreeDeserializer struct {
}

func (PrefixTreeDeserializer) Deserialize

func (v PrefixTreeDeserializer) Deserialize(r io.ByteReader) (*PrefixTree, error)

func (PrefixTreeDeserializer) DeserializeTo

func (v PrefixTreeDeserializer) DeserializeTo(p *PrefixTree, r io.ByteReader) error

Can only be called on an empty tree otherwise panics.

type PrefixTreeSerializer

type PrefixTreeSerializer struct {
	UseLZW       bool
	LzwThreshold byte // =0 => minEffortEfficientLZWLength
	LzwTolerance byte // =0 => compressionTolerance
}

func (PrefixTreeSerializer) Serialize

func (v PrefixTreeSerializer) Serialize(p *PrefixTree, w io.Writer) error

General idea of this serialization is based on the "mountain range" approach to visualize Catalan numbers, yet it is different as we have 2 top and bottom limits and the left and right bounds can be above the bottom limit. https://en.wikipedia.org/wiki/Catalan_number https://brilliant.org/wiki/catalan-numbers/

This implementation is suboptimal and consumes extra >40% of theoretical minimum, but it takes less for balanced trees (down to 2 bytes for a perfect tree).

Approximate size of uncompressed serialized binary is 2 + 0.85*Count(), approx max is 6700 byte. When LZW compression is enabled, it can reduce by 2-3 times, approx max is down to 1400 bytes.

First byte is either =RawSerializeV1 or =LZWSerializeV1

O(n log n)

func (PrefixTreeSerializer) SerializeToRawBytes

func (v PrefixTreeSerializer) SerializeToRawBytes(p *PrefixTree) []byte

Returns uncompressed form only First byte is always =RawSerializeV1

type Tree

type Tree = *PrefixTree

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL