func baiByteBasedShards(ctx context.Context, bamr *bam.Reader, baiPath string, bytesPerShard int64,
	minBases, padding int, includeUnmapped bool) (shards []Shard, err error) {
	type boundary struct {
		ref     *sam.Reference
		pos     int
		filePos int64
	}
	var indexIn file.File
	indexIn, err = file.Open(ctx, baiPath)
	if err != nil {
		return nil, err
	}
	defer file.CloseAndReport(ctx, indexIn, &err)
	var index *Index
	index, err = ReadIndex(indexIn.Reader(ctx))
	if err != nil {
		return nil, err
	}
	chunksByRef := index.AllOffsets()
	if len(chunksByRef) <= 0 {
		return nil, fmt.Errorf("%v: no chunks found in the index", baiPath)
	}
	var (
		prevFilePos int64
		boundaries  []boundary
	)
	for refID := 0; refID < len(chunksByRef); refID++ {
		ref := bamr.Header().Refs()[refID]
		offsets := chunksByRef[refID]
		for i, offset := range offsets {
			if len(boundaries) == 0 || (offset.File-prevFilePos) > bytesPerShard {
				var rec biopb.Coord
				var coordErr error
				rec, coordErr = GetCoordAtOffset(bamr, offset)
				if coordErr != nil {
					log.Panic(coordErr)
				}
				if int(rec.RefId) != refID {
					log.Debug.Printf("No more reads in refid %d %s, filepos %d", refID, ref.Name(), offset.File)
					break
				}
				if i == 0 {
					boundaries = append(boundaries, boundary{ref, 0, offset.File})
				} else {
					boundaries = append(boundaries, boundary{ref, int(rec.Pos), offset.File})
				}
				prevFilePos = offset.File
			}
		}
	}
	if len(boundaries) > 0 {
		boundaries2 := []boundary{boundaries[0]}
		for i := 1; i < len(boundaries); i++ {
			ref := boundaries[i].ref
			if ref == boundaries[i-1].ref && (boundaries[i].filePos-boundaries[i-1].filePos) > 2*bytesPerShard {
				genomeSubdivisions := ((boundaries[i].pos - boundaries[i-1].pos) / int(minBases)) - 1
				bytesSubdivisions := ((boundaries[i].filePos - boundaries[i-1].filePos) / bytesPerShard) - 1
				var subdivisions int
				if int64(genomeSubdivisions) < bytesSubdivisions {
					subdivisions = genomeSubdivisions
				} else {
					subdivisions = int(bytesSubdivisions)
				}
				if subdivisions < 0 {
					subdivisions = 0
				}
				for s := 1; s <= subdivisions; s++ {
					subpos := boundaries[i-1].pos + s*((boundaries[i].pos-boundaries[i-1].pos)/(subdivisions+1))
					boundaries2 = append(boundaries2, boundary{ref, subpos, -1})
				}
			}
			boundaries2 = append(boundaries2, boundaries[i])
		}
		boundaries3 := []boundary{boundaries2[0]}
		for i := 1; i < len(boundaries2); i++ {
			b := boundaries2[i]
			last := boundaries3[len(boundaries3)-1]
			if b.ref != last.ref || b.pos-last.pos >= minBases || i == len(boundaries2)-1 {
				boundaries3 = append(boundaries3, b)
			} else {
				log.Debug.Printf("dropping boundary %v (min bases %d)", b, int32(minBases))
			}
		}
		for i := 0; i < len(boundaries3); i++ {
			start := boundaries3[i]
			var end boundary
			if i < len(boundaries3)-1 {
				end = boundaries3[i+1]
			} else {
				lastRef := bamr.Header().Refs()[len(bamr.Header().Refs())-1]
				end = boundary{
					ref:     lastRef,
					pos:     lastRef.Len(),
					filePos: -1,
				}
			}
			shards = append(shards, Shard{
				StartRef: start.ref,
				EndRef:   end.ref,
				Start:    int(start.pos),
				End:      int(end.pos),
				Padding:  padding,
				ShardIdx: len(shards),
			})
		}
	}
	if includeUnmapped {
		shards = append(shards, Shard{
			End:      math.MaxInt32,
			ShardIdx: len(shards),
		})
	}
	ValidateShardList(bamr.Header(), shards, padding)
	return shards, nil
}
baiByteBasedShards creates shards based on a traditional .bai style index.
package bam
import (
	"context"
	"fmt"
	"math"
	"math/rand"
	"strings"
	"github.com/grailbio/base/backgroundcontext"
	"github.com/grailbio/base/file"
	"github.com/grailbio/base/log"
	"github.com/grailbio/bio/biopb"
	"github.com/grailbio/hts/bam"
	"github.com/grailbio/hts/bgzf"
	"github.com/grailbio/hts/sam"
)
var UniversalRange = biopb.CoordRange{
	Start: biopb.Coord{0, 0, 0},
	Limit: biopb.Coord{biopb.InfinityRefID, biopb.InfinityPos, 0},
}
var MappedRange = biopb.CoordRange{
	Start: biopb.Coord{0, 0, 0},
	Limit: biopb.Coord{biopb.LimitValidRefID, biopb.InfinityPos, 0},
}
type Shard struct {
	StartRef *sam.Reference
	EndRef   *sam.Reference
	Start    int
	End      int
	StartSeq int
	EndSeq   int
	Padding  int
	ShardIdx int
}
func UniversalShard(header *sam.Header) Shard {
	var startRef *sam.Reference
	if len(header.Refs()) > 0 {
		startRef = header.Refs()[0]
	}
	return Shard{
		StartRef: startRef,
		EndRef:   nil,
		Start:    0,
		End:      math.MaxInt32,
	}
}
func (s *Shard) PadStart(padding int) int {
	return max(0, s.Start-padding)
}
func (s *Shard) PaddedStart() int {
	return s.PadStart(s.Padding)
}
func (s *Shard) PadEnd(padding int) int {
	if s.End == 0 && s.EndSeq == 0 {
		return 0
	}
	if s.EndRef == nil {
		return min(math.MaxInt32, s.End+padding)
	}
	return min(s.EndRef.Len(), s.End+padding)
}
func (s *Shard) PaddedEnd() int {
	return s.PadEnd(s.Padding)
}
func (s *Shard) RecordInShard(r *sam.Record) bool {
	return s.CoordInShard(0, CoordFromSAMRecord(r, 0))
}
func (s *Shard) MateInShard(r *sam.Record) bool {
	return s.CoordInShard(0, MateCoordFromSAMRecord(r, 0))
}
func (s *Shard) RecordInPaddedShard(r *sam.Record) bool {
	return s.CoordInShard(s.Padding, CoordFromSAMRecord(r, 0))
}
func (s *Shard) RecordInStartPadding(r *sam.Record) bool {
	paddedStartCoord := NewCoord(s.StartRef, s.PaddedStart(), 0)
	startCoord := NewCoord(s.StartRef, s.Start, 0)
	coord := CoordFromSAMRecord(r, 0)
	return coord.GE(paddedStartCoord) && coord.LT(startCoord)
}
func (s *Shard) CoordInShard(padding int, coord biopb.Coord) bool {
	startCoord := NewCoord(s.StartRef, s.PadStart(padding), 0)
	if coord.LT(startCoord) {
		return false
	}
	endCoord := NewCoord(s.EndRef, s.PadEnd(padding), 0)
	return coord.LT(endCoord)
}
func (s *Shard) String() string {
	return fmt.Sprintf("%d:(%s[%d],%d(%d))-(%s[%d],%d(%d))",
		s.ShardIdx, s.StartRef.Name(), s.StartRef.ID(), s.Start, s.PaddedStart(),
		s.EndRef.Name(), s.EndRef.ID(), s.End, s.PaddedEnd())
}
func min(x, y int) int {
	if y < x {
		return y
	}
	return x
}
func max(x, y int) int {
	if y > x {
		return y
	}
	return x
}
func ShardToCoordRange(shard Shard) biopb.CoordRange {
	return biopb.CoordRange{
		biopb.Coord{RefId: int32(shard.StartRef.ID()), Pos: int32(shard.Start), Seq: int32(shard.StartSeq)},
		biopb.Coord{RefId: int32(shard.EndRef.ID()), Pos: int32(shard.End), Seq: int32(shard.EndSeq)},
	}
}
func CoordRangeToShard(header *sam.Header, r biopb.CoordRange, padding, shardIdx int) Shard {
	var startRef *sam.Reference
	if r.Start.RefId >= 0 {
		startRef = header.Refs()[r.Start.RefId]
	}
	var limitRef *sam.Reference
	var limitPos = int(r.Limit.Pos)
	if r.Limit.RefId >= 0 {
		if n := len(header.Refs()); int(r.Limit.RefId) < n {
			limitRef = header.Refs()[r.Limit.RefId]
			limitPos = int(r.Limit.Pos)
		} else {
			limitRef = header.Refs()[n-1]
			limitPos = limitRef.Len()
		}
	}
	return Shard{
		StartRef: startRef,
		Start:    int(r.Start.Pos),
		StartSeq: int(r.Start.Seq),
		EndRef:   limitRef,
		End:      limitPos,
		EndSeq:   int(r.Limit.Seq),
		Padding:  padding,
		ShardIdx: shardIdx,
	}
}
type CoordGenerator struct {
	LastRec biopb.Coord
}
func NewCoordGenerator() CoordGenerator {
	return CoordGenerator{biopb.Coord{RefId: 0, Pos: -1, Seq: 0}}
}
func (g *CoordGenerator) Generate(refID, pos int32) biopb.Coord {
	if refID == biopb.InfinityRefID {
		pos = 0
	}
	if refID < biopb.UnmappedRefID || pos < 0 {
		log.Panicf("Illegal addr: %v %v", refID, pos)
	}
	a := biopb.Coord{RefId: refID, Pos: pos, Seq: 0}
	p := biopb.Coord{RefId: g.LastRec.RefId, Pos: g.LastRec.Pos, Seq: 0}
	cmp := a.Compare(p)
	if cmp < 0 {
		log.Panicf("Record coordinate decreased from %+v to %v:%v", g.LastRec, refID, pos)
	}
	if cmp == 0 {
		g.LastRec.Seq++
	} else {
		g.LastRec = a
	}
	return g.LastRec
}
func (g *CoordGenerator) GenerateFromRecord(rec *sam.Record) biopb.Coord {
	return g.Generate(int32(rec.Ref.ID()), int32(rec.Pos))
}
func CoordFromSAMRecord(rec *sam.Record, seq int32) biopb.Coord {
	return NewCoord(rec.Ref, rec.Pos, seq)
}
func MateCoordFromSAMRecord(rec *sam.Record, seq int32) biopb.Coord {
	return NewCoord(rec.MateRef, rec.MatePos, seq)
}
func NewCoord(ref *sam.Reference, pos int, seq int32) biopb.Coord {
	a := biopb.Coord{RefId: int32(ref.ID()), Pos: int32(pos), Seq: seq}
	if a.RefId == biopb.InfinityRefID && pos < 0 {
		a.Pos = 0
	}
	return a
}
func NewShardChannel(shards []Shard) chan Shard {
	shuffle := make([]Shard, 0, len(shards))
	shardChan := make(chan Shard, len(shards))
	for _, shard := range shards {
		if shard.EndRef == nil {
			shardChan <- shard
			continue
		}
		shuffle = append(shuffle, shard)
	}
	rand.Shuffle(len(shuffle), func(i, j int) {
		shuffle[i], shuffle[j] = shuffle[j], shuffle[i]
	})
	for _, shard := range shuffle {
		shardChan <- shard
	}
	close(shardChan)
	return shardChan
}
func GetPositionBasedShards(header *sam.Header, shardSize int, padding int, includeUnmapped bool) ([]Shard, error) {
	var shards []Shard
	shardIdx := 0
	for _, ref := range header.Refs() {
		var start int
		for start < ref.Len() {
			end := min(start+shardSize, ref.Len())
			shards = append(shards,
				Shard{
					StartRef: ref,
					EndRef:   ref,
					Start:    start,
					End:      end,
					Padding:  padding,
					ShardIdx: shardIdx,
				})
			start += shardSize
			shardIdx++
		}
	}
	if includeUnmapped {
		shards = append(shards,
			Shard{
				StartRef: nil,
				EndRef:   nil,
				Start:    0,
				End:      math.MaxInt32,
				ShardIdx: shardIdx,
			})
	}
	ValidateShardList(header, shards, padding)
	return shards, nil
}
func GetByteBasedShards(bamPath, baiPath string, bytesPerShard int64, minBases, padding int, includeUnmapped bool) (shards []Shard, err error) {
	ctx := backgroundcontext.Get()
	var bamIn file.File
	bamIn, err = file.Open(ctx, bamPath)
	if err != nil {
		return nil, err
	}
	defer file.CloseAndReport(ctx, bamIn, &err)
	var bamr *bam.Reader
	bamr, err = bam.NewReader(bamIn.Reader(ctx), 1)
	if err != nil {
		return nil, err
	}
	header := bamr.Header()
	if strings.HasSuffix(baiPath, ".gbai") {
		return gbaiByteBasedShards(ctx, header, baiPath, bytesPerShard, minBases, padding, includeUnmapped)
	}
	return baiByteBasedShards(ctx, bamr, baiPath, bytesPerShard, minBases, padding, includeUnmapped)
}