tools: Index | Files

package intsets

import ""

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.


Package Files

popcnt_amd64.go sparse.go util.go


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

Limit values of implementation-specific int type.

type Sparse Uses

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 Uses

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

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

func (*Sparse) BitString Uses

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.


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

func (*Sparse) Clear Uses

func (s *Sparse) Clear()

Clear removes all elements from the set s.

func (*Sparse) Copy Uses

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

Copy sets s to the value of x.

func (*Sparse) Difference Uses

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

Difference sets s to the difference x ∖ y.

func (*Sparse) DifferenceWith Uses

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

DifferenceWith sets s to the difference s ∖ x.

func (*Sparse) Equals Uses

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

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

func (*Sparse) GoString Uses

func (s *Sparse) GoString() string

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

func (*Sparse) Has Uses

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

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

func (*Sparse) Insert Uses

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

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

func (*Sparse) Intersection Uses

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

Intersection sets s to the intersection x ∩ y.

func (*Sparse) IntersectionWith Uses

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

IntersectionWith sets s to the intersection s ∩ x.

func (*Sparse) Intersects Uses

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

Intersects reports whether s ∩ x ≠ ∅.

func (*Sparse) IsEmpty Uses

func (s *Sparse) IsEmpty() bool

IsEmpty reports whether the set s is empty.

func (*Sparse) Len Uses

func (s *Sparse) Len() int

Len returns the number of elements in the set s.

func (*Sparse) LowerBound Uses

func (s *Sparse) LowerBound(x int) int

LowerBound returns the smallest element >= x, or MaxInt if there is no such element.

func (*Sparse) Max Uses

func (s *Sparse) Max() int

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

func (*Sparse) Min Uses

func (s *Sparse) Min() int

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

func (*Sparse) Remove Uses

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

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

func (*Sparse) String Uses

func (s *Sparse) String() string

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

func (*Sparse) SubsetOf Uses

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

SubsetOf reports whether s ∖ x = ∅.

func (*Sparse) SymmetricDifference Uses

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

SymmetricDifference sets s to the symmetric difference x ∆ y.

func (*Sparse) SymmetricDifferenceWith Uses

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

SymmetricDifferenceWith sets s to the symmetric difference s ∆ x.

func (*Sparse) TakeMin Uses

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 Uses

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

Union sets s to the union x ∪ y.

func (*Sparse) UnionWith Uses

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

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

Package intsets imports 2 packages (graph) and is imported by 94 packages. Updated 2021-01-23. Refresh now. Tools for package owners.