// SymmetricDifference returns a new set which s is the difference of items which are in
// one of either, but not in both.
347924
func SymmetricDifference(s Interface, t Interface) Interface {
	u := Difference(s, t)
	v := Difference(t, s)
	return Union(u, v)
}
901832
func (s Set) Difference(other Set) Set {
	ret := make(Set)
	for k := range s {
		if _, ok := other[k]; !ok {
			ret[k] = struct{}{}
		}
	}
	return ret
}
307760
func (s *Set) Difference(other *Set) *Set {
	result := &Set{F: s.F}
	result.once.Do(result.init)

	for k, v := range s.m {
		if _, ok := other.m[k]; !ok {
			result.m[k] = v
		}
	}

	return result
}
469225
func (d *Driver) DiffSize(id, parent string) (size int64, err error) {
	return directory.Size(path.Join(virtPath, id))
}
1209670
func DiffLocks(l1 Lock, l2 Lock) *LockDiff {
	// Default nil locks to empty locks, so that we can still generate a diff
	if l1 == nil {
		l1 = &SimpleLock{}
	}
	if l2 == nil {
		l2 = &SimpleLock{}
	}

	p1, p2 := l1.Projects(), l2.Projects()

	// Check if the slices are sorted already. If they are, we can compare
	// without copying. Otherwise, we have to copy to avoid altering the
	// original input.
	sp1, sp2 := lpsorter(p1), lpsorter(p2)
	if len(p1) > 1 && !sort.IsSorted(sp1) {
		p1 = make([]LockedProject, len(p1))
		copy(p1, l1.Projects())
		sort.Sort(lpsorter(p1))
	}
	if len(p2) > 1 && !sort.IsSorted(sp2) {
		p2 = make([]LockedProject, len(p2))
		copy(p2, l2.Projects())
		sort.Sort(lpsorter(p2))
	}

	diff := LockDiff{}

	h1 := hex.EncodeToString(l1.InputHash())
	h2 := hex.EncodeToString(l2.InputHash())
	if h1 != h2 {
		diff.HashDiff = &StringDiff{Previous: h1, Current: h2}
	}

	var i2next int
	for i1 := 0; i1 < len(p1); i1++ {
		lp1 := p1[i1]
		pr1 := lp1.pi.ProjectRoot

		var matched bool
		for i2 := i2next; i2 < len(p2); i2++ {
			lp2 := p2[i2]
			pr2 := lp2.pi.ProjectRoot

			switch strings.Compare(string(pr1), string(pr2)) {
			case 0: // Found a matching project
				matched = true
				pdiff := DiffProjects(lp1, lp2)
				if pdiff != nil {
					diff.Modify = append(diff.Modify, *pdiff)
				}
				i2next = i2 + 1 // Don't evaluate to this again
			case +1: // Found a new project
				add := buildLockedProjectDiff(lp2)
				diff.Add = append(diff.Add, add)
				i2next = i2 + 1 // Don't evaluate to this again
				continue        // Keep looking for a matching project
			case -1: // Project has been removed, handled below
				break
			}

			break // Done evaluating this project, move onto the next
		}

		if !matched {
			remove := buildLockedProjectDiff(lp1)
			diff.Remove = append(diff.Remove, remove)
		}
	}

	// Anything that still hasn't been evaluated are adds
	for i2 := i2next; i2 < len(p2); i2++ {
		lp2 := p2[i2]
		add := buildLockedProjectDiff(lp2)
		diff.Add = append(diff.Add, add)
	}

	if diff.HashDiff == nil && len(diff.Add) == 0 && len(diff.Remove) == 0 && len(diff.Modify) == 0 {
		return nil // The locks are the equivalent
	}
	return &diff
}
41675
func TwoWayDiff(config, live *unstructured.Unstructured) *DiffResult {
	var configObj, liveObj map[string]interface{}
	if config != nil {
		config = removeNamespaceAnnotation(config)
		configObj = config.Object
	}
	if live != nil {
		liveObj = jsonutil.RemoveMapFields(configObj, live.Object)
	}
	gjDiff := gojsondiff.New().CompareObjects(liveObj, configObj)
	dr := DiffResult{
		Diff:     gjDiff,
		Modified: gjDiff.Modified(),
	}
	return &dr
}
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
}
1267749
func diffAllocs(existing map[string]uint64, allocs *allocUpdates) *diffResult {
	// Scan the existing allocations
	result := &diffResult{}
	for existID, existIndex := range existing {
		// Check if the alloc was updated or filtered because an update wasn't
		// needed.
		alloc, pulled := allocs.pulled[existID]
		_, filtered := allocs.filtered[existID]

		// If not updated or filtered, removed
		if !pulled && !filtered {
			result.removed = append(result.removed, existID)
			continue
		}

		// Check for an update
		if pulled && alloc.AllocModifyIndex > existIndex {
			result.updated = append(result.updated, alloc)
			continue
		}

		// Ignore this
		result.ignore = append(result.ignore, existID)
	}

	// Scan the updated allocations for any that are new
	for id, pulled := range allocs.pulled {
		if _, ok := existing[id]; !ok {
			result.added = append(result.added, pulled)
		}
	}
	return result
}
979847
func (set LiteralFieldSet) SymmetricDifference(other LiteralFieldSet) LiteralFieldSet {
	aDiff := set.Difference(other)
	bDiff := other.Difference(set)
	return aDiff.Union(bDiff)
}
1046347
func DiffPartitions(a []int32, b []int32) []int32 {
	var diff []int32
Iter:
	for _, eA := range a {
		for _, eB := range b {
			if eA == eB {
				continue Iter
			}
		}
		diff = append(diff, eA)
	}
	return diff
}
638011
func HistogramDiff(a, b string) *DiffSolution {
	aw := strings.Split(a, "\n")
	bw := strings.Split(b, "\n")
	return NewHistogramDiffer(aw, bw).Solve()
}
175735
func (d *ADS1x15Driver) ReadDifference(diff int, gain int, dataRate int) (value float64, err error) {
	if err = d.checkChannel(diff); err != nil {
		return
	}

	return d.rawRead(diff, gain, dataRate)
}
1141259
func (d *ADS1x15Driver) ReadDifferenceWithDefaults(diff int) (value float64, err error) {
	return d.ReadDifference(diff, d.DefaultGain, d.DefaultDataRate)
}
1082510
func (d *SequenceDiffer) Solve() *DiffSolution {
	s := &DiffSolution{}
	m := modeBeginning

	// right only?
	if len(d.a) == 1 && d.a[0] == "" {
		for _, l := range d.b {
			s.addLineB(l)
		}
		return s
	}

	// left only?
	if len(d.b) == 1 && d.b[0] == "" {
		for _, l := range d.a {
			s.addLineA(l)
		}
		return s
	}

	// copy over shared prefix
	var i int
	for ; i < len(d.a) && i < len(d.b); i++ {
		if !d.isLineEqual(d.a[i], d.b[i]) {
			break
		}
		s.addLine(d.a[i], d.b[i], LineFromBoth)
	}
	if i > 0 {
		m = modeMatch
	}

	// compute optimal
	_ = d.computeOptimal(i, i, m)
	d.getSolution(s, i, i)
	return s
}
101497
func (set TargetIDSet) Difference(sset TargetIDSet) TargetIDSet {
	nset := NewTargetIDSet()
	for k := range set {
		if _, ok := sset[k]; !ok {
			nset.add(k)
		}
	}

	return nset
}
1152538
func (tg *TaskGroup) Diff(other *TaskGroup, contextual bool) (*TaskGroupDiff, error) {
	diff := &TaskGroupDiff{Type: DiffTypeNone}
	var oldPrimitiveFlat, newPrimitiveFlat map[string]string
	filter := []string{"Name"}

	if tg == nil && other == nil {
		return diff, nil
	} else if tg == nil {
		tg = &TaskGroup{}
		diff.Type = DiffTypeAdded
		diff.Name = other.Name
		newPrimitiveFlat = flatmap.Flatten(other, filter, true)
	} else if other == nil {
		other = &TaskGroup{}
		diff.Type = DiffTypeDeleted
		diff.Name = tg.Name
		oldPrimitiveFlat = flatmap.Flatten(tg, filter, true)
	} else {
		if !reflect.DeepEqual(tg, other) {
			diff.Type = DiffTypeEdited
		}
		if tg.Name != other.Name {
			return nil, fmt.Errorf("can not diff task groups with different names: %q and %q", tg.Name, other.Name)
		}
		diff.Name = other.Name
		oldPrimitiveFlat = flatmap.Flatten(tg, filter, true)
		newPrimitiveFlat = flatmap.Flatten(other, filter, true)
	}

	// Diff the primitive fields.
	diff.Fields = fieldDiffs(oldPrimitiveFlat, newPrimitiveFlat, false)

	// Constraints diff
	conDiff := primitiveObjectSetDiff(
		interfaceSlice(tg.Constraints),
		interfaceSlice(other.Constraints),
		[]string{"str"},
		"Constraint",
		contextual)
	if conDiff != nil {
		diff.Objects = append(diff.Objects, conDiff...)
	}

	// Affinities diff
	affinitiesDiff := primitiveObjectSetDiff(
		interfaceSlice(tg.Affinities),
		interfaceSlice(other.Affinities),
		[]string{"str"},
		"Affinity",
		contextual)
	if affinitiesDiff != nil {
		diff.Objects = append(diff.Objects, affinitiesDiff...)
	}

	// Restart policy diff
	rDiff := primitiveObjectDiff(tg.RestartPolicy, other.RestartPolicy, nil, "RestartPolicy", contextual)
	if rDiff != nil {
		diff.Objects = append(diff.Objects, rDiff)
	}

	// Reschedule policy diff
	reschedDiff := primitiveObjectDiff(tg.ReschedulePolicy, other.ReschedulePolicy, nil, "ReschedulePolicy", contextual)
	if reschedDiff != nil {
		diff.Objects = append(diff.Objects, reschedDiff)
	}

	// EphemeralDisk diff
	diskDiff := primitiveObjectDiff(tg.EphemeralDisk, other.EphemeralDisk, nil, "EphemeralDisk", contextual)
	if diskDiff != nil {
		diff.Objects = append(diff.Objects, diskDiff)
	}

	// Update diff
	// COMPAT: Remove "Stagger" in 0.7.0.
	if uDiff := primitiveObjectDiff(tg.Update, other.Update, []string{"Stagger"}, "Update", contextual); uDiff != nil {
		diff.Objects = append(diff.Objects, uDiff)
	}

	// Tasks diff
	tasks, err := taskDiffs(tg.Tasks, other.Tasks, contextual)
	if err != nil {
		return nil, err
	}
	diff.Tasks = tasks

	return diff, nil
}
1262040
func SymDiff(data sort.Interface, pivot int) (size int) {
	// BUG(extemporalgenome): SymDiff currently uses a multi-pass implementation

	i := Inter(data, pivot)
	l := data.Len()
	b := boundspan{data, span{i, l}}
	sort.Sort(b)
	size = Uniq(b)
	slide(data, 0, i, size)
	l = i + size
	sort.Sort(boundspan{data, span{size, l}})
	return Diff(data, size)
}