avl

Documentation

Index

• Variables
• type SequenceSet
  • func Decode(buf []byte) (*SequenceSet, int, error)
  • func Union(ssa ...*SequenceSet) *SequenceSet
  • func (ss *SequenceSet) Clone() *SequenceSet
  • func (ss *SequenceSet) Delete(seq uint64) bool
  • func (ss *SequenceSet) Empty()
  • func (ss SequenceSet) Encode(buf []byte) ([]byte, error)
  • func (ss SequenceSet) EncodeLen() int
  • func (ss *SequenceSet) Exists(seq uint64) bool
  • func (ss *SequenceSet) Heights() (l, r int)
  • func (ss *SequenceSet) Insert(seq uint64)
  • func (ss *SequenceSet) IsEmpty() bool
  • func (ss *SequenceSet) MinMax() (min, max uint64)
  • func (ss *SequenceSet) Nodes() int
  • func (ss *SequenceSet) Range(f func(uint64) bool)
  • func (ss *SequenceSet) SetInitialMin(min uint64) error
  • func (ss *SequenceSet) Size() int
  • func (ss *SequenceSet) State() (min, max, num uint64)
  • func (ss *SequenceSet) Union(ssa ...*SequenceSet)

Variables

var (
	ErrBadEncoding = errors.New("ss: bad encoding")
	ErrBadVersion  = errors.New("ss: bad version")
	ErrSetNotEmpty = errors.New("ss: set not empty")
)

ErrBadEncoding is returned when we can not decode properly.

Types

type SequenceSet

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

SequenceSet is a memory and encoding optimized set for storing unsigned ints.

SequenceSet is ~80-100 times more efficient memory wise than a map[uint64]struct{}. SequenceSet is ~1.75 times slower at inserts than the same map. SequenceSet is not thread safe.

We use an AVL tree with nodes that hold bitmasks for set membership.

Encoding will convert to a space optimized encoding using bitmasks.

func Decode

func Decode(buf []byte) (*SequenceSet, int, error)

Decode returns the sequence set and number of bytes read from the buffer on success.

func Union

func Union(ssa ...*SequenceSet) *SequenceSet

Union will return a union of all sets.

func (*SequenceSet) Clone

func (ss *SequenceSet) Clone() *SequenceSet

Clone will return a clone of the given SequenceSet.

func (*SequenceSet) Delete

func (ss *SequenceSet) Delete(seq uint64) bool

Delete will remove the sequence from the set. Will optionally remove nodes and rebalance. Returns where the sequence was set.

func (*SequenceSet) Empty

func (ss *SequenceSet) Empty()

Empty will clear all items from a set.

func (SequenceSet) Encode

func (ss SequenceSet) Encode(buf []byte) ([]byte, error)

func (SequenceSet) EncodeLen

func (ss SequenceSet) EncodeLen() int

EncodeLen returns the bytes needed for encoding.

func (*SequenceSet) Exists

func (ss *SequenceSet) Exists(seq uint64) bool

Exists will return true iff the sequence is a member of this set.

func (*SequenceSet) Heights

func (ss *SequenceSet) Heights() (l, r int)

Heights returns the left and right heights of the tree.

func (*SequenceSet) Insert

func (ss *SequenceSet) Insert(seq uint64)

Insert will insert the sequence into the set. The tree will be balanced inline.

func (*SequenceSet) IsEmpty

func (ss *SequenceSet) IsEmpty() bool

IsEmpty is a fast check of the set being empty.

func (*SequenceSet) MinMax

func (ss *SequenceSet) MinMax() (min, max uint64)

MinMax will return the minunum and maximum values in the set.

func (*SequenceSet) Nodes

func (ss *SequenceSet) Nodes() int

Nodes returns the number of nodes in the tree.

func (*SequenceSet) Range

func (ss *SequenceSet) Range(f func(uint64) bool)

Range will invoke the given function for each item in the set. They will range over the set in ascending order. If the callback returns false we terminate the iteration.

func (*SequenceSet) SetInitialMin

func (ss *SequenceSet) SetInitialMin(min uint64) error

SetInitialMin should be used to set the initial minimum sequence when known. This will more effectively utilize space versus self selecting. The set should be empty.

func (*SequenceSet) Size

func (ss *SequenceSet) Size() int

Size returns the number of items in the set.

func (*SequenceSet) State

func (ss *SequenceSet) State() (min, max, num uint64)

Returns min, max and number of set items.

func (*SequenceSet) Union

func (ss *SequenceSet) Union(ssa ...*SequenceSet)

Union will union this SequenceSet with ssa.