algo

Documentation

Overview

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

Index

• func ApplyFilter(u *task.List, f func(uint64, int) bool)
• func Difference(u, v *task.List)
• func IndexOf(u *task.List, uid uint64) int
• func IntersectSorted(lists []*task.List) *task.List
• func IntersectWith(u, v *task.List)
• func MergeSorted(lists []*task.List) *task.List
• func ToUintsListForTest(ul []*task.List) [][]uint64

Functions

func ApplyFilter

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

ApplyFilter applies a filter to our UIDList.

func Difference

func Difference(u, v *task.List)

func IndexOf

func IndexOf(u *task.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 IntersectSorted

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

IntersectSorted intersect a list of UIDLists. An alternative is to do pairwise intersections n-1 times where n=number of lists. This is less efficient: Let p be length of shortest list. Let q be average length of lists. So nq = total number of elements. There are many possible cases. Consider the case where the shortest list is the answer (or close to the answer). The following method requires nq reads (each element is read only once) whereas pairwise intersections can require np + nq - p reads, which can be up to ~twice as many.

func IntersectWith

func IntersectWith(u, v *task.List)

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

func MergeSorted

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

MergeSorted merges sorted lists.

func ToUintsListForTest

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

ToUintsListForTest converts to list of uints for testing purpose only.