Documentation
¶
Index ¶
- Constants
- type Fast
- func (s *Fast) Add(i int)
- func (s *Fast) AddRange(from, to int)
- func (s Fast) Contains(i int) bool
- func (s Fast) Copy() Fast
- func (s *Fast) CopyFrom(other Fast)
- func (s *Fast) Decode(br io.ByteReader) error
- func (s Fast) Difference(rhs Fast) Fast
- func (s *Fast) DifferenceWith(rhs Fast)
- func (s Fast) Empty() bool
- func (s *Fast) Encode(buf *bytes.Buffer) error
- func (s *Fast) EncodeBase64(enc *base64.Encoder, hash *util.FNV64) error
- func (s Fast) Equals(rhs Fast) bool
- func (s Fast) ForEach(f func(i int))
- func (s Fast) Intersection(rhs Fast) Fast
- func (s *Fast) IntersectionWith(rhs Fast)
- func (s Fast) Intersects(rhs Fast) bool
- func (s Fast) Len() int
- func (s Fast) Next(startVal int) (int, bool)
- func (s Fast) Ordered() []int
- func (s *Fast) Remove(i int)
- func (s Fast) String() string
- func (s Fast) SubsetOf(rhs Fast) bool
- func (s Fast) Union(rhs Fast) Fast
- func (s *Fast) UnionWith(rhs Fast)
- type Sparse
- func (s *Sparse) Add(i int)
- func (s *Sparse) Clear()
- func (s Sparse) Contains(i int) bool
- func (s *Sparse) Copy(rhs *Sparse)
- func (s *Sparse) DifferenceWith(rhs *Sparse)
- func (s Sparse) Empty() bool
- func (s *Sparse) Equals(rhs *Sparse) bool
- func (s *Sparse) IntersectionWith(rhs *Sparse)
- func (s *Sparse) Intersects(rhs *Sparse) bool
- func (s Sparse) Len() int
- func (s *Sparse) LowerBound(startVal int) int
- func (s *Sparse) Min() int
- func (s *Sparse) Remove(i int)
- func (s *Sparse) SubsetOf(rhs *Sparse) bool
- func (s *Sparse) UnionWith(rhs *Sparse)
Constants ¶
const ( // MaxInt is the maximum integer that can be stored in a set. MaxInt = int(^uint(0) >> 1) // MinInt is the minimum integer that can be stored in a set. MinInt = -MaxInt - 1 )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Fast ¶
type Fast struct {
// contains filtered or unexported fields
}
Fast keeps track of a set of integers. It does not perform any allocations when the values are in the range [0, smallCutoff). It is not thread-safe.
func (*Fast) Add ¶
Add adds a value to the set. No-op if the value is already in the set. If the large set is not nil and the value is within the range [0, 63], the value is added to both the large and small sets.
func (*Fast) AddRange ¶
AddRange adds values 'from' up to 'to' (inclusively) to the set. E.g. AddRange(1,5) adds the values 1, 2, 3, 4, 5 to the set. 'to' must be >= 'from'. AddRange is always more efficient than individual Adds.
func (*Fast) CopyFrom ¶
CopyFrom sets the receiver to a copy of other, which can then be modified independently.
func (*Fast) Decode ¶
func (s *Fast) Decode(br io.ByteReader) error
Decode does the opposite of Encode. The contents of the receiver are overwritten.
func (Fast) Difference ¶
Difference returns the elements of s that are not in rhs as a new set.
func (*Fast) DifferenceWith ¶
DifferenceWith removes any elements in rhs from this set.
func (*Fast) Encode ¶
Encode the set and write it to a bytes.Buffer using binary.varint byte encoding.
This method cannot be used if the set contains negative elements.
If the set has only elements in the range [0, 63], we encode a 0 followed by a 64-bit bitmap. Otherwise, we encode a length followed by each element.
func (*Fast) EncodeBase64 ¶ added in v0.25.2
EncodeBase64 is similar to Encode. It writes the encoded set to enc. It also adds each pre-base64-encoded byte to hash.
Closures or interfaces could be used to merge both methods into one, but they are intentionally avoided to prevent extra allocations of temporary buffers used during encoding.
WARNING: this is used by plan gists, so if this encoding changes, explain.gistVersion needs to be bumped.
func (Fast) Intersection ¶
Intersection returns the intersection of s and rhs as a new set.
func (*Fast) IntersectionWith ¶
IntersectionWith removes any elements not in rhs from this set.
func (Fast) Intersects ¶
Intersects returns true if s has any elements in common with rhs.
func (Fast) Next ¶
Next returns the first value in the set which is >= startVal. If there is no value, the second return value is false.
func (Fast) Ordered ¶
Ordered returns a slice with all the integers in the set, in increasing order.
func (Fast) String ¶
String returns a list representation of elements. Sequential runs of positive numbers are shown as ranges. For example, for the set {0, 1, 2, 5, 6, 10}, the output is "(0-2,5,6,10)".
type Sparse ¶
type Sparse struct {
// contains filtered or unexported fields
}
Sparse is a set of integers. It is not thread-safe. It must be copied with the Copy method.
Sparse is implemented as a linked list of blocks, each containing an offset and a bitmap. A block with offset=o contains an integer o+b if the b-th bit of the bitmap is set. Block offsets are always divisible by smallCutoff.
For example, here is a diagram of the set {0, 1, 128, 129, 512}, where each block is denoted by {offset, bitmap}:
{0, ..011} ---> {128, ..011} ---> {512, ..001}
Sparse is inspired by golang.org/x/tools/container/intsets. Sparse implements a smaller API, providing only the methods required by Fast. The omission of a Max method allows us to use a singly-linked list here instead of a circular, doubly-linked list.
func (*Sparse) Copy ¶
Copy sets the receiver to a copy of rhs, which can then be modified independently.
func (*Sparse) DifferenceWith ¶
DifferenceWith removes any elements in rhs from this set.
func (*Sparse) IntersectionWith ¶
IntersectionWith removes any elements not in rhs from this set.
func (*Sparse) Intersects ¶
Intersects returns true if s has any elements in common with rhs.
func (*Sparse) LowerBound ¶
LowerBound returns the smallest element >= startVal, or MaxInt if there is no such element.
func (*Sparse) Min ¶
Min returns the minimum value in the set. If the set is empty, MaxInt is returned.
Source Files