Documentation
¶
Overview ¶
Package algo contains algorithms such as merging, intersecting sorted lists.
Index ¶
- func ApplyFilter(u *task.List, f func(uint64, int) bool)
- func BlockToList(b *task.List) []uint64
- func Difference(u, v *task.List)
- func Idx(ul *task.List, i, j int) int
- func IndexOf(u *task.List, uid uint64) (int, int)
- func IntersectSorted(lists []*task.List) *task.List
- func IntersectWith(u, v *task.List)
- func ItemAtIndex(ul *task.List, i int) uint64
- func ListLen(l *task.List) int
- func MergeSorted(lists []*task.List) *task.List
- func Slice(ul *task.List, start, end int)
- func Sort(ul *task.List)
- func SortedListToBlock(l []uint64) *task.List
- func Swap(ul *task.List, i, j int)
- func ToUintsListForTest(ul []*task.List) [][]uint64
- type AsList
- type ListIterator
- type WriteIterator
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func ApplyFilter ¶
ApplyFilter applies a filter to our UIDList.
func BlockToList ¶ added in v0.7.3
func Difference ¶ added in v0.7.2
func IndexOf ¶
IndexOf performs a binary search on the uids slice and returns the index at which it finds the uid, else returns -1
func IntersectSorted ¶
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 Slice ¶ added in v0.7.3
Slice returns a new task.List with the elements between start index and end index of the list passed to it.
func SortedListToBlock ¶ added in v0.7.3
func ToUintsListForTest ¶
ToUintsListForTest converts to list of uints for testing purpose only.
Types ¶
type AsList ¶ added in v0.7.3
type AsList struct {
// contains filtered or unexported fields
}
AsList implements sort.Interface by for block lists
type ListIterator ¶ added in v0.7.3
type ListIterator struct {
// contains filtered or unexported fields
}
ListIterator is used to read through the task.List.
func NewListIterator ¶ added in v0.7.3
func NewListIterator(l *task.List) ListIterator
NewListIterator returns a read iterator for the list passed to it.
func (*ListIterator) Next ¶ added in v0.7.3
func (l *ListIterator) Next()
Next moves the iterator to the next element and also sets the end if the last element is consumed already.
func (*ListIterator) Seek ¶ added in v0.7.3
func (l *ListIterator) Seek(uid uint64, whence int)
Seek seeks to the index whose value is greater than or equal to the given UID. It uses binary search to move around.
func (*ListIterator) SeekToIndex ¶ added in v0.7.3
func (l *ListIterator) SeekToIndex(idx int)
SeekToIndex moves the iterator to the specified index.
func (*ListIterator) Val ¶ added in v0.7.3
func (l *ListIterator) Val() uint64
Val returns the value pointed to by the iterator.
func (*ListIterator) Valid ¶ added in v0.7.3
func (l *ListIterator) Valid() bool
Valid returns true if we haven't reached the end of the list.
type WriteIterator ¶ added in v0.7.3
type WriteIterator struct {
// contains filtered or unexported fields
}
WriteIterator is used to append UIDs to a task.List.
func NewWriteIterator ¶ added in v0.7.3
func NewWriteIterator(l *task.List, whence int) WriteIterator
func (*WriteIterator) Append ¶ added in v0.7.3
func (l *WriteIterator) Append(uid uint64)
Append appends an UID to the end of task.List following the blockSize specified.
func (*WriteIterator) End ¶ added in v0.7.3
func (l *WriteIterator) End()
End is called after the write is over to update the MaxInt of the last block.
Source Files