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 ¶
func Difference ¶
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 ¶
Slice returns a new task.List with the elements between start index and end index of the list passed to it.
func SortedListToBlock ¶
func ToUintsListForTest ¶
ToUintsListForTest converts to list of uints for testing purpose only.
Types ¶
type AsList ¶
type AsList struct {
// contains filtered or unexported fields
}
AsList implements sort.Interface by for block lists
type ListIterator ¶
type ListIterator struct {
// contains filtered or unexported fields
}
ListIterator is used to read through the task.List.
func NewListIterator ¶
func NewListIterator(l *task.List) ListIterator
NewListIterator returns a read iterator for the list passed to it.
func (*ListIterator) Next ¶
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 ¶
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 ¶
func (l *ListIterator) SeekToIndex(idx int)
SeekToIndex moves the iterator to the specified index.
func (*ListIterator) Val ¶
func (l *ListIterator) Val() uint64
Val returns the value pointed to by the iterator.
func (*ListIterator) Valid ¶
func (l *ListIterator) Valid() bool
Valid returns true if we haven't reached the end of the list.
type WriteIterator ¶
type WriteIterator struct {
// contains filtered or unexported fields
}
WriteIterator is used to append UIDs to a task.List.
func NewWriteIterator ¶
func NewWriteIterator(l *task.List, whence int) WriteIterator
func (*WriteIterator) Append ¶
func (l *WriteIterator) Append(uid uint64)
Append appends an UID to the end of task.List following the blockSize specified.
func (*WriteIterator) End ¶
func (l *WriteIterator) End()
End is called after the write is over to update the MaxInt of the last block.
Source Files