package intsets

import "golang.org/x/tools/container/intsets"

Package intsets provides Sparse, a compact and fast representation for sparse sets of int values.

The time complexity of the operations Len, Insert, Remove and Has is in O(n) but in practice those methods are faster and more space-efficient than equivalent operations on sets based on the Go map type. The IsEmpty, Min, Max, Clear and TakeMin operations require constant time.

Index ¶

Package Files ¶

popcnt_amd64.go sparse.go util.go

Constants ¶

const (
    MaxInt = int(^uint(0) >> 1)
    MinInt = -MaxInt - 1
)

Limit values of implementation-specific int type.

type Sparse ¶

type Sparse struct {
    // contains filtered or unexported fields
}

A Sparse is a set of int values. Sparse operations (even queries) are not concurrency-safe.

The zero value for Sparse is a valid empty set.

Sparse sets must be copied using the Copy method, not by assigning a Sparse value.

func (*Sparse) AppendTo ¶

func (s *Sparse) AppendTo(slice []int) []int

AppendTo returns the result of appending the elements of s to slice in order.

func (*Sparse) BitString ¶

func (s *Sparse) BitString() string

BitString returns the set as a string of 1s and 0s denoting the sum of the i'th powers of 2, for each i in s. A radix point, always preceded by a digit, appears if the sum is non-integral.

Examples:

        {}.BitString() =      "0"
     {4,5}.BitString() = "110000"
      {-3}.BitString() =      "0.001"
{-3,0,4,5}.BitString() = "110001.001"

func (*Sparse) Clear ¶

func (s *Sparse) Clear()

Clear removes all elements from the set s.

func (*Sparse) Copy ¶

func (s *Sparse) Copy(x *Sparse)

Copy sets s to the value of x.

func (*Sparse) Difference ¶

func (s *Sparse) Difference(x, y *Sparse)

Difference sets s to the difference x ∖ y.

func (*Sparse) DifferenceWith ¶

func (s *Sparse) DifferenceWith(x *Sparse)

DifferenceWith sets s to the difference s ∖ x.

func (*Sparse) Equals ¶

func (s *Sparse) Equals(t *Sparse) bool

Equals reports whether the sets s and t have the same elements.

func (*Sparse) GoString ¶

func (s *Sparse) GoString() string

GoString returns a string showing the internal representation of the set s.

func (*Sparse) Has ¶

func (s *Sparse) Has(x int) bool

Has reports whether x is an element of the set s.

func (*Sparse) Insert ¶

func (s *Sparse) Insert(x int) bool

Insert adds x to the set s, and reports whether the set grew.

func (*Sparse) Intersection ¶

func (s *Sparse) Intersection(x, y *Sparse)

Intersection sets s to the intersection x ∩ y.

func (*Sparse) IntersectionWith ¶

func (s *Sparse) IntersectionWith(x *Sparse)

IntersectionWith sets s to the intersection s ∩ x.

func (*Sparse) Intersects ¶

func (s *Sparse) Intersects(x *Sparse) bool

Intersects reports whether s ∩ x ≠ ∅.

func (*Sparse) IsEmpty ¶

func (s *Sparse) IsEmpty() bool

IsEmpty reports whether the set s is empty.

func (*Sparse) Len ¶

func (s *Sparse) Len() int

Len returns the number of elements in the set s.

func (*Sparse) Max ¶

func (s *Sparse) Max() int

Max returns the maximum element of the set s, or MinInt if s is empty.

func (*Sparse) Min ¶

func (s *Sparse) Min() int

Min returns the minimum element of the set s, or MaxInt if s is empty.

func (*Sparse) Remove ¶

func (s *Sparse) Remove(x int) bool

Remove removes x from the set s, and reports whether the set shrank.

func (*Sparse) String ¶

func (s *Sparse) String() string

String returns a human-readable description of the set s.

func (*Sparse) SubsetOf ¶

func (s *Sparse) SubsetOf(x *Sparse) bool

SubsetOf reports whether s ∖ x = ∅.

func (*Sparse) SymmetricDifference ¶

func (s *Sparse) SymmetricDifference(x, y *Sparse)

SymmetricDifference sets s to the symmetric difference x ∆ y.

func (*Sparse) SymmetricDifferenceWith ¶

func (s *Sparse) SymmetricDifferenceWith(x *Sparse)

SymmetricDifferenceWith sets s to the symmetric difference s ∆ x.

func (*Sparse) TakeMin ¶

func (s *Sparse) TakeMin(p *int) bool

If set s is non-empty, TakeMin sets *p to the minimum element of the set s, removes that element from the set and returns true. Otherwise, it returns false and *p is undefined.

This method may be used for iteration over a worklist like so:

var x int
for worklist.TakeMin(&x) { use(x) }

func (*Sparse) Union ¶

func (s *Sparse) Union(x, y *Sparse)

Union sets s to the union x ∪ y.

func (*Sparse) UnionWith ¶

func (s *Sparse) UnionWith(x *Sparse) bool

UnionWith sets s to the union s ∪ x, and reports whether s grew.