// Difference returns a set of objects that are not in s2
// For example:
// s1 = {a1, a2, a3}
// s2 = {a1, a2, a4, a5}
// s1.Difference(s2) = {a3}
// s2.Difference(s1) = {a4, a5}
969926
func (s Byte) Difference(s2 Byte) Byte {
	result := NewByte()
	for key := range s {
		if !s2.Has(key) {
			result.Insert(key)
		}
	}
	return result
}
493784
func equal(s Set, s2 Set) bool {
	if s.Len() != s2.Len() {
		return false
	}

	return s.IsSubset(s2)
}
1272562
func (rules Rules) Difference(rules2 Rules) Rules {
	nrules := make(Rules)

	for pattern, targetIDSet := range rules {
		if nv := targetIDSet.Difference(rules2[pattern]); len(nv) > 0 {
			nrules[pattern] = nv
		}
	}

	return nrules
}
80790
func (s *set) Compare(other Value) int {
	o1 := sortOrder(s)
	o2 := sortOrder(other)
	if o1 < o2 {
		return -1
	} else if o1 > o2 {
		return 1
	}
	t := other.(*set)
	sort.Sort(termSlice(s.keys))
	sort.Sort(termSlice(t.keys))
	return termSliceCompare(s.keys, t.keys)
}
539676
func (rule *Rule) Diff(other *Rule) []string {
	result := []string{}

	if rule.Kind != other.Kind {
		result = append(result, fmt.Sprintf("Kind: %s | %s", rule.Kind.String(), other.Kind.String()))
	}

	if rule.Prelude != other.Prelude {
		result = append(result, fmt.Sprintf("Prelude: \"%s\" | \"%s\"", rule.Prelude, other.Prelude))
	}

	if rule.Name != other.Name {
		result = append(result, fmt.Sprintf("Name: \"%s\" | \"%s\"", rule.Name, other.Name))
	}

	if len(rule.Selectors) != len(other.Selectors) {
		result = append(result, fmt.Sprintf("Selectors: %v | %v", strings.Join(rule.Selectors, ", "), strings.Join(other.Selectors, ", ")))
	} else {
		for i, sel := range rule.Selectors {
			if sel != other.Selectors[i] {
				result = append(result, fmt.Sprintf("Selector: \"%s\" | \"%s\"", sel, other.Selectors[i]))
			}
		}
	}

	if len(rule.Declarations) != len(other.Declarations) {
		result = append(result, fmt.Sprintf("Declarations Nb: %d | %d", len(rule.Declarations), len(other.Declarations)))
	} else {
		for i, decl := range rule.Declarations {
			if !decl.Equal(other.Declarations[i]) {
				result = append(result, fmt.Sprintf("Declaration: \"%s\" | \"%s\"", decl.String(), other.Declarations[i].String()))
			}
		}
	}

	if len(rule.Rules) != len(other.Rules) {
		result = append(result, fmt.Sprintf("Rules Nb: %d | %d", len(rule.Rules), len(other.Rules)))
	} else {

		for i, rule := range rule.Rules {
			if !rule.Equal(other.Rules[i]) {
				result = append(result, fmt.Sprintf("Rule: \"%s\" | \"%s\"", rule.String(), other.Rules[i].String()))
			}
		}
	}

	return result
}
643752
func (obj *object) Compare(other Value) int {
	o1 := sortOrder(obj)
	o2 := sortOrder(other)
	if o1 < o2 {
		return -1
	} else if o2 < o1 {
		return 1
	}
	a := obj
	b := other.(*object)
	keysA := a.Keys()
	keysB := b.Keys()
	sort.Sort(termSlice(keysA))
	sort.Sort(termSlice(keysB))
	minLen := a.Len()
	if b.Len() < a.Len() {
		minLen = b.Len()
	}
	for i := 0; i < minLen; i++ {
		keysCmp := Compare(keysA[i], keysB[i])
		if keysCmp < 0 {
			return -1
		}
		if keysCmp > 0 {
			return 1
		}
		valA := a.Get(keysA[i])
		valB := b.Get(keysB[i])
		valCmp := Compare(valA, valB)
		if valCmp != 0 {
			return valCmp
		}
	}
	if a.Len() < b.Len() {
		return -1
	}
	if b.Len() < a.Len() {
		return 1
	}
	return 0
}
370061
func Diff(a, b interface{}) (desc []string) {
	Pdiff((*sbuf)(&desc), a, b)
	return desc
}
194778
func Difference(wants chronograf.Permissions, haves chronograf.Permissions) (revoke chronograf.Permissions, add chronograf.Permissions) {
	for _, want := range wants {
		found := false
		for _, got := range haves {
			if want.Scope != got.Scope || want.Name != got.Name {
				continue
			}
			found = true
			if len(want.Allowed) == 0 {
				revoke = append(revoke, want)
			} else {
				add = append(add, want)
			}
			break
		}
		if !found {
			add = append(add, want)
		}
	}

	for _, got := range haves {
		found := false
		for _, want := range wants {
			if want.Scope != got.Scope || want.Name != got.Name {
				continue
			}
			found = true
			break
		}
		if !found {
			revoke = append(revoke, got)
		}
	}
	return
}
432895
func (from *Tree) Diff(to *Tree) (Changes, error) {
	return DiffTree(from, to)
}
651076
func AttributeDifference(a1, a2 []Attribute) []Attribute {
	ret := make([]Attribute, 0)
	for _, a := range a1 {
		matched := false
		for _, b := range a2 {
			if a.Equals(b) {
				matched = true
				break
			}
		}
		if !matched {
			ret = append(ret, a)
		}
	}
	return ret
}
832423
func (s *SeriesIDSet) Diff(other *SeriesIDSet) {
	other.RLock()
	defer other.RUnlock()

	s.Lock()
	defer s.Unlock()
	s.bitmap = roaring.AndNot(s.bitmap, other.bitmap)
}
345845
func (t Term) Difference(args ...interface{}) Term {
	return constructMethodTerm(t, "Difference", p.Term_DIFFERENCE, args, map[string]interface{}{})
}
688290
func (d *InstanceDiff) Same(d2 *InstanceDiff) (bool, string) {
	// we can safely compare the pointers without a lock
	switch {
	case d == nil && d2 == nil:
		return true, ""
	case d == nil || d2 == nil:
		return false, "one nil"
	case d == d2:
		return true, ""
	}

	d.mu.Lock()
	defer d.mu.Unlock()

	// If we're going from requiring new to NOT requiring new, then we have
	// to see if all required news were computed. If so, it is allowed since
	// computed may also mean "same value and therefore not new".
	oldNew := d.requiresNew()
	newNew := d2.RequiresNew()
	if oldNew && !newNew {
		oldNew = false

		// This section builds a list of ignorable attributes for requiresNew
		// by removing off any elements of collections going to zero elements.
		// For collections going to zero, they may not exist at all in the
		// new diff (and hence RequiresNew == false).
		ignoreAttrs := make(map[string]struct{})
		for k, diffOld := range d.Attributes {
			if !strings.HasSuffix(k, ".%") && !strings.HasSuffix(k, ".#") {
				continue
			}

			// This case is in here as a protection measure. The bug that this
			// code originally fixed (GH-11349) didn't have to deal with computed
			// so I'm not 100% sure what the correct behavior is. Best to leave
			// the old behavior.
			if diffOld.NewComputed {
				continue
			}

			// We're looking for the case a map goes to exactly 0.
			if diffOld.New != "0" {
				continue
			}

			// Found it! Ignore all of these. The prefix here is stripping
			// off the "%" so it is just "k."
			prefix := k[:len(k)-1]
			for k2, _ := range d.Attributes {
				if strings.HasPrefix(k2, prefix) {
					ignoreAttrs[k2] = struct{}{}
				}
			}
		}

		for k, rd := range d.Attributes {
			if _, ok := ignoreAttrs[k]; ok {
				continue
			}

			// If the field is requires new and NOT computed, then what
			// we have is a diff mismatch for sure. We set that the old
			// diff does REQUIRE a ForceNew.
			if rd != nil && rd.RequiresNew && !rd.NewComputed {
				oldNew = true
				break
			}
		}
	}

	if oldNew != newNew {
		return false, fmt.Sprintf(
			"diff RequiresNew; old: %t, new: %t", oldNew, newNew)
	}

	// Verify that destroy matches. The second boolean here allows us to
	// have mismatching Destroy if we're moving from RequiresNew true
	// to false above. Therefore, the second boolean will only pass if
	// we're moving from Destroy: true to false as well.
	if d.Destroy != d2.GetDestroy() && d.requiresNew() == oldNew {
		return false, fmt.Sprintf(
			"diff: Destroy; old: %t, new: %t", d.Destroy, d2.GetDestroy())
	}

	// Go through the old diff and make sure the new diff has all the
	// same attributes. To start, build up the check map to be all the keys.
	checkOld := make(map[string]struct{})
	checkNew := make(map[string]struct{})
	for k, _ := range d.Attributes {
		checkOld[k] = struct{}{}
	}
	for k, _ := range d2.CopyAttributes() {
		checkNew[k] = struct{}{}
	}

	// Make an ordered list so we are sure the approximated hashes are left
	// to process at the end of the loop
	keys := make([]string, 0, len(d.Attributes))
	for k, _ := range d.Attributes {
		keys = append(keys, k)
	}
	sort.StringSlice(keys).Sort()

	for _, k := range keys {
		diffOld := d.Attributes[k]

		if _, ok := checkOld[k]; !ok {
			// We're not checking this key for whatever reason (see where
			// check is modified).
			continue
		}

		// Remove this key since we'll never hit it again
		delete(checkOld, k)
		delete(checkNew, k)

		_, ok := d2.GetAttribute(k)
		if !ok {
			// If there's no new attribute, and the old diff expected the attribute
			// to be removed, that's just fine.
			if diffOld.NewRemoved {
				continue
			}

			// If the last diff was a computed value then the absense of
			// that value is allowed since it may mean the value ended up
			// being the same.
			if diffOld.NewComputed {
				ok = true
			}

			// No exact match, but maybe this is a set containing computed
			// values. So check if there is an approximate hash in the key
			// and if so, try to match the key.
			if strings.Contains(k, "~") {
				parts := strings.Split(k, ".")
				parts2 := append([]string(nil), parts...)

				re := regexp.MustCompile(`^~\d+$`)
				for i, part := range parts {
					if re.MatchString(part) {
						// we're going to consider this the base of a
						// computed hash, and remove all longer matching fields
						ok = true

						parts2[i] = `\d+`
						parts2 = parts2[:i+1]
						break
					}
				}

				re, err := regexp.Compile("^" + strings.Join(parts2, `\.`))
				if err != nil {
					return false, fmt.Sprintf("regexp failed to compile; err: %#v", err)
				}

				for k2, _ := range checkNew {
					if re.MatchString(k2) {
						delete(checkNew, k2)
					}
				}
			}

			// This is a little tricky, but when a diff contains a computed
			// list, set, or map that can only be interpolated after the apply
			// command has created the dependent resources, it could turn out
			// that the result is actually the same as the existing state which
			// would remove the key from the diff.
			if diffOld.NewComputed && (strings.HasSuffix(k, ".#") || strings.HasSuffix(k, ".%")) {
				ok = true
			}

			// Similarly, in a RequiresNew scenario, a list that shows up in the plan
			// diff can disappear from the apply diff, which is calculated from an
			// empty state.
			if d.requiresNew() && (strings.HasSuffix(k, ".#") || strings.HasSuffix(k, ".%")) {
				ok = true
			}

			if !ok {
				return false, fmt.Sprintf("attribute mismatch: %s", k)
			}
		}

		// search for the suffix of the base of a [computed] map, list or set.
		match := multiVal.FindStringSubmatch(k)

		if diffOld.NewComputed && len(match) == 2 {
			matchLen := len(match[1])

			// This is a computed list, set, or map, so remove any keys with
			// this prefix from the check list.
			kprefix := k[:len(k)-matchLen]
			for k2, _ := range checkOld {
				if strings.HasPrefix(k2, kprefix) {
					delete(checkOld, k2)
				}
			}
			for k2, _ := range checkNew {
				if strings.HasPrefix(k2, kprefix) {
					delete(checkNew, k2)
				}
			}
		}

		// We don't compare the values because we can't currently actually
		// guarantee to generate the same value two two diffs created from
		// the same state+config: we have some pesky interpolation functions
		// that do not behave as pure functions (uuid, timestamp) and so they
		// can be different each time a diff is produced.
		// FIXME: Re-organize our config handling so that we don't re-evaluate
		// expressions when we produce a second comparison diff during
		// apply (for EvalCompareDiff).
	}

	// Check for leftover attributes
	if len(checkNew) > 0 {
		extras := make([]string, 0, len(checkNew))
		for attr, _ := range checkNew {
			extras = append(extras, attr)
		}
		return false,
			fmt.Sprintf("extra attributes: %s", strings.Join(extras, ", "))
	}

	return true, ""
}
489654
func (rs RuleSet) Diff(other RuleSet) RuleSet {
	result := NewRuleSet()
	for i := range rs {
		if !other.Contains(rs[i]) {
			result.Add(rs[i])
		}
	}
	return result
}
384163
func Intersect(s1 Set, s2 Set) Set {
	if s1 == nil {
		if s2 == nil {
			return nil
		}

		return s2.New()
	}
	s3 := s1.Copy()
	s3.Intersect(s2)
	return s3
}
634351
func Difference(wants []string, haves []string) (revoke []string, add []string) {
	for _, want := range wants {
		found := false
		for _, got := range haves {
			if want != got {
				continue
			}
			found = true
		}
		if !found {
			add = append(add, want)
		}
	}
	for _, got := range haves {
		found := false
		for _, want := range wants {
			if want != got {
				continue
			}
			found = true
			break
		}
		if !found {
			revoke = append(revoke, got)
		}
	}
	return
}
101497
func (set TargetIDSet) Difference(sset TargetIDSet) TargetIDSet {
	nset := NewTargetIDSet()
	for k := range set {
		if _, ok := sset[k]; !ok {
			nset.add(k)
		}
	}

	return nset
}