loser

README

go-loser

Loser Tree data structure, for fast k-way merge

I will be speaking about this at GopherCon on 27th Sept 2023.

There are currently two versions of the code on two Git branches: main, which works for built-in types like int and string, and any which works on any type but requires you to pass in a function pointer to do less comparisons.

See https://en.wikipedia.org/wiki/K-way_merge_algorithm#Tournament_Tree for more details on the algorithm.

Documentation

Index

• type Sequence
• type Tree
  • func New[E Value, S Sequence[E]](sequences []S, maxVal E) *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
• type Value

Types

type Sequence

type Sequence[E Value] interface {
	At() E      // Returns the current value.
	Next() bool // Advances and returns true if there is a value at this new position.
}

type Tree

type Tree[E Value, S Sequence[E]] 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 Value, S Sequence[E]](sequences []S, maxVal E) *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

type Value

type Value constraints.Ordered