MergeTokens takes in input multiple lists of tokens and returns a single list containing all tokens merged and sorted. Each input single list is required to have tokens already sorted.
(instances [][]uint32)
| 666 | // containing all tokens merged and sorted. Each input single list is required |
| 667 | // to have tokens already sorted. |
| 668 | func MergeTokens(instances [][]uint32) []uint32 { |
| 669 | numTokens := 0 |
| 670 | |
| 671 | // Build the heap. |
| 672 | h := make(TokensHeap, 0, len(instances)) |
| 673 | for _, tokens := range instances { |
| 674 | if len(tokens) == 0 { |
| 675 | continue |
| 676 | } |
| 677 | |
| 678 | // We can safely append the input slice because elements inside are never shuffled. |
| 679 | h = append(h, tokens) |
| 680 | numTokens += len(tokens) |
| 681 | } |
| 682 | heap.Init(&h) |
| 683 | |
| 684 | out := make([]uint32, 0, numTokens) |
| 685 | |
| 686 | for h.Len() > 0 { |
| 687 | // The minimum element in the tree is the root, at index 0. |
| 688 | lowest := h[0] |
| 689 | out = append(out, lowest[0]) |
| 690 | |
| 691 | if len(lowest) > 1 { |
| 692 | // Remove the first token from the lowest because we popped it |
| 693 | // and then fix the heap to keep it sorted. |
| 694 | h[0] = h[0][1:] |
| 695 | heap.Fix(&h, 0) |
| 696 | } else { |
| 697 | heap.Remove(&h, 0) |
| 698 | } |
| 699 | } |
| 700 | |
| 701 | return out |
| 702 | } |
| 703 | |
| 704 | // MergeTokensByZone is like MergeTokens but does it for each input zone. |
| 705 | func MergeTokensByZone(zones map[string][][]uint32) map[string][]uint32 { |