func Merge(its ...Postings) Postings {
	if len(its) == 0 {
		return EmptyPostings()
	}
	if len(its) == 1 {
		return its[0]
	}
	p, ok := newMergedPostings(its)
	if !ok {
		return EmptyPostings()
	}
	return p
}
Merge returns a new iterator over the union of the input iterators.
package index
import (
	"container/heap"
	"encoding/binary"
	"runtime"
	"sort"
	"strings"
	"sync"
	"github.com/prometheus/prometheus/tsdb/labels"
)
var allPostingsKey = labels.Label{}
func AllPostingsKey() (name, value string) {
	return allPostingsKey.Name, allPostingsKey.Value
}
type MemPostings struct {
	mtx     sync.RWMutex
	m       map[string]map[string][]uint64
	ordered bool
}
func NewMemPostings() *MemPostings {
	return &MemPostings{
		m:       make(map[string]map[string][]uint64, 512),
		ordered: true,
	}
}
func NewUnorderedMemPostings() *MemPostings {
	return &MemPostings{
		m:       make(map[string]map[string][]uint64, 512),
		ordered: false,
	}
}
func (p *MemPostings) SortedKeys() []labels.Label {
	p.mtx.RLock()
	keys := make([]labels.Label, 0, len(p.m))
	for n, e := range p.m {
		for v := range e {
			keys = append(keys, labels.Label{Name: n, Value: v})
		}
	}
	p.mtx.RUnlock()
	sort.Slice(keys, func(i, j int) bool {
		if d := strings.Compare(keys[i].Name, keys[j].Name); d != 0 {
			return d < 0
		}
		return keys[i].Value < keys[j].Value
	})
	return keys
}
type PostingsStats struct {
	CardinalityMetricsStats []Stat
	CardinalityLabelStats   []Stat
	LabelValueStats         []Stat
	LabelValuePairsStats    []Stat
}
func (p *MemPostings) Stats(label string) *PostingsStats {
	const maxNumOfRecords = 10
	var size uint64
	p.mtx.RLock()
	metrics := &maxHeap{}
	labels := &maxHeap{}
	labelValueLenght := &maxHeap{}
	labelValuePairs := &maxHeap{}
	metrics.init(maxNumOfRecords)
	labels.init(maxNumOfRecords)
	labelValueLenght.init(maxNumOfRecords)
	labelValuePairs.init(maxNumOfRecords)
	for n, e := range p.m {
		if n == "" {
			continue
		}
		labels.push(Stat{Name: n, Count: uint64(len(e))})
		size = 0
		for name, values := range e {
			if n == label {
				metrics.push(Stat{Name: name, Count: uint64(len(values))})
			}
			labelValuePairs.push(Stat{Name: n + "=" + name, Count: uint64(len(values))})
			size += uint64(len(name))
		}
		labelValueLenght.push(Stat{Name: n, Count: size})
	}
	p.mtx.RUnlock()
	return &PostingsStats{
		CardinalityMetricsStats: metrics.get(),
		CardinalityLabelStats:   labels.get(),
		LabelValueStats:         labelValueLenght.get(),
		LabelValuePairsStats:    labelValuePairs.get(),
	}
}
func (p *MemPostings) Get(name, value string) Postings {
	var lp []uint64
	p.mtx.RLock()
	l := p.m[name]
	if l != nil {
		lp = l[value]
	}
	p.mtx.RUnlock()
	if lp == nil {
		return EmptyPostings()
	}
	return newListPostings(lp...)
}
func (p *MemPostings) All() Postings {
	return p.Get(AllPostingsKey())
}
func (p *MemPostings) EnsureOrder() {
	p.mtx.Lock()
	defer p.mtx.Unlock()
	if p.ordered {
		return
	}
	n := runtime.GOMAXPROCS(0)
	workc := make(chan []uint64)
	var wg sync.WaitGroup
	wg.Add(n)
	for i := 0; i < n; i++ {
		go func() {
			for l := range workc {
				sort.Slice(l, func(i, j int) bool { return l[i] < l[j] })
			}
			wg.Done()
		}()
	}
	for _, e := range p.m {
		for _, l := range e {
			workc <- l
		}
	}
	close(workc)
	wg.Wait()
	p.ordered = true
}
func (p *MemPostings) Delete(deleted map[uint64]struct{}) {
	var keys, vals []string
	p.mtx.RLock()
	for n := range p.m {
		keys = append(keys, n)
	}
	p.mtx.RUnlock()
	for _, n := range keys {
		p.mtx.RLock()
		vals = vals[:0]
		for v := range p.m[n] {
			vals = append(vals, v)
		}
		p.mtx.RUnlock()
		for _, l := range vals {
			p.mtx.Lock()
			found := false
			for _, id := range p.m[n][l] {
				if _, ok := deleted[id]; ok {
					found = true
					break
				}
			}
			if !found {
				p.mtx.Unlock()
				continue
			}
			repl := make([]uint64, 0, len(p.m[n][l]))
			for _, id := range p.m[n][l] {
				if _, ok := deleted[id]; !ok {
					repl = append(repl, id)
				}
			}
			if len(repl) > 0 {
				p.m[n][l] = repl
			} else {
				delete(p.m[n], l)
			}
			p.mtx.Unlock()
		}
		p.mtx.Lock()
		if len(p.m[n]) == 0 {
			delete(p.m, n)
		}
		p.mtx.Unlock()
	}
}
func (p *MemPostings) Iter(f func(labels.Label, Postings) error) error {
	p.mtx.RLock()
	defer p.mtx.RUnlock()
	for n, e := range p.m {
		for v, p := range e {
			if err := f(labels.Label{Name: n, Value: v}, newListPostings(p...)); err != nil {
				return err
			}
		}
	}
	return nil
}
func (p *MemPostings) Add(id uint64, lset labels.Labels) {
	p.mtx.Lock()
	for _, l := range lset {
		p.addFor(id, l)
	}
	p.addFor(id, allPostingsKey)
	p.mtx.Unlock()
}
func (p *MemPostings) addFor(id uint64, l labels.Label) {
	nm, ok := p.m[l.Name]
	if !ok {
		nm = map[string][]uint64{}
		p.m[l.Name] = nm
	}
	list := append(nm[l.Value], id)
	nm[l.Value] = list
	if !p.ordered {
		return
	}
	for i := len(list) - 1; i >= 1; i-- {
		if list[i] >= list[i-1] {
			break
		}
		list[i], list[i-1] = list[i-1], list[i]
	}
}
func ExpandPostings(p Postings) (res []uint64, err error) {
	for p.Next() {
		res = append(res, p.At())
	}
	return res, p.Err()
}
type Postings interface {
	Next() bool
	Seek(v uint64) bool
	At() uint64
	Err() error
}
type errPostings struct {
	err error
}
func (e errPostings) Next() bool       { return false }
func (e errPostings) Seek(uint64) bool { return false }
func (e errPostings) At() uint64       { return 0 }
func (e errPostings) Err() error       { return e.err }
var emptyPostings = errPostings{}
func EmptyPostings() Postings {
	return emptyPostings
}
func ErrPostings(err error) Postings {
	return errPostings{err}
}
func Intersect(its ...Postings) Postings {
	if len(its) == 0 {
		return EmptyPostings()
	}
	if len(its) == 1 {
		return its[0]
	}
	for _, p := range its {
		if p == EmptyPostings() {
			return EmptyPostings()
		}
	}
	return newIntersectPostings(its...)
}
type intersectPostings struct {
	arr []Postings
	cur uint64
}
func newIntersectPostings(its ...Postings) *intersectPostings {
	return &intersectPostings{arr: its}
}
func (it *intersectPostings) At() uint64 {
	return it.cur
}
func (it *intersectPostings) doNext() bool {
Loop:
	for {
		for _, p := range it.arr {
			if !p.Seek(it.cur) {
				return false
			}
			if p.At() > it.cur {
				it.cur = p.At()
				continue Loop
			}
		}
		return true
	}
}
func (it *intersectPostings) Next() bool {
	for _, p := range it.arr {
		if !p.Next() {
			return false
		}
		if p.At() > it.cur {
			it.cur = p.At()
		}
	}
	return it.doNext()
}
func (it *intersectPostings) Seek(id uint64) bool {
	it.cur = id
	return it.doNext()
}
func (it *intersectPostings) Err() error {
	for _, p := range it.arr {
		if p.Err() != nil {
			return p.Err()
		}
	}
	return nil
}