type Sparse … type word … const _m … const bitsPerWord … const bitsPerBlock … const wordsPerBlock … const MaxInt … const MinInt … // popcount returns the number of set bits in w. func popcount(x word) int { … } // nlz returns the number of leading zeros of x. func nlz(x word) int { … } // ntz returns the number of trailing zeros of x. func ntz(x word) int { … } type block … // wordMask returns the word index (in block.bits) // and single-bit mask for the block's ith bit. func wordMask(i uint) (w uint, mask word) { … } // insert sets the block b's ith bit and // returns true if it was not already set. func (b *block) insert(i uint) bool { … } // remove clears the block's ith bit and // returns true if the bit was previously set. // NB: may leave the block empty. func (b *block) remove(i uint) bool { … } // has reports whether the block's ith bit is set. func (b *block) has(i uint) bool { … } // empty reports whether b.len()==0, but more efficiently. func (b *block) empty() bool { … } // len returns the number of set bits in block b. func (b *block) len() int { … } // max returns the maximum element of the block. // The block must not be empty. func (b *block) max() int { … } // min returns the minimum element of the block, // and also removes it if take is set. // The block must not be initially empty. // NB: may leave the block empty. func (b *block) min(take bool) int { … } // lowerBound returns the smallest element of the block that is greater than or // equal to the element corresponding to the ith bit. If there is no such // element, the second return value is false. func (b *block) lowerBound(i uint) (int, bool) { … } // forEach calls f for each element of block b. // f must not mutate b's enclosing Sparse. func (b *block) forEach(f func(int)) { … } // offsetAndBitIndex returns the offset of the block that would // contain x and the bit index of x within that block. func offsetAndBitIndex(x int) (int, uint) { … } var none … type to_copy_a_sparse_you_must_call_its_Copy_method … // init ensures s is properly initialized. func (s *Sparse) init() { … } func (s *Sparse) first() *block { … } // next returns the next block in the list, or end if b is the last block. func (s *Sparse) next(b *block) *block { … } // prev returns the previous block in the list, or end if b is the first block. func (s *Sparse) prev(b *block) *block { … } // IsEmpty reports whether the set s is empty. func (s *Sparse) IsEmpty() bool { … } // Len returns the number of elements in the set s. func (s *Sparse) Len() int { … } // Max returns the maximum element of the set s, or MinInt if s is empty. func (s *Sparse) Max() int { … } // Min returns the minimum element of the set s, or MaxInt if s is empty. func (s *Sparse) Min() int { … } // LowerBound returns the smallest element >= x, or MaxInt if there is no such // element. func (s *Sparse) LowerBound(x int) int { … } // block returns the block that would contain offset, // or nil if s contains no such block. // Precondition: offset is a multiple of bitsPerBlock. func (s *Sparse) block(offset int) *block { … } // Insert adds x to the set s, and reports whether the set grew. func (s *Sparse) Insert(x int) bool { … } // removeBlock removes a block and returns the block that followed it (or end if // it was the last block). func (s *Sparse) removeBlock(b *block) *block { … } // Remove removes x from the set s, and reports whether the set shrank. func (s *Sparse) Remove(x int) bool { … } // Clear removes all elements from the set s. func (s *Sparse) Clear() { … } // 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 (s *Sparse) TakeMin(p *int) bool { … } // Has reports whether x is an element of the set s. func (s *Sparse) Has(x int) bool { … } // forEach applies function f to each element of the set s in order. // // f must not mutate s. Consequently, forEach is not safe to expose // to clients. In any case, using "range s.AppendTo()" allows more // natural control flow with continue/break/return. func (s *Sparse) forEach(f func(int)) { … } // Copy sets s to the value of x. func (s *Sparse) Copy(x *Sparse) { … } // insertBlockBefore returns a new block, inserting it before next. // If next is the root, the root is replaced. If next is end, the block is // inserted at the end. func (s *Sparse) insertBlockBefore(next *block) *block { … } // discardTail removes block b and all its successors from s. func (s *Sparse) discardTail(b *block) { … } // IntersectionWith sets s to the intersection s ∩ x. func (s *Sparse) IntersectionWith(x *Sparse) { … } // Intersection sets s to the intersection x ∩ y. func (s *Sparse) Intersection(x, y *Sparse) { … } // Intersects reports whether s ∩ x ≠ ∅. func (s *Sparse) Intersects(x *Sparse) bool { … } // UnionWith sets s to the union s ∪ x, and reports whether s grew. func (s *Sparse) UnionWith(x *Sparse) bool { … } // Union sets s to the union x ∪ y. func (s *Sparse) Union(x, y *Sparse) { … } // DifferenceWith sets s to the difference s ∖ x. func (s *Sparse) DifferenceWith(x *Sparse) { … } // Difference sets s to the difference x ∖ y. func (s *Sparse) Difference(x, y *Sparse) { … } // SymmetricDifferenceWith sets s to the symmetric difference s ∆ x. func (s *Sparse) SymmetricDifferenceWith(x *Sparse) { … } // SymmetricDifference sets s to the symmetric difference x ∆ y. func (s *Sparse) SymmetricDifference(x, y *Sparse) { … } // SubsetOf reports whether s ∖ x = ∅. func (s *Sparse) SubsetOf(x *Sparse) bool { … } // Equals reports whether the sets s and t have the same elements. func (s *Sparse) Equals(t *Sparse) bool { … } // String returns a human-readable description of the set s. func (s *Sparse) String() 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 (s *Sparse) BitString() string { … } // GoString returns a string showing the internal representation of // the set s. func (s *Sparse) GoString() string { … } // AppendTo returns the result of appending the elements of s to slice // in order. func (s *Sparse) AppendTo(slice []int) []int { … } // check returns an error if the representation invariants of s are violated. func (s *Sparse) check() error { … }
Codebase Browser
gotools