losertree

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]) At() E
  • func (t *Tree[E, S]) Close()
  • func (t *Tree[E, S]) Fix(closed bool)
  • func (t *Tree[E, S]) IsEmpty() bool
  • func (t *Tree[E, S]) Next() bool
  • 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.
}

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]

func (*Tree[E, S]) At

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

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]) Fix

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

Current winner has been advanced independently; fix up the loser tree.

func (*Tree[E, S]) IsEmpty

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

func (*Tree[E, S]) Next

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

func (*Tree[E, S]) Winner

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