loser

Documentation

Index

• type Sequence
• type Tree
  • func New[E any, S Sequence](sequences []S, maxVal E, at func(S) E, less func(E, E) bool, close func(S)) *Tree[E, S]
  • func (t *Tree[E, S]) Close()
  • func (t *Tree[E, S]) Err() error
  • func (t *Tree[E, S]) Next() bool
  • func (t *Tree[E, S]) Push(sequence S) error
  • func (t *Tree[E, S]) Winner() S

Types

type Sequence

type Sequence interface {
	Next() bool // Advances and returns true if there is a value at this new position.
	Err() error // Returns any error encountered while advancing.
}

type Tree

type Tree[E any, S Sequence] struct {
	// contains filtered or unexported fields
}

A loser tree is a binary tree laid out such that nodes N and N+1 have parent N/2. We store M leaf nodes in positions M...2M-1, and M-1 internal nodes in positions 1..M-1. Node 0 is a special node, containing the winner of the contest.

func New

func New[E any, S Sequence](sequences []S, maxVal E, at func(S) E, less func(E, E) bool, close func(S)) *Tree[E, S]

New returns a new loser tree that merges the given sequences. The sequences must be sorted according to the less function already. The maxVal is used to initialize the tree. The at function returns the current value of the sequence. The less function compares two values. The close function is called on each sequence when the tree is closed or when a sequence returns false from Next(). If any sequence returns an error from Err() after Next() = false, the tree will stop and return that error in Err(). Examples:

tree := loser.New(...)
defer tree.Close()
for tree.Next() {
	value := tree.Winner().At()
	...
}
if err := tree.Err(); err != nil {
	...
}

func (*Tree[E, S]) Close

func (t *Tree[E, S]) Close()

Call the close function on all sequences that are still open.

func (*Tree[E, S]) Err

func (t *Tree[E, S]) Err() error

func (*Tree[E, S]) Next

func (t *Tree[E, S]) Next() bool

func (*Tree[E, S]) Push

func (t *Tree[E, S]) Push(sequence S) error

Add a new sequence to the merge set

func (*Tree[E, S]) Winner

func (t *Tree[E, S]) Winner() S