func TestFlipBigACOW(t *testing.T) {
	Convey("flipTestBigA ", t, func() {
		numCases := 1000
		bs := bitset.New(0)
		checkTime := 2.0
		rb1 := NewBitmap()
		rb1.SetCopyOnWrite(true)
		rb2 := NewBitmap()
		rb2.SetCopyOnWrite(true)

		for i := 0; i < numCases; i++ {
			start := rand.Intn(65536 * 20)
			end := rand.Intn(65536 * 20)
			if rand.Float64() < 0.1 {
				end = start + rand.Intn(100)
			}

			if (i & 1) == 0 {
				rb2 = FlipInt(rb1, start, end)
				// tweak the other, catch bad sharing
				rb1.FlipInt(rand.Intn(65536*20), rand.Intn(65536*20))
			} else {
				rb1 = FlipInt(rb2, start, end)
				rb2.FlipInt(rand.Intn(65536*20), rand.Intn(65536*20))
			}

			if start < end {
				FlipRange(start, end, bs) // throws exception
			}
			// otherwise
			// insert some more ANDs to keep things sparser
			if (rand.Float64() < 0.2) && (i&1) == 0 {
				mask := NewBitmap()
				mask.SetCopyOnWrite(true)
				mask1 := bitset.New(0)
				startM := rand.Intn(65536 * 20)
				endM := startM + 100000
				mask.FlipInt(startM, endM)
				FlipRange(startM, endM, mask1)
				mask.FlipInt(0, 65536*20+100000)
				FlipRange(0, 65536*20+100000, mask1)
				rb2.And(mask)
				bs.InPlaceIntersection(mask1)
			}

			if float64(i) > checkTime {
				var rb *Bitmap

				if (i & 1) == 0 {
					rb = rb2
				} else {
					rb = rb1
				}
				So(equalsBitSet(bs, rb), ShouldEqual, true)
				checkTime *= 1.5
			}
		}
	})
}

// getMergeSet finds the nodes that share at least 1 parent and 1 child with trie[i][j]
// These will be the nodes that get merged into j
func (this *Analyzer) getMergeSet(i, j int, cur *analyzerNode) (*bitset.BitSet, error) {
	level := this.levels[i]

	// shareParents is a bitset marks all the nodes that share at least 1 parent
	// with the current node being checked
	shareParents := bitset.New(uint(len(level)))

	// shareChildren is a bitset marks all the nodes that share at least 1 child
	// with the current node being checked
	shareChildren := bitset.New(uint(len(level)))

	// Set the current node's bit in both shareParents and shareChildren
	shareParents.Set(uint(j))
	shareChildren.Set(uint(j))

	// For each node after the current constant/word node, check to see if there's
	// any that share at least 1 parent or 1 child
	for k, tmp := range level[j+1:] {
		// - If node if nil, then most likely have been merged, let's move on
		// - We only merge nodes that are literals or strings, anything else
		//   is already a variable so move on
		// - If node is a single character literal, then not merging, move on
		if tmp == nil ||
			(tmp.Type != TokenLiteral && tmp.Type != TokenString) ||
			(tmp.Type == TokenLiteral && len(tmp.Value) == 1) {

			continue
		}

		// Take the intersection of current node's parent bitset and the next
		// constant/word node's parent bitset, if the cardinality of the result
		// bitset is greater than 0, then it means they share at least 1 parent.
		// If so, then set the bit that represent that node in shareParent.
		if c := cur.parents.IntersectionCardinality(tmp.parents); c > 0 {
			shareParents.Set(uint(k + j + 1))
		}

		// Take the intersection of current node's children bitset and the next
		// constant/word node's children bitset, if the cardinality of the result
		// bitset is greater than 0, then it means they share at least 1 child.
		// If so, then set the bit that represent that node in shareChildren.
		if c := cur.children.IntersectionCardinality(tmp.children); c > 0 {
			shareChildren.Set(uint(k + j + 1))
		}
	}

	// The goal is to identify all nodes that share at least 1 parent and 1 child
	// with the current node. Now that we have all the nodes that share at least
	// 1 parent in shareParents, and all the nodes that share at least 1 child
	// in shareChildren, we can then take the intersection of shareParent and
	// shareChildren to get all the nodes that share both
	mergeSet := shareParents.Intersection(shareChildren)

	return mergeSet, nil
}

// some extra tests
func TestBitmapExtraCOW(t *testing.T) {
	for N := uint32(1); N <= 65536; N *= 2 {
		Convey("extra tests"+strconv.Itoa(int(N)), t, func() {
			for gap := uint32(1); gap <= 65536; gap *= 2 {
				bs1 := bitset.New(0)
				rb1 := NewBitmap()
				rb1.SetCopyOnWrite(true)
				rb1.SetCopyOnWrite(true)

				for x := uint32(0); x <= N; x += gap {
					bs1.Set(uint(x))
					rb1.Add(x)
				}
				So(bs1.Count(), ShouldEqual, rb1.GetCardinality())
				So(equalsBitSet(bs1, rb1), ShouldEqual, true)
				for offset := uint32(1); offset <= gap; offset *= 2 {
					bs2 := bitset.New(0)
					rb2 := NewBitmap()
					rb2.SetCopyOnWrite(true)

					for x := uint32(0); x <= N; x += gap {
						bs2.Set(uint(x + offset))
						rb2.Add(x + offset)
					}
					So(bs2.Count(), ShouldEqual, rb2.GetCardinality())
					So(equalsBitSet(bs2, rb2), ShouldEqual, true)

					clonebs1 := bs1.Clone()
					clonebs1.InPlaceIntersection(bs2)
					if !equalsBitSet(clonebs1, And(rb1, rb2)) {
						t := rb1.Clone()
						t.And(rb2)
						So(equalsBitSet(clonebs1, t), ShouldEqual, true)
					}

					// testing OR
					clonebs1 = bs1.Clone()
					clonebs1.InPlaceUnion(bs2)

					So(equalsBitSet(clonebs1, Or(rb1, rb2)), ShouldEqual, true)
					// testing XOR
					clonebs1 = bs1.Clone()
					clonebs1.InPlaceSymmetricDifference(bs2)
					So(equalsBitSet(clonebs1, Xor(rb1, rb2)), ShouldEqual, true)

					//testing NOTAND
					clonebs1 = bs1.Clone()
					clonebs1.InPlaceDifference(bs2)
					So(equalsBitSet(clonebs1, AndNot(rb1, rb2)), ShouldEqual, true)
				}
			}
		})
	}
}

func rTestCOW(N int) {
	log.Println("rtest N=", N)
	for gap := 1; gap <= 65536; gap *= 2 {
		bs1 := bitset.New(0)
		rb1 := NewBitmap()
		rb1.SetCopyOnWrite(true)
		for x := 0; x <= N; x += gap {
			bs1.Set(uint(x))
			rb1.AddInt(x)
		}
		So(bs1.Count(), ShouldEqual, rb1.GetCardinality())
		So(equalsBitSet(bs1, rb1), ShouldEqual, true)
		for offset := 1; offset <= gap; offset *= 2 {
			bs2 := bitset.New(0)
			rb2 := NewBitmap()
			rb2.SetCopyOnWrite(true)
			for x := 0; x <= N; x += gap {
				bs2.Set(uint(x + offset))
				rb2.AddInt(x + offset)
			}
			So(bs2.Count(), ShouldEqual, rb2.GetCardinality())
			So(equalsBitSet(bs2, rb2), ShouldEqual, true)

			clonebs1 := bs1.Clone()
			clonebs1.InPlaceIntersection(bs2)
			if !equalsBitSet(clonebs1, And(rb1, rb2)) {
				t := rb1.Clone()
				t.And(rb2)
				So(equalsBitSet(clonebs1, t), ShouldEqual, true)
			}

			// testing OR
			clonebs1 = bs1.Clone()
			clonebs1.InPlaceUnion(bs2)

			So(equalsBitSet(clonebs1, Or(rb1, rb2)), ShouldEqual, true)
			// testing XOR
			clonebs1 = bs1.Clone()
			clonebs1.InPlaceSymmetricDifference(bs2)
			So(equalsBitSet(clonebs1, Xor(rb1, rb2)), ShouldEqual, true)

			//testing NOTAND
			clonebs1 = bs1.Clone()
			clonebs1.InPlaceDifference(bs2)
			So(equalsBitSet(clonebs1, AndNot(rb1, rb2)), ShouldEqual, true)
		}
	}
}

func (window *Window) initialize() {
	window.primes = []uint{2}
	window.segment = bitset.New(window.size)
	window.span = window.size * 2
	window.shift(3)
	window.Count = 1
}

// Any returns true if any index is set
func (p *PermissionSet) Any(indices ...uint) bool {
	other := bitset.New(p.bits.Len())
	for _, i := range indices {
		other.Set(i)
	}
	return p.bits.Intersection(other).Any()
}

// All returns true iff all bits are set
func (p *PermissionSet) All(indices ...uint) bool {
	other := bitset.New(p.bits.Len())
	for _, i := range indices {
		other.Set(i)
	}
	return p.bits.IsSuperSet(other)
}

func NewCompensator() *Compensator {
	rv := Compensator{
		inFlight:          gtreap.NewTreap(inFlightItemCompare),
		deletedDocNumbers: bitset.New(1000000),
	}
	return &rv
}

func NewLedgerSet(start, capacity uint32) *LedgerSet {
	return &LedgerSet{
		ledgers: bitset.New(uint(capacity)).Complement(),
		start:   start,
		taken:   make(map[uint32]time.Time),
	}
}

func generateUniformBitmap(N, max int) ([]int32, error) {
	if N > max {
		return nil, errors.New("encoding/generateUniformBitmap: N > max, not possible")
	}

	r := rand.New(rand.NewSource(c1))
	ans := make([]int32, N)
	bs := bitset.New(uint(max))
	cardinality := uint(0)

	for int(cardinality) < N {
		v := r.Int31n(int32(max))
		if !bs.Test(uint(v)) {
			bs.Set(uint(v))
			cardinality += 1
		}
	}

	for i, c := int32(0), 0; c < N; i++ {
		if bs.Test(uint(i)) {
			ans[c] = i
			c += 1
		}
	}

	return ans, nil
}

func TestFirstClearBitNothing(t *testing.T) {
	bs := bitset.New(2)

	i, s := firstClearBit(bs)
	assert.Equal(t, i, uint(0), "First bit should be 0")
	assert.True(t, s, "Success should be true")
}

func (c *MsgpackDeltasCodec) ToBitset() *bitset.BitSet {
	bs := bitset.New(8)
	for _, id := range c.Documents() {
		bs.Set(uint(id))
	}
	return bs
}

func New(l uint64, m uint64, w uint64) (*Sketch, error) {
	if l == 0 || m == 0 || w == 0 {
		return nil, errors.New("All parameters must be > 0")
	} else if l > (1<<w)-1 || l > (1<<64)-1 {
		return nil, errors.New("l must be < 2**w and < 2**64")
	}
	return &Sketch{l: l, m: m, w: w, bitmap: bitset.New(uint(l)), changed: true}, nil
}

func NewSubnet() *Subnet {
	return &Subnet{
		Leases:     make(map[string]*Lease),
		Bindings:   make(map[string]*Binding),
		Options:    make(dhcp.Options),
		ActiveBits: bitset.New(0),
	}
}

func main() {
	var maxv = uint(65536)
	args := os.Args[1:len(os.Args)]
	log.Println("args", args)
	if len(args) != 0 {
		if _, err := os.Stat(args[0]); err == nil {
			dumpfile(args[0])
			return
		}
		maxv64, _ := strconv.ParseUint(args[0], 0, 64)
		maxv = uint(maxv64)
	}
	var maxvv = uint(math.Sqrt(float64(maxv)))
	log.Println("calculate primes", maxv, maxvv)
	var bs = bitset.New(maxv)
	for x := uint(1); x < maxvv; x++ {
		for y := uint(1); y < maxvv; y++ {
			var k = uint(4*x*x + y*y)
			if k < maxv && (k%12 == 1 || k%12 == 5) {
				bs.Flip(k)
			}
			k = uint(3*x*x + y*y)
			if k < maxv && (k%12 == 7) {
				bs.Flip(k)
			}
			if x > y {
				k = 3*x*x - y*y
				if k < maxv && k%12 == 11 {
					bs.Flip(k)
				}
			}
		}
	}
	cnt := bs.Count()
	log.Println("bs.Count=", cnt, "/", bs.Len(), bs.Len()/(bs.Len()-cnt))
	bs.Set(2)
	bs.Set(3)
	for n := uint(5); n < maxvv; n++ {
		if bs.Test(n) {
			n2 := n * n
			for k := n2; k < maxv; k += n2 {
				bs.Clear(k)
			}
		}
	}
	fp, err := os.Create("prime.dat")
	if err != nil {
		log.Panic("file open error")
	}
	defer fp.Close()
	var primes = intseq.NewIntSeq()
	for n := uint(2); n < maxv; n++ {
		if bs.Test(n) {
			primes.Add(uint64(n))
		}
	}
	primes.Write(fp)
}

// go test -bench BenchmarkSize -run -
func BenchmarkSizeBitset(b *testing.B) {
	b.StopTimer()
	r := rand.New(rand.NewSource(0))
	s1 := bitset.New(0)
	sz := 150000
	initsize := 65000
	for i := 0; i < initsize; i++ {
		s1.Set(uint(r.Int31n(int32(sz))))
	}
	s2 := bitset.New(0)
	sz = 100000000
	initsize = 65000
	for i := 0; i < initsize; i++ {
		s2.Set(uint(r.Int31n(int32(sz))))
	}
	fmt.Printf("%.1f MB ", float32(s1.BinaryStorageSize()+s2.BinaryStorageSize())/(1024.0*1024))

}

func makePartitions(k, s uint) []*bitset.BitSet {
	b := make([]*bitset.BitSet, k)

	for i := uint(0); i < k; i++ {
		b[i] = bitset.New(s)
	}

	return b
}

func makePartitions(k, s uint) []*bitset.BitSet {
	b := make([]*bitset.BitSet, k)

	for i, _ := range b {
		b[i] = bitset.New(s)
	}

	return b
}

func main() {
	olddb, err := Open(os.Args[1])
	if err != nil {
		panic(err)
	}
	newdb, err := Open(os.Args[2])
	if err != nil {
		panic(err)
	}

	iter := olddb.NewIterator(&util.Range{Start: nil, Limit: nil}, nil)

	totalBitset := 0
	totalMsgpack := 0

	rows := 0

	var batch *leveldb.Batch
	batch = new(leveldb.Batch)
	for iter.Next() {
		key := iter.Key()
		value := iter.Value()
		if bytes.HasPrefix(key, []byte("doc:")) {
			batch.Put(key, value)
			continue
		}
		bs := bitset.New(8)
		bs.ReadFrom(bytes.NewBuffer(value))
		var docIDs []uint
		for i, e := bs.NextSet(0); e; i, e = bs.NextSet(i + 1) {
			docIDs = append(docIDs, i)
		}
		b, err := msgpack.Marshal(delta_encode(docIDs))
		if err != nil {
			panic(err)
		}
		//fmt.Printf("bitset size is %d\n", len(value))
		//fmt.Printf("msgpack size is %d\n", len(b))

		totalBitset += len(value)
		totalMsgpack += len(b)
		batch.Put(key, b)
		if rows%10000 == 0 {
			log.Print("rows ", rows)
			newdb.Write(batch, nil)
			batch = new(leveldb.Batch)
		}
		rows++

	}
	fmt.Printf("bitset size is %d\n", totalBitset)
	fmt.Printf("msgpack size is %d\n", totalMsgpack)
	newdb.Write(batch, nil)
	newdb.CompactRange(util.Range{Start: nil, Limit: nil})

}

func TestFirstClearBitAllSet(t *testing.T) {
	bs := bitset.New(2)

	bs.Set(0)
	bs.Set(1)

	i, s := firstClearBit(bs)
	assert.Equal(t, i, uint(0), "First bit should be 0")
	assert.False(t, s, "Success should be false")
}