Documentation
¶
Overview ¶
Package loser implements a tournament tree (also known as a loser tree) for efficiently merging multiple sorted sequences. This implementation is based on the work by Bryan Boreham (https://github.com/bboreham/go-loser).
A loser tree is a binary tree structure where each internal node holds the "loser" of a comparison between its children, and the root holds the overall "winner". This makes it particularly efficient for merging multiple sorted sequences, as it requires fewer comparisons than a standard merge algorithm.
Key features:
- Generic implementation supporting any comparable type
- Efficient merging of multiple sorted sequences
- Iterator-based interface using Go's iter.Seq
- O(log n) comparisons per element
- Memory-efficient implementation
Basic usage:
// Create sorted sequences
seq1 := NewList(1, 3, 5)
seq2 := NewList(2, 4, 6)
seq3 := NewList(7, 8, 9)
// Create a loser tree to merge the sequences
tree := loser.New(
[]loser.Sequence[int]{seq1, seq2, seq3},
math.MaxInt, // Maximum possible value
func(a, b int) bool { return a < b },
)
// Iterate over merged results
for v := range tree.All() {
fmt.Println(v) // Will print: 1, 2, 3, 4, 5, 6, 7, 8, 9
}
Implementation Details: The loser tree is implemented as a binary tree laid out in an array where:
- For node N, its children are at positions 2N and 2N+1
- Leaf nodes are stored in positions M to 2M-1 (where M is the number of sequences)
- Internal nodes are stored in positions 1 to M-1
- Node 0 is special, containing the current winner
Each node contains:
- index: The index of the losing sequence (or winning sequence for node 0)
- value: The value from the losing sequence
- next: Function to get next value (only for leaf nodes)
The tree maintains the invariant that each internal node contains the larger (losing) value of its children, ensuring that the smallest (winning) value propagates to the root.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Tree ¶
type Tree[E any] struct { // contains filtered or unexported fields }
Tree 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 ¶
Example (Basic) ¶
ExampleNew_basic demonstrates basic usage of a loser tree to merge sorted sequences.
// Create three sorted sequences
seq1 := NewList(1, 4, 7)
seq2 := NewList(2, 5, 8)
seq3 := NewList(3, 6, 9)
// Create a loser tree to merge the sequences
tree := loser.New(
[]loser.Sequence[int]{seq1, seq2, seq3},
math.MaxInt,
func(a, b int) bool { return a < b },
)
// Print merged sequence
for v := range tree.All() {
fmt.Printf("%d ", v)
}
Output: 1 2 3 4 5 6 7 8 9
Example (Empty) ¶
ExampleNew_empty demonstrates handling empty sequences.
// Create mix of empty and non-empty sequences
seq1 := NewList(1, 3, 5)
seq2 := NewList[int]() // Empty sequence
seq3 := NewList(2, 4)
tree := loser.New(
[]loser.Sequence[int]{seq1, seq2, seq3},
math.MaxInt,
func(a, b int) bool { return a < b },
)
// Print merged sequence
for v := range tree.All() {
fmt.Printf("%d ", v)
}
Output: 1 2 3 4 5
Example (Strings) ¶
ExampleNew_strings shows how to use the loser tree with string sequences.
// Create sequences of sorted strings
seq1 := NewList("apple", "dog", "zebra")
seq2 := NewList("banana", "elephant")
seq3 := NewList("cat", "fish")
// Create loser tree for strings
tree := loser.New(
[]loser.Sequence[string]{seq1, seq2, seq3},
"zzz", // Maximum possible string value
func(a, b string) bool { return a < b },
)
// Print merged sequence
for v := range tree.All() {
fmt.Printf("%s ", v)
}
Output: apple banana cat dog elephant fish zebra
Source Files