// Intersects reports whether this points-to set and the
// argument points-to set contain common members.
func (x PointsToSet) Intersects(y PointsToSet) bool {
	if x.pts == nil || y.pts == nil {
		return false
	}
	// This takes Θ(|x|+|y|) time.
	var z intsets.Sparse
	z.Intersection(&x.pts.Sparse, &y.pts.Sparse)
	return !z.IsEmpty()
}

func BenchmarkAppendTo(b *testing.B) {
	prng := rand.New(rand.NewSource(0))
	var x intsets.Sparse
	for i := 0; i < 1000; i++ {
		x.Insert(int(prng.Int()) % 10000)
	}
	var space [1000]int
	for tries := 0; tries < b.N; tries++ {
		x.AppendTo(space[:0])
	}
}

// adds pb to the map literal -> pb.Id; as well as recording litSets
func addToCategory(nextId *int, pb *Threshold, cat map[sat.Literal][]int, lit2id map[sat.Literal]int, litSet *intsets.Sparse) {
	pb.Normalize(LE, true)
	for _, x := range pb.Entries {
		cat[x.Literal] = append(cat[x.Literal], pb.Id)
	}
	for _, e := range pb.Entries {
		if _, b := lit2id[e.Literal]; !b {
			lit2id[e.Literal] = *nextId
			*nextId++
		}
		litSet.Insert(lit2id[e.Literal])
	}
}

func TestFailFastOnShallowCopy(t *testing.T) {
	var x intsets.Sparse
	x.Insert(1)

	y := x // shallow copy (breaks representation invariants)
	defer func() {
		got := fmt.Sprint(recover())
		want := "A Sparse has been copied without (*Sparse).Copy()"
		if got != want {
			t.Errorf("shallow copy: recover() = %q, want %q", got, want)
		}
	}()
	y.String() // panics
	t.Error("didn't panic as expected")
}

func doChaining(pbs []*Threshold, complOcc map[sat.Literal][]int, simplOcc map[sat.Literal][]int,
	lit2id map[sat.Literal]int, litSets []intsets.Sparse) {

	//2) Prepare Matchings

	checked := make(map[Match]bool, 0)

	//ex_matchings := make(map[int][]Matching, 0)  // simpl_id -> []Matchings
	//currently ex and amo matchings are treated equivalently, the only
	//difference is that ex adds the unit clause of the ladder encoding, thus
	//the rewrite is correct and after UP the first value in the Ex is propagated.
	// TODO: explicitly rewrite and remove smallest value

	amo_matchings := make(map[int][]Matching, 0) // compl_id -> []Matchings

	for lit, list := range complOcc {
		//id2lit[lit2id[lit]] = lit
		for _, c := range list {
			for _, s := range simplOcc[lit] {
				if !checked[Match{c, s}] {
					// of comp c and simpl s there is at least
					checked[Match{c, s}] = true
					// 0 means it has not been checked,
					// as there is at least one intersection
					var inter intsets.Sparse
					inter.Intersection(&litSets[c], &litSets[s])
					if pbs[s].Typ == LE {
						if inter.Len() >= *glob.Len_rewrite_amo_flag {
							amo_matchings[c] = append(amo_matchings[c], Matching{s, &inter})
						}
					} else if pbs[s].Typ == EQ {
						if inter.Len() >= *glob.Len_rewrite_ex_flag {
							amo_matchings[c] = append(amo_matchings[c], Matching{s, &inter})
							//ex_matchings[c] = append(amo_matchings[c], Matching{s, &inter})
						}
					} else {
						glob.A(false, "case not treated")
					}
				}
			}
		}
	}

	glob.D("amo/ex_matchings:", len(amo_matchings))

	//3) amo/ex matchings

	for comp, _ := range pbs {
		if matchings, b := amo_matchings[comp]; b {
			workOnMatching(pbs, comp, matchings, lit2id, litSets)
		}
	}
}

func ArrayPairSum2(array []int, sum int) []IntPair {
	if len(array) < 2 {
		return nil
	}

	seen := intsets.Sparse{}
	result := make([]IntPair, 0, 100)
	for _, n := range array {
		target := sum - n
		if !seen.Has(target) {
			fmt.Printf("Insert: target=%d, n=%d, seen=%v\n", target, n, seen.String())
			seen.Insert(n)
		} else {
			fmt.Printf("Has: target=%d, n=%d, seen=%v\n", target, n, seen.String())
			result = append(result, IntPair{
				int(math.Min(float64(n), float64(target))),
				int(math.Max(float64(n), float64(target))),
			})
		}
	}
	return result
}

// From returns all nodes in g that can be reached directly from u.
func (g Undirect) From(u Node) []Node {
	var (
		nodes []Node
		seen  intsets.Sparse
	)
	for _, n := range g.G.From(u) {
		seen.Insert(n.ID())
		nodes = append(nodes, n)
	}
	for _, n := range g.G.To(u) {
		id := n.ID()
		if seen.Has(id) {
			continue
		}
		seen.Insert(id)
		nodes = append(nodes, n)
	}
	return nodes
}

func TestBitString(t *testing.T) {
	for _, test := range []struct {
		input []int
		want  string
	}{
		{nil, "0"},
		{[]int{0}, "1"},
		{[]int{0, 4, 5}, "110001"},
		{[]int{0, 7, 177}, "1" + strings.Repeat("0", 169) + "10000001"},
		{[]int{-3, 0, 4, 5}, "110001.001"},
		{[]int{-3}, "0.001"},
	} {
		var set intsets.Sparse
		for _, x := range test.input {
			set.Insert(x)
		}
		if got := set.BitString(); got != test.want {
			t.Errorf("BitString(%s) = %s, want %s", set.String(), got, test.want)
		}
	}
}

func TestIntersects(t *testing.T) {
	prng := rand.New(rand.NewSource(0))

	for i := uint(0); i < 12; i++ {
		X, Y := randomPset(prng, 1<<i), randomPset(prng, 1<<i)
		x, y := &X.bits, &Y.bits

		// test the slow way
		var z intsets.Sparse
		z.Copy(x)
		z.IntersectionWith(y)

		if got, want := x.Intersects(y), !z.IsEmpty(); got != want {
			t.Errorf("Intersects: got %v, want %v", got, want)
		}

		// make it false
		a := x.AppendTo(nil)
		for _, v := range a {
			y.Remove(v)
		}

		if got, want := x.Intersects(y), false; got != want {
			t.Errorf("Intersects: got %v, want %v", got, want)
		}

		// make it true
		if x.IsEmpty() {
			continue
		}
		i := prng.Intn(len(a))
		y.Insert(a[i])

		if got, want := x.Intersects(y), true; got != want {
			t.Errorf("Intersects: got %v, want %v", got, want)
		}
	}
}

func TestSubsetOf(t *testing.T) {
	prng := rand.New(rand.NewSource(0))

	for i := uint(0); i < 12; i++ {
		X, Y := randomPset(prng, 1<<i), randomPset(prng, 1<<i)
		x, y := &X.bits, &Y.bits

		// test the slow way
		var z intsets.Sparse
		z.Copy(x)
		z.DifferenceWith(y)

		if got, want := x.SubsetOf(y), z.IsEmpty(); got != want {
			t.Errorf("SubsetOf: got %v, want %v", got, want)
		}

		// make it true
		y.UnionWith(x)

		if got, want := x.SubsetOf(y), true; got != want {
			t.Errorf("SubsetOf: got %v, want %v", got, want)
		}

		// make it false
		if x.IsEmpty() {
			continue
		}
		a := x.AppendTo(nil)
		i := prng.Intn(len(a))
		y.Remove(a[i])

		if got, want := x.SubsetOf(y), false; got != want {
			t.Errorf("SubsetOf: got %v, want %v", got, want)
		}
	}
}

func TestBasics(t *testing.T) {
	var s intsets.Sparse
	if len := s.Len(); len != 0 {
		t.Errorf("Len({}): got %d, want 0", len)
	}
	if s := s.String(); s != "{}" {
		t.Errorf("String({}): got %q, want \"{}\"", s)
	}
	if s.Has(3) {
		t.Errorf("Has(3): got true, want false")
	}
	if err := s.Check(); err != nil {
		t.Error(err)
	}

	if !s.Insert(3) {
		t.Errorf("Insert(3): got false, want true")
	}
	if max := s.Max(); max != 3 {
		t.Errorf("Max: got %d, want 3", max)
	}

	if !s.Insert(435) {
		t.Errorf("Insert(435): got false, want true")
	}
	if s := s.String(); s != "{3 435}" {
		t.Errorf("String({3 435}): got %q, want \"{3 435}\"", s)
	}
	if max := s.Max(); max != 435 {
		t.Errorf("Max: got %d, want 435", max)
	}
	if len := s.Len(); len != 2 {
		t.Errorf("Len: got %d, want 2", len)
	}

	if !s.Remove(435) {
		t.Errorf("Remove(435): got false, want true")
	}
	if s := s.String(); s != "{3}" {
		t.Errorf("String({3}): got %q, want \"{3}\"", s)
	}
}

func TestTakeMin(t *testing.T) {
	var set intsets.Sparse
	set.Insert(456)
	set.Insert(123)
	set.Insert(789)
	set.Insert(-123)
	var got int
	for i, want := range []int{-123, 123, 456, 789} {
		if !set.TakeMin(&got) || got != want {
			t.Errorf("TakeMin #%d: got %d, want %d", i, got, want)
		}
	}
	if set.TakeMin(&got) {
		t.Errorf("%s.TakeMin returned true", &set)
	}
	if err := set.Check(); err != nil {
		t.Fatalf("check: %s: %#v", err, &set)
	}
}

// Insert, Len, IsEmpty, Hash, Clear, AppendTo.
func TestMoreBasics(t *testing.T) {
	set := new(intsets.Sparse)
	set.Insert(456)
	set.Insert(123)
	set.Insert(789)
	if set.Len() != 3 {
		t.Errorf("%s.Len: got %d, want 3", set, set.Len())
	}
	if set.IsEmpty() {
		t.Errorf("%s.IsEmpty: got true", set)
	}
	if !set.Has(123) {
		t.Errorf("%s.Has(123): got false", set)
	}
	if set.Has(1234) {
		t.Errorf("%s.Has(1234): got true", set)
	}
	got := set.AppendTo([]int{-1})
	if want := []int{-1, 123, 456, 789}; fmt.Sprint(got) != fmt.Sprint(want) {
		t.Errorf("%s.AppendTo: got %v, want %v", set, got, want)
	}

	set.Clear()

	if set.Len() != 0 {
		t.Errorf("Clear: got %d, want 0", set.Len())
	}
	if !set.IsEmpty() {
		t.Errorf("IsEmpty: got false")
	}
	if set.Has(123) {
		t.Errorf("%s.Has: got false", set)
	}
}

func (sb *SearchBotT) Search(searchBy map[string]string, searchFor []string, login string, password string, tid string) stonelizard.Response {
	var providers *intsets.Sparse
	var searchFields *intsets.Sparse
	var commonFields *intsets.Sparse
	var oneShotProviders *intsets.Sparse
	var field string
	var isFragmented bool
	var i int
	var p *TaxonomyTreeT
	var hasQueryParm bool
	var rep chan map[string]ResponseFieldT
	var response map[string]ResponseFieldT
	var responses map[string][]ResponseFieldT
	var respCount int

	//TODO: Readaptar
	searchBy["X-Login"] = login
	searchBy["X-Password"] = password
	searchBy["X-Trackid"] = tid

	//   Goose.Search = goose.Alert(6)
	//   defer func() { Goose.Search = goose.Alert(2) }()

	providers = &intsets.Sparse{}

	Goose.Search.Logf(2, "TID:%s len(sb.Providers): %d", tid, len(sb.Providers))

	// Fill the providers set with all provider currently known
	for i = 0; i < len(sb.Providers); i++ {
		providers.Insert(i)
	}

	// Determine if there is at least one bot providing all data needed
	// by repeatedly computing providers ∩= 'providers of a given field'
	for _, field = range searchFor {
		i, _, p = sb.Taxonomy.Search(field)
		if ((i + 1) != len(field)) || (p == nil) || (p.Id < 0) {
			Goose.Search.Logf(1, "TID:%s %s: %s", tid, ErrUndefinedField, field)
			return stonelizard.Response{
				Status: http.StatusInternalServerError,
				Body:   fmt.Sprintf("%s: %s", ErrUndefinedField, field),
			}
		}
		if sb.ByProvision[p.Id] == nil {
			isFragmented = true
			break
		}
		providers.IntersectionWith(sb.ByProvision[p.Id])
		if providers.IsEmpty() {
			isFragmented = true
			break
		}
	}

	Goose.Search.Logf(4, "TID:%s Determined if there is at least one bot providing all data needed (isFragmented=%#v): %#v", tid, isFragmented, providers)

	if !isFragmented {
		// Select in the bots that have all information needed
		// those who require only information we have
		searchFields = &intsets.Sparse{}
		for field, _ = range searchBy {
			i, _, p = sb.Taxonomy.Search(field)
			searchFields.Insert(p.Id)
		}

		Goose.Search.Logf(4, "TID:%s Bitstring of search created: %#v", tid, searchFields)

		oneShotProviders = &intsets.Sparse{}
		commonFields = &intsets.Sparse{}

		Goose.Search.Logf(4, "TID:%s providers.Max(): %d", tid, providers.Max())
		for i = 0; i <= providers.Max(); i++ {
			Goose.Search.Logf(4, "TID:%s Bitstring of sb.Providers[%d].Requires: %#v", tid, i, sb.Providers[i].Requires)
			commonFields.Intersection(searchFields, sb.Providers[i].Requires)
			if commonFields.Len() == sb.Providers[i].Requires.Len() {
				Goose.Search.Logf(4, "TID:%s Intersection at %d", tid, i)
				oneShotProviders.Insert(i)
			}
		}

		Goose.Search.Logf(4, "TID:%s Bitstring of oneShotProviders: %#v", tid, oneShotProviders)

		// If there is at least one bot who gives all fields
		// we need and requires just fields we already have...
		if oneShotProviders.Len() > 0 {
			rep = make(chan map[string]ResponseFieldT, oneShotProviders.Len())
			Goose.Search.Logf(4, "TID:%s len(sb.Providers): %d", tid, len(sb.Providers))
			for i = 0; i <= oneShotProviders.Max(); i++ {
				Goose.Search.Logf(4, "TID:%s oneShotProvider: %d", tid, i)
				if oneShotProviders.Has(i) {
					go func(instance int, report chan map[string]ResponseFieldT) {
						var err error
						var req *http.Request
						var host string
						var path string
						var swParm stonelizard.SwaggerParameterT
						var body map[string]interface{}
						var b_body []byte
						var resp *http.Response
						var qryResponse map[string]ResponseFieldT
//.........这里部分代码省略.........

func BenchmarkSparseBitVector(b *testing.B) {
	prng := rand.New(rand.NewSource(0))
	for tries := 0; tries < b.N; tries++ {
		var x, y, z intsets.Sparse
		for i := 0; i < 1000; i++ {
			n := int(prng.Int()) % 100000
			if i%2 == 0 {
				x.Insert(n)
			} else {
				y.Insert(n)
			}
		}
		z.Union(&x, &y)
		z.Difference(&x, &y)
	}
}

func TestMinAndMax(t *testing.T) {
	values := []int{0, 456, 123, 789, -123} // elt 0 => empty set
	wantMax := []int{intsets.MinInt, 456, 456, 789, 789}
	wantMin := []int{intsets.MaxInt, 456, 123, 123, -123}

	var set intsets.Sparse
	for i, x := range values {
		if i != 0 {
			set.Insert(x)
		}
		if got, want := set.Min(), wantMin[i]; got != want {
			t.Errorf("Min #%d: got %d, want %d", i, got, want)
		}
		if got, want := set.Max(), wantMax[i]; got != want {
			t.Errorf("Max #%d: got %d, want %d", i, got, want)
		}
	}

	set.Insert(intsets.MinInt)
	if got, want := set.Min(), intsets.MinInt; got != want {
		t.Errorf("Min: got %d, want %d", got, want)
	}

	set.Insert(intsets.MaxInt)
	if got, want := set.Max(), intsets.MaxInt; got != want {
		t.Errorf("Max: got %d, want %d", got, want)
	}
}

func TestEquals(t *testing.T) {
	var setX intsets.Sparse
	setX.Insert(456)
	setX.Insert(123)
	setX.Insert(789)

	if !setX.Equals(&setX) {
		t.Errorf("Equals(%s, %s): got false", &setX, &setX)
	}

	var setY intsets.Sparse
	setY.Insert(789)
	setY.Insert(456)
	setY.Insert(123)

	if !setX.Equals(&setY) {
		t.Errorf("Equals(%s, %s): got false", &setX, &setY)
	}

	setY.Insert(1)
	if setX.Equals(&setY) {
		t.Errorf("Equals(%s, %s): got true", &setX, &setY)
	}

	var empty intsets.Sparse
	if setX.Equals(&empty) {
		t.Errorf("Equals(%s, %s): got true", &setX, &empty)
	}

	// Edge case: some block (with offset=0) appears in X but not Y.
	setY.Remove(123)
	if setX.Equals(&setY) {
		t.Errorf("Equals(%s, %s): got true", &setX, &setY)
	}
}

// deltaQ returns the highest gain in modularity attainable by moving
// n from its current community to another connected community and
// the index of the chosen destination. The index into the localMover's
// communities field is returned in src if n is in communities.
func (l *localMover) deltaQ(n graph.Node) (deltaQ float64, dst int, src commIdx) {
	id := n.ID()
	a_aa := l.weight(n, n)
	k_a := l.edgeWeightOf[id]
	m2 := l.m2
	gamma := l.resolution

	// Find communites connected to n.
	var connected intsets.Sparse
	// The following for loop is equivalent to:
	//
	//  for _, v := range l.g.From(n) {
	//  	connected.Insert(l.memberships[v.ID()])
	//  }
	//
	// This is done to avoid an allocation.
	for _, vid := range l.g.edges[id] {
		connected.Insert(l.memberships[vid])
	}
	// Insert the node's own community.
	connected.Insert(l.memberships[id])

	// Calculate the highest modularity gain
	// from moving into another community and
	// keep the index of that community.
	var dQremove float64
	dQadd, dst, src := math.Inf(-1), -1, commIdx{-1, -1}
	var i int
	for connected.TakeMin(&i) {
		c := l.communities[i]
		var k_aC, sigma_totC float64 // C is a substitution for ^