func (placements Placements) ActiveIndex(timeNanos int64) int {
	idx := 0
	for idx < len(placements) && placements[idx].CutoverNanos() <= timeNanos {
		idx++
	}
	idx--
	return idx
}
ActiveIndex finds the index of the last placement whose cutover time is no
later than timeNanos (a.k.a. the active placement). Assuming the cutover times
of the placements are sorted in ascending order (i.e., earliest time first).
package placement
import (
	"errors"
	"fmt"
	"sort"
	"strings"
	"github.com/m3db/m3cluster/generated/proto/placementpb"
	"github.com/m3db/m3cluster/shard"
)
const (
	uninitializedShardSetID = 0
)
var (
	errNilPlacementProto          = errors.New("nil placement proto")
	errNilPlacementSnapshotsProto = errors.New("nil placement snapshots proto")
	errNilPlacementInstanceProto  = errors.New("nil placement instance proto")
	errDuplicatedShards           = errors.New("invalid placement, there are duplicated shards in one replica")
	errUnexpectedShards           = errors.New("invalid placement, there are unexpected shard ids on instance")
	errMirrorNotSharded           = errors.New("invalid placement, mirrored placement must be sharded")
)
type placement struct {
	instances        map[string]Instance
	instancesByShard map[uint32][]Instance
	rf               int
	shards           []uint32
	isSharded        bool
	isMirrored       bool
	cutoverNanos     int64
	maxShardSetID    uint32
	version          int
}
func NewPlacement() Placement {
	return &placement{}
}
func NewPlacementFromProto(p *placementpb.Placement) (Placement, error) {
	if p == nil {
		return nil, errNilPlacementProto
	}
	shards := make([]uint32, p.NumShards)
	for i := uint32(0); i < p.NumShards; i++ {
		shards[i] = i
	}
	instances := make([]Instance, 0, len(p.Instances))
	for _, instance := range p.Instances {
		pi, err := NewInstanceFromProto(instance)
		if err != nil {
			return nil, err
		}
		instances = append(instances, pi)
	}
	return NewPlacement().
		SetInstances(instances).
		SetShards(shards).
		SetReplicaFactor(int(p.ReplicaFactor)).
		SetIsSharded(p.IsSharded).
		SetCutoverNanos(p.CutoverTime).
		SetIsMirrored(p.IsMirrored).
		SetMaxShardSetID(p.MaxShardSetId), nil
}
func (p *placement) InstancesForShard(shard uint32) []Instance {
	if len(p.instancesByShard) == 0 {
		return nil
	}
	return p.instancesByShard[shard]
}
func (p *placement) Instances() []Instance {
	result := make([]Instance, 0, p.NumInstances())
	for _, instance := range p.instances {
		result = append(result, instance)
	}
	sort.Sort(ByIDAscending(result))
	return result
}
func (p *placement) SetInstances(instances []Instance) Placement {
	instancesMap := make(map[string]Instance, len(instances))
	instancesByShard := make(map[uint32][]Instance)
	for _, instance := range instances {
		instancesMap[instance.ID()] = instance
		for _, shard := range instance.Shards().AllIDs() {
			instancesByShard[shard] = append(instancesByShard[shard], instance)
		}
	}
	for _, instances := range instancesByShard {
		sort.Sort(ByIDAscending(instances))
	}
	p.instancesByShard = instancesByShard
	p.instances = instancesMap
	return p
}
func (p *placement) NumInstances() int {
	return len(p.instances)
}
func (p *placement) Instance(id string) (Instance, bool) {
	instance, ok := p.instances[id]
	return instance, ok
}
func (p *placement) ReplicaFactor() int {
	return p.rf
}
func (p *placement) SetReplicaFactor(rf int) Placement {
	p.rf = rf
	return p
}
func (p *placement) Shards() []uint32 {
	return p.shards
}
func (p *placement) SetShards(shards []uint32) Placement {
	p.shards = shards
	return p
}
func (p *placement) NumShards() int {
	return len(p.shards)
}
func (p *placement) IsSharded() bool {
	return p.isSharded
}
func (p *placement) SetIsSharded(v bool) Placement {
	p.isSharded = v
	return p
}
func (p *placement) IsMirrored() bool {
	return p.isMirrored
}
func (p *placement) SetIsMirrored(v bool) Placement {
	p.isMirrored = v
	return p
}
func (p *placement) MaxShardSetID() uint32 {
	return p.maxShardSetID
}
func (p *placement) SetMaxShardSetID(v uint32) Placement {
	p.maxShardSetID = v
	return p
}
func (p *placement) CutoverNanos() int64 {
	return p.cutoverNanos
}
func (p *placement) SetCutoverNanos(cutoverNanos int64) Placement {
	p.cutoverNanos = cutoverNanos
	return p
}
func (p *placement) GetVersion() int {
	return p.version
}
func (p *placement) SetVersion(v int) Placement {
	p.version = v
	return p
}
func (p *placement) String() string {
	return fmt.Sprintf(
		"Placement[Instances=%s, NumShards=%d, ReplicaFactor=%d, IsSharded=%v, IsMirrored=%v]",
		p.Instances(), p.NumShards(), p.ReplicaFactor(), p.IsSharded(), p.IsMirrored(),
	)
}
func (p *placement) Proto() (*placementpb.Placement, error) {
	instances := make(map[string]*placementpb.Instance, p.NumInstances())
	for _, instance := range p.Instances() {
		pi, err := instance.Proto()
		if err != nil {
			return nil, err
		}
		instances[instance.ID()] = pi
	}
	return &placementpb.Placement{
		Instances:     instances,
		ReplicaFactor: uint32(p.ReplicaFactor()),
		NumShards:     uint32(p.NumShards()),
		IsSharded:     p.IsSharded(),
		CutoverTime:   p.CutoverNanos(),
		IsMirrored:    p.IsMirrored(),
		MaxShardSetId: p.MaxShardSetID(),
	}, nil
}
func (p *placement) Clone() Placement {
	return NewPlacement().
		SetInstances(Instances(p.Instances()).Clone()).
		SetShards(p.Shards()).
		SetReplicaFactor(p.ReplicaFactor()).
		SetIsSharded(p.IsSharded()).
		SetIsMirrored(p.IsMirrored()).
		SetCutoverNanos(p.CutoverNanos()).
		SetMaxShardSetID(p.MaxShardSetID())
}
type Placements []Placement
func NewPlacementsFromProto(p *placementpb.PlacementSnapshots) (Placements, error) {
	if p == nil {
		return nil, errNilPlacementSnapshotsProto
	}
	placements := make([]Placement, 0, len(p.Snapshots))
	for _, snapshot := range p.Snapshots {
		placement, err := NewPlacementFromProto(snapshot)
		if err != nil {
			return nil, err
		}
		placements = append(placements, placement)
	}
	sort.Sort(placementsByCutoverAsc(placements))
	return placements, nil
}
func (placements Placements) Proto() (*placementpb.PlacementSnapshots, error) {
	snapshots := make([]*placementpb.Placement, 0, len(placements))
	for _, p := range placements {
		placementProto, err := p.Proto()
		if err != nil {
			return nil, err
		}
		snapshots = append(snapshots, placementProto)
	}
	return &placementpb.PlacementSnapshots{
		Snapshots: snapshots,
	}, nil
}