| 5 | import "cmp" |
| 6 | |
| 7 | func New[E cmp.Ordered](lists [][]E, maxVal E) *Tree[E] { |
| 8 | nLists := len(lists) |
| 9 | t := Tree[E]{ |
| 10 | maxVal: maxVal, |
| 11 | nodes: make([]node[E], nLists*2), |
| 12 | } |
| 13 | for i, s := range lists { |
| 14 | t.nodes[i+nLists].items = s |
| 15 | t.moveNext(i + nLists) // Must call Next on each item so that At() has a value. |
| 16 | } |
| 17 | if nLists > 0 { |
| 18 | t.nodes[0].index = -1 // flag to be initialized on first call to Next(). |
| 19 | } |
| 20 | return &t |
| 21 | } |
| 22 | |
| 23 | // A loser tree is a binary tree laid out such that nodes N and N+1 have parent N/2. |
| 24 | // We store M leaf nodes in positions M...2M-1, and M-1 internal nodes in positions 1..M-1. |