func firstClearBit(bs *bitset.BitSet) (uint, bool) {
	for i := uint(0); i < bs.Len(); i++ {
		if !bs.Test(i) {
			return i, true
		}
	}
	return 0, false
}

func toBitSet(number uint64) bitset.BitSet {
	lsbString := strconv.FormatUint(number, 2)

	var b bitset.BitSet
	for i, character := range lsbString {
		if character == '1' {
			b.Set(uint(len(lsbString)-1) - uint(i))
		}
	}
	return b
}

func (ls *LevelDBStore) bitsetToDocs(bs *bitset.BitSet) ([]string, error) {
	var err error
	var docs []string
	for i, e := bs.NextSet(0); e; i, e = bs.NextSet(i + 1) {
		name, err := ls.DocumentIDToName(uint64(i))
		if err != nil {
			break
		}
		docs = append(docs, name)
	}
	return docs, err
}

func solve(pr *codejam.Problem, d *data) {
	n := len(d.pairs)

	ais := make([]int, n)
	bis := make([]int, n)

	for i := 0; i < n; i++ {
		ais[i] = i
		bis[i] = i
	}

	psa := &pairSorter{
		indices: ais,
		pairs:   d.pairs,
		column:  0,
	}

	psb := &pairSorter{
		indices: bis,
		pairs:   d.pairs,
		column:  1,
	}

	sort.Sort(psa)
	sort.Sort(psb)

	var nw int

	for i := 0; i < n-1; i++ {
		v := d.pairs[ais[i]][1]

		k := sort.Search(n, func(j int) bool {
			return d.pairs[bis[j]][1] >= v
		})

		// count common indices from ais[i+1:] and bis[:k]
		var ba bitset.BitSet
		var bb bitset.BitSet

		for _, c := range ais[i+1:] {
			ba.Set(uint(c))
		}

		for _, c := range bis[:k] {
			bb.Set(uint(c))
		}

		nw += int(ba.IntersectionCardinality(&bb))
	}

	pr.Write(fmt.Sprintf("Case #%d: %d\n", d.testIndex, nw))
}

func requestRetransmit(blocks []int, bs *bitset.BitSet, conn net.Conn, e Encoder, isRestart bool) {
	if len(blocks) <= 0 {
		return
	}
	var missingBlocks []int
	if isRestart {
		missingBlocks = blocks[0:1]
	} else {
		for _, b := range blocks {
			if !bs.Test(uint(b)) {
				missingBlocks = append(missingBlocks, b)
			}
		}
	}

	payload := Retransmit{IsRestart: isRestart, BlockNums: missingBlocks}
	pkt := Packet{Type: RETRANSMIT, Payload: payload}
	_, err := sendPacket(&pkt, conn, e)
	if err != nil {
		log.Println("Error sending retransmit blocks: " + err.Error())
	}
}

func (p *smatPair) equalsBitSet(a *bitset.BitSet, b *Bitmap) bool {
	for i, e := a.NextSet(0); e; i, e = a.NextSet(i + 1) {
		if !b.ContainsInt(int(i)) {
			fmt.Printf("in a bitset, not b bitmap, i: %d\n", i)
			fmt.Printf("  a bitset: %s\n  b bitmap: %s\n",
				a.String(), b.String())
			return false
		}
	}

	i := b.Iterator()
	for i.HasNext() {
		v := i.Next()
		if !a.Test(uint(v)) {
			fmt.Printf("in b bitmap, not a bitset, v: %d\n", v)
			fmt.Printf("  a bitset: %s\n  b bitmap: %s\n",
				a.String(), b.String())
			return false
		}
	}

	return true
}

func equalsBitSet(a *bitset.BitSet, b *Bitmap) bool {
	for i, e := a.NextSet(0); e; i, e = a.NextSet(i + 1) {
		if !b.ContainsInt(int(i)) {
			return false
		}
	}
	i := b.Iterator()
	for i.HasNext() {
		if !a.Test(uint(i.Next())) {
			return false
		}
	}
	return true
}

func FlipRange(start, end int, bs *bitset.BitSet) {
	for i := start; i < end; i++ {
		bs.Flip(uint(i))
	}
}

func Similarity(a, b *bitset.BitSet, nHashes uint) float64 {
	count := a.SymmetricDifferenceCardinality(b)
	return 1. - float64(count)/float64(nHashes)
}