algo

Documentation

Overview

Package algo contains algorithms such as merging, intersecting sorted lists.

Index

• func ApplyFilter(u *protos.List, f func(uint64, int) bool)
• func Difference(u, v *protos.List) *protos.List
• func IndexOf(u *protos.List, uid uint64) int
• func IntersectCompressedWith(u []byte, afterUID uint64, v, o *protos.List)
• func IntersectCompressedWithBin(bi *bp128.BPackIterator, q []uint64, o *[]uint64)
• func IntersectCompressedWithLinJump(bi *bp128.BPackIterator, v []uint64, o *[]uint64)
• func IntersectSorted(lists []*protos.List) *protos.List
• func IntersectWith(u, v, o *protos.List)
• func IntersectWithBin(d, q []uint64, o *[]uint64)
• func IntersectWithJump(u, v []uint64, o *[]uint64) (int, int)
• func IntersectWithLin(u, v []uint64, o *[]uint64) (int, int)
• func MergeSorted(lists []*protos.List) *protos.List
• func ToUintsListForTest(ul []*protos.List) [][]uint64

Functions

func ApplyFilter

func ApplyFilter(u *protos.List, f func(uint64, int) bool)

ApplyFilter applies a filter to our UIDList.

func Difference

func Difference(u, v *protos.List) *protos.List

func IndexOf

func IndexOf(u *protos.List, uid uint64) int

IndexOf performs a binary search on the uids slice and returns the index at which it finds the uid, else returns -1

func IntersectCompressedWith

func IntersectCompressedWith(u []byte, afterUID uint64, v, o *protos.List)

func IntersectCompressedWithBin

func IntersectCompressedWithBin(bi *bp128.BPackIterator, q []uint64, o *[]uint64)

IntersectWithBin is based on the paper "Fast Intersection Algorithms for Sorted Sequences" https://link.springer.com/chapter/10.1007/978-3-642-12476-1_3

func IntersectCompressedWithLinJump

func IntersectCompressedWithLinJump(bi *bp128.BPackIterator, v []uint64, o *[]uint64)

func IntersectSorted

func IntersectSorted(lists []*protos.List) *protos.List

func IntersectWith

func IntersectWith(u, v, o *protos.List)

IntersectWith intersects u with v. The update is made to o. u, v should be sorted.

func IntersectWithBin

func IntersectWithBin(d, q []uint64, o *[]uint64)

IntersectWithBin is based on the paper "Fast Intersection Algorithms for Sorted Sequences" https://link.springer.com/chapter/10.1007/978-3-642-12476-1_3

func IntersectWithJump

func IntersectWithJump(u, v []uint64, o *[]uint64) (int, int)

func IntersectWithLin

func IntersectWithLin(u, v []uint64, o *[]uint64) (int, int)

func MergeSorted

func MergeSorted(lists []*protos.List) *protos.List

MergeSorted merges sorted lists.

func ToUintsListForTest

func ToUintsListForTest(ul []*protos.List) [][]uint64

ToUintsListForTest converts to list of uints for testing purpose only.