# intsets

package
v3.0.0+incompatible Latest Latest

Go to latest
Published: Jan 29, 2019 License: MIT, BSD-3-Clause

## Documentation ¶

### Overview ¶

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.

### Constants ¶

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

Limit values of implementation-specific int type.

### Variables ¶

This section is empty.

### Functions ¶

This section is empty.

### Types ¶

#### 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) LowerBound ¶

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

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

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