summaryrefslogtreecommitdiff
path: root/vendor/github.com/willf/bitset/bitset.go
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/willf/bitset/bitset.go')
-rw-r--r--vendor/github.com/willf/bitset/bitset.go72
1 files changed, 62 insertions, 10 deletions
diff --git a/vendor/github.com/willf/bitset/bitset.go b/vendor/github.com/willf/bitset/bitset.go
index 22e5d42e5..21e889da2 100644
--- a/vendor/github.com/willf/bitset/bitset.go
+++ b/vendor/github.com/willf/bitset/bitset.go
@@ -138,6 +138,9 @@ func (b *BitSet) Len() uint {
// extendSetMaybe adds additional words to incorporate new bits if needed
func (b *BitSet) extendSetMaybe(i uint) {
if i >= b.length { // if we need more bits, make 'em
+ if i >= Cap() {
+ panic("You are exceeding the capacity")
+ }
nsize := wordsNeeded(i + 1)
if b.set == nil {
b.set = make([]uint64, nsize)
@@ -160,7 +163,12 @@ func (b *BitSet) Test(i uint) bool {
return b.set[i>>log2WordSize]&(1<<(i&(wordSize-1))) != 0
}
-// Set bit i to 1
+// Set bit i to 1, the capacity of the bitset is automatically
+// increased accordingly.
+// If i>= Cap(), this function will panic.
+// Warning: using a very large value for 'i'
+// may lead to a memory shortage and a panic: the caller is responsible
+// for providing sensible parameters in line with their memory capacity.
func (b *BitSet) Set(i uint) *BitSet {
b.extendSetMaybe(i)
b.set[i>>log2WordSize] |= 1 << (i & (wordSize - 1))
@@ -176,7 +184,11 @@ func (b *BitSet) Clear(i uint) *BitSet {
return b
}
-// SetTo sets bit i to value
+// SetTo sets bit i to value.
+// If i>= Cap(), this function will panic.
+// Warning: using a very large value for 'i'
+// may lead to a memory shortage and a panic: the caller is responsible
+// for providing sensible parameters in line with their memory capacity.
func (b *BitSet) SetTo(i uint, value bool) *BitSet {
if value {
return b.Set(i)
@@ -184,7 +196,11 @@ func (b *BitSet) SetTo(i uint, value bool) *BitSet {
return b.Clear(i)
}
-// Flip bit at i
+// Flip bit at i.
+// If i>= Cap(), this function will panic.
+// Warning: using a very large value for 'i'
+// may lead to a memory shortage and a panic: the caller is responsible
+// for providing sensible parameters in line with their memory capacity.
func (b *BitSet) Flip(i uint) *BitSet {
if i >= b.length {
return b.Set(i)
@@ -193,26 +209,51 @@ func (b *BitSet) Flip(i uint) *BitSet {
return b
}
-// Shrink shrinks BitSet to desired length in bits. It clears all bits > length
-// and reduces the size and length of the set.
+// Shrink shrinks BitSet so that the provided value is the last possible
+// set value. It clears all bits > the provided index and reduces the size
+// and length of the set.
+//
+// Note that the parameter value is not the new length in bits: it is the
+// maximal value that can be stored in the bitset after the function call.
+// The new length in bits is the parameter value + 1. Thus it is not possible
+// to use this function to set the length to 0, the minimal value of the length
+// after this function call is 1.
//
// A new slice is allocated to store the new bits, so you may see an increase in
// memory usage until the GC runs. Normally this should not be a problem, but if you
// have an extremely large BitSet its important to understand that the old BitSet will
// remain in memory until the GC frees it.
-func (b *BitSet) Shrink(length uint) *BitSet {
- idx := wordsNeeded(length + 1)
+func (b *BitSet) Shrink(lastbitindex uint) *BitSet {
+ length := lastbitindex + 1
+ idx := wordsNeeded(length)
if idx > len(b.set) {
return b
}
shrunk := make([]uint64, idx)
copy(shrunk, b.set[:idx])
b.set = shrunk
- b.length = length + 1
- b.set[idx-1] &= (allBits >> (uint64(64) - uint64(length&(wordSize-1)) - 1))
+ b.length = length
+ b.set[idx-1] &= (allBits >> (uint64(64) - uint64(length&(wordSize-1))))
return b
}
+// Compact shrinks BitSet to so that we preserve all set bits, while minimizing
+// memory usage. Compact calls Shrink.
+func (b *BitSet) Compact() *BitSet {
+ idx := len(b.set) - 1
+ for ; idx >= 0 && b.set[idx] == 0; idx-- {
+ }
+ newlength := uint((idx + 1) << log2WordSize)
+ if newlength >= b.length {
+ return b // nothing to do
+ }
+ if newlength > 0 {
+ return b.Shrink(newlength - 1)
+ }
+ // We preserve one word
+ return b.Shrink(63)
+}
+
// InsertAt takes an index which indicates where a bit should be
// inserted. Then it shifts all the bits in the set to the left by 1, starting
// from the given index position, and sets the index position to 0.
@@ -323,6 +364,9 @@ func (b *BitSet) DeleteAt(i uint) *BitSet {
// including possibly the current index
// along with an error code (true = valid, false = no set bit found)
// for i,e := v.NextSet(0); e; i,e = v.NextSet(i + 1) {...}
+//
+// Users concerned with performance may want to use NextSetMany to
+// retrieve several values at once.
func (b *BitSet) NextSet(i uint) (uint, bool) {
x := int(i >> log2WordSize)
if x >= len(b.set) {
@@ -358,6 +402,14 @@ func (b *BitSet) NextSet(i uint) (uint, bool) {
// j += 1
// }
//
+//
+// It is possible to retrieve all set bits as follow:
+//
+// indices := make([]uint, bitmap.Count())
+// bitmap.NextSetMany(0, indices)
+//
+// However if bitmap.Count() is large, it might be preferable to
+// use several calls to NextSetMany, for performance reasons.
func (b *BitSet) NextSetMany(i uint, buffer []uint) (uint, []uint) {
myanswer := buffer
capacity := cap(buffer)
@@ -809,7 +861,7 @@ func (b *BitSet) ReadFrom(stream io.Reader) (int64, error) {
newset := New(uint(length))
if uint64(newset.length) != length {
- return 0, errors.New("Unmarshalling error: type mismatch")
+ return 0, errors.New("unmarshalling error: type mismatch")
}
// Read remaining bytes as set