NewMerkleTree

// NewMerkleTree constructs a merkle tree with given entries.
func NewMerkleTree(entries []*Entry) *MerkleTree {
	if len(entries) == 0 {
		return nil
	}
	// Assign an unique salt for each entry. The hash
	// of entry is calculated by keccak256(value, salt)
	// so we can preserve the privacy of given value.
	for _, entry := range entries {
		entry.salt = rand.Uint64()
	}
	// Verify the validity of the given entries.
	var sum, totalWeight uint64
	for _, entry := range entries {
		sum += entry.Weight
	}
	for _, entry := range entries {
		var l float64
		if entry.Weight > 0 {
			l = math.Log2(float64(sum) / float64(entry.Weight))
		} else {
			l = 1000
		}
		c := math.Ceil(l)
		if c > maxLevel+1 {
			c = maxLevel+1 // maxLevel+1 means the entry is not included in the tree
		}
		entry.level = uint64(c)
		entry.bias = l - c
		if entry.level <= maxLevel {
			totalWeight += maxWeight >> entry.level
		}
	}
	sort.Sort(EntryByBias(entries))

	// Bump the weight of entry if we can't reach 100%
	shift := entries
	for totalWeight < maxWeight && len(shift) > 0 {
		var limit int
		for index, entry := range shift {
			var addWeight uint64
			if entry.level <= maxLevel {
				addWeight = maxWeight >> entry.level
			} else {
				addWeight = maxWeight >> maxLevel
			}
			if totalWeight+addWeight <= maxWeight {
				totalWeight += addWeight
				entry.level -= 1
				if index != limit {
					shift[limit], shift[index] = shift[index], shift[limit]
				}
				limit += 1
				if totalWeight == maxWeight {
					break
				}
			}
		}
		shift = shift[:limit]
	}
	sort.Sort(EntryByLevel(entries))
	for len(entries) > 0 && entries[len(entries)-1].level > maxLevel {
		entries = entries[:len(entries)-1]
	}

	// Start to build the merkle tree, short circuit if there is only 1 entry.
	root, leaves := newTree(entries)
	return &MerkleTree{Root: root, Leaves: leaves}
}