func (ef *FeeEstimator) newEstimateFeeSet() *estimateFeeSet {
	set := &estimateFeeSet{}
	capacity := 0
	for i, b := range ef.bin {
		l := len(b)
		set.bin[i] = uint32(l)
		capacity += l
	}
	set.feeRate = make([]nanoSoterPerByte, capacity)
	i := 0
	for _, b := range ef.bin {
		for _, o := range b {
			set.feeRate[i] = o.feeRate
			i++
		}
	}
	sort.Sort(set)
	return set
}
newEstimateFeeSet creates a temporary data structure that
can be used to find all fee estimates.
package mempool
import (
	"bytes"
	"encoding/binary"
	"errors"
	"fmt"
	"io"
	"math"
	"math/rand"
	"sort"
	"strings"
	"sync"
	"github.com/soteria-dag/soterd/chaincfg/chainhash"
	"github.com/soteria-dag/soterd/miningdag"
	"github.com/soteria-dag/soterd/soterutil"
)
const (
	estimateFeeDepth = 25
	estimateFeeBinSize = 100
	estimateFeeMaxReplacements = 10
	DefaultEstimateFeeMaxRollback = 2
	DefaultEstimateFeeMinRegisteredBlocks = 3
	bytePerKb = 1000
)
var (
	EstimateFeeDatabaseKey = []byte("estimatefee")
)
type nanoSoterPerByte float64
type SotoPerKilobyte float64
func (rate nanoSoterPerByte) ToSotoPerKb() SotoPerKilobyte {
	if rate == nanoSoterPerByte(-1.0) {
		return -1.0
	}
	return SotoPerKilobyte(float64(rate) * bytePerKb * soterutil.NanoSoter)
}
func (rate nanoSoterPerByte) Fee(size uint32) soterutil.Amount {
	if rate == nanoSoterPerByte(-1) {
		return soterutil.Amount(-1)
	}
	return soterutil.Amount(float64(rate) * float64(size))
}
func NewNanoSoterPerByte(fee soterutil.Amount, size uint32) nanoSoterPerByte {
	return nanoSoterPerByte(float64(fee) / float64(size))
}
type observedTransaction struct {
	hash chainhash.Hash
	feeRate nanoSoterPerByte
	observed int32
	mined int32
}
func (o *observedTransaction) Serialize(w io.Writer) {
	binary.Write(w, binary.BigEndian, o.hash)
	binary.Write(w, binary.BigEndian, o.feeRate)
	binary.Write(w, binary.BigEndian, o.observed)
	binary.Write(w, binary.BigEndian, o.mined)
}
func deserializeObservedTransaction(r io.Reader) (*observedTransaction, error) {
	ot := observedTransaction{}
	binary.Read(r, binary.BigEndian, &ot.hash)
	binary.Read(r, binary.BigEndian, &ot.feeRate)
	binary.Read(r, binary.BigEndian, &ot.observed)
	binary.Read(r, binary.BigEndian, &ot.mined)
	return &ot, nil
}
type registeredBlock struct {
	hash         chainhash.Hash
	transactions []*observedTransaction
}
func (rb *registeredBlock) serialize(w io.Writer, txs map[*observedTransaction]uint32) {
	binary.Write(w, binary.BigEndian, rb.hash)
	binary.Write(w, binary.BigEndian, uint32(len(rb.transactions)))
	for _, o := range rb.transactions {
		binary.Write(w, binary.BigEndian, txs[o])
	}
}
type FeeEstimator struct {
	maxRollback uint32
	binSize     int32
	maxReplacements int32
	minRegisteredBlocks uint32
	lastKnownHeight int32
	numBlocksRegistered uint32
	mtx      sync.RWMutex
	observed map[chainhash.Hash]*observedTransaction
	bin      [estimateFeeDepth][]*observedTransaction
	cached []nanoSoterPerByte
	dropped []*registeredBlock
}
func NewFeeEstimator(maxRollback, minRegisteredBlocks uint32) *FeeEstimator {
	return &FeeEstimator{
		maxRollback:         maxRollback,
		minRegisteredBlocks: minRegisteredBlocks,
		lastKnownHeight:     miningdag.UnminedHeight,
		binSize:             estimateFeeBinSize,
		maxReplacements:     estimateFeeMaxReplacements,
		observed:            make(map[chainhash.Hash]*observedTransaction),
		dropped:             make([]*registeredBlock, 0, maxRollback),
	}
}
func (ef *FeeEstimator) ObserveTransaction(t *TxDesc) {
	ef.mtx.Lock()
	defer ef.mtx.Unlock()
	if ef.lastKnownHeight == miningdag.UnminedHeight {
		return
	}
	hash := *t.Tx.Hash()
	if _, ok := ef.observed[hash]; !ok {
		size := uint32(GetTxVirtualSize(t.Tx))
		ef.observed[hash] = &observedTransaction{
			hash:     hash,
			feeRate:  NewNanoSoterPerByte(soterutil.Amount(t.Fee), size),
			observed: t.Height,
			mined:    miningdag.UnminedHeight,
		}
	}
}
func (ef *FeeEstimator) RegisterBlock(block *soterutil.Block) error {
	ef.mtx.Lock()
	defer ef.mtx.Unlock()
	ef.cached = nil
	height := block.Height()
	if height != ef.lastKnownHeight+1 && ef.lastKnownHeight != miningdag.UnminedHeight {
		return fmt.Errorf("intermediate block not recorded; current height is %d; new height is %d",
			ef.lastKnownHeight, height)
	}
	ef.lastKnownHeight = height
	ef.numBlocksRegistered++
	transactions := make(map[*soterutil.Tx]struct{})
	for _, t := range block.Transactions() {
		transactions[t] = struct{}{}
	}
	var replacementCounts [estimateFeeDepth]int
	dropped := &registeredBlock{
		hash:         *block.Hash(),
		transactions: make([]*observedTransaction, 0, 100),
	}
	for t := range transactions {
		hash := *t.Hash()
		o, ok := ef.observed[hash]
		if !ok {
			continue
		}
		blocksToConfirm := height - o.observed - 1
		if o.mined != miningdag.UnminedHeight {
			log.Error("Estimate fee: transaction ", hash.String(), " has already been mined")
			return errors.New("Transaction has already been mined")
		}
		if blocksToConfirm >= estimateFeeDepth {
			continue
		}
		if replacementCounts[blocksToConfirm] == int(ef.maxReplacements) {
			continue
		}
		o.mined = height
		replacementCounts[blocksToConfirm]++
		bin := ef.bin[blocksToConfirm]
		if len(bin) == int(ef.binSize) {
			l := int(ef.binSize) - replacementCounts[blocksToConfirm]
			drop := rand.Intn(l)
			dropped.transactions = append(dropped.transactions, bin[drop])
			bin[drop] = bin[l-1]
			bin[l-1] = o
		} else {
			bin = append(bin, o)
		}
		ef.bin[blocksToConfirm] = bin
	}
	for hash, o := range ef.observed {
		if o.mined == miningdag.UnminedHeight && height-o.observed >= estimateFeeDepth {
			delete(ef.observed, hash)
		}
	}
	if ef.maxRollback == 0 {
		return nil
	}
	if uint32(len(ef.dropped)) == ef.maxRollback {
		ef.dropped = append(ef.dropped[1:], dropped)
	} else {
		ef.dropped = append(ef.dropped, dropped)
	}
	return nil
}
func (ef *FeeEstimator) LastKnownHeight() int32 {
	ef.mtx.Lock()
	defer ef.mtx.Unlock()
	return ef.lastKnownHeight
}
func (ef *FeeEstimator) Rollback(hash *chainhash.Hash) error {
	ef.mtx.Lock()
	defer ef.mtx.Unlock()
	var n int
	for n = 1; n <= len(ef.dropped); n++ {
		if ef.dropped[len(ef.dropped)-n].hash.IsEqual(hash) {
			break
		}
	}
	if n > len(ef.dropped) {
		return errors.New("no such block was recently registered")
	}
	for i := 0; i < n; i++ {
		ef.rollback()
	}
	return nil
}
func (ef *FeeEstimator) rollback() {
	ef.cached = nil
	last := len(ef.dropped) - 1
	if last == -1 {
		return
	}
	dropped := ef.dropped[last]
	var replacementCounters [estimateFeeDepth]int
	for _, o := range dropped.transactions {
		blocksToConfirm := o.mined - o.observed - 1
		bin := ef.bin[blocksToConfirm]
		var counter = replacementCounters[blocksToConfirm]
		for {
			if counter >= len(bin) {
				panic(errors.New("illegal state: cannot rollback dropped transaction"))
			}
			prev := bin[counter]
			if prev.mined == ef.lastKnownHeight {
				prev.mined = miningdag.UnminedHeight
				bin[counter] = o
				counter++
				break
			}
			counter++
		}
		replacementCounters[blocksToConfirm] = counter
	}
	for i, j := range replacementCounters {
		for {
			l := len(ef.bin[i])
			if j >= l {
				break
			}
			prev := ef.bin[i][j]
			if prev.mined == ef.lastKnownHeight {
				prev.mined = miningdag.UnminedHeight
				newBin := append(ef.bin[i][0:j], ef.bin[i][j+1:l]...)
				ef.bin[i] = newBin
				continue
			}
			j++
		}
	}
	ef.dropped = ef.dropped[0:last]
	ef.numBlocksRegistered--
	ef.lastKnownHeight--
}
type estimateFeeSet struct {
	feeRate []nanoSoterPerByte
	bin     [estimateFeeDepth]uint32
}
func (b *estimateFeeSet) Len() int { return len(b.feeRate) }
func (b *estimateFeeSet) Less(i, j int) bool {
	return b.feeRate[i] > b.feeRate[j]
}
func (b *estimateFeeSet) Swap(i, j int) {
	b.feeRate[i], b.feeRate[j] = b.feeRate[j], b.feeRate[i]
}
func (b *estimateFeeSet) estimateFee(confirmations int) nanoSoterPerByte {
	if confirmations <= 0 {
		return nanoSoterPerByte(math.Inf(1))
	}
	if confirmations > estimateFeeDepth {
		return 0
	}
	if len(b.feeRate) == 0 {
		return 0
	}
	var min, max int = 0, 0
	for i := 0; i < confirmations-1; i++ {
		min += int(b.bin[i])
	}
	max = min + int(b.bin[confirmations-1]) - 1
	if max < min {
		max = min
	}
	feeIndex := (min + max) / 2
	if feeIndex >= len(b.feeRate) {
		feeIndex = len(b.feeRate) - 1
	}
	return b.feeRate[feeIndex]
}