Documentation
¶
Index ¶
- Constants
- type DropID
- type ExactID
- type ID
- type LegID
- type Prefix
- type PrefixTree
- func (p *PrefixTree) Cleanup()
- func (p *PrefixTree) Count() int
- func (p *PrefixTree) Enum(fn func(Prefix, uint8) bool) bool
- func (p *PrefixTree) GetPrefix(prefix Prefix) (Prefix, uint8)
- func (p *PrefixTree) Init()
- func (p *PrefixTree) IsEmpty() bool
- func (p *PrefixTree) IsZero() bool
- func (p *PrefixTree) MakePerfect(depth uint8)
- func (p *PrefixTree) MaxDepth() uint8
- func (p *PrefixTree) Merge(prefix Prefix, prefixLimit uint8)
- func (p *PrefixTree) MinDepth() uint8
- func (p *PrefixTree) PrintTable()
- func (p *PrefixTree) PrintTableAll()
- func (p *PrefixTree) SetPropagate()
- func (p *PrefixTree) Split(prefix Prefix, prefixLimit uint8)
- func (p *PrefixTree) String() string
- type PrefixTreeDeserializer
- type PrefixTreeSerializer
- type Tree
Constants ¶
const ( RawSerializeV1 = 1 LZWSerializeV1 = 2 )
const IDBitLen = 16
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type PrefixTree ¶
type PrefixTree struct {
// contains filtered or unexported fields
}
func NewPrefixTree ¶
func NewPrefixTree(autoPropagate bool) PrefixTree
func (*PrefixTree) Count ¶
func (p *PrefixTree) Count() int
Returns a total number of jets in this tree. Always >= 1. O(log n)
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) 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
Source Files