sortlist

Documentation

Overview

Package sortlist implements a sorted list that is built incrementally. The list is in blocks of blockSize. Blocks are individually sorted once they are full. Blocks are two-way merged. A background goroutine is used to do the sorting and merging concurrently.

Blocks are recycled by merges so we use at most two extra blocks.

Note: Zero is used as a terminator, it must not be added as a value.

Index

• type Builder
  • func NewSorting[T any](zero func(x T) bool, less func(x, y T) bool) *Builder[T]
  • func NewUnsorted[T any](zero func(x T) bool) *Builder[T]
  • func (b *Builder[T]) Add(x T)
  • func (b *Builder[T]) Finish() List[T]
  • func (b *Builder[T]) Iter() func() T
  • func (b *Builder[T]) Sort(less func(x, y T) bool)
• type Iter
  • func (it *Iter[T]) Cur() T
  • func (it *Iter[T]) Eof() bool
  • func (it *Iter[T]) Next()
  • func (it *Iter[T]) Prev()
  • func (it *Iter[T]) Rewind()
  • func (it *Iter[T]) Seek(key []string)
• type List
  • func (li List[T]) Iter(less iterLess[T]) *Iter[T]

Types

type Builder

type Builder[T any] struct {
	// contains filtered or unexported fields
}

func NewSorting

func NewSorting[T any](zero func(x T) bool, less func(x, y T) bool) *Builder[T]

NewSorting returns a new list Builder with incremental sorting. WARNING: this creates a goroutine which must be ended by Finish.

func NewUnsorted

func NewUnsorted[T any](zero func(x T) bool) *Builder[T]

NewUnsorted returns a new list Builder without sorting.

func (*Builder[T]) Add

func (b *Builder[T]) Add(x T)

Add adds a value to the list.

func (*Builder[T]) Finish

func (b *Builder[T]) Finish() List[T]

Finish completes sorting and merging and returns the ordered List. No more values should be added after this.

func (*Builder[T]) Iter

func (b *Builder[T]) Iter() func() T

Iter from Builder returns a function that returns 0 when finished

func (*Builder[T]) Sort

func (b *Builder[T]) Sort(less func(x, y T) bool)

Sort sorts the list by the given compare function. It is used to re-sort by a different compare function.

type Iter

type Iter[T any] struct {
	// contains filtered or unexported fields
}

Iter is used by tempindex

func (*Iter[T]) Cur

func (it *Iter[T]) Cur() T

func (*Iter[T]) Eof

func (it *Iter[T]) Eof() bool

func (*Iter[T]) Next

func (it *Iter[T]) Next()

func (*Iter[T]) Prev

func (it *Iter[T]) Prev()

func (*Iter[T]) Rewind

func (it *Iter[T]) Rewind()

func (*Iter[T]) Seek

func (it *Iter[T]) Seek(key []string)

Seek does a binary search to find the first element greater than or equal

type List

type List[T any] struct {
	// contains filtered or unexported fields
}

func (List[T]) Iter

func (li List[T]) Iter(less iterLess[T]) *Iter[T]

Iter returns an iterator for the list. Warning: The less function (used by seek) must be consistent with the sort function.