k2tree

README

k2tree

Go Implementation of a K^2 Tree

Documentation

Index

• Constants
• Variables
• type Config
• type Iterator
  • func (it *Iterator) ExtractAll() []int
  • func (it *Iterator) Next() bool
  • func (it *Iterator) Value() int
• type K2Tree
  • func New() (*K2Tree, error)
  • func NewWithConfig(config Config) (*K2Tree, error)
  • func (k *K2Tree) Add(i, j int) error
  • func (k *K2Tree) From(i int) *Iterator
  • func (k *K2Tree) Stats() Stats
  • func (k *K2Tree) To(j int) *Iterator
• type LayerDef
• type Stats
  • func (st Stats) String() string

Constants

const (
	// DefaultLRUCacheDistance was optimized experimentally. It's the distance
	// in bits between cache hits. It's a tradeoff between leaning on the POPCNT
	// instruction between known offsets in the cache and the overhead of
	// maintaining the LRU. If the LRU gets cheaper to maintain, this may get
	// decreased. If POPCNT gets faster, this may increase.
	DefaultLRUCacheDistance = 512
)

const (
	DefaultPagesize = 512 * 1024
)

Variables

var FourBitsPerLayer = LayerDef{
	// contains filtered or unexported fields
}

var SixteenBitsPerLayer = LayerDef{
	// contains filtered or unexported fields
}

Types

type Config

type Config struct {
	TreeLayerDef LayerDef
	CellLayerDef LayerDef
}

var DefaultConfig Config = SixteenFourConfig

var FourFourConfig Config = Config{
	TreeLayerDef: FourBitsPerLayer,
	CellLayerDef: FourBitsPerLayer,
}

var SixteenFourConfig Config = Config{
	TreeLayerDef: SixteenBitsPerLayer,
	CellLayerDef: FourBitsPerLayer,
}

var SixteenSixteenConfig Config = Config{
	TreeLayerDef: SixteenBitsPerLayer,
	CellLayerDef: SixteenBitsPerLayer,
}

type Iterator

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

func (*Iterator) ExtractAll

func (it *Iterator) ExtractAll() []int

func (*Iterator) Next

func (it *Iterator) Next() bool

func (*Iterator) Value

func (it *Iterator) Value() int

type K2Tree

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

K2Tree is the main data structure for this package. It represents a compressed representation of a graph adjacency matrix.

func New

func New() (*K2Tree, error)

New creates a new K2 Tree with the default creation options.

func NewWithConfig

func NewWithConfig(config Config) (*K2Tree, error)

func (*K2Tree) Add

func (k *K2Tree) Add(i, j int) error

Add asserts the existence of a link from node i to node j. i and j are zero-indexed, the tree will grow to support them if larger than the tree.

func (*K2Tree) From

func (k *K2Tree) From(i int) *Iterator

func (*K2Tree) Stats

func (k *K2Tree) Stats() Stats

Stats returns some statistics about the memory usage of the K2 tree.

func (*K2Tree) To

func (k *K2Tree) To(j int) *Iterator

type LayerDef

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

type Stats

type Stats struct {
	BitsPerLink  float64
	Links        int
	LevelOffsets []int
	Bytes        int
	TDebug       string
	LDebug       string
}

Stats describes the memory usage of the K2 tree.

func (Stats) String

func (st Stats) String() string