blob: 52cefe11942be0495dc549174fa28d6e7d2882c9 [file] [log] [blame]
 // Copyright 2015 Kevin Gillette. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. package set import "sort" // The Op type can be used to represent any of the mutating functions, such // as Inter. type Op func(data sort.Interface, pivot int) (size int) // Uniq swaps away duplicate elements in data, returning the size of the // unique set. data is expected to be pre-sorted, and the resulting set in // the range [0:size] will remain in sorted order. Uniq, following a // sort.Sort call, can be used to prepare arbitrary inputs for use as sets. func Uniq(data sort.Interface) (size int) { p, l := 0, data.Len() if l <= 1 { return l } for i := 1; i < l; i++ { if !data.Less(p, i) { continue } p++ if p < i { data.Swap(p, i) } } return p + 1 } // Inter performs an in-place intersection on the two sets [0:pivot] and // [pivot:Len]; the resulting set will occupy [0:size]. Inter is both // associative and commutative. func Inter(data sort.Interface, pivot int) (size int) { k, l := pivot, data.Len() p, i, j := 0, 0, k for i < k && j < l { switch { case data.Less(i, j): i++ case data.Less(j, i): j++ case p < i: data.Swap(p, i) fallthrough default: p, i, j = p+1, i+1, j+1 } } return p } // Union performs an in-place union on the two sets [0:pivot] and // [pivot:Len]; the resulting set will occupy [0:size]. Union is both // associative and commutative. func Union(data sort.Interface, pivot int) (size int) { // BUG(extemporalgenome): Union currently uses a multi-pass implementation sort.Sort(data) return Uniq(data) } // Diff performs an in-place difference on the two sets [0:pivot] and // [pivot:Len]; the resulting set will occupy [0:size]. Diff is neither // associative nor commutative. func Diff(data sort.Interface, pivot int) (size int) { k, l := pivot, data.Len() p, i, j := 0, 0, k for i < k && j < l { switch { case data.Less(i, j): if p < i { data.Swap(p, i) } p, i = p+1, i+1 case data.Less(j, i): j++ default: i, j = i+1, j+1 } } return xcopy(data, p, i, k, k) } // SymDiff performs an in-place symmetric difference on the two sets // [0:pivot] and [pivot:Len]; the resulting set will occupy [0:size]. // SymDiff is both associative and commutative. 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) }