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) 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.
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